
/*
**  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(_ABSGRA_H_)

#define _ABSGRA_H_

#include <absmix.h>


class abstractGraph : public virtual abstractMixedGraph
{
public:

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

    bool            IsUndirected() throw() {return 1;};


    // *************************************************************** //
    //           Graph Export Methods                                  //
    // *************************************************************** //
    
    void            WriteGraph(char* fileName,TWriteInc options) throw(ERFile);
    virtual void    Write(char* fileName) throw(ERFile)
                        {WriteGraph(fileName,WRITE_INCIDENCES);};
    

    // *************************************************************** //
    //              Minimum Spanning Tree Algorithms                   //
    // *************************************************************** //
    
        // Return the optimum value

    TFloat          MinTree(TNode r = NoNode) throw(ERRange,ERRejected);
    TFloat          Prim(TNode r = 0) throw(ERRange,ERRejected);
    TFloat          Prim2(TNode r = 0) throw(ERRange,ERRejected);
        // Returns a minimal spanning tree by the predecessor labels.
        // The optional node v is the root of this arborescence.
    TFloat          Kruskal(TNode r = NoNode) throw(ERRange,ERRejected);
        // Returns the connected components by the partition data structure.
    TFloat          SteinerHeuristics(TNode = NoNode) throw(ERRange);
    TFloat          SteinerEnumerate(TNode = NoNode) throw(ERRange);
    

    // *************************************************************** //
    //                      TSP Algorithms                             //
    // *************************************************************** //
    
        // Return the length of the best found tour,
        // and a corresponding tour by the predecessor labels.
        
    virtual TFloat  TSPHeuristics(TNode) throw(ERRange,ERRejected);
    TFloat          TSPHeuristicsChristofides(TNode = NoNode) throw(ERRange);
    TFloat          TSPLocalSearch() throw(ERRejected);
    bool            TSP2Exchange(TFloat = 0) throw(ERRejected);
    TFloat          TSPSubOpt1Tree(TNode,TFloat = InfFloat,TOption = 1) throw(ERRange);
    TFloat          TSPBranchAndBound(TNode,TFloat = InfFloat) throw();
    

    // *************************************************************** //
    //                    Matching Algorithms                          //
    // *************************************************************** //
    
    virtual bool    MaximumMatching() throw();
    virtual bool    MaximumMatching(TCap cDeg) throw();
    virtual bool    MaximumMatching(TCap *pLower,TCap *pDeg = NULL) throw();

    virtual bool    MinCMatching() throw();
    virtual bool    MinCMatching(TCap cDeg) throw();
    virtual bool    MinCMatching(TCap *pLower,TCap *pDeg = NULL) throw();
    bool            PMHeuristicsCandidates() throw();
    TFloat          PMHeuristicsRandom() throw();

    void            ComputeTJoin() throw();
    void            MinCTJoin() throw();
    void            MinCTJoin(TNode,TNode) throw(ERRange);
    void            ChinesePostman() throw();
    

    // *************************************************************** //
    //                    Minimum and Maximum Cuts                     //
    // *************************************************************** //
    
    TCap  StrongConnectivity() throw() {return Connectivity();};
    TCap  StrongEdgeConnectivity() throw(){return EdgeConnectivity();};

    TCap  MaxCut(TNode = NoNode,TNode = NoNode) throw(ERRange);
    TCap  MaxCutHeuristicsTree(TNode = NoNode,TNode = NoNode) throw(ERRange);

};                           


#endif

