1.1 --- a/src/work/edmonds_karp.h Wed Mar 17 17:04:41 2004 +0000
1.2 +++ b/src/work/edmonds_karp.h Wed Mar 17 18:18:26 2004 +0000
1.3 @@ -551,10 +551,11 @@
1.4 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.5 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.6 typedef typename AugGraph::Edge AugEdge;
1.7 + typename Graph::NodeMap<int> used; //0
1.8
1.9 public:
1.10 MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
1.11 - G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
1.12 + G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
1.13 bool augmentOnShortestPath() {
1.14 AugGraph res_graph(*G, *flow, *capacity);
1.15 bool _augment=false;
1.16 @@ -563,14 +564,14 @@
1.17 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
1.18 typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.19 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.20 - if (S->get(s)) {
1.21 - Number u=0;
1.22 - for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.23 - u+=flow->get(e);
1.24 - if (u<1) {
1.25 + if ((S->get(s)) && (used.get(s)<1) ) {
1.26 + //Number u=0;
1.27 + //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.28 + //u+=flow->get(e);
1.29 + //if (u<1) {
1.30 res_bfs.pushAndSetReached(s);
1.31 pred.set(s, AugEdge(INVALID));
1.32 - }
1.33 + //}
1.34 }
1.35 }
1.36
1.37 @@ -590,14 +591,14 @@
1.38 free.set(w, res_graph.free(e));
1.39 }
1.40 n=res_graph.head(e);
1.41 - if (T->get(n)) {
1.42 - Number u=0;
1.43 - for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.44 - u+=flow->get(f);
1.45 - if (u<1) {
1.46 + if (T->get(n) && (used.get(n)<1) ) {
1.47 + //Number u=0;
1.48 + //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.49 + //u+=flow->get(f);
1.50 + //if (u<1) {
1.51 _augment=true;
1.52 break;
1.53 - }
1.54 + //}
1.55 }
1.56 }
1.57
1.58 @@ -606,12 +607,14 @@
1.59
1.60 if (_augment) {
1.61 //Node n=t;
1.62 + used.set(n, 1); //mind2 vegen jav
1.63 Number augment_value=free.get(n);
1.64 while (res_graph.valid(pred.get(n))) {
1.65 AugEdge e=pred.get(n);
1.66 res_graph.augment(e, augment_value);
1.67 n=res_graph.tail(e);
1.68 }
1.69 + used.set(n, 1); //mind2 vegen jav
1.70 }
1.71
1.72 return _augment;
2.1 --- a/src/work/marci/leda_graph_wrapper.h Wed Mar 17 17:04:41 2004 +0000
2.2 +++ b/src/work/marci/leda_graph_wrapper.h Wed Mar 17 18:18:26 2004 +0000
2.3 @@ -70,6 +70,7 @@
2.4 //Node(const Node &) {}
2.5 bool operator==(Node n) const { return _n==n._n; } //FIXME
2.6 bool operator!=(Node n) const { return _n!=n._n; } //FIXME
2.7 + operator leda_node () { return _n; }
2.8 };
2.9
2.10 /// This iterator goes through each node.
2.11 @@ -100,7 +101,8 @@
2.12 Edge(Invalid) : _e(0) {}
2.13 //Edge(const Edge &) {}
2.14 bool operator==(Edge e) const { return _e==e._e; } //FIXME
2.15 - bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
2.16 + bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
2.17 + operator leda_edge () { return _e; }
2.18 };
2.19
2.20 /// This iterator goes trought the outgoing edges of a certain graph.
3.1 --- a/src/work/marci/max_bipartite_matching_demo.cc Wed Mar 17 17:04:41 2004 +0000
3.2 +++ b/src/work/marci/max_bipartite_matching_demo.cc Wed Mar 17 18:18:26 2004 +0000
3.3 @@ -91,12 +91,13 @@
3.4 // G.addEdge(s_nodes[2], t_nodes[4-4]);
3.5 // G.addEdge(s_nodes[3], t_nodes[4-4]);
3.6
3.7 -
3.8 + leda_list<leda_node> A;
3.9 + leda_list<leda_node> B;
3.10 Graph::NodeMap<bool> s_map(G); //false
3.11 Graph::NodeMap<bool> t_map(G); //false
3.12
3.13 - for(int i=0; i<a; ++i) s_map.set(s_nodes[i], true);
3.14 - for(int i=0; i<b; ++i) t_map.set(t_nodes[i], true);
3.15 + for(int i=0; i<a; ++i) { s_map.set(s_nodes[i], true); A+=s_nodes[i]; }
3.16 + for(int i=0; i<b; ++i) { t_map.set(t_nodes[i], true); B+=t_nodes[i]; }
3.17
3.18 // cout << "bfs and dfs iterator demo on the directed graph" << endl;
3.19 // for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
3.20 @@ -112,7 +113,7 @@
3.21
3.22
3.23 {
3.24 - std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl;
3.25 + std::cout << "on-the-fly max bipartite matching (Edmonds-Karp) demo on wrapped leda graph..." << std::endl;
3.26 Graph::EdgeMap<int> flow(G); //0 flow
3.27 Graph::EdgeMap<int> cap(G, 1);
3.28
3.29 @@ -144,51 +145,54 @@
3.30 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.31 }
3.32
3.33 - {
3.34 - std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl;
3.35 - Graph::EdgeMap<int> flow(G); //0 flow
3.36 - Graph::EdgeMap<int> cap(G, 1);
3.37 +// {
3.38 +// std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl;
3.39 +// Graph::EdgeMap<int> flow(G); //0 flow
3.40 +// Graph::EdgeMap<int> cap(G, 1);
3.41
3.42 - Timer ts;
3.43 - ts.reset();
3.44 +// Timer ts;
3.45 +// ts.reset();
3.46
3.47 - MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
3.48 - int i=0;
3.49 - while (max_flow_test.augmentOnBlockingFlow2()) {
3.50 -// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
3.51 -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
3.52 -// std::cout<<std::endl;
3.53 - ++i;
3.54 - }
3.55 +// MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
3.56 +// int i=0;
3.57 +// while (max_flow_test.augmentOnBlockingFlow2()) {
3.58 +// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
3.59 +// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
3.60 +// // std::cout<<std::endl;
3.61 +// ++i;
3.62 +// }
3.63
3.64 -// std::cout << "maximum matching: "<< std::endl;
3.65 -// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
3.66 -// if (flow.get(e))
3.67 -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
3.68 -// std::cout<<std::endl;
3.69 -// std::cout << "edges which are not in this maximum matching: "<< std::endl;
3.70 -// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
3.71 -// if (!flow.get(e))
3.72 -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
3.73 -// std::cout<<std::endl;
3.74 +// // std::cout << "maximum matching: "<< std::endl;
3.75 +// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
3.76 +// // if (flow.get(e))
3.77 +// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
3.78 +// // std::cout<<std::endl;
3.79 +// // std::cout << "edges which are not in this maximum matching: "<< std::endl;
3.80 +// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
3.81 +// // if (!flow.get(e))
3.82 +// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
3.83 +// // std::cout<<std::endl;
3.84
3.85 - std::cout << "elapsed time: " << ts << std::endl;
3.86 - std::cout << "number of augmentation phases: " << i << std::endl;
3.87 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.88 - }
3.89 +// std::cout << "elapsed time: " << ts << std::endl;
3.90 +// std::cout << "number of augmentation phases: " << i << std::endl;
3.91 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.92 +// }
3.93
3.94 {
3.95 std::cout << "max bipartite matching (LEDA)..." << std::endl;
3.96 //Graph::EdgeMap<int> flow(G); //0 flow
3.97 //Graph::EdgeMap<int> cap(G, 1);
3.98
3.99 + leda_node_array<bool> NC(g);
3.100 +
3.101 Timer ts;
3.102 ts.reset();
3.103
3.104 //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
3.105 //int i=0;
3.106 //while (max_flow_test.augmentOnShortestPath()) { ++i; }
3.107 -
3.108 +
3.109 + //leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING_HK(g, A, B, NC, false);
3.110 leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);
3.111
3.112