source: lemon-0.x/src/work/jacint/edmonds.h @ 516:c37949721c61

// -*- C++ -*-
/*
Kell meg a dual oldal
esetleg az elejen moho matching kereses

  //baj van pos-sal: nem tudok vegigmaszni a halmazok elemein. De
  //pos-ra nem lenne szukseg ha unionfindban lenne egy element ami
  //true ha benne van false ha nincs

MISI strukijahoz hasznalok:

void addElement(b,a): b meg nem volt egy osztalyban sem, ezzel hozzaadjuk a osztalyahoz
void insert(a): a meg nem volt egy osztalyban sem, ezzel egy uj egyelemu osztalyt alkot
bool element(a): true ha benne van false ha nincs
void erase(a)

ez a 4 a vegso szetrobbantashoz es egyideju elemfelsorolashoz kell, mas megoldas is jo ehelyett:

bool empty(int i): ures-e az i nevu osztaly
int find(a)
void pop(int i): egy fix elso elemet kitorol az i osztalybol
T top(int i): visszad egy fix elso elemet 

unionfindba kene:
bool element(a): true ha benne van false ha nincs  (vagy 'bool empty')
void split(a) (vagy clear)
T rep(a): visszaadja a halmazanak reprezentanselemet, lehet operator()-val is
void makeRep(a): a-t a sajat halmazanak reprezentansava teszi

Szoljatok ha nem lehet valamelyiket hatekonyan
*/

#ifndef HUGO_EDMONDS_H
#define HUGO_EDMONDS_H

#include <queue>

#include <invalid.h>
#include <unionfind.h>

namespace hugo {

  template <typename Graph>
  class Edmonds {
    
    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::EdgeIt EdgeIt;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::OutEdgeIt OutEdgeIt;

    typedef UnionFindEnum<Node, Graph::NodeMap > ufe;
            
    const Graph& G;

  public:
    Edmonds(Graph& _G) : G(_G) {}
    
    
    int run(std::vector<Edge> matching) {

      enum pos_enum{
        D=0,
        A=1,
        C=2
      };
      Graph::template NodeMap<pos_enum> pos(G,C);

      int p=0;   //needed for path

      typename Graph::NodeMap<Node> mate(G,INVALID);
      for ( int i=0; i!=matching.size(); ++i ) {
        Node u=G.aNode(matching[i]);
        Node v=G.bNode(matching[i]);
        mate.set(u,v);
        mate.set(v,u);
      }
      matching.clear();

      typename Graph::NodeMap<Node> ear(G,INVALID);   
      // a basepontok es a C-beliek earje szemet

      ufe::MapType blossom_base(G);
      ufe blossom(blossom_base);
      ufe::MapType tree_base(G);
      ufe tree(tree_base);

      NodeIt v;
      for(G.first(v); G.valid(v), G.next(v) ) {
        
        if ( pos[v]==C && mate[v]=INVALID ) {
          
          blossom.insert(v);
          tree.insert(v); 
          pos.set(v,D);

          std::queue<Node> Q;   //a vizsgalando csucsok sora
          Q.push(v);  

          while ( !Q.empty() ) {
            Node x=Q.top();
            Q.pop();
            
            OutEdgeIt e;
            for( G.first(e); G.valid(e), G.next(e) ) {
              Node y=G.bNode(e);

              if ( pos[y]==D ) { 

                if ( tree.find(x) != tree.find(y) ) {  //augment 
                  augment(x, mate, ear, blossom, tree); 
                  augment(y, mate, ear, blossom, tree); 
                  mate.set(x)=y;
                  mate.set(y)=x;
                  goto increased;
                } else 
                  if ( blossom.find(x) != blossom.find(y) ) {

                    typename Graph::NodeMap<int> path(G,0);

                    ++p;
                    Node b=blossom.find(x);
                    path.set(b,p);
                    while ( b!=INVALID ) {
                      b=blossom.find(ear[mate[b]]);
                      path.set(b,p);
                    }          //going till the root
        
                    Node w=y;
                    Node v=blossom.find(w);
                    while ( path[v]!=p ) {                    
                      Q.push(mate[v]);
                      w=shrink_step(w,v,mate,ear,tree,blossom);
                      v=blossom.find(w);
                    }
                    //now v is the base of the first common ancestor

                    w=x;
                    Node z=blossom.find(w);
                    while ( z!=v ) {
                      Q.push(mate[z]);
                      w=shrink_step(w,z,mate,ear,tree,blossom);
                      z=blossom.find(w);
                    }

                    ear.set(x,y);
                    ear.set(y,x);

                    blossom.makeRep(v);
                  }
              } else if ( pos[y] == C ) 
                
                if ( mate[y]!=INVALID ) {       //grow
                  ear.set(y,x);
                  Node w=mate(y);
                  blossom.insert(w);
                  tree.insert(w);
                  tree.join(y,x);  
                  tree.join(w,x);  
                  Q.push(w);
                } else {
                  augment(x, mate, ear, blossom, tree); 
                  mate.set(x)=y;
                  mate.set(y)=x;
                  goto increased;
                }
            }
          }
        increased:  //Misi, warningol, hogy nincs utasitas!
        }
      }

      int s=0;
      NodeIt v;
      for(G.first(v); G.valid(v), G.next(v) ) 
        if ( mate[v]!=INVALID ) ++s;
        
      return (int)(s/2);

      //egyelore nem ad semmit vissza
      
    }
  

    void augment(const Node x, typename Graph::NodeMap<Node>& mate, 
                 typename Graph::NodeMap<Node>& ear, 
                 ufe& blossom, ufe& tree) { 
      Node v=mate[x];
      while ( v!=INVALID ) {
        Node u=ear[v];
        mate.set(v,u);
        Node tmp=v;
        v=mate[u];
        mate.set(u,tmp);
      }
      //FIXME, blossom szetszed
      tree.eraseClass(x);
    }


    Node shrink_step(const Node z, const Node v, typename Graph::NodeMap<Node>& mate, 
                     typename Graph::NodeMap<Node>& ear, 
                     ufe& blossom, ufe& tree) {  
      if ( z!=v ) {
        Node t=z;
        Node u;
        while ( t!=v ) {
          u=mate[t];
          t=ear[u];
        }
        ear.set(v,u);
      }

      Node u=mate[v];
      Node w=ear[u];
      tree.erase(u);
      tree.erase(v);
      blossom.insert(u);
      blossom.join(u,w);
      blossom.join(v,w);
      ear.set(w,u);      

      return w;
    }


  };

} //namespace hugo

#endif //EDMONDS_H