// -*- 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