Dynamic maps became the defaults.
Maps got copy constructors and operator=. Also work between different types.
SymSmartGraph added
smart_graph_demo.cc was extended.
3 #ifndef EDMONDS_KARP_HH
4 #define EDMONDS_KARP_HH
8 //#include <marci_property_vector.hh>
12 //#include <bfs_iterator.hh>
15 template <typename Graph, typename FlowMap, typename CapacityMap>
16 typename FlowMap::ValueType maxFlow(Graph &G,
19 typename Graph::NodeIt s,
20 typename Graph::NodeIt t)
22 typedef typename Graph::NodeIt NodeIt;
23 typedef typename Graph::EachNodeIt EachNodeIt;
24 typedef typename Graph::EdgeIt EdgeIt;
25 typedef typename Graph::EachEdgeIt EachEdgeIt;
26 typedef typename Graph::OutEdgeIt OutEdgeIt;
27 typedef typename Graph::InEdgeIt InEdgeIt;
28 typedef typename FlowMap::ValueType T;
33 for(EachEdgeIt e(G);G.valid(e);G.goNext(e))
36 std::queue<NodeIt> bfs_queue;
37 typename Graph::NodeMap<int> visited(G); //0: unvisited,
38 //1: reached by a forward edge
39 //2: reached by a backward edge
41 typename Graph::NodeMap<EdgeIt> tree(G);
43 NodeIt gn; //FIXME: it might be too global for some people...
47 for(EachNodeIt n(G);G.valid(n);G.goNext(n))
52 //There must be a better way to do this:
53 while(!bfs_queue.empty()) bfs_queue.pop();
57 while(!bfs_queue.empty() && !visited.get(t))
59 NodeIt n(bfs_queue.front());
61 for(OutEdgeIt e(G,n);G.valid(e);G.goNext(e))
62 if(f.get(e)<c.get(e) && //FIXME: <
63 !visited.get(G.bNode(e)))
65 NodeIt nn(G.bNode(e)); //It improves nothing
70 for(InEdgeIt e(G,n);G.valid(e);G.goNext(e))
71 if(f.get(e)>0 && //FIXME: >
72 !visited.get(G.bNode(e)))
74 NodeIt nn(G.bNode(e));
81 if(!visited.get(t)) return flow_val;
83 // Augmenting value computation
84 aug_val = visited.get(t)==1 ?
85 c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t));
86 //FIXME: I would need 'G.opposite(e,n)'
87 gn = visited.get(t)==1 ? G.tail(tree.get(t)) : G.head(tree.get(t));
88 while(gn!=s) if(visited.get(gn)==1)
90 //FIXME: nonstandard gcc extension!
91 aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn));
92 gn=G.tail(tree.get(gn));
95 //FIXME: nonstandard gcc extension!
96 aug_val <?= f.get(tree.get(gn));
97 gn=G.head(tree.get(gn));
100 // The augmentation itself
102 while(gn!=s) if(visited.get(gn)==1)
104 f.set(tree.get(gn),f.get(tree.get(gn))+aug_val);
105 gn=G.tail(tree.get(gn));
108 f.set(tree.get(gn),f.get(tree.get(gn))-aug_val);
109 gn=G.head(tree.get(gn));
114 goto augment; // Vivat goto forever!
119 #endif //EDMONDS_KARP_HH