# HG changeset patch
# User jacint
# Date 1083307599 0
# Node ID e42f56e7ad9349453f3b98acb0caf3027d5b995a
# Parent  bbd1db03f0fefa8225345ff86d74204bd9b3c8ec
Felkesz kod!

diff -r bbd1db03f0fe -r e42f56e7ad93 src/work/jacint/edmonds.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/edmonds.cc	Fri Apr 30 06:46:39 2004 +0000
@@ -0,0 +1,220 @@
+#include <iostream>
+#include <vector>
+#include <string>
+
+#include <list_graph.h>
+#include <edmonds.h>
+
+using namespace hugo;
+
+int main (int, char*[])
+{
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EdgeIt EdgeIt;
+  typedef ListGraph::Node Node;
+  typedef ListGraph::Edge Edge;
+  typedef ListGraph::OutEdgeIt OutEdgeIt;
+  typedef ListGraph::InEdgeIt InEdgeIt;
+  
+  ListGraph flow_test;
+ 
+  /*    //Ahuja könyv példája, maxflowvalue=13*/
+  Node s=flow_test.addNode();
+  Node v1=flow_test.addNode();
+  Node v2=flow_test.addNode();
+  Node v3=flow_test.addNode();
+  Node v4=flow_test.addNode();
+  Node v5=flow_test.addNode();
+  Node t=flow_test.addNode();
+  
+  ListGraph::NodeMap<std::string> Node_name(flow_test);
+  Node_name.set(s, "s");
+  Node_name.set(v1, "v1");
+  Node_name.set(v2, "v2");
+  Node_name.set(v3, "v3");
+  Node_name.set(v4, "v4");
+  Node_name.set(v5, "v5");
+  Node_name.set(t, "t");
+
+  Edge s_v1=flow_test.addEdge(s, v1);
+  Edge s_v2=flow_test.addEdge(s, v2);
+  Edge s_v3=flow_test.addEdge(s, v3);
+  Edge v2_v4=flow_test.addEdge(v2, v4);
+  Edge v2_v5=flow_test.addEdge(v2, v5);
+  Edge v3_v5=flow_test.addEdge(v3, v5);
+  Edge v4_t=flow_test.addEdge(v4, t);
+  Edge v5_t=flow_test.addEdge(v5, t);
+  Edge v2_s=flow_test.addEdge(v2, s);
+  
+   ListGraph::EdgeMap<int> cap(flow_test);  
+  cap.set(s_v1, 0);
+  cap.set(s_v2, 10);
+  cap.set(s_v3, 10);
+ cap.set(v2_v4, 5);
+  cap.set(v2_v5, 8);
+  cap.set(v3_v5, 5);
+  cap.set(v4_t, 8);
+  cap.set(v5_t, 8);
+  cap.set(v2_s, 0);
+  
+
+  Edmonds<ListGraph> edmonds(flow_test);
+  std::vector<Edge> matching(0);
+  std::cout<<  edmonds.run(matching);
+
+  
+  /*  //Marci példája, maxflowvalue=23
+    Node s=flow_test.addNode();
+  Node v1=flow_test.addNode();
+  Node v2=flow_test.addNode();
+  Node v3=flow_test.addNode();
+  Node v4=flow_test.addNode();
+  Node t=flow_test.addNode();
+  Node z=flow_test.addNode();
+
+  
+   ListGraph::NodeMap<std::string> Node_name(flow_test);
+  Node_name.set(s, "s");
+  Node_name.set(v1, "v1");
+  Node_name.set(v2, "v2");
+  Node_name.set(v3, "v3");
+  Node_name.set(v4, "v4");
+  Node_name.set(t, "t");
+  Node_name.set(z, "z");
+
+  Edge s_v1=flow_test.addEdge(s, v1);
+  Edge s_v2=flow_test.addEdge(s, v2);
+  Edge v1_v2=flow_test.addEdge(v1, v2);
+  Edge v2_v1=flow_test.addEdge(v2, v1);
+  Edge v1_v3=flow_test.addEdge(v1, v3);
+  Edge v3_v2=flow_test.addEdge(v3, v2);
+  Edge v2_v4=flow_test.addEdge(v2, v4);
+  Edge v4_v3=flow_test.addEdge(v4, v3);
+  Edge v3_t=flow_test.addEdge(v3, t);
+  Edge v4_t=flow_test.addEdge(v4, t);
+  Edge v3_v3=flow_test.addEdge(v3, v3);
+  Edge s_z=flow_test.addEdge(s, z);
+  //  Edge v2_s=flow_test.addEdge(v2, s);
+  
+
+
+   ListGraph::EdgeMap<int> cap(flow_test);  
+  cap.set(s_v1, 16);
+  cap.set(s_v2, 13);
+  cap.set(v1_v2, 10);
+  cap.set(v2_v1, 4);
+  cap.set(v1_v3, 12);
+  cap.set(v3_v2, 9);
+  cap.set(v2_v4, 14);
+  cap.set(v4_v3, 7);
+  cap.set(v3_t, 20);
+  cap.set(v4_t, 4);
+  cap.set(v3_v3, 4);
+  cap.set(s_z, 4);
+  //  cap.set(v2_s, 0);
+
+  */
+
+  //pelda 3, maxflowvalue=4
+  /*      Node s=flow_test.addNode();
+  Node v1=flow_test.addNode();
+  Node v2=flow_test.addNode();
+  Node t=flow_test.addNode();
+  Node w=flow_test.addNode();
+  
+  NodeMap<ListGraph, std::string> Node_name(flow_test);
+  Node_name.set(s, "s");
+  Node_name.set(v1, "v1");
+  Node_name.set(v2, "v2");
+  Node_name.set(t, "t");
+  Node_name.set(w, "w");
+
+  Edge s_v1=flow_test.addEdge(s, v1);
+  Edge v1_v2=flow_test.addEdge(v1, v2);
+  Edge v2_t=flow_test.addEdge(v2, t);
+  Edge v1_v1=flow_test.addEdge(v1, v1);
+  Edge s_w=flow_test.addEdge(s, w);
+
+
+  EdgeMap<ListGraph, int> cap(flow_test); 
+    
+  cap.set(s_v1, 16);
+  cap.set(v1_v2, 10);
+  cap.set(v2_t, 4);
+  cap.set(v1_v1, 3);
+  cap.set(s_w, 5);
+  */
+  
+
+
+  /*
+  std::cout << "Testing reverse_bfs..." << std::endl;
+  
+  reverse_bfs<ListGraph> bfs_test(flow_test, t);
+
+  bfs_test.run();
+
+  for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
+    std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
+    }
+
+  */
+
+
+  /*
+  std::cout << "Testing preflow_push_hl..." << std::endl;
+  
+  preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
+
+  preflow_push_test.run();
+
+  std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
+
+  std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
+
+   ListGraph::EdgeMap<int> flow=preflow_push_test.allflow();  
+  for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
+    std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
+    }
+
+  std::cout << "A minimum cut: " <<std::endl;  
+   ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
+
+  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
+      if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
+    }
+  
+  std::cout<<"\n\n"<<std::endl;
+
+
+
+
+  std::cout << "Testing preflow_push_max_flow..." << std::endl;
+ 
+  preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
+
+  max_flow_test.run();
+
+  std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
+
+  std::cout << "A minimum cut: " <<std::endl;  
+   ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
+
+  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
+    if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
+  }
+  
+  std::cout << std::endl <<std::endl;
+  */
+
+  return 0;
+}
+
+
+
+
+
+
+
+
+
diff -r bbd1db03f0fe -r e42f56e7ad93 src/work/jacint/edmonds.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/edmonds.h	Fri Apr 30 06:46:39 2004 +0000
@@ -0,0 +1,235 @@
+// -*- 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
+
+
+
+
diff -r bbd1db03f0fe -r e42f56e7ad93 src/work/jacint/makefile
--- a/src/work/jacint/makefile	Fri Apr 30 01:59:15 2004 +0000
+++ b/src/work/jacint/makefile	Fri Apr 30 06:46:39 2004 +0000
@@ -1,3 +1,3 @@
-BINARIES = preflow preflow_res_comp preflow_excess_test
+BINARIES = edmonds #preflow preflow_res_comp preflow_excess_test
 INCLUDEDIRS= -I../../include -I.. -I../{klao,marci,jacint,alpar,johanna,akos}
-include ../makefile
+include ../makefile