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


#if !defined(_ABSDIG_H_)

#define _ABSDIG_H_

#include <absmix.h>


class abstractDiGraph : public virtual abstractMixedGraph
{
protected:

    TCap            delta;      // Threshold for Capacity Scaling Alg.

public:

    abstractDiGraph() throw();
    virtual ~abstractDiGraph() throw();
	
	unsigned long	Allocated() throw();

    bool            IsDirected() throw() {return 1;};
	
    TFloat          NodeCap(TNode v) throw(ERRange)
        {if (DegIn(v)<DegOut(v)) return DegIn(v); else return DegOut(v);};
    
    TCap            Demand(TNode v) throw(ERRange) {return 0;};
    
    TFloat          RedLength(TArc a) throw(ERRange);     
    virtual TFloat  ModLength(TArc a) throw(ERRange) {return RedLength(a);};     

    bool            Eligible(TArc a) throw(ERRange);
        // Arc selector for graph search algorithms 

    virtual TFloat  Flow(TArc a) throw(ERRange) {return Sub(a);};
    virtual void    Push(TArc a,TFloat Lambda) throw(ERRange,ERRejected);
        // Increase or decrease the flow value of the
        // arc a by an amount Lambda
    TFloat          ResCap(TArc a) throw(ERRange);          
        // Return the residual capacity of the arc a
    void            InitFlow() throw();
    
    TFloat FindCap(TNode u,TNode v) throw(ERRange,ERRejected);
        // Compute the residual capacity of the augmenting
        // path found by FindPath
    void  Augment(TNode u,TNode v,TFloat Lambda) throw(ERRange,ERRejected);
        // Augment on the path found by FindPath by an
        // amount Lambda

    void  AdjustDivergence(TArc a,TFloat Lambda) throw(ERRange,ERRejected);
        // Update the degree labels with respect to a push operation
    
    TFloat          FlowValue(TNode s,TNode t) throw(ERRange,ERCheck);                     
        // Checks wether the flow labels define an st-flow
        // and, if so, show the flow value
    bool            Compatible() throw();
        // Checks wether the flow labels and the node potentials
        // satisfy the complementary slackness conditions

    void            WriteDiGraph(char* fileName,TWriteInc options) throw(ERFile);
    virtual void    Write(char* fileName) throw(ERFile)
                        {WriteDiGraph(fileName,WRITE_INCIDENCES);};


    // --------------------------------------------------------------
    //                  Mathematical Algorithms
    // --------------------------------------------------------------

    bool            TopSort() throw();
    TNode           MinimumMeanCycle() throw();
    
    TCap            TreePacking(TNode) throw(ERRange);
    abstractDiGraph*TreePKGInit() throw();
    TCap            TreePKGStripTree(abstractDiGraph*,TCap*,TNode) throw(ERRange);
    
    
    // --------------------------------------------------------------
    //                 Compute a maximum st-flow
    // --------------------------------------------------------------
    
    TFloat          MaxFlow(TNode s,TNode t) throw(ERRange,ERRejected);     
    TFloat          EdmondsKarp(TNode s,TNode t) throw(ERRange);     
    TFloat          CapacityScaling(TNode s,TNode t) throw(ERRange);     
    TFloat          GoldbergTarjan(TNode s,TNode t) throw(ERRange);     
    TFloat          Dinic(TNode s,TNode t) throw(ERRange);     
    
    
    // --------------------------------------------------------------
    //                 Compute a minimum edge cut
    // --------------------------------------------------------------
    
    TCap            MinCutHaoOrlin(TNode r) throw(ERRange);     
    
    // --------------------------------------------------------------
    //              Compute a minimum cost st-flow
    // --------------------------------------------------------------

    TFloat          MinCostFlow(TNode,TNode,TFloat = 0) throw(ERRange,ERRejected);     
    TFloat          BusackerGowen(TNode,TNode,TFloat = 0) throw(ERRange);     
    TFloat          EdmondsKarp2(TNode,TNode,TFloat = 0) throw(ERRange,ERRejected);     
    TFloat          WCapacityScaling(TNode,TNode,TFloat = 0) throw(ERRange,ERRejected);     
    
    // --------------------------------------------------------------
    //             Compute an admissible ciculation
    // --------------------------------------------------------------
        
    bool            AdmissibleCirculation() throw();     

    // --------------------------------------------------------------
    //            Compute a minimum cost circulation
    // --------------------------------------------------------------

    TFloat          MinCostCirculation() throw(ERRejected);
    TFloat          CycleCanceling() throw();
    TFloat          MinMeanCycleCanceling() throw();
    TFloat          CostScaling() throw();
    TFloat          NWSimplex() throw();
    TFloat          ShortestAugmentingPath() throw(ERRejected);
    
protected:

    void            NWSimplexCancelFree() throw();
    void            NWSimplexStrongTree() throw();
    void            NWSimplexThreadIndex(TNode*) throw();
    void            NWSimplexComputePotentials(TNode*) throw();
    TNode           NWSimplexUpdateThread(TNode*,TNode,TNode,TNode) throw();
    TArc            NWSimplexPivotArc() throw();
    bool            NWSimplexPivotOperation(TNode*,TArc) throw();

};


#endif
