1.1 --- a/src/hugo/graph_wrapper.h Tue Aug 31 13:40:07 2004 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Tue Aug 31 17:54:22 2004 +0000
1.3 @@ -181,7 +181,7 @@
1.4 EdgeIt(const GraphWrapper<Graph>& _gw) :
1.5 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
1.6 EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
1.7 - Edge(w), gw(&_gw) { }
1.8 + Edge(e), gw(&_gw) { }
1.9 EdgeIt& operator++() {
1.10 *(static_cast<Edge*>(this))=
1.11 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.12 @@ -428,7 +428,7 @@
1.13 // OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
1.14 OutEdgeIt(Invalid i) : Edge(i) { }
1.15 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
1.16 - Edge(typename Graph::OutEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
1.17 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
1.18 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.19 const Edge& e) :
1.20 Edge(e), gw(&_gw) { }
1.21 @@ -450,7 +450,7 @@
1.22 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
1.23 InEdgeIt(Invalid i) : Edge(i) { }
1.24 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
1.25 - Edge(typename Graph::InEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
1.26 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
1.27 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.28 const Edge& e) :
1.29 Edge(e), gw(&_gw) { }
1.30 @@ -2040,48 +2040,54 @@
1.31 // operator Node() const { return Node(typename Graph::Node(n)); }
1.32 // };
1.33 typedef typename GraphWrapper<Graph>::Edge Edge;
1.34 - class OutEdgeIt {
1.35 + class OutEdgeIt : public Edge {
1.36 friend class GraphWrapper<Graph>;
1.37 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.38 -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.39 - typename Graph::OutEdgeIt e;
1.40 + const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1.41 public:
1.42 OutEdgeIt() { }
1.43 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.44 - OutEdgeIt(const Invalid& i) : e(i) { }
1.45 - OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.46 - const Node& _n) :
1.47 - e((*_G.first_out_edges)[_n]) { }
1.48 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.49 + //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
1.50 + OutEdgeIt(Invalid i) : Edge(i) { }
1.51 + OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1.52 + const Node& n) :
1.53 + Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1.54 + OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1.55 + const Edge& e) :
1.56 + Edge(e), gw(&_gw) { }
1.57 + OutEdgeIt& operator++() {
1.58 + *(static_cast<Edge*>(this))=
1.59 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.60 + return *this;
1.61 + }
1.62 };
1.63 - class InEdgeIt {
1.64 - friend class GraphWrapper<Graph>;
1.65 - friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.66 -// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.67 - typename Graph::InEdgeIt e;
1.68 - public:
1.69 - InEdgeIt() { }
1.70 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.71 - InEdgeIt(const Invalid& i) : e(i) { }
1.72 - InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.73 - const Node& _n) :
1.74 - e(*(_G.graph), typename Graph::Node(_n)) { }
1.75 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.76 - };
1.77 +// class InEdgeIt {
1.78 +// friend class GraphWrapper<Graph>;
1.79 +// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.80 +// // typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.81 +// typename Graph::InEdgeIt e;
1.82 +// public:
1.83 +// InEdgeIt() { }
1.84 +// InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.85 +// InEdgeIt(const Invalid& i) : e(i) { }
1.86 +// InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.87 +// const Node& _n) :
1.88 +// e(*(_G.graph), typename Graph::Node(_n)) { }
1.89 +// operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.90 +// };
1.91 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.92 - class EdgeIt {
1.93 - friend class GraphWrapper<Graph>;
1.94 - friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.95 -// typedef typename Graph::EdgeIt GraphEdgeIt;
1.96 - typename Graph::EdgeIt e;
1.97 - public:
1.98 - EdgeIt() { }
1.99 - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.100 - EdgeIt(const Invalid& i) : e(i) { }
1.101 - EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.102 - e(*(_G.graph)) { }
1.103 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.104 - };
1.105 +// class EdgeIt {
1.106 +// friend class GraphWrapper<Graph>;
1.107 +// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.108 +// // typedef typename Graph::EdgeIt GraphEdgeIt;
1.109 +// typename Graph::EdgeIt e;
1.110 +// public:
1.111 +// EdgeIt() { }
1.112 +// EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.113 +// EdgeIt(const Invalid& i) : e(i) { }
1.114 +// EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.115 +// e(*(_G.graph)) { }
1.116 +// operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.117 +// };
1.118
1.119 using GraphWrapper<Graph>::first;
1.120 // NodeIt& first(NodeIt& i) const {
1.121 @@ -2090,32 +2096,33 @@
1.122 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.123 i=OutEdgeIt(*this, p); return i;
1.124 }
1.125 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.126 - i=InEdgeIt(*this, p); return i;
1.127 - }
1.128 - EdgeIt& first(EdgeIt& i) const {
1.129 - i=EdgeIt(*this); return i;
1.130 - }
1.131 +// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.132 +// i=InEdgeIt(*this, p); return i;
1.133 +// }
1.134 +// EdgeIt& first(EdgeIt& i) const {
1.135 +// i=EdgeIt(*this); return i;
1.136 +// }
1.137
1.138 - using GraphWrapper<Graph>::next;
1.139 -// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1.140 - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.141 - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.142 - EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1.143 +// using GraphWrapper<Graph>::next;
1.144 +// // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1.145 +// OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1.146 +// InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1.147 +// EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1.148
1.149 - Node aNode(const OutEdgeIt& e) const {
1.150 - return Node(this->graph->aNode(e.e)); }
1.151 - Node aNode(const InEdgeIt& e) const {
1.152 - return Node(this->graph->aNode(e.e)); }
1.153 - Node bNode(const OutEdgeIt& e) const {
1.154 - return Node(this->graph->bNode(e.e)); }
1.155 - Node bNode(const InEdgeIt& e) const {
1.156 - return Node(this->graph->bNode(e.e)); }
1.157 +// Node aNode(const OutEdgeIt& e) const {
1.158 +// return Node(this->graph->aNode(e.e)); }
1.159 +// Node aNode(const InEdgeIt& e) const {
1.160 +// return Node(this->graph->aNode(e.e)); }
1.161 +// Node bNode(const OutEdgeIt& e) const {
1.162 +// return Node(this->graph->bNode(e.e)); }
1.163 +// Node bNode(const InEdgeIt& e) const {
1.164 +// return Node(this->graph->bNode(e.e)); }
1.165
1.166 - void erase(const OutEdgeIt& e) const {
1.167 - OutEdgeIt f=e;
1.168 - this->next(f);
1.169 - first_out_edges->set(this->tail(e), f.e);
1.170 + void erase(const Edge& e) const {
1.171 + Node n=tail(e);
1.172 + typename Graph::OutEdgeIt f(*graph, n);
1.173 + ++f;
1.174 + first_out_edges->set(n, f);
1.175 }
1.176 };
1.177
2.1 --- a/src/work/marci/augmenting_flow.h Tue Aug 31 13:40:07 2004 +0000
2.2 +++ b/src/work/marci/augmenting_flow.h Tue Aug 31 17:54:22 2004 +0000
2.3 @@ -11,7 +11,7 @@
2.4 #include <bfs_dfs.h>
2.5 #include <hugo/invalid.h>
2.6 #include <hugo/maps.h>
2.7 -#include <for_each_macros.h>
2.8 +//#include <for_each_macros.h>
2.9
2.10 /// \file
2.11 /// \brief Maximum flow algorithms.
2.12 @@ -1082,8 +1082,8 @@
2.13
2.14 Num flowValue() const {
2.15 Num a=0;
2.16 - FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
2.17 - FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
2.18 + for (InEdgeIt e(*g, t); e!=INVALID; ++e) a+=(*flow)[e];
2.19 + for (OutEdgeIt e(*g, t); e!=INVALID; ++e) a-=(*flow)[e];
2.20 return a;
2.21 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
2.22 }
2.23 @@ -1121,7 +1121,7 @@
2.24 bool _augment=false;
2.25
2.26 //ReachedMap level(res_graph);
2.27 - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.28 + for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
2.29 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.30 bfs.pushAndSetReached(s);
2.31
2.32 @@ -1132,7 +1132,7 @@
2.33
2.34 //searching for augmenting path
2.35 while ( !bfs.finished() ) {
2.36 - ResGWOutEdgeIt e=bfs;
2.37 + ResGWEdge e=bfs;
2.38 if (e!=INVALID && bfs.isBNodeNewlyReached()) {
2.39 Node v=res_graph.tail(e);
2.40 Node w=res_graph.head(e);
2.41 @@ -1169,7 +1169,7 @@
2.42 bool _augment=false;
2.43
2.44 if (status!=AFTER_FAST_AUGMENTING) {
2.45 - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.46 + for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
2.47 number_of_augmentations=1;
2.48 } else {
2.49 ++number_of_augmentations;
2.50 @@ -1189,7 +1189,7 @@
2.51
2.52 //searching for augmenting path
2.53 while ( !bfs.finished() ) {
2.54 - ResGWOutEdgeIt e=bfs;
2.55 + ResGWEdge e=bfs;
2.56 if (e!=INVALID && bfs.isBNodeNewlyReached()) {
2.57 Node v=res_graph.tail(e);
2.58 Node w=res_graph.head(e);
2.59 @@ -1231,7 +1231,7 @@
2.60
2.61 //bfs for distances on the residual graph
2.62 //ReachedMap level(res_graph);
2.63 - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.64 + for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
2.65 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.66 bfs.pushAndSetReached(s);
2.67 typename ResGW::template NodeMap<int>
2.68 @@ -1255,7 +1255,7 @@
2.69 typename MG::template EdgeMap<Num> residual_capacity(F);
2.70
2.71 while ( !bfs.finished() ) {
2.72 - ResGWOutEdgeIt e=bfs;
2.73 + ResGWEdge e=bfs;
2.74 if (e!=INVALID) {
2.75 if (bfs.isBNodeNewlyReached()) {
2.76 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.77 @@ -1296,8 +1296,8 @@
2.78 ++dfs;
2.79 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
2.80 if (dfs.isBNodeNewlyReached()) {
2.81 - typename MG::Node v=F.aNode(dfs);
2.82 - typename MG::Node w=F.bNode(dfs);
2.83 + typename MG::Node v=F.tail(dfs);
2.84 + typename MG::Node w=F.head(dfs);
2.85 pred.set(w, dfs);
2.86 if (pred[v]!=INVALID) {
2.87 free.set(w, std::min(free[v], residual_capacity[dfs]));
2.88 @@ -1345,20 +1345,20 @@
2.89 ResGW res_graph(*g, *capacity, *flow);
2.90
2.91 //ReachedMap level(res_graph);
2.92 - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.93 + for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
2.94 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.95
2.96 bfs.pushAndSetReached(s);
2.97 DistanceMap<ResGW> dist(res_graph);
2.98 while ( !bfs.finished() ) {
2.99 - ResGWOutEdgeIt e=bfs;
2.100 + ResGWEdge e=bfs;
2.101 if (e!=INVALID && bfs.isBNodeNewlyReached()) {
2.102 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.103 }
2.104 ++bfs;
2.105 } //computing distances from s in the residual graph
2.106
2.107 - //Subgraph containing the edges on some shortest paths
2.108 + //Subgraph containing the edges on some shortest paths
2.109 ConstMap<typename ResGW::Node, bool> true_map(true);
2.110 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
2.111 DistanceMap<ResGW> > FilterResGW;
2.112 @@ -1366,17 +1366,17 @@
2.113
2.114 //Subgraph, which is able to delete edges which are already
2.115 //met by the dfs
2.116 - typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
2.117 + typename FilterResGW::template NodeMap<typename FilterResGW::Edge>
2.118 first_out_edges(filter_res_graph);
2.119 typename FilterResGW::NodeIt v;
2.120 for(filter_res_graph.first(v); v!=INVALID; ++v)
2.121 {
2.122 - typename FilterResGW::OutEdgeIt e;
2.123 - filter_res_graph.first(e, v);
2.124 - first_out_edges.set(v, e);
2.125 + typename FilterResGW::OutEdgeIt e;
2.126 + filter_res_graph.first(e, v);
2.127 + first_out_edges.set(v, e);
2.128 }
2.129 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
2.130 - template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
2.131 + template NodeMap<typename FilterResGW::Edge> > ErasingResGW;
2.132 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
2.133
2.134 bool __augment=true;
2.135 @@ -1389,8 +1389,7 @@
2.136 typename ErasingResGW::template NodeMap<bool> >
2.137 dfs(erasing_res_graph);
2.138 typename ErasingResGW::
2.139 - template NodeMap<typename ErasingResGW::OutEdgeIt>
2.140 - pred(erasing_res_graph);
2.141 + template NodeMap<typename ErasingResGW::Edge> pred(erasing_res_graph);
2.142 pred.set(s, INVALID);
2.143 //invalid iterators for sources
2.144
2.145 @@ -1398,31 +1397,32 @@
2.146 free1(erasing_res_graph);
2.147
2.148 dfs.pushAndSetReached
2.149 - ///\bug hugo 0.2
2.150 + /// \bug hugo 0.2
2.151 (typename ErasingResGW::Node
2.152 (typename FilterResGW::Node
2.153 (typename ResGW::Node(s)
2.154 )
2.155 )
2.156 );
2.157 +
2.158 while (!dfs.finished()) {
2.159 ++dfs;
2.160 - if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs)))
2.161 + if (typename ErasingResGW::Edge(dfs)!=INVALID)
2.162 {
2.163 if (dfs.isBNodeNewlyReached()) {
2.164
2.165 - typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
2.166 - typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
2.167 + typename ErasingResGW::Node v=erasing_res_graph.tail(dfs);
2.168 + typename ErasingResGW::Node w=erasing_res_graph.head(dfs);
2.169
2.170 - pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
2.171 + pred.set(w, typename ErasingResGW::Edge(dfs));
2.172 if (pred[v]!=INVALID) {
2.173 free1.set
2.174 (w, std::min(free1[v], res_graph.resCap
2.175 - (typename ErasingResGW::OutEdgeIt(dfs))));
2.176 + (typename ErasingResGW::Edge(dfs))));
2.177 } else {
2.178 free1.set
2.179 (w, res_graph.resCap
2.180 - (typename ErasingResGW::OutEdgeIt(dfs)));
2.181 + (typename ErasingResGW::Edge(dfs)));
2.182 }
2.183
2.184 if (w==t) {
2.185 @@ -1449,8 +1449,8 @@
2.186 // typename ErasingResGW::Node b2;
2.187 // Num j2=a2[b2];
2.188 Num augment_value=free1[n];
2.189 - while (erasing_res_graph.valid(pred[n])) {
2.190 - typename ErasingResGW::OutEdgeIt e=pred[n];
2.191 + while (pred[n]!=INVALID) {
2.192 + typename ErasingResGW::Edge e=pred[n];
2.193 res_graph.augment(e, augment_value);
2.194 n=erasing_res_graph.tail(e);
2.195 if (res_graph.resCap(e)==0)
3.1 --- a/src/work/marci/bfs_dfs.h Tue Aug 31 13:40:07 2004 +0000
3.2 +++ b/src/work/marci/bfs_dfs.h Tue Aug 31 17:54:22 2004 +0000
3.3 @@ -27,12 +27,13 @@
3.4 class BfsIterator {
3.5 protected:
3.6 typedef typename Graph::Node Node;
3.7 + typedef typename Graph::Edge Edge;
3.8 typedef typename Graph::OutEdgeIt OutEdgeIt;
3.9 const Graph* graph;
3.10 std::queue<Node> bfs_queue;
3.11 ReachedMap& reached;
3.12 bool b_node_newly_reached;
3.13 - OutEdgeIt actual_edge;
3.14 + Edge actual_edge;
3.15 bool own_reached_map;
3.16 public:
3.17 /// In that constructor \c _reached have to be a reference
3.18 @@ -55,11 +56,12 @@
3.19 /// If the queue is empty, then \c s is pushed in the bfs queue
3.20 /// and the first out-edge is processed.
3.21 /// If the queue is not empty, then \c s is simply pushed.
3.22 - void pushAndSetReached(Node s) {
3.23 + BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
3.24 reached.set(s, true);
3.25 if (bfs_queue.empty()) {
3.26 bfs_queue.push(s);
3.27 - graph->first(actual_edge, s);
3.28 + actual_edge=OutEdgeIt(*graph, s);
3.29 + //graph->first(actual_edge, s);
3.30 if (actual_edge!=INVALID) {
3.31 Node w=graph->head(actual_edge);
3.32 if (!reached[w]) {
3.33 @@ -73,13 +75,15 @@
3.34 } else {
3.35 bfs_queue.push(s);
3.36 }
3.37 + return *this;
3.38 }
3.39 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
3.40 /// its \c operator++() iterates on the edges in a bfs order.
3.41 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
3.42 operator++() {
3.43 if (actual_edge!=INVALID) {
3.44 - ++actual_edge;
3.45 + actual_edge=++OutEdgeIt(*graph, actual_edge);
3.46 + //++actual_edge;
3.47 if (actual_edge!=INVALID) {
3.48 Node w=graph->head(actual_edge);
3.49 if (!reached[w]) {
3.50 @@ -93,7 +97,8 @@
3.51 } else {
3.52 bfs_queue.pop();
3.53 if (!bfs_queue.empty()) {
3.54 - graph->first(actual_edge, bfs_queue.front());
3.55 + actual_edge=OutEdgeIt(*graph, bfs_queue.front());
3.56 + //graph->first(actual_edge, bfs_queue.front());
3.57 if (actual_edge!=INVALID) {
3.58 Node w=graph->head(actual_edge);
3.59 if (!reached[w]) {
3.60 @@ -113,15 +118,15 @@
3.61 /// The conversion operator makes for converting the bfs-iterator
3.62 /// to an \c out-edge-iterator.
3.63 ///\bug Edge have to be in HUGO 0.2
3.64 - operator OutEdgeIt() const { return actual_edge; }
3.65 + operator Edge() const { return actual_edge; }
3.66 /// Returns if b-node has been reached just now.
3.67 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.68 /// Returns if a-node is examined.
3.69 bool isANodeExamined() const { return actual_edge==INVALID; }
3.70 /// Returns a-node of the actual edge, so does if the edge is invalid.
3.71 - Node aNode() const { return bfs_queue.front(); }
3.72 + Node tail() const { return bfs_queue.front(); }
3.73 /// \pre The actual edge have to be valid.
3.74 - Node bNode() const { return graph->bNode(actual_edge); }
3.75 + Node head() const { return graph->head(actual_edge); }
3.76 /// Guess what?
3.77 /// \deprecated
3.78 const ReachedMap& getReachedMap() const { return reached; }
3.79 @@ -159,7 +164,7 @@
3.80 /// If \c s was not marked previously, then
3.81 /// in addition its pred is set to be \c INVALID, and dist to \c 0.
3.82 /// if \c s was marked previuosly, then it is simply pushed.
3.83 - void push(Node s) {
3.84 + Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) {
3.85 if (this->reached[s]) {
3.86 Parent::pushAndSetReached(s);
3.87 } else {
3.88 @@ -167,11 +172,13 @@
3.89 pred.set(s, INVALID);
3.90 dist.set(s, 0);
3.91 }
3.92 + return *this;
3.93 }
3.94 /// A bfs is processed from \c s.
3.95 - void run(Node s) {
3.96 + Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) {
3.97 push(s);
3.98 while (!this->finished()) this->operator++();
3.99 + return *this;
3.100 }
3.101 /// Beside the bfs iteration, \c pred and \dist are saved in a
3.102 /// newly reached node.
3.103 @@ -179,8 +186,8 @@
3.104 Parent::operator++();
3.105 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
3.106 {
3.107 - pred.set(this->bNode(), this->actual_edge);
3.108 - dist.set(this->bNode(), dist[this->aNode()]);
3.109 + pred.set(this->head(), this->actual_edge);
3.110 + dist.set(this->head(), dist[this->tail()]);
3.111 }
3.112 return *this;
3.113 }
3.114 @@ -201,11 +208,12 @@
3.115 class DfsIterator {
3.116 protected:
3.117 typedef typename Graph::Node Node;
3.118 + typedef typename Graph::Edge Edge;
3.119 typedef typename Graph::OutEdgeIt OutEdgeIt;
3.120 const Graph* graph;
3.121 std::stack<OutEdgeIt> dfs_stack;
3.122 bool b_node_newly_reached;
3.123 - OutEdgeIt actual_edge;
3.124 + Edge actual_edge;
3.125 Node actual_node;
3.126 ReachedMap& reached;
3.127 bool own_reached_map;
3.128 @@ -224,25 +232,25 @@
3.129 own_reached_map(true) { }
3.130 ~DfsIterator() { if (own_reached_map) delete &reached; }
3.131 /// This method markes s reached and first out-edge is processed.
3.132 - void pushAndSetReached(Node s) {
3.133 + DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
3.134 actual_node=s;
3.135 reached.set(s, true);
3.136 - OutEdgeIt e;
3.137 - graph->first(e, s);
3.138 + OutEdgeIt e(*graph, s);
3.139 + //graph->first(e, s);
3.140 dfs_stack.push(e);
3.141 + return *this;
3.142 }
3.143 /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
3.144 /// its \c operator++() iterates on the edges in a dfs order.
3.145 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
3.146 operator++() {
3.147 actual_edge=dfs_stack.top();
3.148 - //actual_node=G.aNode(actual_edge);
3.149 if (actual_edge!=INVALID/*.valid()*/) {
3.150 Node w=graph->head(actual_edge);
3.151 actual_node=w;
3.152 if (!reached[w]) {
3.153 - OutEdgeIt e;
3.154 - graph->first(e, w);
3.155 + OutEdgeIt e(*graph, w);
3.156 + //graph->first(e, w);
3.157 dfs_stack.push(e);
3.158 reached.set(w, true);
3.159 b_node_newly_reached=true;
3.160 @@ -262,16 +270,16 @@
3.161 /// The conversion operator makes for converting the bfs-iterator
3.162 /// to an \c out-edge-iterator.
3.163 ///\bug Edge have to be in HUGO 0.2
3.164 - operator OutEdgeIt() const { return actual_edge; }
3.165 + operator Edge() const { return actual_edge; }
3.166 /// Returns if b-node has been reached just now.
3.167 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.168 /// Returns if a-node is examined.
3.169 bool isANodeExamined() const { return actual_edge==INVALID; }
3.170 /// Returns a-node of the actual edge, so does if the edge is invalid.
3.171 - Node aNode() const { return actual_node; /*FIXME*/}
3.172 + Node tail() const { return actual_node; /*FIXME*/}
3.173 /// Returns b-node of the actual edge.
3.174 /// \pre The actual edge have to be valid.
3.175 - Node bNode() const { return graph->bNode(actual_edge); }
3.176 + Node head() const { return graph->head(actual_edge); }
3.177 /// Guess what?
3.178 /// \deprecated
3.179 const ReachedMap& getReachedMap() const { return reached; }
3.180 @@ -304,18 +312,20 @@
3.181 /// If \c s was not marked previously, then
3.182 /// in addition its pred is set to be \c INVALID.
3.183 /// if \c s was marked previuosly, then it is simply pushed.
3.184 - void push(Node s) {
3.185 + Dfs<Graph, ReachedMap, PredMap>& push(Node s) {
3.186 if (this->reached[s]) {
3.187 Parent::pushAndSetReached(s);
3.188 } else {
3.189 Parent::pushAndSetReached(s);
3.190 pred.set(s, INVALID);
3.191 }
3.192 + return *this;
3.193 }
3.194 /// A bfs is processed from \c s.
3.195 - void run(Node s) {
3.196 + Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
3.197 push(s);
3.198 while (!this->finished()) this->operator++();
3.199 + return *this;
3.200 }
3.201 /// Beside the dfs iteration, \c pred is saved in a
3.202 /// newly reached node.
3.203 @@ -323,7 +333,7 @@
3.204 Parent::operator++();
3.205 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
3.206 {
3.207 - pred.set(this->bNode(), this->actual_edge);
3.208 + pred.set(this->head(), this->actual_edge);
3.209 }
3.210 return *this;
3.211 }
4.1 --- a/src/work/marci/bfsit_vs_byhand.cc Tue Aug 31 13:40:07 2004 +0000
4.2 +++ b/src/work/marci/bfsit_vs_byhand.cc Tue Aug 31 17:54:22 2004 +0000
4.3 @@ -33,7 +33,7 @@
4.4 cout << g.nodeNum() << endl;
4.5 cout << g.edgeNum() << endl;
4.6
4.7 - Graph::NodeMap<OutEdgeIt> pred(g);
4.8 + Graph::NodeMap<Edge> pred(g);
4.9 cout << "iteration time of bfs written by hand..." << endl;
4.10 Timer ts;
4.11 {
4.12 @@ -69,7 +69,7 @@
4.13 while (!bfs.finished()) {
4.14 ++bfs;
4.15 if (g.valid(bfs) && bfs.isBNodeNewlyReached())
4.16 - pred.set(bfs.bNode(), bfs);
4.17 + pred.set(bfs.head(), Graph::Edge(bfs));
4.18 }
4.19 std::cout << ts << std::endl;
4.20 }
5.1 --- a/src/work/marci/graph_wrapper_time.cc Tue Aug 31 13:40:07 2004 +0000
5.2 +++ b/src/work/marci/graph_wrapper_time.cc Tue Aug 31 17:54:22 2004 +0000
5.3 @@ -1,5 +1,8 @@
5.4 // -*- c++ -*-
5.5
5.6 +// Use a DIMACS max flow file as follows:
5.7 +// graph_wrapper_time dimacs_max_flow_file
5.8 +
5.9 #include <iostream>
5.10 #include <fstream>
5.11 #include <string>
5.12 @@ -28,8 +31,7 @@
5.13 readDimacs(is, g, cap, s, t);
5.14 Timer ts;
5.15 ts.reset();
5.16 - cout << g.nodeNum() << endl;
5.17 - cout << g.edgeNum() << endl;
5.18 +
5.19 typedef MaxFlow<Graph, int, FlowMap, FlowMap> MyMaxFlow;
5.20 MyMaxFlow max_flow(g, s, t, cap, flow);
5.21 max_flow.run(MyMaxFlow::NO_FLOW);
5.22 @@ -41,17 +43,9 @@
5.23
5.24 typedef ListGraph Graph;
5.25 Graph g;
5.26 -// cout << g.id(g.addNode()) << endl;
5.27 -// cout << g.id(g.addNode()) << endl;
5.28 -// cout << g.nodeNum() << endl;
5.29 timeTest<Graph>(in, g);
5.30 typedef GraphWrapper<Graph> Graph1;
5.31 Graph1 g1(g);
5.32 -// g1.clear();
5.33 -// cout << g.id(g1.addNode()) << endl;
5.34 -// cout << g.id(g1.addNode()) << endl;
5.35 -// cout << g1.nodeNum() << endl;
5.36 -// g1.clear();
5.37 timeTest<Graph1>(in, g1);
5.38 typedef GraphWrapper<Graph1> Graph2;
5.39 Graph2 g2(g1);
5.40 @@ -59,18 +53,18 @@
5.41 typedef GraphWrapper<Graph2> Graph3;
5.42 Graph3 g3(g2);
5.43 timeTest<Graph3>(in, g3);
5.44 -// typedef GraphWrapper<Graph3> Graph4;
5.45 -// Graph4 g4(g3);
5.46 -// timeTest<Graph4>(in, g4);
5.47 -// typedef GraphWrapper<Graph4> Graph5;
5.48 -// Graph5 g5(g4);
5.49 -// timeTest<Graph5>(in, g5);
5.50 -// typedef GraphWrapper<Graph5> Graph6;
5.51 -// Graph6 g6(g5);
5.52 -// timeTest<Graph6>(in, g6);
5.53 -// typedef GraphWrapper<Graph6> Graph7;
5.54 -// Graph7 g7(g6);
5.55 -// timeTest<Graph7>(in, g7);
5.56 + typedef GraphWrapper<Graph3> Graph4;
5.57 + Graph4 g4(g3);
5.58 + timeTest<Graph4>(in, g4);
5.59 + typedef GraphWrapper<Graph4> Graph5;
5.60 + Graph5 g5(g4);
5.61 + timeTest<Graph5>(in, g5);
5.62 + typedef GraphWrapper<Graph5> Graph6;
5.63 + Graph6 g6(g5);
5.64 + timeTest<Graph6>(in, g6);
5.65 + typedef GraphWrapper<Graph6> Graph7;
5.66 + Graph7 g7(g6);
5.67 + timeTest<Graph7>(in, g7);
5.68
5.69 return 0;
5.70 }
6.1 --- a/src/work/marci/iterator_bfs_demo.cc Tue Aug 31 13:40:07 2004 +0000
6.2 +++ b/src/work/marci/iterator_bfs_demo.cc Tue Aug 31 17:54:22 2004 +0000
6.3 @@ -9,6 +9,7 @@
6.4 #include <hugo/graph_wrapper.h>
6.5
6.6 using namespace hugo;
6.7 +
6.8 using std::cout;
6.9 using std::endl;
6.10 using std::string;
6.11 @@ -72,21 +73,6 @@
6.12 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
6.13 cout << " \\--> -------------> "<< endl;
6.14
6.15 -// typedef TrivGraphWrapper<const Graph> CGW;
6.16 -// CGW gw(G);
6.17 -
6.18 -// cout << "bfs and dfs demo on the directed graph" << endl;
6.19 -// for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {
6.20 -// cout << n << ": ";
6.21 -// cout << "out edges: ";
6.22 -// for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
6.23 -// cout << e << " ";
6.24 -// cout << "in edges: ";
6.25 -// for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)
6.26 -// cout << e << " ";
6.27 -// cout << endl;
6.28 -// }
6.29 -
6.30 {
6.31 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
6.32
6.33 @@ -107,7 +93,7 @@
6.34 bfs.pushAndSetReached(s);
6.35 while (!bfs.finished()) {
6.36 //cout << "edge: ";
6.37 - if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {
6.38 + if (Graph::Edge(bfs)!=INVALID) {
6.39 cout << edge_name[bfs] << /*endl*/", " <<
6.40 node_name[G.tail(bfs)] <<
6.41 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.42 @@ -116,7 +102,7 @@
6.43 ": is not newly reached.");
6.44 } else {
6.45 cout << "invalid" << /*endl*/", " <<
6.46 - node_name[bfs.aNode()] <<
6.47 + node_name[bfs.tail()] <<
6.48 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.49
6.50 "invalid.";
6.51 @@ -141,7 +127,7 @@
6.52 while (!dfs.finished()) {
6.53 ++dfs;
6.54 //cout << "edge: ";
6.55 - if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {
6.56 + if (Graph::Edge(dfs)!=INVALID) {
6.57 cout << edge_name[dfs] << /*endl*/", " <<
6.58 node_name[G.tail(dfs)] <<
6.59 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.60 @@ -150,7 +136,7 @@
6.61 ": is not newly reached.");
6.62 } else {
6.63 cout << "invalid" << /*endl*/", " <<
6.64 - node_name[dfs.aNode()] <<
6.65 + node_name[dfs.tail()] <<
6.66 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.67
6.68 "invalid.";
6.69 @@ -183,8 +169,8 @@
6.70 bfs.pushAndSetReached(t);
6.71 while (!bfs.finished()) {
6.72 //cout << "edge: ";
6.73 - if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {
6.74 - cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
6.75 + if (GW::Edge(bfs)!=INVALID) {
6.76 + cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
6.77 node_name[gw.tail(bfs)] <<
6.78 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.79 node_name[gw.head(bfs)] <<
6.80 @@ -192,7 +178,7 @@
6.81 ": is not newly reached.");
6.82 } else {
6.83 cout << "invalid" << /*endl*/", " <<
6.84 - node_name[bfs.aNode()] <<
6.85 + node_name[bfs.tail()] <<
6.86 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.87
6.88 "invalid.";
6.89 @@ -217,8 +203,8 @@
6.90 while (!dfs.finished()) {
6.91 ++dfs;
6.92 //cout << "edge: ";
6.93 - if (GW::OutEdgeIt(dfs)!=INVALID) {
6.94 - cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
6.95 + if (GW::Edge(dfs)!=INVALID) {
6.96 + cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
6.97 node_name[gw.tail(dfs)] <<
6.98 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.99 node_name[gw.head(dfs)] <<
6.100 @@ -226,7 +212,7 @@
6.101 ": is not newly reached.");
6.102 } else {
6.103 cout << "invalid" << /*endl*/", " <<
6.104 - node_name[dfs.aNode()] <<
6.105 + node_name[dfs.tail()] <<
6.106 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.107
6.108 "invalid.";
6.109 @@ -346,8 +332,8 @@
6.110 bfs.pushAndSetReached(t);
6.111 while (!bfs.finished()) {
6.112 //cout << "edge: ";
6.113 - if (GW::OutEdgeIt(bfs)!=INVALID) {
6.114 - cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
6.115 + if (GW::Edge(bfs)!=INVALID) {
6.116 + cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
6.117 node_name[gw.tail(bfs)] <<
6.118 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.119 node_name[gw.head(bfs)] <<
6.120 @@ -355,7 +341,7 @@
6.121 ": is not newly reached.");
6.122 } else {
6.123 cout << "invalid" << /*endl*/", " <<
6.124 - node_name[bfs.aNode()] <<
6.125 + node_name[bfs.tail()] <<
6.126 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.127
6.128 "invalid.";
6.129 @@ -380,8 +366,8 @@
6.130 while (!dfs.finished()) {
6.131 ++dfs;
6.132 //cout << "edge: ";
6.133 - if (GW::OutEdgeIt(dfs)!=INVALID) {
6.134 - cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
6.135 + if (GW::Edge(dfs)!=INVALID) {
6.136 + cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
6.137 node_name[gw.tail(dfs)] <<
6.138 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.139 node_name[gw.head(dfs)] <<
6.140 @@ -389,7 +375,7 @@
6.141 ": is not newly reached.");
6.142 } else {
6.143 cout << "invalid" << /*endl*/", " <<
6.144 - node_name[dfs.aNode()] <<
6.145 + node_name[dfs.tail()] <<
6.146 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
6.147
6.148 "invalid.";
7.1 --- a/src/work/marci/lg_vs_sg_vs_sg.cc Tue Aug 31 13:40:07 2004 +0000
7.2 +++ b/src/work/marci/lg_vs_sg_vs_sg.cc Tue Aug 31 17:54:22 2004 +0000
7.3 @@ -53,7 +53,7 @@
7.4
7.5 {
7.6 std::cout << "physical blocking flow augmentation ..." << std::endl;
7.7 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.8 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.9 ts.reset();
7.10 int i=0;
7.11 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
7.12 @@ -75,7 +75,7 @@
7.13
7.14 {
7.15 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
7.16 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.17 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.18 ts.reset();
7.19 int i=0;
7.20 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
7.21 @@ -86,7 +86,7 @@
7.22
7.23 {
7.24 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
7.25 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.26 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.27 ts.reset();
7.28 int i=0;
7.29 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
7.30 @@ -121,7 +121,7 @@
7.31
7.32 {
7.33 std::cout << "preflow ..." << std::endl;
7.34 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.35 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.36 ts.reset();
7.37 max_flow_test.run();
7.38 std::cout << "elapsed time: " << ts << std::endl;
7.39 @@ -130,7 +130,7 @@
7.40
7.41 {
7.42 std::cout << "physical blocking flow augmentation ..." << std::endl;
7.43 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.44 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.45 ts.reset();
7.46 int i=0;
7.47 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
7.48 @@ -152,7 +152,7 @@
7.49
7.50 {
7.51 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
7.52 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.53 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.54 ts.reset();
7.55 int i=0;
7.56 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
7.57 @@ -163,7 +163,7 @@
7.58
7.59 {
7.60 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
7.61 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.62 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.63 ts.reset();
7.64 int i=0;
7.65 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
7.66 @@ -198,7 +198,7 @@
7.67
7.68 {
7.69 std::cout << "preflow ..." << std::endl;
7.70 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.71 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.72 ts.reset();
7.73 max_flow_test.run();
7.74 std::cout << "elapsed time: " << ts << std::endl;
7.75 @@ -207,7 +207,7 @@
7.76
7.77 {
7.78 std::cout << "physical blocking flow augmentation ..." << std::endl;
7.79 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.80 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.81 ts.reset();
7.82 int i=0;
7.83 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
7.84 @@ -229,7 +229,7 @@
7.85
7.86 {
7.87 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
7.88 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.89 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.90 ts.reset();
7.91 int i=0;
7.92 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
7.93 @@ -240,7 +240,7 @@
7.94
7.95 {
7.96 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
7.97 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.98 + for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
7.99 ts.reset();
7.100 int i=0;
7.101 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
8.1 --- a/src/work/marci/max_flow_demo.cc Tue Aug 31 13:40:07 2004 +0000
8.2 +++ b/src/work/marci/max_flow_demo.cc Tue Aug 31 17:54:22 2004 +0000
8.3 @@ -1,4 +1,9 @@
8.4 // -*- c++ -*-
8.5 +
8.6 +// Use a DIMACS max flow file as stdin.
8.7 +// max_flow_demo < dimacs_max_flow_file
8.8 +
8.9 +
8.10 #include <iostream>
8.11 #include <fstream>
8.12
8.13 @@ -15,9 +20,6 @@
8.14
8.15 using namespace hugo;
8.16
8.17 -// Use a DIMACS max flow file as stdin.
8.18 -// max_flow_demo < dimacs_max_flow_file
8.19 -
8.20 int main(int, char **) {
8.21
8.22 typedef SageGraph MutableGraph;
8.23 @@ -102,23 +104,23 @@
8.24 }
8.25 }
8.26
8.27 -// {
8.28 -// std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
8.29 -// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
8.30 -// ts.reset();
8.31 -// int i=0;
8.32 -// while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
8.33 -// std::cout << "elapsed time: " << ts << std::endl;
8.34 -// std::cout << "number of augmentation phases: " << i << std::endl;
8.35 -// std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
8.36 + {
8.37 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
8.38 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
8.39 + ts.reset();
8.40 + int i=0;
8.41 + while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
8.42 + std::cout << "elapsed time: " << ts << std::endl;
8.43 + std::cout << "number of augmentation phases: " << i << std::endl;
8.44 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
8.45
8.46 -// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
8.47 -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
8.48 -// std::cout << "Slackness does not hold!" << std::endl;
8.49 -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
8.50 -// std::cout << "Slackness does not hold!" << std::endl;
8.51 -// }
8.52 -// }
8.53 + FOR_EACH_LOC(Graph::EdgeIt, e, g) {
8.54 + if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
8.55 + std::cout << "Slackness does not hold!" << std::endl;
8.56 + if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
8.57 + std::cout << "Slackness does not hold!" << std::endl;
8.58 + }
8.59 + }
8.60
8.61 {
8.62 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;