# HG changeset patch
# User marci
# Date 1095244452 0
# Node ID baf0b6e40211bc8e585790e22cc28e577f6eb5f8
# Parent 4cb8f31c1ff84411ae5192ed260d21cd3e1f4194
correction of SubGraphWrapper bug.
diff -r 4cb8f31c1ff8 -r baf0b6e40211 src/hugo/graph_wrapper.h
--- a/src/hugo/graph_wrapper.h Tue Sep 14 17:42:43 2004 +0000
+++ b/src/hugo/graph_wrapper.h Wed Sep 15 10:34:12 2004 +0000
@@ -378,7 +378,12 @@
// NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
NodeIt(Invalid i) : Node(i) { }
NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
- Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
+ Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
+ while (*static_cast<Node*>(this)!=INVALID &&
+ !(*(gw->edge_filter_map))[*this])
+ *(static_cast<Node*>(this))=
+ ++(typename Graph::NodeIt(*(gw->graph), *this));
+ }
NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
const Node& n) :
Node(n), gw(&_gw) { }
@@ -401,7 +406,12 @@
// OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
OutEdgeIt(Invalid i) : Edge(i) { }
OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
- Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
+ Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
+ while (*static_cast<Edge*>(this)!=INVALID &&
+ !(*(gw->edge_filter_map))[*this])
+ *(static_cast<Edge*>(this))=
+ ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+ }
OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
const Edge& e) :
Edge(e), gw(&_gw) { }
@@ -423,7 +433,12 @@
// InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
InEdgeIt(Invalid i) : Edge(i) { }
InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
- Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
+ Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
+ while (*static_cast<Edge*>(this)!=INVALID &&
+ !(*(gw->edge_filter_map))[*this])
+ *(static_cast<Edge*>(this))=
+ ++(typename Graph::InEdgeIt(*(gw->graph), *this));
+ }
InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
const Edge& e) :
Edge(e), gw(&_gw) { }
@@ -445,7 +460,12 @@
// EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
EdgeIt(Invalid i) : Edge(i) { }
EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
- Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
+ Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
+ while (*static_cast<Edge*>(this)!=INVALID &&
+ !(*(gw->edge_filter_map))[*this])
+ *(static_cast<Edge*>(this))=
+ ++(typename Graph::EdgeIt(*(gw->graph), *this));
+ }
EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
const Edge& e) :
Edge(e), gw(&_gw) { }
diff -r 4cb8f31c1ff8 -r baf0b6e40211 src/work/makefile
--- a/src/work/makefile Tue Sep 14 17:42:43 2004 +0000
+++ b/src/work/makefile Wed Sep 15 10:34:12 2004 +0000
@@ -1,5 +1,5 @@
INCLUDEDIRS ?= -I.. -I. -I./{marci,jacint,alpar,klao,akos}
-CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
+CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
BINARIES ?= bin_heap_demo
diff -r 4cb8f31c1ff8 -r baf0b6e40211 src/work/marci/augmenting_flow.h
--- a/src/work/marci/augmenting_flow.h Tue Sep 14 17:42:43 2004 +0000
+++ b/src/work/marci/augmenting_flow.h Wed Sep 15 10:34:12 2004 +0000
@@ -1261,17 +1261,17 @@
dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
res_graph_to_F[res_graph.head(e)]);
- original_edge.update();
+ //original_edge.update();
original_edge.set(f, e);
- residual_capacity.update();
+ //residual_capacity.update();
residual_capacity.set(f, res_graph.resCap(e));
} else {
if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
res_graph_to_F[res_graph.head(e)]);
- original_edge.update();
+ //original_edge.update();
original_edge.set(f, e);
- residual_capacity.update();
+ //residual_capacity.update();
residual_capacity.set(f, res_graph.resCap(e));
}
}
@@ -1294,7 +1294,7 @@
dfs.pushAndSetReached(sF);
while (!dfs.finished()) {
++dfs;
- if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
+ if (typename MG::Edge(dfs)!=INVALID) {
if (dfs.isBNodeNewlyReached()) {
typename MG::Node v=F.tail(dfs);
typename MG::Node w=F.head(dfs);
@@ -1311,7 +1311,7 @@
}
} else {
- F.erase(/*typename MG::OutEdgeIt*/(dfs));
+ F.erase(typename MG::Edge(dfs));
}
}
}
diff -r 4cb8f31c1ff8 -r baf0b6e40211 src/work/marci/max_flow_demo.cc
--- a/src/work/marci/max_flow_demo.cc Tue Sep 14 17:42:43 2004 +0000
+++ b/src/work/marci/max_flow_demo.cc Wed Sep 15 10:34:12 2004 +0000
@@ -3,30 +3,23 @@
// Use a DIMACS max flow file as stdin.
// max_flow_demo < dimacs_max_flow_file
-
#include <iostream>
#include <fstream>
-#include <sage_graph.h>
#include <hugo/smart_graph.h>
+#include <hugo/list_graph.h>
#include <hugo/dimacs.h>
#include <hugo/time_measure.h>
-//#include <graph_wrapper.h>
#include <hugo/preflow.h>
#include <augmenting_flow.h>
-//#include <preflow_res.h>
-#include <for_each_macros.h>
#include <graph_concept.h>
using namespace hugo;
int main(int, char **) {
- typedef SageGraph MutableGraph;
-
- //typedef FullFeatureGraphConcept Graph;
- //typedef SmartGraph Graph;
- typedef SageGraph Graph;
+ typedef ListGraph MutableGraph;
+ typedef SmartGraph Graph;
typedef Graph::Node Node;
typedef Graph::EdgeIt EdgeIt;
@@ -53,7 +46,7 @@
std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
max_flow_test.minCut(cut);
- FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
std::cout << "Slackness does not hold!" << std::endl;
if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
@@ -63,13 +56,13 @@
{
std::cout << "preflow ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
- max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
+ max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
std::cout << "elapsed time: " << ts << std::endl;
std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
std::cout << "Slackness does not hold!" << std::endl;
if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
@@ -88,7 +81,7 @@
{
std::cout << "physical blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
@@ -96,7 +89,7 @@
std::cout << "number of augmentation phases: " << i << std::endl;
std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
std::cout << "Slackness does not hold!" << std::endl;
if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
@@ -106,7 +99,7 @@
{
std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
@@ -114,7 +107,7 @@
std::cout << "number of augmentation phases: " << i << std::endl;
std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
std::cout << "Slackness does not hold!" << std::endl;
if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
@@ -124,7 +117,7 @@
{
std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
@@ -132,7 +125,7 @@
std::cout << "number of augmentation phases: " << i << std::endl;
std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
std::cout << "Slackness does not hold!" << std::endl;
if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
@@ -142,7 +135,7 @@
{
std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
ts.reset();
int i=0;
while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
@@ -150,7 +143,7 @@
std::cout << "number of augmentation phases: " << i << std::endl;
std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
- FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+ for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
std::cout << "Slackness does not hold!" << std::endl;
if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)