1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/edmonds.cc Fri Apr 30 06:46:39 2004 +0000
1.3 @@ -0,0 +1,220 @@
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 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/jacint/edmonds.h Fri Apr 30 06:46:39 2004 +0000
2.3 @@ -0,0 +1,235 @@
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 +
3.1 --- a/src/work/jacint/makefile Fri Apr 30 01:59:15 2004 +0000
3.2 +++ b/src/work/jacint/makefile Fri Apr 30 06:46:39 2004 +0000
3.3 @@ -1,3 +1,3 @@
3.4 -BINARIES = preflow preflow_res_comp preflow_excess_test
3.5 +BINARIES = edmonds #preflow preflow_res_comp preflow_excess_test
3.6 INCLUDEDIRS= -I../../include -I.. -I../{klao,marci,jacint,alpar,johanna,akos}
3.7 -include ../makefile
3.8 +include ../makefile