1.1 --- a/src/work/jacint/edmonds.h Wed May 05 17:51:56 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,235 +0,0 @@
1.4 -// -*- C++ -*-
1.5 -/*
1.6 -Kell meg a dual oldal
1.7 -esetleg az elejen moho matching kereses
1.8 -
1.9 - //baj van pos-sal: nem tudok vegigmaszni a halmazok elemein. De
1.10 - //pos-ra nem lenne szukseg ha unionfindban lenne egy element ami
1.11 - //true ha benne van false ha nincs
1.12 -
1.13 -MISI strukijahoz hasznalok:
1.14 -
1.15 -void addElement(b,a): b meg nem volt egy osztalyban sem, ezzel hozzaadjuk a osztalyahoz
1.16 -void insert(a): a meg nem volt egy osztalyban sem, ezzel egy uj egyelemu osztalyt alkot
1.17 -bool element(a): true ha benne van false ha nincs
1.18 -void erase(a)
1.19 -
1.20 -ez a 4 a vegso szetrobbantashoz es egyideju elemfelsorolashoz kell, mas megoldas is jo ehelyett:
1.21 -
1.22 -bool empty(int i): ures-e az i nevu osztaly
1.23 -int find(a)
1.24 -void pop(int i): egy fix elso elemet kitorol az i osztalybol
1.25 -T top(int i): visszad egy fix elso elemet
1.26 -
1.27 -unionfindba kene:
1.28 -bool element(a): true ha benne van false ha nincs (vagy 'bool empty')
1.29 -void split(a) (vagy clear)
1.30 -T rep(a): visszaadja a halmazanak reprezentanselemet, lehet operator()-val is
1.31 -void makeRep(a): a-t a sajat halmazanak reprezentansava teszi
1.32 -
1.33 -Szoljatok ha nem lehet valamelyiket hatekonyan
1.34 -*/
1.35 -
1.36 -#ifndef HUGO_EDMONDS_H
1.37 -#define HUGO_EDMONDS_H
1.38 -
1.39 -#include <queue>
1.40 -
1.41 -#include <invalid.h>
1.42 -#include <unionfind.h>
1.43 -
1.44 -namespace hugo {
1.45 -
1.46 - template <typename Graph>
1.47 - class Edmonds {
1.48 -
1.49 - typedef typename Graph::Node Node;
1.50 - typedef typename Graph::Edge Edge;
1.51 - typedef typename Graph::EdgeIt EdgeIt;
1.52 - typedef typename Graph::NodeIt NodeIt;
1.53 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.54 -
1.55 - typedef UnionFindEnum<Node, Graph::NodeMap > ufe;
1.56 -
1.57 - const Graph& G;
1.58 -
1.59 - public:
1.60 - Edmonds(Graph& _G) : G(_G) {}
1.61 -
1.62 -
1.63 - int run(std::vector<Edge> matching) {
1.64 -
1.65 - enum pos_enum{
1.66 - D=0,
1.67 - A=1,
1.68 - C=2
1.69 - };
1.70 - Graph::template NodeMap<pos_enum> pos(G,C);
1.71 -
1.72 - int p=0; //needed for path
1.73 -
1.74 - typename Graph::NodeMap<Node> mate(G,INVALID);
1.75 - for ( int i=0; i!=matching.size(); ++i ) {
1.76 - Node u=G.aNode(matching[i]);
1.77 - Node v=G.bNode(matching[i]);
1.78 - mate.set(u,v);
1.79 - mate.set(v,u);
1.80 - }
1.81 - matching.clear();
1.82 -
1.83 - typename Graph::NodeMap<Node> ear(G,INVALID);
1.84 - // a basepontok es a C-beliek earje szemet
1.85 -
1.86 - ufe::MapType blossom_base(G);
1.87 - ufe blossom(blossom_base);
1.88 - ufe::MapType tree_base(G);
1.89 - ufe tree(tree_base);
1.90 -
1.91 - NodeIt v;
1.92 - for(G.first(v); G.valid(v), G.next(v) ) {
1.93 -
1.94 - if ( pos[v]==C && mate[v]=INVALID ) {
1.95 -
1.96 - blossom.insert(v);
1.97 - tree.insert(v);
1.98 - pos.set(v,D);
1.99 -
1.100 - std::queue<Node> Q; //a vizsgalando csucsok sora
1.101 - Q.push(v);
1.102 -
1.103 - while ( !Q.empty() ) {
1.104 - Node x=Q.top();
1.105 - Q.pop();
1.106 -
1.107 - OutEdgeIt e;
1.108 - for( G.first(e); G.valid(e), G.next(e) ) {
1.109 - Node y=G.bNode(e);
1.110 -
1.111 - if ( pos[y]==D ) {
1.112 -
1.113 - if ( tree.find(x) != tree.find(y) ) { //augment
1.114 - augment(x, mate, ear, blossom, tree);
1.115 - augment(y, mate, ear, blossom, tree);
1.116 - mate.set(x)=y;
1.117 - mate.set(y)=x;
1.118 - goto increased;
1.119 - } else
1.120 - if ( blossom.find(x) != blossom.find(y) ) {
1.121 -
1.122 - typename Graph::NodeMap<int> path(G,0);
1.123 -
1.124 - ++p;
1.125 - Node b=blossom.find(x);
1.126 - path.set(b,p);
1.127 - while ( b!=INVALID ) {
1.128 - b=blossom.find(ear[mate[b]]);
1.129 - path.set(b,p);
1.130 - } //going till the root
1.131 -
1.132 - Node w=y;
1.133 - Node v=blossom.find(w);
1.134 - while ( path[v]!=p ) {
1.135 - Q.push(mate[v]);
1.136 - w=shrink_step(w,v,mate,ear,tree,blossom);
1.137 - v=blossom.find(w);
1.138 - }
1.139 - //now v is the base of the first common ancestor
1.140 -
1.141 - w=x;
1.142 - Node z=blossom.find(w);
1.143 - while ( z!=v ) {
1.144 - Q.push(mate[z]);
1.145 - w=shrink_step(w,z,mate,ear,tree,blossom);
1.146 - z=blossom.find(w);
1.147 - }
1.148 -
1.149 - ear.set(x,y);
1.150 - ear.set(y,x);
1.151 -
1.152 - blossom.makeRep(v);
1.153 - }
1.154 - } else if ( pos[y] == C )
1.155 -
1.156 - if ( mate[y]!=INVALID ) { //grow
1.157 - ear.set(y,x);
1.158 - Node w=mate(y);
1.159 - blossom.insert(w);
1.160 - tree.insert(w);
1.161 - tree.join(y,x);
1.162 - tree.join(w,x);
1.163 - Q.push(w);
1.164 - } else {
1.165 - augment(x, mate, ear, blossom, tree);
1.166 - mate.set(x)=y;
1.167 - mate.set(y)=x;
1.168 - goto increased;
1.169 - }
1.170 - }
1.171 - }
1.172 - increased: //Misi, warningol, hogy nincs utasitas!
1.173 - }
1.174 - }
1.175 -
1.176 - int s=0;
1.177 - NodeIt v;
1.178 - for(G.first(v); G.valid(v), G.next(v) )
1.179 - if ( mate[v]!=INVALID ) ++s;
1.180 -
1.181 - return (int)(s/2);
1.182 -
1.183 - //egyelore nem ad semmit vissza
1.184 -
1.185 - }
1.186 -
1.187 -
1.188 - void augment(const Node x, typename Graph::NodeMap<Node>& mate,
1.189 - typename Graph::NodeMap<Node>& ear,
1.190 - ufe& blossom, ufe& tree) {
1.191 - Node v=mate[x];
1.192 - while ( v!=INVALID ) {
1.193 - Node u=ear[v];
1.194 - mate.set(v,u);
1.195 - Node tmp=v;
1.196 - v=mate[u];
1.197 - mate.set(u,tmp);
1.198 - }
1.199 - //FIXME, blossom szetszed
1.200 - tree.eraseClass(x);
1.201 - }
1.202 -
1.203 -
1.204 - Node shrink_step(const Node z, const Node v, typename Graph::NodeMap<Node>& mate,
1.205 - typename Graph::NodeMap<Node>& ear,
1.206 - ufe& blossom, ufe& tree) {
1.207 - if ( z!=v ) {
1.208 - Node t=z;
1.209 - Node u;
1.210 - while ( t!=v ) {
1.211 - u=mate[t];
1.212 - t=ear[u];
1.213 - }
1.214 - ear.set(v,u);
1.215 - }
1.216 -
1.217 - Node u=mate[v];
1.218 - Node w=ear[u];
1.219 - tree.erase(u);
1.220 - tree.erase(v);
1.221 - blossom.insert(u);
1.222 - blossom.join(u,w);
1.223 - blossom.join(v,w);
1.224 - ear.set(w,u);
1.225 -
1.226 - return w;
1.227 - }
1.228 -
1.229 -
1.230 - };
1.231 -
1.232 -} //namespace hugo
1.233 -
1.234 -#endif //EDMONDS_H
1.235 -
1.236 -
1.237 -
1.238 -