1.1 --- a/src/hugo/graph_wrapper.h Tue Sep 14 17:42:43 2004 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Wed Sep 15 10:34:12 2004 +0000
1.3 @@ -378,7 +378,12 @@
1.4 // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
1.5 NodeIt(Invalid i) : Node(i) { }
1.6 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
1.7 - Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
1.8 + Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
1.9 + while (*static_cast<Node*>(this)!=INVALID &&
1.10 + !(*(gw->edge_filter_map))[*this])
1.11 + *(static_cast<Node*>(this))=
1.12 + ++(typename Graph::NodeIt(*(gw->graph), *this));
1.13 + }
1.14 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.15 const Node& n) :
1.16 Node(n), gw(&_gw) { }
1.17 @@ -401,7 +406,12 @@
1.18 // OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
1.19 OutEdgeIt(Invalid i) : Edge(i) { }
1.20 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
1.21 - Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
1.22 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
1.23 + while (*static_cast<Edge*>(this)!=INVALID &&
1.24 + !(*(gw->edge_filter_map))[*this])
1.25 + *(static_cast<Edge*>(this))=
1.26 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.27 + }
1.28 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.29 const Edge& e) :
1.30 Edge(e), gw(&_gw) { }
1.31 @@ -423,7 +433,12 @@
1.32 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
1.33 InEdgeIt(Invalid i) : Edge(i) { }
1.34 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
1.35 - Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
1.36 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
1.37 + while (*static_cast<Edge*>(this)!=INVALID &&
1.38 + !(*(gw->edge_filter_map))[*this])
1.39 + *(static_cast<Edge*>(this))=
1.40 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.41 + }
1.42 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.43 const Edge& e) :
1.44 Edge(e), gw(&_gw) { }
1.45 @@ -445,7 +460,12 @@
1.46 // EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
1.47 EdgeIt(Invalid i) : Edge(i) { }
1.48 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
1.49 - Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
1.50 + Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
1.51 + while (*static_cast<Edge*>(this)!=INVALID &&
1.52 + !(*(gw->edge_filter_map))[*this])
1.53 + *(static_cast<Edge*>(this))=
1.54 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.55 + }
1.56 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.57 const Edge& e) :
1.58 Edge(e), gw(&_gw) { }
2.1 --- a/src/work/makefile Tue Sep 14 17:42:43 2004 +0000
2.2 +++ b/src/work/makefile Wed Sep 15 10:34:12 2004 +0000
2.3 @@ -1,5 +1,5 @@
2.4 INCLUDEDIRS ?= -I.. -I. -I./{marci,jacint,alpar,klao,akos}
2.5 -CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
2.6 +CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
2.7
2.8 BINARIES ?= bin_heap_demo
2.9
3.1 --- a/src/work/marci/augmenting_flow.h Tue Sep 14 17:42:43 2004 +0000
3.2 +++ b/src/work/marci/augmenting_flow.h Wed Sep 15 10:34:12 2004 +0000
3.3 @@ -1261,17 +1261,17 @@
3.4 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
3.5 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
3.6 res_graph_to_F[res_graph.head(e)]);
3.7 - original_edge.update();
3.8 + //original_edge.update();
3.9 original_edge.set(f, e);
3.10 - residual_capacity.update();
3.11 + //residual_capacity.update();
3.12 residual_capacity.set(f, res_graph.resCap(e));
3.13 } else {
3.14 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
3.15 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
3.16 res_graph_to_F[res_graph.head(e)]);
3.17 - original_edge.update();
3.18 + //original_edge.update();
3.19 original_edge.set(f, e);
3.20 - residual_capacity.update();
3.21 + //residual_capacity.update();
3.22 residual_capacity.set(f, res_graph.resCap(e));
3.23 }
3.24 }
3.25 @@ -1294,7 +1294,7 @@
3.26 dfs.pushAndSetReached(sF);
3.27 while (!dfs.finished()) {
3.28 ++dfs;
3.29 - if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
3.30 + if (typename MG::Edge(dfs)!=INVALID) {
3.31 if (dfs.isBNodeNewlyReached()) {
3.32 typename MG::Node v=F.tail(dfs);
3.33 typename MG::Node w=F.head(dfs);
3.34 @@ -1311,7 +1311,7 @@
3.35 }
3.36
3.37 } else {
3.38 - F.erase(/*typename MG::OutEdgeIt*/(dfs));
3.39 + F.erase(typename MG::Edge(dfs));
3.40 }
3.41 }
3.42 }
4.1 --- a/src/work/marci/max_flow_demo.cc Tue Sep 14 17:42:43 2004 +0000
4.2 +++ b/src/work/marci/max_flow_demo.cc Wed Sep 15 10:34:12 2004 +0000
4.3 @@ -3,30 +3,23 @@
4.4 // Use a DIMACS max flow file as stdin.
4.5 // max_flow_demo < dimacs_max_flow_file
4.6
4.7 -
4.8 #include <iostream>
4.9 #include <fstream>
4.10
4.11 -#include <sage_graph.h>
4.12 #include <hugo/smart_graph.h>
4.13 +#include <hugo/list_graph.h>
4.14 #include <hugo/dimacs.h>
4.15 #include <hugo/time_measure.h>
4.16 -//#include <graph_wrapper.h>
4.17 #include <hugo/preflow.h>
4.18 #include <augmenting_flow.h>
4.19 -//#include <preflow_res.h>
4.20 -#include <for_each_macros.h>
4.21 #include <graph_concept.h>
4.22
4.23 using namespace hugo;
4.24
4.25 int main(int, char **) {
4.26
4.27 - typedef SageGraph MutableGraph;
4.28 -
4.29 - //typedef FullFeatureGraphConcept Graph;
4.30 - //typedef SmartGraph Graph;
4.31 - typedef SageGraph Graph;
4.32 + typedef ListGraph MutableGraph;
4.33 + typedef SmartGraph Graph;
4.34 typedef Graph::Node Node;
4.35 typedef Graph::EdgeIt EdgeIt;
4.36
4.37 @@ -53,7 +46,7 @@
4.38 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
4.39 max_flow_test.minCut(cut);
4.40
4.41 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.42 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
4.43 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
4.44 std::cout << "Slackness does not hold!" << std::endl;
4.45 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
4.46 @@ -63,13 +56,13 @@
4.47
4.48 {
4.49 std::cout << "preflow ..." << std::endl;
4.50 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.51 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
4.52 ts.reset();
4.53 - max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
4.54 + max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
4.55 std::cout << "elapsed time: " << ts << std::endl;
4.56 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
4.57
4.58 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.59 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
4.60 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
4.61 std::cout << "Slackness does not hold!" << std::endl;
4.62 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
4.63 @@ -88,7 +81,7 @@
4.64
4.65 {
4.66 std::cout << "physical blocking flow augmentation ..." << std::endl;
4.67 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.68 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
4.69 ts.reset();
4.70 int i=0;
4.71 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
4.72 @@ -96,7 +89,7 @@
4.73 std::cout << "number of augmentation phases: " << i << std::endl;
4.74 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
4.75
4.76 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.77 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
4.78 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
4.79 std::cout << "Slackness does not hold!" << std::endl;
4.80 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
4.81 @@ -106,7 +99,7 @@
4.82
4.83 {
4.84 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
4.85 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.86 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
4.87 ts.reset();
4.88 int i=0;
4.89 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
4.90 @@ -114,7 +107,7 @@
4.91 std::cout << "number of augmentation phases: " << i << std::endl;
4.92 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
4.93
4.94 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.95 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
4.96 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
4.97 std::cout << "Slackness does not hold!" << std::endl;
4.98 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
4.99 @@ -124,7 +117,7 @@
4.100
4.101 {
4.102 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
4.103 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.104 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
4.105 ts.reset();
4.106 int i=0;
4.107 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
4.108 @@ -132,7 +125,7 @@
4.109 std::cout << "number of augmentation phases: " << i << std::endl;
4.110 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
4.111
4.112 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.113 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
4.114 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
4.115 std::cout << "Slackness does not hold!" << std::endl;
4.116 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
4.117 @@ -142,7 +135,7 @@
4.118
4.119 {
4.120 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
4.121 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.122 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
4.123 ts.reset();
4.124 int i=0;
4.125 while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
4.126 @@ -150,7 +143,7 @@
4.127 std::cout << "number of augmentation phases: " << i << std::endl;
4.128 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
4.129
4.130 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.131 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
4.132 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
4.133 std::cout << "Slackness does not hold!" << std::endl;
4.134 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)