
/*
**  This file forms part of the GOBLIN C++ Class Library.
**
**  Written by Christian Fremuth-Paeger, February 2000.
**  
**  Copying, compiling, distribution and modification
**  of this source code is permitted only in accordance
**  with the GOBLIN general licence information.
*/             


#if !defined(_SURGRA_H_)

#define _SURGRA_H_

#include <absbal.h>
#include <shrfam.h>
#include <dynstaq.h>


class surfaceGraph : public abstractBalancedFNW
{                                        
friend class iSurfaceGraph;
protected:

    abstractBalancedFNW &   G;  // The original network
    shrinkingFamily<TNode>  S;  // The blossoms
    
    TNode       n0; // Number of nodes in the original network (real nodes)
    TNode       nr; // Number of real node pairs
    TNode       nv; // Number of virtual node pairs (blossoms)
        // n0==nr*2, n1==nr+nv
    
    TFloat*     modlength;  // Explicit modified length labels
    TArc*       bprop;      // Current blossom props
    bool        real;
        // Switches arc incidences between surface graph and original network

public:             

    surfaceGraph(abstractBalancedFNW &GC) throw();
    ~surfaceGraph() throw();

    void            Init() throw();
    unsigned long   Size() throw();     
    unsigned long   Allocated() throw();     
    goblinIterator* NewIterator() throw();

    TNode           StartNode(TArc a) throw(ERRange);
    TNode           EndNode(TArc a) throw(ERRange);
   
    TArc            First(TNode v) throw(ERRange,ERRejected);
    TArc            Right(TArc a,TNode u) throw(ERRange,ERRejected);

    TCap            LCap(TArc a) throw(ERRange);
    bool            CLCap() throw() {return G.CLCap();};
    TCap            UCap(TArc a) throw(ERRange);
    bool            CUCap() throw() {return G.CUCap();};
    TFloat          Length(TArc a) throw(ERRange);
    bool            CLength() throw() {return G.CLength();};
    bool            Blocking(TArc a) throw() {return a&1;};

    TFloat          C(TNode v,char i) throw(ERRange);
    TFloat          CMax(char i) throw(ERRange) {return G.CMax(i);};
    char            Dim() throw() {return G.Dim();};
    bool            HiddenNode(TNode v) throw(ERRange);
    bool            HiddenArc(TArc a) throw(ERRange);
    void            ConfigDisplay(goblinController &CFG) throw();

    TFloat          Flow(TArc a) throw(ERRange);
    TFloat          BalFlow(TArc a) throw(ERRange);
    void            Push(TArc a,TFloat Lambda) throw(ERRange,ERRejected);
    void            BalPush(TArc a,TFloat Lambda) throw(ERRange,ERRejected);
    
    TFloat          Sub(TArc a) throw(ERRange) {return BalFlow(a);};
    void            AddArc(TArc a,TFloat Lambda) throw() {};
    void            OmitArc(TArc a,TFloat Lambda) throw() {};

    void            Symmetrize() throw() {G.Symmetrize();};
    void            Relax() throw() {G.Relax();};

    void            Write(char* fileName) throw(ERFile)
                        {WriteBalancedFNW(fileName,WRITE_INCIDENCES);};

    // --------------------------------------------------------------
    //            Handling of Blossoms and Fragments
    // --------------------------------------------------------------
    
	TNode			MakeBlossom(TNode b,TArc a) throw(ERRange);
        // Initializes a new blossom and returns the corresponding node index
	bool			Top(TNode v) throw(ERRange);
        // Decides wether v is in the surface graph or shrunk into a blossom
    
    // --------------------------------------------------------------
    //            Handling of Modified length labels
    // --------------------------------------------------------------
    
	TFloat			ModLength(TArc a) throw(ERRange);
        // Returns the label encoded into modlength
	TFloat			RModLength(TArc a) throw(ERRange);
        // Computes the modified length label recursively
	TFloat			RedLength(TArc a) throw(ERRange) {return ModLength(a);};
	void			ShiftPotential(TNode v,TFloat epsilon) throw(ERRange);
        // Increases pi[v] and decreases pi[v^1] by an amount epsilon
	void			ShiftModLength(TArc a,TFloat epsilon) throw(ERRange);
        // Increases ModLength(a) and ModLength(a^2), and decreases
        // ModLength(a^1) and ModLength(a^3) by an amount epsilon
    
    bool            Compatible() throw();
        // Verifies the complementary slackness conditions
    void            CheckDual() throw();
        // Checks if the explicit modified length labels coincide
        // with the labels returned by RModLength(..)
    
    // --------------------------------------------------------------
    //         Generic Shrinking and Expansion Operations
    // --------------------------------------------------------------
    
    TArc FindSupport(TNode s,TArc a,dynamicStack<TNode,TFloat> &Support) throw();
        // Tracks back on the prop-labels from the start nodes of
        // the petals a and a^2. Determines the blossom base b and a path
        // from b to b^1 which is returned by the Q-labels. The return value
        // is the first arc on this path.
        // The nodes forming the blossom are pushed onto the stack Support.
    void Traverse(TArc aIn,TArc aOut) throw();
        // If the end node v of aIn is real, P[v] = aIn is set.
        // Otherwise, if v is a blossom, it is expanded.
        // The end nodes of aIn and aOut must be the same!
    void Expand(TArc aIn,TArc aOut) throw();
        // Tries to find a path through a blossom, starting at the
        // end node of aIn, and ending at the start node of aOut.
        // Uses the Q-labels, returns the path by the P-labels.
    void ExpandAndAugment(TArc aIn,TArc aOut) throw();
        // Calls Expand(aIn,aOut), determines the path capacity,
        // and finally augments on aIn, aOut, and the intermediate path.
    
    // --------------------------------------------------------------
    //           Primal-Dual Algorithms and Subroutines
    // --------------------------------------------------------------
    
    TFloat          ComputeEpsilon() throw();
        // Determines the multiplier for the restricted primal by which
        // the node potentials are iterated in the main procedure
    void PrimalDual0(TNode s) throw(ERRange);
        // Node oriented version with O(nm) operations per augmentation
    void Explore(goblinQueue<TArc,TFloat> &Q,goblinIterator &I,TNode v) throw();
        // Puts all incidences of node v onto the queue Q
    TFloat ComputeEpsilon1() throw();
        // Determines the multiplier for the restricted primal by which
        // the node potentials are iterated in the main procedure
    void PrimalDual1(TNode s) throw(ERRange);
        // Arc oriented version with O(nm) operations per augmentation

};                             



class iSurfaceGraph : public virtual goblinIterator
{                                        
private:

    abstractBalancedFNW &   G;  // The original network
    surfaceGraph &          N;  // The surface graph
    shrinkingFamily<TNode> &S;  // The blossoms
    
    TNode       n;  // Number of nodes in the surface graph
    TNode       n0; // Number of nodes in the original network (real nodes)
    TNode       nr; // Number of real node pairs (n0==2*nr)
    TNode       nv; // Number of virtual node pairs (blossoms)
    TNode       n1; // Number of node pairs (n1==nr+nv)
    TArc        m;  // Number of arcs (which coincides in G and N)

    THandle     Handle;     // Iterator handle in the original network
    TNode *     current;    // Currently investigated element of a blossom

public:

    iSurfaceGraph(surfaceGraph &GC) throw();
    ~iSurfaceGraph() throw();

    unsigned long   Size() throw();     
    unsigned long   Allocated() throw();

    void            Reset() throw();
    void            Reset(TNode v) throw(ERRange);
    TArc            Read(TNode v) throw(ERRange,ERRejected);
    TArc            ReadBlossom(TNode v,TArc thisProp) throw(ERRange);
    TArc            Peek(TNode v) throw(ERRange,ERRejected);
    bool            Active(TNode v) throw(ERRange);
    bool            ActiveBlossom(TNode v) throw(ERRange);

};                             


#endif
