jacint@494: // -*- C++ -*-
jacint@494: /*
jacint@494: Kell meg a dual oldal
jacint@494: esetleg az elejen moho matching kereses
jacint@494: 
jacint@494:   //baj van pos-sal: nem tudok vegigmaszni a halmazok elemein. De
jacint@494:   //pos-ra nem lenne szukseg ha unionfindban lenne egy element ami
jacint@494:   //true ha benne van false ha nincs
jacint@494: 
jacint@494: MISI strukijahoz hasznalok:
jacint@494: 
jacint@494: void addElement(b,a): b meg nem volt egy osztalyban sem, ezzel hozzaadjuk a osztalyahoz
jacint@494: void insert(a): a meg nem volt egy osztalyban sem, ezzel egy uj egyelemu osztalyt alkot
jacint@494: bool element(a): true ha benne van false ha nincs
jacint@494: void erase(a)
jacint@494: 
jacint@494: ez a 4 a vegso szetrobbantashoz es egyideju elemfelsorolashoz kell, mas megoldas is jo ehelyett:
jacint@494: 
jacint@494: bool empty(int i): ures-e az i nevu osztaly
jacint@494: int find(a)
jacint@494: void pop(int i): egy fix elso elemet kitorol az i osztalybol
jacint@494: T top(int i): visszad egy fix elso elemet 
jacint@494: 
jacint@494: unionfindba kene:
jacint@494: bool element(a): true ha benne van false ha nincs  (vagy 'bool empty')
jacint@494: void split(a) (vagy clear)
jacint@494: T rep(a): visszaadja a halmazanak reprezentanselemet, lehet operator()-val is
jacint@494: void makeRep(a): a-t a sajat halmazanak reprezentansava teszi
jacint@494: 
jacint@494: Szoljatok ha nem lehet valamelyiket hatekonyan
jacint@494: */
jacint@494: 
jacint@494: #ifndef HUGO_EDMONDS_H
jacint@494: #define HUGO_EDMONDS_H
jacint@494: 
jacint@494: #include <queue>
jacint@494: 
jacint@494: #include <invalid.h>
jacint@494: #include <unionfind.h>
jacint@494: 
jacint@494: namespace hugo {
jacint@494: 
jacint@494:   template <typename Graph>
jacint@494:   class Edmonds {
jacint@494:     
jacint@494:     typedef typename Graph::Node Node;
jacint@494:     typedef typename Graph::Edge Edge;
jacint@494:     typedef typename Graph::EdgeIt EdgeIt;
jacint@494:     typedef typename Graph::NodeIt NodeIt;
jacint@494:     typedef typename Graph::OutEdgeIt OutEdgeIt;
jacint@494: 
jacint@494:     typedef UnionFindEnum<Node, Graph::NodeMap > ufe;
jacint@494:             
jacint@494:     const Graph& G;
jacint@494: 
jacint@494:   public:
jacint@494:     Edmonds(Graph& _G) : G(_G) {}
jacint@494:     
jacint@494:     
jacint@494:     int run(std::vector<Edge> matching) {
jacint@494: 
jacint@494:       enum pos_enum{
jacint@494: 	D=0,
jacint@494: 	A=1,
jacint@494: 	C=2
jacint@494:       };
jacint@494:       Graph::template NodeMap<pos_enum> pos(G,C);
jacint@494: 
jacint@494:       int p=0;   //needed for path
jacint@494: 
jacint@494:       typename Graph::NodeMap<Node> mate(G,INVALID);
jacint@494:       for ( int i=0; i!=matching.size(); ++i ) {
jacint@494: 	Node u=G.aNode(matching[i]);
jacint@494: 	Node v=G.bNode(matching[i]);
jacint@494: 	mate.set(u,v);
jacint@494: 	mate.set(v,u);
jacint@494:       }
jacint@494:       matching.clear();
jacint@494: 
jacint@494:       typename Graph::NodeMap<Node> ear(G,INVALID);   
jacint@494:       // a basepontok es a C-beliek earje szemet
jacint@494: 
jacint@494:       ufe::MapType blossom_base(G);
jacint@494:       ufe blossom(blossom_base);
jacint@494:       ufe::MapType tree_base(G);
jacint@494:       ufe tree(tree_base);
jacint@494: 
jacint@494:       NodeIt v;
jacint@494:       for(G.first(v); G.valid(v), G.next(v) ) {
jacint@494: 	
jacint@494: 	if ( pos[v]==C && mate[v]=INVALID ) {
jacint@494: 	  
jacint@494: 	  blossom.insert(v);
jacint@494: 	  tree.insert(v); 
jacint@494: 	  pos.set(v,D);
jacint@494: 
jacint@494: 	  std::queue<Node> Q;   //a vizsgalando csucsok sora
jacint@494: 	  Q.push(v);  
jacint@494: 
jacint@494: 	  while ( !Q.empty() ) {
jacint@494: 	    Node x=Q.top();
jacint@494: 	    Q.pop();
jacint@494: 	    
jacint@494: 	    OutEdgeIt e;
jacint@494: 	    for( G.first(e); G.valid(e), G.next(e) ) {
jacint@494: 	      Node y=G.bNode(e);
jacint@494: 
jacint@494: 	      if ( pos[y]==D ) { 
jacint@494: 
jacint@494: 		if ( tree.find(x) != tree.find(y) ) {  //augment 
jacint@494: 		  augment(x, mate, ear, blossom, tree); 
jacint@494: 		  augment(y, mate, ear, blossom, tree); 
jacint@494: 		  mate.set(x)=y;
jacint@494: 		  mate.set(y)=x;
jacint@494: 		  goto increased;
jacint@494: 		} else 
jacint@494: 		  if ( blossom.find(x) != blossom.find(y) ) {
jacint@494: 
jacint@494: 		    typename Graph::NodeMap<int> path(G,0);
jacint@494: 
jacint@494: 		    ++p;
jacint@494: 		    Node b=blossom.find(x);
jacint@494: 		    path.set(b,p);
jacint@494: 		    while ( b!=INVALID ) {
jacint@494: 		      b=blossom.find(ear[mate[b]]);
jacint@494: 		      path.set(b,p);
jacint@494: 		    }          //going till the root
jacint@494: 	
jacint@494: 		    Node w=y;
jacint@494: 		    Node v=blossom.find(w);
jacint@494: 		    while ( path[v]!=p ) {		      
jacint@494: 		      Q.push(mate[v]);
jacint@494: 		      w=shrink_step(w,v,mate,ear,tree,blossom);
jacint@494: 		      v=blossom.find(w);
jacint@494: 		    }
jacint@494: 		    //now v is the base of the first common ancestor
jacint@494: 
jacint@494: 		    w=x;
jacint@494: 		    Node z=blossom.find(w);
jacint@494: 		    while ( z!=v ) {
jacint@494: 		      Q.push(mate[z]);
jacint@494: 		      w=shrink_step(w,z,mate,ear,tree,blossom);
jacint@494: 		      z=blossom.find(w);
jacint@494: 		    }
jacint@494: 
jacint@494: 		    ear.set(x,y);
jacint@494: 		    ear.set(y,x);
jacint@494: 
jacint@494: 		    blossom.makeRep(v);
jacint@494: 		  }
jacint@494: 	      } else if ( pos[y] == C ) 
jacint@494: 		
jacint@494: 		if ( mate[y]!=INVALID ) {       //grow
jacint@494: 		  ear.set(y,x);
jacint@494: 		  Node w=mate(y);
jacint@494: 		  blossom.insert(w);
jacint@494: 		  tree.insert(w);
jacint@494: 		  tree.join(y,x);  
jacint@494: 		  tree.join(w,x);  
jacint@494: 		  Q.push(w);
jacint@494: 		} else {
jacint@494: 		  augment(x, mate, ear, blossom, tree); 
jacint@494: 		  mate.set(x)=y;
jacint@494: 		  mate.set(y)=x;
jacint@494: 		  goto increased;
jacint@494: 		}
jacint@494: 	    }
jacint@494: 	  }
jacint@494: 	increased:  //Misi, warningol, hogy nincs utasitas!
jacint@494: 	}
jacint@494:       }
jacint@494: 
jacint@494:       int s=0;
jacint@494:       NodeIt v;
jacint@494:       for(G.first(v); G.valid(v), G.next(v) ) 
jacint@494: 	if ( mate[v]!=INVALID ) ++s;
jacint@494: 	
jacint@494:       return (int)(s/2);
jacint@494: 
jacint@494:       //egyelore nem ad semmit vissza
jacint@494:       
jacint@494:     }
jacint@494:   
jacint@494: 
jacint@494:     void augment(const Node x, typename Graph::NodeMap<Node>& mate, 
jacint@494: 		 typename Graph::NodeMap<Node>& ear, 
jacint@494: 		 ufe& blossom, ufe& tree) { 
jacint@494:       Node v=mate[x];
jacint@494:       while ( v!=INVALID ) {
jacint@494: 	Node u=ear[v];
jacint@494: 	mate.set(v,u);
jacint@494: 	Node tmp=v;
jacint@494: 	v=mate[u];
jacint@494: 	mate.set(u,tmp);
jacint@494:       }
jacint@494:       //FIXME, blossom szetszed
jacint@494:       tree.eraseClass(x);
jacint@494:     }
jacint@494: 
jacint@494: 
jacint@494:     Node shrink_step(const Node z, const Node v, typename Graph::NodeMap<Node>& mate, 
jacint@494: 		     typename Graph::NodeMap<Node>& ear, 
jacint@494: 		     ufe& blossom, ufe& tree) {  
jacint@494:       if ( z!=v ) {
jacint@494: 	Node t=z;
jacint@494: 	Node u;
jacint@494: 	while ( t!=v ) {
jacint@494: 	  u=mate[t];
jacint@494: 	  t=ear[u];
jacint@494: 	}
jacint@494: 	ear.set(v,u);
jacint@494:       }
jacint@494: 
jacint@494:       Node u=mate[v];
jacint@494:       Node w=ear[u];
jacint@494:       tree.erase(u);
jacint@494:       tree.erase(v);
jacint@494:       blossom.insert(u);
jacint@494:       blossom.join(u,w);
jacint@494:       blossom.join(v,w);
jacint@494:       ear.set(w,u);      
jacint@494: 
jacint@494:       return w;
jacint@494:     }
jacint@494: 
jacint@494: 
jacint@494:   };
jacint@494: 
jacint@494: } //namespace hugo
jacint@494: 
jacint@494: #endif //EDMONDS_H
jacint@494: 
jacint@494: 
jacint@494: 
jacint@494: