COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/edmonds.h @ 524:bd8109f8e2fa

Last change on this file since 524:bd8109f8e2fa was 494:e42f56e7ad93, checked in by jacint, 20 years ago

Felkesz kod!

File size: 5.0 KB
Line 
1// -*- C++ -*-
2/*
3Kell meg a dual oldal
4esetleg az elejen moho matching kereses
5
6  //baj van pos-sal: nem tudok vegigmaszni a halmazok elemein. De
7  //pos-ra nem lenne szukseg ha unionfindban lenne egy element ami
8  //true ha benne van false ha nincs
9
10MISI strukijahoz hasznalok:
11
12void addElement(b,a): b meg nem volt egy osztalyban sem, ezzel hozzaadjuk a osztalyahoz
13void insert(a): a meg nem volt egy osztalyban sem, ezzel egy uj egyelemu osztalyt alkot
14bool element(a): true ha benne van false ha nincs
15void erase(a)
16
17ez a 4 a vegso szetrobbantashoz es egyideju elemfelsorolashoz kell, mas megoldas is jo ehelyett:
18
19bool empty(int i): ures-e az i nevu osztaly
20int find(a)
21void pop(int i): egy fix elso elemet kitorol az i osztalybol
22T top(int i): visszad egy fix elso elemet
23
24unionfindba kene:
25bool element(a): true ha benne van false ha nincs  (vagy 'bool empty')
26void split(a) (vagy clear)
27T rep(a): visszaadja a halmazanak reprezentanselemet, lehet operator()-val is
28void makeRep(a): a-t a sajat halmazanak reprezentansava teszi
29
30Szoljatok ha nem lehet valamelyiket hatekonyan
31*/
32
33#ifndef HUGO_EDMONDS_H
34#define HUGO_EDMONDS_H
35
36#include <queue>
37
38#include <invalid.h>
39#include <unionfind.h>
40
41namespace hugo {
42
43  template <typename Graph>
44  class Edmonds {
45   
46    typedef typename Graph::Node Node;
47    typedef typename Graph::Edge Edge;
48    typedef typename Graph::EdgeIt EdgeIt;
49    typedef typename Graph::NodeIt NodeIt;
50    typedef typename Graph::OutEdgeIt OutEdgeIt;
51
52    typedef UnionFindEnum<Node, Graph::NodeMap > ufe;
53           
54    const Graph& G;
55
56  public:
57    Edmonds(Graph& _G) : G(_G) {}
58   
59   
60    int run(std::vector<Edge> matching) {
61
62      enum pos_enum{
63        D=0,
64        A=1,
65        C=2
66      };
67      Graph::template NodeMap<pos_enum> pos(G,C);
68
69      int p=0;   //needed for path
70
71      typename Graph::NodeMap<Node> mate(G,INVALID);
72      for ( int i=0; i!=matching.size(); ++i ) {
73        Node u=G.aNode(matching[i]);
74        Node v=G.bNode(matching[i]);
75        mate.set(u,v);
76        mate.set(v,u);
77      }
78      matching.clear();
79
80      typename Graph::NodeMap<Node> ear(G,INVALID);   
81      // a basepontok es a C-beliek earje szemet
82
83      ufe::MapType blossom_base(G);
84      ufe blossom(blossom_base);
85      ufe::MapType tree_base(G);
86      ufe tree(tree_base);
87
88      NodeIt v;
89      for(G.first(v); G.valid(v), G.next(v) ) {
90       
91        if ( pos[v]==C && mate[v]=INVALID ) {
92         
93          blossom.insert(v);
94          tree.insert(v);
95          pos.set(v,D);
96
97          std::queue<Node> Q;   //a vizsgalando csucsok sora
98          Q.push(v); 
99
100          while ( !Q.empty() ) {
101            Node x=Q.top();
102            Q.pop();
103           
104            OutEdgeIt e;
105            for( G.first(e); G.valid(e), G.next(e) ) {
106              Node y=G.bNode(e);
107
108              if ( pos[y]==D ) {
109
110                if ( tree.find(x) != tree.find(y) ) {  //augment
111                  augment(x, mate, ear, blossom, tree);
112                  augment(y, mate, ear, blossom, tree);
113                  mate.set(x)=y;
114                  mate.set(y)=x;
115                  goto increased;
116                } else
117                  if ( blossom.find(x) != blossom.find(y) ) {
118
119                    typename Graph::NodeMap<int> path(G,0);
120
121                    ++p;
122                    Node b=blossom.find(x);
123                    path.set(b,p);
124                    while ( b!=INVALID ) {
125                      b=blossom.find(ear[mate[b]]);
126                      path.set(b,p);
127                    }          //going till the root
128       
129                    Node w=y;
130                    Node v=blossom.find(w);
131                    while ( path[v]!=p ) {                   
132                      Q.push(mate[v]);
133                      w=shrink_step(w,v,mate,ear,tree,blossom);
134                      v=blossom.find(w);
135                    }
136                    //now v is the base of the first common ancestor
137
138                    w=x;
139                    Node z=blossom.find(w);
140                    while ( z!=v ) {
141                      Q.push(mate[z]);
142                      w=shrink_step(w,z,mate,ear,tree,blossom);
143                      z=blossom.find(w);
144                    }
145
146                    ear.set(x,y);
147                    ear.set(y,x);
148
149                    blossom.makeRep(v);
150                  }
151              } else if ( pos[y] == C )
152               
153                if ( mate[y]!=INVALID ) {       //grow
154                  ear.set(y,x);
155                  Node w=mate(y);
156                  blossom.insert(w);
157                  tree.insert(w);
158                  tree.join(y,x); 
159                  tree.join(w,x); 
160                  Q.push(w);
161                } else {
162                  augment(x, mate, ear, blossom, tree);
163                  mate.set(x)=y;
164                  mate.set(y)=x;
165                  goto increased;
166                }
167            }
168          }
169        increased:  //Misi, warningol, hogy nincs utasitas!
170        }
171      }
172
173      int s=0;
174      NodeIt v;
175      for(G.first(v); G.valid(v), G.next(v) )
176        if ( mate[v]!=INVALID ) ++s;
177       
178      return (int)(s/2);
179
180      //egyelore nem ad semmit vissza
181     
182    }
183 
184
185    void augment(const Node x, typename Graph::NodeMap<Node>& mate,
186                 typename Graph::NodeMap<Node>& ear,
187                 ufe& blossom, ufe& tree) {
188      Node v=mate[x];
189      while ( v!=INVALID ) {
190        Node u=ear[v];
191        mate.set(v,u);
192        Node tmp=v;
193        v=mate[u];
194        mate.set(u,tmp);
195      }
196      //FIXME, blossom szetszed
197      tree.eraseClass(x);
198    }
199
200
201    Node shrink_step(const Node z, const Node v, typename Graph::NodeMap<Node>& mate,
202                     typename Graph::NodeMap<Node>& ear,
203                     ufe& blossom, ufe& tree) { 
204      if ( z!=v ) {
205        Node t=z;
206        Node u;
207        while ( t!=v ) {
208          u=mate[t];
209          t=ear[u];
210        }
211        ear.set(v,u);
212      }
213
214      Node u=mate[v];
215      Node w=ear[u];
216      tree.erase(u);
217      tree.erase(v);
218      blossom.insert(u);
219      blossom.join(u,w);
220      blossom.join(v,w);
221      ear.set(w,u);     
222
223      return w;
224    }
225
226
227  };
228
229} //namespace hugo
230
231#endif //EDMONDS_H
232
233
234
235
Note: See TracBrowser for help on using the repository browser.