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


#if !defined(_ABSBAL_H_)

#define _ABSBAL_H_

#include <absdig.h>


class abstractBalancedFNW : public virtual abstractDiGraph
{
friend class bal2bal;
protected:

    TNode           n1;         // Number of outer nodes

    TArc *          Q;
        // Pointer to an array for encoding of odd cycles
    TArc *          prop;
        // Pointer to an array of node props
    TArc *          petal;
        // Pointer to an array of node petals
    TNode *         base;
        // Pointer to an array of blossom bases

public:

    abstractBalancedFNW(TNode nn = 0) throw();
    virtual ~abstractBalancedFNW() throw();
	
    unsigned long   Allocated() throw();

    bool            IsBalanced() throw() {return 1;};
	
    virtual void    Symmetrize() throw() = 0;
    virtual void    Relax() throw() = 0;
    
    void            WriteBalancedFNW(char* fileName,TOption options)
                        throw(ERFile);
    void            Write(char* fileName) throw(ERFile)
                        {WriteBalancedFNW(fileName,WRITE_INCIDENCES);};
    
    TNode           N1() throw() {return n1;};
    
    bool            Outer(TNode v) throw(ERRange);
    bool            Inner(TNode v) throw(ERRange);

    TNode           ComplNode(TNode v) throw(ERRange);
    TArc            ComplArc(TArc a) throw(ERRange);
    
    // *************************************************************** //
    //           Management of Odd Cycles                              //
    // *************************************************************** //
    
    void            InitCycles() throw();
    void            ReleaseCycles() throw();
    
    // *************************************************************** //
    //           Management of Blossoms and Blossom Bases              //
    // *************************************************************** //
    
    void            InitBlossoms() throw();
    void            ReleaseBlossoms() throw();
    TNode           Base(TNode v) throw(ERRange);
    TNode           Pred(TNode v) throw(ERRange);
    void            Bud(TNode v) throw(ERRange);
    void            Shrink(TNode u,TNode v) throw(ERRange);
    
    void            InitPartition() throw() {InitBlossoms();};
    void            ReleasePartition() throw() {ReleaseBlossoms();};
    void            Merge(TNode u,TNode v) throw(ERRange) {Shrink(u,v);};
    TNode           Find(TNode v) throw(ERRange) {return Base(v);};
    
    // *************************************************************** //
    //           Management of Props                                   //
    // *************************************************************** //
    
    void            InitProps() throw();
    void            ReleaseProps() throw();
    
    // *************************************************************** //
    //           Management of Petals                                  //
    // *************************************************************** //
    
    void            InitPetals() throw();
    void            ReleasePetals() throw();
    
    TFloat          FindBalCap(TNode u,TNode v) throw(ERRange,ERRejected);
    virtual void    BalPush(TArc a,TFloat Lambda) throw(ERRange,ERRejected) = 0;
    virtual TFloat  BalFlow(TArc a) throw(ERRange) = 0;
    virtual TFloat  BalCap(TArc a) throw(ERRange);
    void            BalAugment(TNode u,TNode v,TFloat Lambda) throw(ERRange,ERRejected);

    void            CancelEven() throw();
    void            MakeIntegral(TArc *PP,TNode u,TNode v) throw(ERRange);

    TFloat          MaxBalFlow(TNode s) throw(ERRange);
    TFloat          Anstee(TNode s) throw(ERRange);
    virtual TFloat  CancelOdd() throw();
    TFloat          MicaliVazirani(TNode s,TNode t=NoNode) throw(ERRange);
    
    TFloat          BNSAndAugment(TNode s) throw(ERRange);
    TFloat          BalancedScaling(TNode s) throw(ERRange);
    bool            BNS(TNode s,TNode t=NoNode) throw(ERRange,ERRejected);
    void            Expand(TNode u,TNode v) throw(ERRange);
    void            CoExpand(TNode u,TNode v) throw(ERRange);

    bool            BNSKocayStone(TNode s,TNode t=NoNode) throw(ERRange);
    bool            BNSKamedaMunro(TNode s,TNode t=NoNode) throw(ERRange);
    bool            BNSHeuristicsBF(TNode s,TNode t=NoNode) throw(ERRange);
    bool            BNSMicaliVazirani(TNode s,TNode t=NoNode) throw(ERRange);
    
    TFloat          MinCBalFlow(TNode s) throw(ERRange,ERRejected);
    TFloat          PrimalDual(TNode s) throw(ERRange,ERRejected);
    TFloat          EnhancedPD(TNode s) throw(ERRange,ERRejected);
    TFloat          CancelPD() throw();
    
};                           


#endif
