1.1 --- a/src/work/bfs_iterator.h Wed Mar 24 13:06:06 2004 +0000
1.2 +++ b/src/work/bfs_iterator.h Thu Mar 25 09:42:59 2004 +0000
1.3 @@ -9,47 +9,47 @@
1.4
1.5 namespace hugo {
1.6
1.7 - template <typename Graph>
1.8 - struct bfs {
1.9 - typedef typename Graph::Node Node;
1.10 - typedef typename Graph::Edge Edge;
1.11 - typedef typename Graph::NodeIt NodeIt;
1.12 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.13 - Graph& G;
1.14 - Node s;
1.15 - typename Graph::NodeMap<bool> reached;
1.16 - typename Graph::NodeMap<Edge> pred;
1.17 - typename Graph::NodeMap<int> dist;
1.18 - std::queue<Node> bfs_queue;
1.19 - bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
1.20 - bfs_queue.push(s);
1.21 - for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)
1.22 - reached.set(i, false);
1.23 - reached.set(s, true);
1.24 - dist.set(s, 0);
1.25 - }
1.26 +// template <typename Graph>
1.27 +// struct bfs {
1.28 +// typedef typename Graph::Node Node;
1.29 +// typedef typename Graph::Edge Edge;
1.30 +// typedef typename Graph::NodeIt NodeIt;
1.31 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.32 +// Graph& G;
1.33 +// Node s;
1.34 +// typename Graph::NodeMap<bool> reached;
1.35 +// typename Graph::NodeMap<Edge> pred;
1.36 +// typename Graph::NodeMap<int> dist;
1.37 +// std::queue<Node> bfs_queue;
1.38 +// bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
1.39 +// bfs_queue.push(s);
1.40 +// for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)
1.41 +// reached.set(i, false);
1.42 +// reached.set(s, true);
1.43 +// dist.set(s, 0);
1.44 +// }
1.45
1.46 - void run() {
1.47 - while (!bfs_queue.empty()) {
1.48 - Node v=bfs_queue.front();
1.49 - OutEdgeIt e=G.template first<OutEdgeIt>(v);
1.50 - bfs_queue.pop();
1.51 - for( ; e.valid(); ++e) {
1.52 - Node w=G.bNode(e);
1.53 - std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
1.54 - if (!reached.get(w)) {
1.55 - std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.56 - bfs_queue.push(w);
1.57 - dist.set(w, dist.get(v)+1);
1.58 - pred.set(w, e);
1.59 - reached.set(w, true);
1.60 - } else {
1.61 - std::cout << G.id(w) << " is already reached" << std::endl;
1.62 - }
1.63 - }
1.64 - }
1.65 - }
1.66 - };
1.67 +// void run() {
1.68 +// while (!bfs_queue.empty()) {
1.69 +// Node v=bfs_queue.front();
1.70 +// OutEdgeIt e=G.template first<OutEdgeIt>(v);
1.71 +// bfs_queue.pop();
1.72 +// for( ; e.valid(); ++e) {
1.73 +// Node w=G.bNode(e);
1.74 +// std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
1.75 +// if (!reached.get(w)) {
1.76 +// std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.77 +// bfs_queue.push(w);
1.78 +// dist.set(w, dist.get(v)+1);
1.79 +// pred.set(w, e);
1.80 +// reached.set(w, true);
1.81 +// } else {
1.82 +// std::cout << G.id(w) << " is already reached" << std::endl;
1.83 +// }
1.84 +// }
1.85 +// }
1.86 +// }
1.87 +// };
1.88
1.89 // template <typename Graph>
1.90 // struct bfs_visitor {
1.91 @@ -544,90 +544,90 @@
1.92 // };
1.93
1.94
1.95 - template <typename Graph, typename OutEdgeIt,
1.96 - typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.97 - class BfsIterator4 {
1.98 - typedef typename Graph::Node Node;
1.99 - const Graph& G;
1.100 - std::queue<Node> bfs_queue;
1.101 - ReachedMap& reached;
1.102 - bool b_node_newly_reached;
1.103 - OutEdgeIt actual_edge;
1.104 - bool own_reached_map;
1.105 - public:
1.106 - BfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.107 - G(_G), reached(_reached),
1.108 - own_reached_map(false) { }
1.109 - BfsIterator4(const Graph& _G) :
1.110 - G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.111 - own_reached_map(true) { }
1.112 - ~BfsIterator4() { if (own_reached_map) delete &reached; }
1.113 - void pushAndSetReached(Node s) {
1.114 - //std::cout << "mimi" << &reached << std::endl;
1.115 - reached.set(s, true);
1.116 - //std::cout << "mumus" << std::endl;
1.117 - if (bfs_queue.empty()) {
1.118 - //std::cout << "bibi1" << std::endl;
1.119 - bfs_queue.push(s);
1.120 - //std::cout << "zizi" << std::endl;
1.121 - G./*getF*/first(actual_edge, s);
1.122 - //std::cout << "kiki" << std::endl;
1.123 - if (G.valid(actual_edge)/*.valid()*/) {
1.124 - Node w=G.bNode(actual_edge);
1.125 - if (!reached.get(w)) {
1.126 - bfs_queue.push(w);
1.127 - reached.set(w, true);
1.128 - b_node_newly_reached=true;
1.129 - } else {
1.130 - b_node_newly_reached=false;
1.131 - }
1.132 - }
1.133 - } else {
1.134 - //std::cout << "bibi2" << std::endl;
1.135 - bfs_queue.push(s);
1.136 - }
1.137 - }
1.138 - BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.139 - operator++() {
1.140 - if (G.valid(actual_edge)/*.valid()*/) {
1.141 - /*++*/G.next(actual_edge);
1.142 - if (G.valid(actual_edge)/*.valid()*/) {
1.143 - Node w=G.bNode(actual_edge);
1.144 - if (!reached.get(w)) {
1.145 - bfs_queue.push(w);
1.146 - reached.set(w, true);
1.147 - b_node_newly_reached=true;
1.148 - } else {
1.149 - b_node_newly_reached=false;
1.150 - }
1.151 - }
1.152 - } else {
1.153 - bfs_queue.pop();
1.154 - if (!bfs_queue.empty()) {
1.155 - G./*getF*/first(actual_edge, bfs_queue.front());
1.156 - if (G.valid(actual_edge)/*.valid()*/) {
1.157 - Node w=G.bNode(actual_edge);
1.158 - if (!reached.get(w)) {
1.159 - bfs_queue.push(w);
1.160 - reached.set(w, true);
1.161 - b_node_newly_reached=true;
1.162 - } else {
1.163 - b_node_newly_reached=false;
1.164 - }
1.165 - }
1.166 - }
1.167 - }
1.168 - return *this;
1.169 - }
1.170 - bool finished() const { return bfs_queue.empty(); }
1.171 - operator OutEdgeIt () const { return actual_edge; }
1.172 - bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.173 - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.174 - Node aNode() const { return bfs_queue.front(); }
1.175 - Node bNode() const { return G.bNode(actual_edge); }
1.176 - const ReachedMap& getReachedMap() const { return reached; }
1.177 - const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.178 - };
1.179 +// template <typename Graph, typename OutEdgeIt,
1.180 +// typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.181 +// class BfsIterator4 {
1.182 +// typedef typename Graph::Node Node;
1.183 +// const Graph& G;
1.184 +// std::queue<Node> bfs_queue;
1.185 +// ReachedMap& reached;
1.186 +// bool b_node_newly_reached;
1.187 +// OutEdgeIt actual_edge;
1.188 +// bool own_reached_map;
1.189 +// public:
1.190 +// BfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.191 +// G(_G), reached(_reached),
1.192 +// own_reached_map(false) { }
1.193 +// BfsIterator4(const Graph& _G) :
1.194 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.195 +// own_reached_map(true) { }
1.196 +// ~BfsIterator4() { if (own_reached_map) delete &reached; }
1.197 +// void pushAndSetReached(Node s) {
1.198 +// //std::cout << "mimi" << &reached << std::endl;
1.199 +// reached.set(s, true);
1.200 +// //std::cout << "mumus" << std::endl;
1.201 +// if (bfs_queue.empty()) {
1.202 +// //std::cout << "bibi1" << std::endl;
1.203 +// bfs_queue.push(s);
1.204 +// //std::cout << "zizi" << std::endl;
1.205 +// G./*getF*/first(actual_edge, s);
1.206 +// //std::cout << "kiki" << std::endl;
1.207 +// if (G.valid(actual_edge)/*.valid()*/) {
1.208 +// Node w=G.bNode(actual_edge);
1.209 +// if (!reached.get(w)) {
1.210 +// bfs_queue.push(w);
1.211 +// reached.set(w, true);
1.212 +// b_node_newly_reached=true;
1.213 +// } else {
1.214 +// b_node_newly_reached=false;
1.215 +// }
1.216 +// }
1.217 +// } else {
1.218 +// //std::cout << "bibi2" << std::endl;
1.219 +// bfs_queue.push(s);
1.220 +// }
1.221 +// }
1.222 +// BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.223 +// operator++() {
1.224 +// if (G.valid(actual_edge)/*.valid()*/) {
1.225 +// /*++*/G.next(actual_edge);
1.226 +// if (G.valid(actual_edge)/*.valid()*/) {
1.227 +// Node w=G.bNode(actual_edge);
1.228 +// if (!reached.get(w)) {
1.229 +// bfs_queue.push(w);
1.230 +// reached.set(w, true);
1.231 +// b_node_newly_reached=true;
1.232 +// } else {
1.233 +// b_node_newly_reached=false;
1.234 +// }
1.235 +// }
1.236 +// } else {
1.237 +// bfs_queue.pop();
1.238 +// if (!bfs_queue.empty()) {
1.239 +// G./*getF*/first(actual_edge, bfs_queue.front());
1.240 +// if (G.valid(actual_edge)/*.valid()*/) {
1.241 +// Node w=G.bNode(actual_edge);
1.242 +// if (!reached.get(w)) {
1.243 +// bfs_queue.push(w);
1.244 +// reached.set(w, true);
1.245 +// b_node_newly_reached=true;
1.246 +// } else {
1.247 +// b_node_newly_reached=false;
1.248 +// }
1.249 +// }
1.250 +// }
1.251 +// }
1.252 +// return *this;
1.253 +// }
1.254 +// bool finished() const { return bfs_queue.empty(); }
1.255 +// operator OutEdgeIt () const { return actual_edge; }
1.256 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.257 +// bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.258 +// Node aNode() const { return bfs_queue.front(); }
1.259 +// Node bNode() const { return G.bNode(actual_edge); }
1.260 +// const ReachedMap& getReachedMap() const { return reached; }
1.261 +// const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.262 +// };
1.263
1.264
1.265 template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.266 @@ -717,61 +717,61 @@
1.267 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.268 };
1.269
1.270 - template <typename Graph, typename OutEdgeIt,
1.271 - typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.272 - class DfsIterator4 {
1.273 - typedef typename Graph::Node Node;
1.274 - const Graph& G;
1.275 - std::stack<OutEdgeIt> dfs_stack;
1.276 - bool b_node_newly_reached;
1.277 - OutEdgeIt actual_edge;
1.278 - Node actual_node;
1.279 - ReachedMap& reached;
1.280 - bool own_reached_map;
1.281 - public:
1.282 - DfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.283 - G(_G), reached(_reached),
1.284 - own_reached_map(false) { }
1.285 - DfsIterator4(const Graph& _G) :
1.286 - G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.287 - own_reached_map(true) { }
1.288 - ~DfsIterator4() { if (own_reached_map) delete &reached; }
1.289 - void pushAndSetReached(Node s) {
1.290 - actual_node=s;
1.291 - reached.set(s, true);
1.292 - dfs_stack.push(G.template first<OutEdgeIt>(s));
1.293 - }
1.294 - DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.295 - operator++() {
1.296 - actual_edge=dfs_stack.top();
1.297 - //actual_node=G.aNode(actual_edge);
1.298 - if (G.valid(actual_edge)/*.valid()*/) {
1.299 - Node w=G.bNode(actual_edge);
1.300 - actual_node=w;
1.301 - if (!reached.get(w)) {
1.302 - dfs_stack.push(G.template first<OutEdgeIt>(w));
1.303 - reached.set(w, true);
1.304 - b_node_newly_reached=true;
1.305 - } else {
1.306 - actual_node=G.aNode(actual_edge);
1.307 - /*++*/G.next(dfs_stack.top());
1.308 - b_node_newly_reached=false;
1.309 - }
1.310 - } else {
1.311 - //actual_node=G.aNode(dfs_stack.top());
1.312 - dfs_stack.pop();
1.313 - }
1.314 - return *this;
1.315 - }
1.316 - bool finished() const { return dfs_stack.empty(); }
1.317 - operator OutEdgeIt () const { return actual_edge; }
1.318 - bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.319 - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.320 - Node aNode() const { return actual_node; /*FIXME*/}
1.321 - Node bNode() const { return G.bNode(actual_edge); }
1.322 - const ReachedMap& getReachedMap() const { return reached; }
1.323 - const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.324 - };
1.325 +// template <typename Graph, typename OutEdgeIt,
1.326 +// typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.327 +// class DfsIterator4 {
1.328 +// typedef typename Graph::Node Node;
1.329 +// const Graph& G;
1.330 +// std::stack<OutEdgeIt> dfs_stack;
1.331 +// bool b_node_newly_reached;
1.332 +// OutEdgeIt actual_edge;
1.333 +// Node actual_node;
1.334 +// ReachedMap& reached;
1.335 +// bool own_reached_map;
1.336 +// public:
1.337 +// DfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.338 +// G(_G), reached(_reached),
1.339 +// own_reached_map(false) { }
1.340 +// DfsIterator4(const Graph& _G) :
1.341 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.342 +// own_reached_map(true) { }
1.343 +// ~DfsIterator4() { if (own_reached_map) delete &reached; }
1.344 +// void pushAndSetReached(Node s) {
1.345 +// actual_node=s;
1.346 +// reached.set(s, true);
1.347 +// dfs_stack.push(G.template first<OutEdgeIt>(s));
1.348 +// }
1.349 +// DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.350 +// operator++() {
1.351 +// actual_edge=dfs_stack.top();
1.352 +// //actual_node=G.aNode(actual_edge);
1.353 +// if (G.valid(actual_edge)/*.valid()*/) {
1.354 +// Node w=G.bNode(actual_edge);
1.355 +// actual_node=w;
1.356 +// if (!reached.get(w)) {
1.357 +// dfs_stack.push(G.template first<OutEdgeIt>(w));
1.358 +// reached.set(w, true);
1.359 +// b_node_newly_reached=true;
1.360 +// } else {
1.361 +// actual_node=G.aNode(actual_edge);
1.362 +// /*++*/G.next(dfs_stack.top());
1.363 +// b_node_newly_reached=false;
1.364 +// }
1.365 +// } else {
1.366 +// //actual_node=G.aNode(dfs_stack.top());
1.367 +// dfs_stack.pop();
1.368 +// }
1.369 +// return *this;
1.370 +// }
1.371 +// bool finished() const { return dfs_stack.empty(); }
1.372 +// operator OutEdgeIt () const { return actual_edge; }
1.373 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.374 +// bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.375 +// Node aNode() const { return actual_node; /*FIXME*/}
1.376 +// Node bNode() const { return G.bNode(actual_edge); }
1.377 +// const ReachedMap& getReachedMap() const { return reached; }
1.378 +// const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.379 +// };
1.380
1.381 template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.382 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
2.1 --- a/src/work/edmonds_karp.h Wed Mar 24 13:06:06 2004 +0000
2.2 +++ b/src/work/edmonds_karp.h Thu Mar 25 09:42:59 2004 +0000
2.3 @@ -319,7 +319,7 @@
2.4 AugGraph res_graph(*G, *flow, *capacity);
2.5
2.6 typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.7 - BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
2.8 + BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
2.9
2.10 bfs.pushAndSetReached(s);
2.11 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
2.12 @@ -362,8 +362,8 @@
2.13 while (__augment) {
2.14 __augment=false;
2.15 //computing blocking flow with dfs
2.16 - typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
2.17 - DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
2.18 + typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
2.19 + DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
2.20 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
2.21 pred.set(sF, typename MutableGraph::Edge(INVALID));
2.22 //invalid iterators for sources
2.23 @@ -420,7 +420,7 @@
2.24
2.25 //bfs for distances on the residual graph
2.26 typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.27 - BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
2.28 + BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
2.29 bfs.pushAndSetReached(s);
2.30 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
2.31
2.32 @@ -465,8 +465,8 @@
2.33 while (__augment) {
2.34 __augment=false;
2.35 //computing blocking flow with dfs
2.36 - typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
2.37 - DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
2.38 + typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
2.39 + DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
2.40 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
2.41 pred.set(sF, typename MutableGraph::Edge(INVALID));
2.42 //invalid iterators for sources
2.43 @@ -527,9 +527,9 @@
2.44 EAugGraph res_graph(*G, *flow, *capacity);
2.45
2.46 //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
2.47 - BfsIterator4<
2.48 + BfsIterator5<
2.49 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
2.50 - typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
2.51 + /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
2.52 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
2.53
2.54 bfs.pushAndSetReached(s);
2.55 @@ -552,7 +552,7 @@
2.56 __augment=false;
2.57 //computing blocking flow with dfs
2.58 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
2.59 - DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
2.60 + DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
2.61 dfs(res_graph);
2.62 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
2.63 pred.set(s, EAugEdge(INVALID));
2.64 @@ -854,9 +854,9 @@
2.65 EAugGraph res_graph(*G, *flow, *capacity);
2.66
2.67 //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
2.68 - BfsIterator4<
2.69 + BfsIterator5<
2.70 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
2.71 - typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
2.72 + /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
2.73 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
2.74
2.75
2.76 @@ -894,7 +894,7 @@
2.77 __augment=false;
2.78 //computing blocking flow with dfs
2.79 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
2.80 - DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
2.81 + DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
2.82 dfs(res_graph);
2.83 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
2.84 //pred.set(s, EAugEdge(INVALID));
3.1 --- a/src/work/makefile Wed Mar 24 13:06:06 2004 +0000
3.2 +++ b/src/work/makefile Thu Mar 25 09:42:59 2004 +0000
3.3 @@ -1,7 +1,7 @@
3.4 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
3.5 CXXFLAGS = -g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
3.6
3.7 -BINARIES ?= bin_heap_demo marci_graph_demo iterator_bfs_demo
3.8 +BINARIES ?= bin_heap_demo iterator_bfs_demo
3.9
3.10 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
3.11 # ismert rendszeren :-) (Misi)
4.1 --- a/src/work/marci/edmonds_karp_demo.cc Wed Mar 24 13:06:06 2004 +0000
4.2 +++ b/src/work/marci/edmonds_karp_demo.cc Thu Mar 25 09:42:59 2004 +0000
4.3 @@ -34,8 +34,8 @@
4.4
4.5 typedef ListGraph MutableGraph;
4.6
4.7 - typedef SmartGraph Graph;
4.8 - //typedef ListGraph Graph;
4.9 + //typedef SmartGraph Graph;
4.10 + typedef ListGraph Graph;
4.11 typedef Graph::Node Node;
4.12 typedef Graph::EdgeIt EdgeIt;
4.13
4.14 @@ -85,7 +85,7 @@
4.15
4.16
4.17 {
4.18 - std::cout << "SmartGraph..." << std::endl;
4.19 + //std::cout << "SmartGraph..." << std::endl;
4.20 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
4.21 Graph::EdgeMap<int> flow(G); //0 flow
4.22
4.23 @@ -114,7 +114,7 @@
4.24 }
4.25
4.26 {
4.27 - std::cout << "SmartGraph..." << std::endl;
4.28 + //std::cout << "SmartGraph..." << std::endl;
4.29 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
4.30 Graph::EdgeMap<int> flow(G); //0 flow
4.31
5.1 --- a/src/work/marci_graph_demo.cc Wed Mar 24 13:06:06 2004 +0000
5.2 +++ b/src/work/marci_graph_demo.cc Thu Mar 25 09:42:59 2004 +0000
5.3 @@ -2,109 +2,109 @@
5.4 #include <vector>
5.5 #include <string>
5.6
5.7 -#include <list_graph.hh>
5.8 -#include <bfs_iterator.hh>
5.9 -#include <edmonds_karp.hh>
5.10 +#include <list_graph.h>
5.11 +#include <bfs_iterator.h>
5.12 +#include <edmonds_karp.h>
5.13
5.14 using namespace hugo;
5.15
5.16 int main (int, char*[])
5.17 {
5.18 + typedef ListGraph::Node Node;
5.19 + typedef ListGraph::Edge Edge;
5.20 typedef ListGraph::NodeIt NodeIt;
5.21 typedef ListGraph::EdgeIt EdgeIt;
5.22 - typedef ListGraph::EachNodeIt EachNodeIt;
5.23 - typedef ListGraph::EachEdgeIt EachEdgeIt;
5.24 typedef ListGraph::OutEdgeIt OutEdgeIt;
5.25 typedef ListGraph::InEdgeIt InEdgeIt;
5.26 typedef ListGraph::SymEdgeIt SymEdgeIt;
5.27 ListGraph G;
5.28 - std::vector<NodeIt> vector_of_NodeIts;
5.29 - for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
5.30 + std::vector<Node> vector_of_Nodes;
5.31 + for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode());
5.32 for(int i=0; i!=8; ++i)
5.33 for(int j=0; j!=8; ++j)
5.34 - if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]);
5.35 + if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]);
5.36
5.37 std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl;
5.38 - std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl;
5.39 + std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl;
5.40
5.41 - for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
5.42 + for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
5.43 std::cout << "node " << G.id(i) << std::endl;
5.44 std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";
5.45 - for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
5.46 + for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
5.47 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
5.48 }
5.49 std::cout << std::endl;
5.50
5.51 std::cout<< " ";
5.52 - for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
5.53 + for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
5.54 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
5.55 std::cout<<std::endl;
5.56
5.57 std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
5.58 - for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
5.59 + for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
5.60 std::cout << j << " "; }
5.61 std::cout << std::endl;
5.62
5.63 std::cout<< " ";
5.64 - for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
5.65 + for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
5.66 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
5.67 std::cout<<std::endl;
5.68
5.69 std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
5.70 - for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
5.71 + for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
5.72 std::cout << j << " "; }
5.73 std::cout<<std::endl;
5.74
5.75 std::cout<< " ";
5.76 - for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
5.77 + for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
5.78 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
5.79 std::cout<<std::endl;
5.80 }
5.81
5.82 std::cout << "all edges: ";
5.83 - for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
5.84 + for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
5.85 std::cout << i << " ";
5.86 }
5.87 std::cout << std::endl;
5.88
5.89 std::cout << "node property array test" << std::endl;
5.90 ListGraph::NodeMap<int> my_property_vector(G);
5.91 - EachNodeIt v;
5.92 - G.getFirst(v);
5.93 + NodeIt v;
5.94 + G.first(v);
5.95 my_property_vector.set(v, 42);
5.96 - my_property_vector.set(++G.first<EachNodeIt>(), 314);
5.97 - my_property_vector.set(++++G.first<EachNodeIt>(), 1956);
5.98 - my_property_vector.set(vector_of_NodeIts[3], 1989);
5.99 - my_property_vector.set(vector_of_NodeIts[4], 2003);
5.100 - my_property_vector.set(vector_of_NodeIts[7], 1978);
5.101 + my_property_vector.set(G.next(G.first<NodeIt>()), 314);
5.102 + my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956);
5.103 + my_property_vector.set(vector_of_Nodes[3], 1989);
5.104 + my_property_vector.set(vector_of_Nodes[4], 2003);
5.105 + my_property_vector.set(vector_of_Nodes[7], 1978);
5.106 std::cout << "some node property values..." << std::endl;
5.107 - for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
5.108 + for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
5.109 std::cout << my_property_vector.get(i) << std::endl;
5.110 }
5.111 int _i=1;
5.112 int _ii=1;
5.113 ListGraph::EdgeMap<int> my_edge_property(G);
5.114 - for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
5.115 + for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
5.116 my_edge_property.set(i, _i);
5.117 _i*=_ii; ++_ii;
5.118 }
5.119
5.120 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
5.121 - for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {
5.122 + for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {
5.123 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
5.124 }
5.125 std::cout << std::endl;
5.126 /*
5.127 std::cout << "bfs from the first node" << std::endl;
5.128 - bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
5.129 + bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
5.130 bfs_test.run();
5.131 std::cout << "reached: ";
5.132 - for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
5.133 + for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
5.134 std::cout << bfs_test.reached.get(i) << " ";
5.135 }
5.136 std::cout<<std::endl;
5.137 std::cout << "dist: ";
5.138 - for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
5.139 + for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
5.140 std::cout << bfs_test.dist.get(i) << " ";
5.141 }
5.142 std::cout<<std::endl;
5.143 @@ -113,12 +113,12 @@
5.144 std::cout << "augmenting path flow algorithm test..." << std::endl;
5.145 ListGraph flowG;
5.146
5.147 - NodeIt s=flowG.addNode();
5.148 - NodeIt v1=flowG.addNode();
5.149 - NodeIt v2=flowG.addNode();
5.150 - NodeIt v3=flowG.addNode();
5.151 - NodeIt v4=flowG.addNode();
5.152 - NodeIt t=flowG.addNode();
5.153 + Node s=flowG.addNode();
5.154 + Node v1=flowG.addNode();
5.155 + Node v2=flowG.addNode();
5.156 + Node v3=flowG.addNode();
5.157 + Node v4=flowG.addNode();
5.158 + Node t=flowG.addNode();
5.159
5.160 ListGraph::NodeMap<std::string> node_name(flowG);
5.161 node_name.set(s, "s");
5.162 @@ -128,16 +128,16 @@
5.163 node_name.set(v4, "v4");
5.164 node_name.set(t, "t");
5.165
5.166 - EdgeIt s_v1=flowG.addEdge(s, v1);
5.167 - EdgeIt s_v2=flowG.addEdge(s, v2);
5.168 - EdgeIt v1_v2=flowG.addEdge(v1, v2);
5.169 - EdgeIt v2_v1=flowG.addEdge(v2, v1);
5.170 - EdgeIt v1_v3=flowG.addEdge(v1, v3);
5.171 - EdgeIt v3_v2=flowG.addEdge(v3, v2);
5.172 - EdgeIt v2_v4=flowG.addEdge(v2, v4);
5.173 - EdgeIt v4_v3=flowG.addEdge(v4, v3);
5.174 - EdgeIt v3_t=flowG.addEdge(v3, t);
5.175 - EdgeIt v4_t=flowG.addEdge(v4, t);
5.176 + Edge s_v1=flowG.addEdge(s, v1);
5.177 + Edge s_v2=flowG.addEdge(s, v2);
5.178 + Edge v1_v2=flowG.addEdge(v1, v2);
5.179 + Edge v2_v1=flowG.addEdge(v2, v1);
5.180 + Edge v1_v3=flowG.addEdge(v1, v3);
5.181 + Edge v3_v2=flowG.addEdge(v3, v2);
5.182 + Edge v2_v4=flowG.addEdge(v2, v4);
5.183 + Edge v4_v3=flowG.addEdge(v4, v3);
5.184 + Edge v3_t=flowG.addEdge(v3, t);
5.185 + Edge v4_t=flowG.addEdge(v4, t);
5.186
5.187 ListGraph::EdgeMap<int> cap(flowG);
5.188
5.189 @@ -154,13 +154,13 @@
5.190
5.191 std::cout << "on directed graph graph" << std::endl; //<< flowG;
5.192 std::cout << "names and capacity values" << std::endl;
5.193 - for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
5.194 + for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
5.195 std::cout << node_name.get(i) << ": ";
5.196 std::cout << "out edges: ";
5.197 - for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
5.198 + for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
5.199 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
5.200 std::cout << "in edges: ";
5.201 - for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
5.202 + for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
5.203 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
5.204 std::cout << std::endl;
5.205 }
5.206 @@ -174,45 +174,45 @@
5.207 //flowG.setTail(v3_t, v2);
5.208 //flowG.setHead(v3_t, s);
5.209 /*
5.210 - for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
5.211 + for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
5.212 std::cout << node_name.get(i) << ": ";
5.213 std::cout << "out edges: ";
5.214 - for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
5.215 + for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
5.216 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
5.217 std::cout << "in edges: ";
5.218 - for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
5.219 + for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
5.220 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
5.221 std::cout << std::endl;
5.222 }
5.223
5.224 - for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {
5.225 + for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
5.226 std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
5.227 }
5.228 */
5.229 /*
5.230 - while (flowG.first<EachEdgeIt>().valid()) {
5.231 - flowG.deleteEdge(flowG.first<EachEdgeIt>());
5.232 - for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
5.233 + while (flowG.valid(flowG.first<EdgeIt>())) {
5.234 + flowG.deleteEdge(flowG.first<EdgeIt>());
5.235 + for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
5.236 std::cout << node_name.get(i) << ": ";
5.237 std::cout << "out edges: ";
5.238 - for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
5.239 + for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
5.240 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
5.241 std::cout << "in edges: ";
5.242 - for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
5.243 + for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
5.244 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
5.245 std::cout << std::endl;
5.246 }
5.247 }
5.248
5.249 - while (flowG.first<EachNodeIt>().valid()) {
5.250 - flowG.deleteNode(flowG.first<EachNodeIt>());
5.251 - for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
5.252 + while (flowG.valid(flowG.first<NodeIt>())) {
5.253 + flowG.deleteNode(flowG.first<NodeIt>());
5.254 + for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
5.255 std::cout << node_name.get(i) << ": ";
5.256 std::cout << "out edges: ";
5.257 - for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
5.258 + for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
5.259 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
5.260 std::cout << "in edges: ";
5.261 - for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
5.262 + for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
5.263 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
5.264 std::cout << std::endl;
5.265 }
5.266 @@ -227,12 +227,12 @@
5.267 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
5.268 /*
5.269 max_flow_test.augmentOnBlockingFlow<ListGraph>();
5.270 - for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
5.271 + for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
5.272 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
5.273 }
5.274 std::cout<<std::endl;
5.275 max_flow_test.augmentOnBlockingFlow<ListGraph>();
5.276 - for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
5.277 + for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
5.278 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
5.279 }
5.280 std::cout<<std::endl;*/
5.281 @@ -240,7 +240,7 @@
5.282
5.283 //std::cout << "maximum flow: "<< std::endl;
5.284 while (max_flow_test.augmentOnShortestPath()) {
5.285 - for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
5.286 + for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
5.287 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
5.288 }
5.289 std::cout<<std::endl;
5.290 @@ -249,9 +249,9 @@
5.291 }
5.292 /*
5.293 {
5.294 - std::list<NodeIt> S;
5.295 + std::list<Node> S;
5.296 S.push_back(s); S.push_back(v3);
5.297 - std::list<NodeIt> T;
5.298 + std::list<Node> T;
5.299 T.push_back(t);
5.300
5.301 ListGraph::EdgeMap<int> flow(flowG, 0);
5.302 @@ -259,7 +259,7 @@
5.303 max_flow_test.run();
5.304
5.305 std::cout << "maximum flow: "<< std::endl;
5.306 - for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
5.307 + for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
5.308 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
5.309 }
5.310 std::cout<<std::endl;