1.1 --- a/src/work/jacint/edmonds.cc Wed May 05 17:51:56 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,220 +0,0 @@
1.4 -#include <iostream>
1.5 -#include <vector>
1.6 -#include <string>
1.7 -
1.8 -#include <list_graph.h>
1.9 -#include <edmonds.h>
1.10 -
1.11 -using namespace hugo;
1.12 -
1.13 -int main (int, char*[])
1.14 -{
1.15 - typedef ListGraph::NodeIt NodeIt;
1.16 - typedef ListGraph::EdgeIt EdgeIt;
1.17 - typedef ListGraph::Node Node;
1.18 - typedef ListGraph::Edge Edge;
1.19 - typedef ListGraph::OutEdgeIt OutEdgeIt;
1.20 - typedef ListGraph::InEdgeIt InEdgeIt;
1.21 -
1.22 - ListGraph flow_test;
1.23 -
1.24 - /* //Ahuja könyv példája, maxflowvalue=13*/
1.25 - Node s=flow_test.addNode();
1.26 - Node v1=flow_test.addNode();
1.27 - Node v2=flow_test.addNode();
1.28 - Node v3=flow_test.addNode();
1.29 - Node v4=flow_test.addNode();
1.30 - Node v5=flow_test.addNode();
1.31 - Node t=flow_test.addNode();
1.32 -
1.33 - ListGraph::NodeMap<std::string> Node_name(flow_test);
1.34 - Node_name.set(s, "s");
1.35 - Node_name.set(v1, "v1");
1.36 - Node_name.set(v2, "v2");
1.37 - Node_name.set(v3, "v3");
1.38 - Node_name.set(v4, "v4");
1.39 - Node_name.set(v5, "v5");
1.40 - Node_name.set(t, "t");
1.41 -
1.42 - Edge s_v1=flow_test.addEdge(s, v1);
1.43 - Edge s_v2=flow_test.addEdge(s, v2);
1.44 - Edge s_v3=flow_test.addEdge(s, v3);
1.45 - Edge v2_v4=flow_test.addEdge(v2, v4);
1.46 - Edge v2_v5=flow_test.addEdge(v2, v5);
1.47 - Edge v3_v5=flow_test.addEdge(v3, v5);
1.48 - Edge v4_t=flow_test.addEdge(v4, t);
1.49 - Edge v5_t=flow_test.addEdge(v5, t);
1.50 - Edge v2_s=flow_test.addEdge(v2, s);
1.51 -
1.52 - ListGraph::EdgeMap<int> cap(flow_test);
1.53 - cap.set(s_v1, 0);
1.54 - cap.set(s_v2, 10);
1.55 - cap.set(s_v3, 10);
1.56 - cap.set(v2_v4, 5);
1.57 - cap.set(v2_v5, 8);
1.58 - cap.set(v3_v5, 5);
1.59 - cap.set(v4_t, 8);
1.60 - cap.set(v5_t, 8);
1.61 - cap.set(v2_s, 0);
1.62 -
1.63 -
1.64 - Edmonds<ListGraph> edmonds(flow_test);
1.65 - std::vector<Edge> matching(0);
1.66 - std::cout<< edmonds.run(matching);
1.67 -
1.68 -
1.69 - /* //Marci példája, maxflowvalue=23
1.70 - Node s=flow_test.addNode();
1.71 - Node v1=flow_test.addNode();
1.72 - Node v2=flow_test.addNode();
1.73 - Node v3=flow_test.addNode();
1.74 - Node v4=flow_test.addNode();
1.75 - Node t=flow_test.addNode();
1.76 - Node z=flow_test.addNode();
1.77 -
1.78 -
1.79 - ListGraph::NodeMap<std::string> Node_name(flow_test);
1.80 - Node_name.set(s, "s");
1.81 - Node_name.set(v1, "v1");
1.82 - Node_name.set(v2, "v2");
1.83 - Node_name.set(v3, "v3");
1.84 - Node_name.set(v4, "v4");
1.85 - Node_name.set(t, "t");
1.86 - Node_name.set(z, "z");
1.87 -
1.88 - Edge s_v1=flow_test.addEdge(s, v1);
1.89 - Edge s_v2=flow_test.addEdge(s, v2);
1.90 - Edge v1_v2=flow_test.addEdge(v1, v2);
1.91 - Edge v2_v1=flow_test.addEdge(v2, v1);
1.92 - Edge v1_v3=flow_test.addEdge(v1, v3);
1.93 - Edge v3_v2=flow_test.addEdge(v3, v2);
1.94 - Edge v2_v4=flow_test.addEdge(v2, v4);
1.95 - Edge v4_v3=flow_test.addEdge(v4, v3);
1.96 - Edge v3_t=flow_test.addEdge(v3, t);
1.97 - Edge v4_t=flow_test.addEdge(v4, t);
1.98 - Edge v3_v3=flow_test.addEdge(v3, v3);
1.99 - Edge s_z=flow_test.addEdge(s, z);
1.100 - // Edge v2_s=flow_test.addEdge(v2, s);
1.101 -
1.102 -
1.103 -
1.104 - ListGraph::EdgeMap<int> cap(flow_test);
1.105 - cap.set(s_v1, 16);
1.106 - cap.set(s_v2, 13);
1.107 - cap.set(v1_v2, 10);
1.108 - cap.set(v2_v1, 4);
1.109 - cap.set(v1_v3, 12);
1.110 - cap.set(v3_v2, 9);
1.111 - cap.set(v2_v4, 14);
1.112 - cap.set(v4_v3, 7);
1.113 - cap.set(v3_t, 20);
1.114 - cap.set(v4_t, 4);
1.115 - cap.set(v3_v3, 4);
1.116 - cap.set(s_z, 4);
1.117 - // cap.set(v2_s, 0);
1.118 -
1.119 - */
1.120 -
1.121 - //pelda 3, maxflowvalue=4
1.122 - /* Node s=flow_test.addNode();
1.123 - Node v1=flow_test.addNode();
1.124 - Node v2=flow_test.addNode();
1.125 - Node t=flow_test.addNode();
1.126 - Node w=flow_test.addNode();
1.127 -
1.128 - NodeMap<ListGraph, std::string> Node_name(flow_test);
1.129 - Node_name.set(s, "s");
1.130 - Node_name.set(v1, "v1");
1.131 - Node_name.set(v2, "v2");
1.132 - Node_name.set(t, "t");
1.133 - Node_name.set(w, "w");
1.134 -
1.135 - Edge s_v1=flow_test.addEdge(s, v1);
1.136 - Edge v1_v2=flow_test.addEdge(v1, v2);
1.137 - Edge v2_t=flow_test.addEdge(v2, t);
1.138 - Edge v1_v1=flow_test.addEdge(v1, v1);
1.139 - Edge s_w=flow_test.addEdge(s, w);
1.140 -
1.141 -
1.142 - EdgeMap<ListGraph, int> cap(flow_test);
1.143 -
1.144 - cap.set(s_v1, 16);
1.145 - cap.set(v1_v2, 10);
1.146 - cap.set(v2_t, 4);
1.147 - cap.set(v1_v1, 3);
1.148 - cap.set(s_w, 5);
1.149 - */
1.150 -
1.151 -
1.152 -
1.153 - /*
1.154 - std::cout << "Testing reverse_bfs..." << std::endl;
1.155 -
1.156 - reverse_bfs<ListGraph> bfs_test(flow_test, t);
1.157 -
1.158 - bfs_test.run();
1.159 -
1.160 - for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
1.161 - std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
1.162 - }
1.163 -
1.164 - */
1.165 -
1.166 -
1.167 - /*
1.168 - std::cout << "Testing preflow_push_hl..." << std::endl;
1.169 -
1.170 - preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
1.171 -
1.172 - preflow_push_test.run();
1.173 -
1.174 - std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
1.175 -
1.176 - std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
1.177 -
1.178 - ListGraph::EdgeMap<int> flow=preflow_push_test.allflow();
1.179 - for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
1.180 - std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
1.181 - }
1.182 -
1.183 - std::cout << "A minimum cut: " <<std::endl;
1.184 - ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
1.185 -
1.186 - for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
1.187 - if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
1.188 - }
1.189 -
1.190 - std::cout<<"\n\n"<<std::endl;
1.191 -
1.192 -
1.193 -
1.194 -
1.195 - std::cout << "Testing preflow_push_max_flow..." << std::endl;
1.196 -
1.197 - preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
1.198 -
1.199 - max_flow_test.run();
1.200 -
1.201 - std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
1.202 -
1.203 - std::cout << "A minimum cut: " <<std::endl;
1.204 - ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
1.205 -
1.206 - for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
1.207 - if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
1.208 - }
1.209 -
1.210 - std::cout << std::endl <<std::endl;
1.211 - */
1.212 -
1.213 - return 0;
1.214 -}
1.215 -
1.216 -
1.217 -
1.218 -
1.219 -
1.220 -
1.221 -
1.222 -
1.223 -
2.1 --- a/src/work/jacint/edmonds.h Wed May 05 17:51:56 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,235 +0,0 @@
2.4 -// -*- C++ -*-
2.5 -/*
2.6 -Kell meg a dual oldal
2.7 -esetleg az elejen moho matching kereses
2.8 -
2.9 - //baj van pos-sal: nem tudok vegigmaszni a halmazok elemein. De
2.10 - //pos-ra nem lenne szukseg ha unionfindban lenne egy element ami
2.11 - //true ha benne van false ha nincs
2.12 -
2.13 -MISI strukijahoz hasznalok:
2.14 -
2.15 -void addElement(b,a): b meg nem volt egy osztalyban sem, ezzel hozzaadjuk a osztalyahoz
2.16 -void insert(a): a meg nem volt egy osztalyban sem, ezzel egy uj egyelemu osztalyt alkot
2.17 -bool element(a): true ha benne van false ha nincs
2.18 -void erase(a)
2.19 -
2.20 -ez a 4 a vegso szetrobbantashoz es egyideju elemfelsorolashoz kell, mas megoldas is jo ehelyett:
2.21 -
2.22 -bool empty(int i): ures-e az i nevu osztaly
2.23 -int find(a)
2.24 -void pop(int i): egy fix elso elemet kitorol az i osztalybol
2.25 -T top(int i): visszad egy fix elso elemet
2.26 -
2.27 -unionfindba kene:
2.28 -bool element(a): true ha benne van false ha nincs (vagy 'bool empty')
2.29 -void split(a) (vagy clear)
2.30 -T rep(a): visszaadja a halmazanak reprezentanselemet, lehet operator()-val is
2.31 -void makeRep(a): a-t a sajat halmazanak reprezentansava teszi
2.32 -
2.33 -Szoljatok ha nem lehet valamelyiket hatekonyan
2.34 -*/
2.35 -
2.36 -#ifndef HUGO_EDMONDS_H
2.37 -#define HUGO_EDMONDS_H
2.38 -
2.39 -#include <queue>
2.40 -
2.41 -#include <invalid.h>
2.42 -#include <unionfind.h>
2.43 -
2.44 -namespace hugo {
2.45 -
2.46 - template <typename Graph>
2.47 - class Edmonds {
2.48 -
2.49 - typedef typename Graph::Node Node;
2.50 - typedef typename Graph::Edge Edge;
2.51 - typedef typename Graph::EdgeIt EdgeIt;
2.52 - typedef typename Graph::NodeIt NodeIt;
2.53 - typedef typename Graph::OutEdgeIt OutEdgeIt;
2.54 -
2.55 - typedef UnionFindEnum<Node, Graph::NodeMap > ufe;
2.56 -
2.57 - const Graph& G;
2.58 -
2.59 - public:
2.60 - Edmonds(Graph& _G) : G(_G) {}
2.61 -
2.62 -
2.63 - int run(std::vector<Edge> matching) {
2.64 -
2.65 - enum pos_enum{
2.66 - D=0,
2.67 - A=1,
2.68 - C=2
2.69 - };
2.70 - Graph::template NodeMap<pos_enum> pos(G,C);
2.71 -
2.72 - int p=0; //needed for path
2.73 -
2.74 - typename Graph::NodeMap<Node> mate(G,INVALID);
2.75 - for ( int i=0; i!=matching.size(); ++i ) {
2.76 - Node u=G.aNode(matching[i]);
2.77 - Node v=G.bNode(matching[i]);
2.78 - mate.set(u,v);
2.79 - mate.set(v,u);
2.80 - }
2.81 - matching.clear();
2.82 -
2.83 - typename Graph::NodeMap<Node> ear(G,INVALID);
2.84 - // a basepontok es a C-beliek earje szemet
2.85 -
2.86 - ufe::MapType blossom_base(G);
2.87 - ufe blossom(blossom_base);
2.88 - ufe::MapType tree_base(G);
2.89 - ufe tree(tree_base);
2.90 -
2.91 - NodeIt v;
2.92 - for(G.first(v); G.valid(v), G.next(v) ) {
2.93 -
2.94 - if ( pos[v]==C && mate[v]=INVALID ) {
2.95 -
2.96 - blossom.insert(v);
2.97 - tree.insert(v);
2.98 - pos.set(v,D);
2.99 -
2.100 - std::queue<Node> Q; //a vizsgalando csucsok sora
2.101 - Q.push(v);
2.102 -
2.103 - while ( !Q.empty() ) {
2.104 - Node x=Q.top();
2.105 - Q.pop();
2.106 -
2.107 - OutEdgeIt e;
2.108 - for( G.first(e); G.valid(e), G.next(e) ) {
2.109 - Node y=G.bNode(e);
2.110 -
2.111 - if ( pos[y]==D ) {
2.112 -
2.113 - if ( tree.find(x) != tree.find(y) ) { //augment
2.114 - augment(x, mate, ear, blossom, tree);
2.115 - augment(y, mate, ear, blossom, tree);
2.116 - mate.set(x)=y;
2.117 - mate.set(y)=x;
2.118 - goto increased;
2.119 - } else
2.120 - if ( blossom.find(x) != blossom.find(y) ) {
2.121 -
2.122 - typename Graph::NodeMap<int> path(G,0);
2.123 -
2.124 - ++p;
2.125 - Node b=blossom.find(x);
2.126 - path.set(b,p);
2.127 - while ( b!=INVALID ) {
2.128 - b=blossom.find(ear[mate[b]]);
2.129 - path.set(b,p);
2.130 - } //going till the root
2.131 -
2.132 - Node w=y;
2.133 - Node v=blossom.find(w);
2.134 - while ( path[v]!=p ) {
2.135 - Q.push(mate[v]);
2.136 - w=shrink_step(w,v,mate,ear,tree,blossom);
2.137 - v=blossom.find(w);
2.138 - }
2.139 - //now v is the base of the first common ancestor
2.140 -
2.141 - w=x;
2.142 - Node z=blossom.find(w);
2.143 - while ( z!=v ) {
2.144 - Q.push(mate[z]);
2.145 - w=shrink_step(w,z,mate,ear,tree,blossom);
2.146 - z=blossom.find(w);
2.147 - }
2.148 -
2.149 - ear.set(x,y);
2.150 - ear.set(y,x);
2.151 -
2.152 - blossom.makeRep(v);
2.153 - }
2.154 - } else if ( pos[y] == C )
2.155 -
2.156 - if ( mate[y]!=INVALID ) { //grow
2.157 - ear.set(y,x);
2.158 - Node w=mate(y);
2.159 - blossom.insert(w);
2.160 - tree.insert(w);
2.161 - tree.join(y,x);
2.162 - tree.join(w,x);
2.163 - Q.push(w);
2.164 - } else {
2.165 - augment(x, mate, ear, blossom, tree);
2.166 - mate.set(x)=y;
2.167 - mate.set(y)=x;
2.168 - goto increased;
2.169 - }
2.170 - }
2.171 - }
2.172 - increased: //Misi, warningol, hogy nincs utasitas!
2.173 - }
2.174 - }
2.175 -
2.176 - int s=0;
2.177 - NodeIt v;
2.178 - for(G.first(v); G.valid(v), G.next(v) )
2.179 - if ( mate[v]!=INVALID ) ++s;
2.180 -
2.181 - return (int)(s/2);
2.182 -
2.183 - //egyelore nem ad semmit vissza
2.184 -
2.185 - }
2.186 -
2.187 -
2.188 - void augment(const Node x, typename Graph::NodeMap<Node>& mate,
2.189 - typename Graph::NodeMap<Node>& ear,
2.190 - ufe& blossom, ufe& tree) {
2.191 - Node v=mate[x];
2.192 - while ( v!=INVALID ) {
2.193 - Node u=ear[v];
2.194 - mate.set(v,u);
2.195 - Node tmp=v;
2.196 - v=mate[u];
2.197 - mate.set(u,tmp);
2.198 - }
2.199 - //FIXME, blossom szetszed
2.200 - tree.eraseClass(x);
2.201 - }
2.202 -
2.203 -
2.204 - Node shrink_step(const Node z, const Node v, typename Graph::NodeMap<Node>& mate,
2.205 - typename Graph::NodeMap<Node>& ear,
2.206 - ufe& blossom, ufe& tree) {
2.207 - if ( z!=v ) {
2.208 - Node t=z;
2.209 - Node u;
2.210 - while ( t!=v ) {
2.211 - u=mate[t];
2.212 - t=ear[u];
2.213 - }
2.214 - ear.set(v,u);
2.215 - }
2.216 -
2.217 - Node u=mate[v];
2.218 - Node w=ear[u];
2.219 - tree.erase(u);
2.220 - tree.erase(v);
2.221 - blossom.insert(u);
2.222 - blossom.join(u,w);
2.223 - blossom.join(v,w);
2.224 - ear.set(w,u);
2.225 -
2.226 - return w;
2.227 - }
2.228 -
2.229 -
2.230 - };
2.231 -
2.232 -} //namespace hugo
2.233 -
2.234 -#endif //EDMONDS_H
2.235 -
2.236 -
2.237 -
2.238 -