/Users/jst/src/grafalgo/cpp/include/fastEdmonds.h

// Header file for class that implements Edmond's algorithm for
// finding a maximum size matching in a general graph. To use,
// invoke the constructor.

#ifndef FASTEDMONDS_H
#define FASTEDMONDS_H

#include "stdinc.h"
#include "Graph.h"
#include "List.h"
#include "Dlist.h"
#include "RlistSet.h"
#include "Partition.h"

using namespace grafalgo;

class fastEdmonds {
public: fastEdmonds(Graph&,Dlist&,int&);
        string& statString(bool, string&);
private:
        Graph* graf;            
        Dlist* match;           
        Partition *blossoms;    
        RlistSet* augpath;      
        vertex* origin;         

        struct BridgePair {     
        edge e; vertex v;       
        };
        BridgePair *bridge;     


        enum stype {unreached, odd, even};
        stype *state;           
        edge* mEdge;            
        edge* pEdge;            
        bool* mark;             
        int  searchNum;         
        int* latestSearch;      

        edge* nextEdge;         
        List* pending;          
        Dlist* unmatched;       

        int iSize, mSize, stepCount, blossomCount;
        int imatchTime, rmatchTime, pathInitTime, pathFindTime;
        
        vertex nca(vertex,vertex); // return nearest-common ancestor
        edge path(vertex,vertex); // construct augmenting path
        void augment(edge);     // augment the matching
        edge findpath();        // find an altmenting path
};

#endif