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


#if !defined(_ABSMIX_H_)

#define _ABSMIX_H_

#include <absobj.h>
#include <iterator.h>
#include <import.h>
#include <export.h>
#include <queue.h>
#include <absfam.h>
#include <hashtbl.h>


class abstractMixedGraph : public virtual goblinDataObject
{
friend class bal2bal;
friend class surfaceGraph;
private:

    THandle                             itCounter;
    goblinIterator **                   pIterator;
    THandle                             LH,RH;
        // Data structures for iterator access
    
    goblinHashTable<TArc,TArc> *        adj;
        // Node adjacencies
    
protected:

    goblinDisjointSetSystem<TNode> *    partition;
         // Partition of the node set (connected components, colourings)

    goblinQueue<TNode,TFloat> *         nHeap;
        // Cached priority queue, used in Dijkstra algorithm

    goblinQueue<TNode,TFloat> * NewNodeHeap() throw(ERRejected);
    goblinQueue<TArc,TFloat> * NewArcHeap() throw(ERRejected);

    TFloat *    sDeg;
    TFloat *    sDegIn;
    TFloat *    sDegOut;
         // Explicit degree labels

    TNode           n;
        // Number of nodes
    TNode           ni;
        // Number of Interpolation Points
    TArc            m;
        // Number of arcs
    TArc *          P;
        // Array for path encoding
    TFloat *        d;
        // Array of distance labels
    TFloat *        pi;
        // Array of node potentials
    TNode *         colour;
        // Array of node colours

    TCap            mu;
        // Threshold for Cost Scaling Alg.

    TNode           sourceNode;
    TNode           targetNode;
    TNode           rootNode;
        // Special nodes for graph algorithms

public:

    abstractMixedGraph(TNode = 0,TArc = 0) throw();
    virtual ~abstractMixedGraph() throw();
    
    void            CheckLimits() throw(ERRejected);
    unsigned long   Allocated() throw();
    
    virtual bool IsGraphObject() throw() {return true;};
    virtual bool IsBipartite()   throw() {return false;};
    virtual bool IsDirected()    throw() {return false;};
    virtual bool IsUndirected()  throw() {return false;};
    virtual bool IsSparse()      throw() {return false;};
    virtual bool IsDense()       throw() {return false;};
    virtual bool IsBalanced()    throw() {return false;};
    bool IsPhysical() throw() {return IsSparse() || IsDense();};
    bool IsLogical()  throw() {return !IsPhysical();};

    
    // *************************************************************** //
    //           Graph Manipulation Methods                            //
    // *************************************************************** //
    
    virtual TArc    InsertArc(TNode u,TNode v) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual TArc    InsertArc(TNode u,TNode v,TCap cc,TFloat ll)
                        throw(ERRange,ERRejected) {throw ERRejected();};
    virtual TArc    InsertArc(TNode u,TNode v,TCap cc,TCap bb,TFloat ll)
                        throw(ERRange,ERRejected) {throw ERRejected();};

    virtual TNode   InsertNode() throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual TNode   InsertAlignmentPoint(TArc a) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual TNode   InsertBendNode(TNode v) throw(ERRange,ERRejected)
                        {throw ERRejected();};
     
    virtual void    FlipArc(TArc a) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual void    ReleaseBendNodes(TArc a) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual void    DeleteArc(TArc a) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual void    DeleteNode(TNode v) throw(ERRange,ERRejected)
                        {throw ERRejected();};

    virtual void    RandomArcs(TArc) throw(ERRejected);
    void            RandEulerian(TArc) throw(ERRejected);
    virtual void    RandRegular(TNode) throw(ERRejected);
    
    void            Merge(abstractMixedGraph&) throw(ERRejected);


    // *************************************************************** //
    //           Graph Access Methods                                  //
    // *************************************************************** //
    
    TNode           N() throw()                     {return n;};
    TNode           NI() throw()                    {return ni;};
    TArc            M() throw()                     {return m;};

    virtual TNode   Source() {return sourceNode;};
    virtual TNode   Target() {return targetNode;};
    TNode           Root()   {return rootNode;};

    void            SetSourceNode(TNode) throw(ERRange);
    void            SetTargetNode(TNode) throw(ERRange);
    void            SetRootNode(TNode) throw(ERRange);

    virtual TNode   StartNode(TArc) throw(ERRange) = 0;
    virtual TNode   EndNode(TArc) throw(ERRange);

    TArc            Reverse(TArc) throw(ERRange);
    virtual bool    Blocking(TArc) throw(ERRange) = 0;

    virtual TArc    First(TNode) throw(ERRange,ERRejected) = 0;
    virtual TArc    Right(TArc,TNode) throw(ERRange,ERRejected) = 0;
     
    virtual bool    Outer(TNode) throw(ERRange,ERRejected);
    virtual bool    Inner(TNode) throw(ERRange,ERRejected);

    virtual TCap    Demand(TNode v) throw(ERRange)  {return 1;};
    virtual void    SetDemand(TNode v,TCap bb) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual void    SetCDemand(TCap bb) throw(ERRejected)
                        {throw ERRejected();};
    virtual TCap    MaxDemand() throw()             {return 1;};
    virtual bool    CDemand() throw()               {return true;};
    
    virtual TCap    UCap(TArc) throw(ERRange) = 0;     
    virtual void    SetUCap(TArc a,TCap uu) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual void    SetCUCap(TCap uu) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual TCap    MaxUCap() throw();     
    virtual bool    CUCap() throw() = 0;
    virtual TCap    LCap(TArc a) throw(ERRange)     {return 0;};
    virtual void    SetLCap(TArc a,TCap ll) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual void    SetCLCap(TCap ll) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual TCap    MaxLCap() throw();
    virtual bool    CLCap() throw()                 {return true;};

    virtual TFloat  Length(TArc) throw(ERRange) = 0;     
    virtual void    SetLength(TArc a,TFloat ll) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual void    SetCLength(TFloat ll) throw(ERRejected)
                        {throw ERRejected();};
    virtual TFloat  MaxLength() throw();
    virtual bool    CLength() throw() = 0;
    virtual TFloat  RedLength(TArc) throw(ERRange);     
    
    virtual TFloat  C(TNode v,char i) throw(ERRange) {return 0;};
    virtual void    SetC(TNode v,char i,TFloat xx) throw(ERRange,ERRejected)
                        {throw ERRejected();};
    virtual TFloat  CMax(char i) throw(ERRange)     {return 0;};
    virtual char    Dim() throw()                   {return 0;};

    virtual char    Orientation(TArc a) throw(ERRange) {return 1;};
    virtual void    SetOrientation(TArc a,char oo) throw(ERRejected,ERRange)
                        {throw ERRejected();};     
    virtual char    Orientation() throw()           {return 1;};     
    virtual bool    COrientation() throw()          {return true;};
    
    virtual TNode   Align(TArc a) throw(ERRange)    {return NoNode;};
    virtual bool    CAlign() throw()                {return true;};
    virtual TNode   Interpolate(TNode v) throw(ERRange) {return NoNode;};
    virtual bool    CInterpolate() throw()          {return true;};
    virtual bool    HiddenNode(TNode v) throw(ERRange)
                        {return C(v,0)==-InfFloat;};
    virtual bool    HiddenArc(TArc a) throw(ERRange);

    virtual TArc    Adjacency(TNode,TNode) throw(ERRange);
    void            ReleaseAdjacencies() throw();
    
    
    // *************************************************************** //
    //           Layout Manipulation Methods                            //
    // *************************************************************** //
    
    void    StripEmbedding() throw(ERRejected);
    void    ScaleEmbedding(TFloat,TFloat) throw(ERRejected);
    void    AutoArcAlignment(TFloat = 0,TOption = 0) throw(ERRejected);
    void    TreeLayout(TFloat = 0,TFloat = 0) throw(ERRejected);
    void    ColourLayout(TFloat = 0,TFloat = 0) throw(ERRejected);
    void    CircleLayout(TFloat = 0) throw(ERRejected);
    void    GridLayout(TFloat = 0) throw(ERRejected);
    void    SpringEmbedding(TFloat = 0,TFloat = 0) throw(ERRejected);


    // *************************************************************** //
    //           Graph Search Methods (Implicit Iterator Access)       //
    // *************************************************************** //
    
    virtual goblinIterator *  NewIterator() throw();
    
    THandle         Investigate() throw(ERRejected);
    goblinIterator &Iterator(THandle) throw(ERRejected);
    void            Reset(THandle) throw(ERRejected);
    void            Reset(THandle, TNode) throw(ERRange,ERRejected);
        // Initialize a graph search
    TArc            Read(THandle, TNode) throw(ERRange,ERRejected);
        // Read an arc from the incidence list of v
    TArc            Peek(THandle, TNode) throw(ERRange,ERRejected);
        // Like Read, but arc can be read again
    bool            Active(THandle, TNode) throw(ERRange,ERRejected);
        // Is there another arc incident with v? 
    void            Close(THandle) throw(ERRejected);
        // Conclude a graph search
    void            ReleaseIterators() throw();
        // Disallocate cached iterator objects
    void            StripIterators() throw();
        // Strip iterator array
    
    
    // *************************************************************** //
    //           Subgraph Management                                   //
    // *************************************************************** //

    void            InitSubgraph() throw();
    
    virtual void    AddArc(TArc,TFloat Lambda) throw(ERRange,ERRejected) = 0;
    void            AddArc(TArc a) throw(ERRange,ERRejected) {AddArc(a,1);};
    virtual void    OmitArc(TArc,TFloat) throw(ERRange,ERRejected) = 0;
    void            OmitArc(TArc a) throw(ERRange,ERRejected) {OmitArc(a,1);};
    virtual void    SetSub(TArc,TFloat) throw(ERRange,ERRejected);
    virtual TFloat  Sub(TArc) throw(ERRange) = 0;
    
    TCap            Cardinality() throw();
    TFloat          Length() throw();
    TFloat          Weight() throw();
    
    void            AddToSubgraph(TNode = NoNode) throw(ERRange,ERRejected);


    // *************************************************************** //
    //           Partitions (Access to Disjoint Set Union Structure)   //
    // *************************************************************** //
    
    virtual void    InitPartition() throw();
    virtual void    Bud(TNode) throw(ERRange);
    virtual void    Merge(TNode,TNode) throw(ERRange);
    virtual TNode   Find(TNode) throw(ERRange);
    virtual void    ReleasePartition() throw();
    

    // *************************************************************** //
    //           Distance labels                                       //
    // *************************************************************** //
    
    void            InitLabels(TFloat = InfFloat) throw();
    virtual TFloat  Dist(TNode) throw(ERRange);
    void            SetDist(TNode,TFloat) throw(ERRange);
    void            ReleaseLabels() throw();


    // *************************************************************** //
    //           Node Potentials                                       //
    // *************************************************************** //
    
    void            InitPotentials(TFloat = 0) throw();
    TFloat          Pi(TNode) throw(ERRange);
    void            SetPotential(TNode,TFloat) throw(ERRange);
    void            PushPotential(TNode,TFloat) throw(ERRange);
    void            UpdatePotentials(TFloat) throw(ERRejected);
    void            ReleasePotentials() throw();
    

    // *************************************************************** //
    //           Node Colours                                          //
    // *************************************************************** //
    
    void            InitColours(TNode = NoNode) throw();
    virtual TNode   Colour(TNode) throw(ERRange);
    void            SetColour(TNode,TNode) throw(ERRange);
    void            ReleaseColours() throw();

    void            ExtractCut() throw(ERRejected);
    void            ExtractBipartition() throw(ERRejected);
    void            ExtractColours() throw(ERRejected);
    

    // *************************************************************** //
    //           Edge Colours                                          //
    // *************************************************************** //
    
    void            InitEdgeColours(TArc = NoNode) throw();
    TArc            EdgeColour(TArc) throw(ERRange);
    void            SetEdgeColour(TArc,TArc) throw(ERRange);
    void            ReleaseEdgeColours() throw();


    // *************************************************************** //
    //           Predecessor labels                                    //
    // *************************************************************** //
    
    void            InitPredecessors() throw();
    TArc            Pred(TNode) throw(ERRange);
    void            SetPred(TNode,TArc) throw(ERRange,ERRejected);
    void            ReleasePredecessors() throw();

    void            ExtractTrees() throw(ERCheck);
    void            ExtractTree(TNode) throw(ERCheck);
    TNode           ExtractPath(TNode,TNode) throw(ERCheck);
    TNode           ExtractCycles() throw(ERCheck);
    void            Extract1Matching() throw(ERCheck);


    // *************************************************************** //
    //           Degree labels                                         //
    // *************************************************************** //
    
    void            InitDegrees() throw();
    void            InitDegIO() throw();
    TFloat          Deg(TNode) throw(ERRange);
    TFloat          DegIn(TNode) throw(ERRange);
    TFloat          DegOut(TNode) throw(ERRange);
    TFloat          Divergence(TNode v) throw(ERRange) {return DegIn(v)-DegOut(v);};
    void            AdjustDegrees(TArc,TFloat) throw(ERRange);
    void            ReleaseDegrees() throw();

    void            ReleaseSolutions() throw();
    

    // *************************************************************** //
    //           Graph Export and Import Methods                                  //
    // *************************************************************** //
    
    void            WriteMixedGraph(char*) throw(ERFile);
    virtual void    Write(char* fileName) throw(ERFile)
                        {WriteMixedGraph(fileName);};

    virtual void    WriteIncidences(goblinExport*) throw();
    void            WriteUCap(goblinExport*) throw();
    void            WriteLCap(goblinExport*) throw();
    void            WriteDemand(goblinExport*) throw();
    void            WriteOrientation(goblinExport*) throw();

    void            WriteObjectives(goblinExport*) throw();
    void            WriteGeometry(goblinExport*) throw();
    void            WriteLayout(goblinExport*) throw();

    void            WriteSolutions(goblinExport*) throw();
    void            WriteLabels(goblinExport*) throw();
    void            WritePredecessors(goblinExport*) throw();
    void            WriteSubgraph(goblinExport*) throw();
    void            WritePotentials(goblinExport*) throw();
    void            WriteColours(goblinExport*) throw();
    
    void            ReadSolutions(goblinImport&) throw();
    void            ReadLabels(goblinImport*) throw();
    void            ReadPredecessors(goblinImport*) throw();
    void            ReadSubgraph(goblinImport*) throw(ERRange);
    void            ReadPotentials(goblinImport*) throw();
    void            ReadColours(goblinImport*) throw();
    
        
    // *************************************************************** //
    //           Mathematical Algorithms                               //
    // *************************************************************** //
    
        // Shortest path algorithms. Return 1, if v can be reached from u,
        // a shortest path tree by the predecessor labels, and the minimum
        // distance labels

    bool            BFS(TNode,TNode = NoNode) throw(ERRange);
    virtual bool    Eligible(TArc) throw(ERRange);
        // Arc selector for graph search algorithms
         
    bool            ShortestPath(TNode,TNode = NoNode)
                        throw(ERRange,ERRejected);
    bool            Dijkstra(TNode,TNode = NoNode) throw(ERRange,ERRejected);
    TNode           VoronoiRegions() throw(ERRejected);
    bool            BellmanFord(TNode,TNode = NoNode)
                        throw(ERRange,ERCheck);
    bool            FIFOLabelCorrecting(TNode,TNode = NoNode)
                        throw(ERRange,ERCheck);
    TNode           NegativeCycle(TNode = NoNode) throw(ERRange);

    
        // Computation of connected components and minimum edge cuts.
        // Components/cuts are encoded into the node colours and/or the
        // subgraph labels.

    bool            Connected() throw();
    virtual bool    Connected(TCap) throw();
    bool            CutNodes(TNode* = NULL,TNode* = NULL) throw();
    bool            TwoConnected() throw();
    virtual bool    EdgeConnected(TCap) throw();
    bool            StronglyConnected() throw();
    virtual bool    StronglyConnected(TCap) throw();
    virtual bool    StronglyEdgeConnected(TCap) throw();

    TCap            Connectivity() throw();
    TCap            EdgeConnectivity() throw();
    virtual TCap    StrongConnectivity() throw();
    virtual TCap    StrongEdgeConnectivity() throw();
    TCap            StrongEdgeConnectivity(TNode) throw(ERRange);
    TCap            StrongEdgeConnectivity(TNode,TNode) throw(ERRange);

    TCap            MinCutLegalOrdering(TNode,TNode&,TNode&) throw(ERRange,ERRejected);
    TCap            MinCutNodeIdentification() throw(ERRejected);

    
        // Planarity algorithms.
    
    bool            IsPlanar() throw(ERRejected);


        // Minimum Spanning Tree algorithms.
    
    virtual TFloat  MinTree(TNode = NoNode) throw(ERRange,ERRejected);
    virtual TCap    TreePacking(TNode) throw(ERRejected,ERRange);

    TFloat          SteinerTree(TNode) throw(ERRange,ERRejected);
    TFloat          SteinerTrimLeaves() throw();
    virtual TFloat  SteinerHeuristics(TNode) throw(ERRange);
    virtual TFloat  SteinerEnumerate(TNode) throw(ERRange);


        // Computation of node packings, partitions and coverings.

    virtual TNode   StableSet() throw();
    TNode           Clique() throw();
    virtual TNode   VertexCover() throw();
    virtual TNode   NodeColouring(TNode = NoNode) throw();
    TNode           PlanarColouring() throw(ERRejected);
    TNode   	    NCLocalSearch() throw(ERRejected);
    bool   	        NCKempeExchange(TNode,TNode) throw(ERRange,ERRejected);
    TNode           CliqueCover(TNode = NoNode) throw();
    TNode           EdgeColouring(TNode = NoNode) throw(ERRange);

    
        // Prototype for Chinese Postman tours / Eulerian Supergraphs.

    virtual void    ChinesePostman() throw(ERRejected);

    
        // TSP and Hamiltonian Cycles.

    TFloat          TSP(TNode = NoNode) throw(ERRejected);
    virtual TFloat  TSPHeuristics(TNode) throw(ERRange,ERRejected);
    TFloat          TSPHeuristicsRandom() throw(ERRejected);
    TFloat          TSPHeuristicsInsert() throw(ERRejected);
    TFloat          TSPHeuristicsInsert(TNode) throw(ERRange,ERRejected);
    TFloat          TSPHeuristicsTree() throw(ERRejected);
    TFloat          TSPHeuristicsTree(TNode) throw(ERRange,ERRejected);
    virtual TFloat  TSPLocalSearch() throw(ERRejected);
    bool            TSPNodeExchange(TFloat = 0) throw(ERRejected);
    virtual TFloat  TSPSubOpt1Tree(TNode,TFloat = InfFloat,TOption = 1) throw(ERRange,ERRejected);
    virtual TFloat  TSPBranchAndBound(TNode,TFloat = InfFloat) throw(ERRejected);


        // Maximum Edge Cuts and Maximum Bipartite Subgraphs.

    virtual TCap    MaxCut(TNode = NoNode,TNode = NoNode) throw(ERRange);
    TCap  MaxCutHeuristicsRandom(TNode = NoNode,TNode = NoNode) throw(ERRange);
    TCap  MaxCutLocalSearch(TNode = NoNode,TNode = NoNode)
                throw(ERRange,ERRejected);


    // *************************************************************** //
    //                   Display methods                               //
    // *************************************************************** //
        
    virtual char*   Display() throw(ERRejected,ERFile);
    void            TextDisplay(TNode,TNode = NoNode) throw();
        // List the graph in a text file
    void            DisplayPath(TNode,TNode) throw(ERRange,ERRejected);
        // Display the uv-path encoded into the predecessor labels
    TFloat          CutCapacity(TFloat = InfFloat) throw(ERCheck);
        // Returns the capacity of the cut induced by the distance labels

    void            Export2XFig(char*) throw(ERFile);
    void            Export2Tk(char*) throw(ERFile);
    void            Export2Ascii(char*,TOption = 0) throw(ERFile);

};                           



class iGraph : public virtual goblinIterator
{                                        
private:

    abstractMixedGraph &    G;
    TNode                   n;
    TArc *                  current;

public:             

    iGraph(abstractMixedGraph &GC) throw();
    ~iGraph() throw();

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

    void            Reset() throw();
    void            Reset(TNode) throw(ERRange);
    TArc            Read(TNode) throw(ERRange,ERRejected);
    TArc            Peek(TNode) throw(ERRange,ERRejected);
    bool            Active(TNode) throw(ERRange);
    
};                             


#endif


