# HG changeset patch
# User marci
# Date 1081183966 0
# Node ID 1b377a730d027d439d1c7c5b14ff50a2f50d5fcd
# Parent 2c52fc9781d49c6195ca29bdea0008f22fbcb3cb
konvergalunk, konvergalunk...
diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/bfs_iterator.h
--- a/src/work/marci/bfs_iterator.h Mon Apr 05 15:31:21 2004 +0000
+++ b/src/work/marci/bfs_iterator.h Mon Apr 05 16:52:46 2004 +0000
@@ -5,7 +5,6 @@
#include <queue>
#include <stack>
#include <utility>
-#include <graph_wrapper.h>
namespace hugo {
@@ -630,40 +629,34 @@
// };
- template <typename GraphWrapper, /*typename OutEdgeIt,*/
- typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
+ template <typename Graph, /*typename OutEdgeIt,*/
+ typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
class BfsIterator5 {
- typedef typename GraphWrapper::Node Node;
- typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
- GraphWrapper G;
+ protected:
+ typedef typename Graph::Node Node;
+ typedef typename Graph::OutEdgeIt OutEdgeIt;
+ const Graph* graph;
std::queue<Node> bfs_queue;
ReachedMap& reached;
bool b_node_newly_reached;
OutEdgeIt actual_edge;
bool own_reached_map;
public:
- BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
- G(_G), reached(_reached),
+ BfsIterator5(const Graph& _graph, ReachedMap& _reached) :
+ graph(&_graph), reached(_reached),
own_reached_map(false) { }
- BfsIterator5(const GraphWrapper& _G) :
- G(_G), reached(*(new ReachedMap(G /*, false*/))),
+ BfsIterator5(const Graph& _graph) :
+ graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
own_reached_map(true) { }
-// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
-// ReachedMap& _reached) :
-// G(_G), reached(_reached),
-// own_reached_map(false) { }
-// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
-// G(_G), reached(*(new ReachedMap(G /*, false*/))),
-// own_reached_map(true) { }
~BfsIterator5() { if (own_reached_map) delete &reached; }
void pushAndSetReached(Node s) {
reached.set(s, true);
if (bfs_queue.empty()) {
bfs_queue.push(s);
- G./*getF*/first(actual_edge, s);
- if (G.valid(actual_edge)/*.valid()*/) {
- Node w=G.bNode(actual_edge);
- if (!reached.get(w)) {
+ graph->first(actual_edge, s);
+ if (graph->valid(actual_edge)) {
+ Node w=graph->bNode(actual_edge);
+ if (!reached[w]) {
bfs_queue.push(w);
reached.set(w, true);
b_node_newly_reached=true;
@@ -675,13 +668,13 @@
bfs_queue.push(s);
}
}
- BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
+ BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
operator++() {
- if (G.valid(actual_edge)/*.valid()*/) {
- /*++*/G.next(actual_edge);
- if (G.valid(actual_edge)/*.valid()*/) {
- Node w=G.bNode(actual_edge);
- if (!reached.get(w)) {
+ if (graph->valid(actual_edge)) {
+ graph->next(actual_edge);
+ if (graph->valid(actual_edge)) {
+ Node w=graph->bNode(actual_edge);
+ if (!reached[w]) {
bfs_queue.push(w);
reached.set(w, true);
b_node_newly_reached=true;
@@ -692,10 +685,10 @@
} else {
bfs_queue.pop();
if (!bfs_queue.empty()) {
- G./*getF*/first(actual_edge, bfs_queue.front());
- if (G.valid(actual_edge)/*.valid()*/) {
- Node w=G.bNode(actual_edge);
- if (!reached.get(w)) {
+ graph->first(actual_edge, bfs_queue.front());
+ if (graph->valid(actual_edge)) {
+ Node w=graph->bNode(actual_edge);
+ if (!reached[w]) {
bfs_queue.push(w);
reached.set(w, true);
b_node_newly_reached=true;
@@ -710,9 +703,9 @@
bool finished() const { return bfs_queue.empty(); }
operator OutEdgeIt () const { return actual_edge; }
bool isBNodeNewlyReached() const { return b_node_newly_reached; }
- bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
+ bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
Node aNode() const { return bfs_queue.front(); }
- Node bNode() const { return G.bNode(actual_edge); }
+ Node bNode() const { return graph->bNode(actual_edge); }
const ReachedMap& getReachedMap() const { return reached; }
const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
};
@@ -773,12 +766,13 @@
// const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
// };
- template <typename GraphWrapper, /*typename OutEdgeIt,*/
- typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
+ template <typename Graph, /*typename OutEdgeIt,*/
+ typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
class DfsIterator5 {
- typedef typename GraphWrapper::Node Node;
- typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
- GraphWrapper G;
+ protected:
+ typedef typename Graph::Node Node;
+ typedef typename Graph::OutEdgeIt OutEdgeIt;
+ const Graph* graph;
std::stack<OutEdgeIt> dfs_stack;
bool b_node_newly_reached;
OutEdgeIt actual_edge;
@@ -786,36 +780,36 @@
ReachedMap& reached;
bool own_reached_map;
public:
- DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
- G(_G), reached(_reached),
+ DfsIterator5(const Graph& _graph, ReachedMap& _reached) :
+ graph(&_graph), reached(_reached),
own_reached_map(false) { }
- DfsIterator5(const GraphWrapper& _G) :
- G(_G), reached(*(new ReachedMap(G /*, false*/))),
+ DfsIterator5(const Graph& _graph) :
+ graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
own_reached_map(true) { }
~DfsIterator5() { if (own_reached_map) delete &reached; }
void pushAndSetReached(Node s) {
actual_node=s;
reached.set(s, true);
OutEdgeIt e;
- G.first(e, s);
+ graph->first(e, s);
dfs_stack.push(e);
}
- DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
+ DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
operator++() {
actual_edge=dfs_stack.top();
//actual_node=G.aNode(actual_edge);
- if (G.valid(actual_edge)/*.valid()*/) {
- Node w=G.bNode(actual_edge);
+ if (graph->valid(actual_edge)/*.valid()*/) {
+ Node w=graph->bNode(actual_edge);
actual_node=w;
- if (!reached.get(w)) {
+ if (!reached[w]) {
OutEdgeIt e;
- G.first(e, w);
+ graph->first(e, w);
dfs_stack.push(e);
reached.set(w, true);
b_node_newly_reached=true;
} else {
- actual_node=G.aNode(actual_edge);
- /*++*/G.next(dfs_stack.top());
+ actual_node=graph->aNode(actual_edge);
+ graph->next(dfs_stack.top());
b_node_newly_reached=false;
}
} else {
@@ -827,7 +821,7 @@
bool finished() const { return dfs_stack.empty(); }
operator OutEdgeIt () const { return actual_edge; }
bool isBNodeNewlyReached() const { return b_node_newly_reached; }
- bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
+ bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
Node aNode() const { return actual_node; /*FIXME*/}
Node bNode() const { return G.bNode(actual_edge); }
const ReachedMap& getReachedMap() const { return reached; }
diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/edmonds_karp.h
--- a/src/work/marci/edmonds_karp.h Mon Apr 05 15:31:21 2004 +0000
+++ b/src/work/marci/edmonds_karp.h Mon Apr 05 16:52:46 2004 +0000
@@ -8,6 +8,7 @@
#include <bfs_iterator.h>
#include <invalid.h>
+#include <graph_wrapper.h>
namespace hugo {
@@ -247,31 +248,29 @@
};
- template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
+ template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
class MaxFlow {
protected:
- typedef GraphWrapper GW;
- typedef typename GW::Node Node;
- typedef typename GW::Edge Edge;
- typedef typename GW::EdgeIt EdgeIt;
- typedef typename GW::OutEdgeIt OutEdgeIt;
- typedef typename GW::InEdgeIt InEdgeIt;
- //const Graph* G;
- GW gw;
+ typedef typename Graph::Node Node;
+ typedef typename Graph::Edge Edge;
+ typedef typename Graph::EdgeIt EdgeIt;
+ typedef typename Graph::OutEdgeIt OutEdgeIt;
+ typedef typename Graph::InEdgeIt InEdgeIt;
+ const Graph* g;
Node s;
Node t;
FlowMap* flow;
const CapacityMap* capacity;
- typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW;
+ typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
typedef typename ResGW::Edge ResGWEdge;
public:
- MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
- gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
+ MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
+ g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
bool augmentOnShortestPath() {
- ResGW res_graph(gw, *flow, *capacity);
+ ResGW res_graph(*g, *flow, *capacity);
bool _augment=false;
typedef typename ResGW::NodeMap<bool> ReachedMap;
@@ -290,8 +289,8 @@
Node v=res_graph.tail(e);
Node w=res_graph.head(e);
pred.set(w, e);
- if (res_graph.valid(pred.get(v))) {
- free.set(w, std::min(free.get(v), res_graph.resCap(e)));
+ if (res_graph.valid(pred[v])) {
+ free.set(w, std::min(free[v], res_graph.resCap(e)));
} else {
free.set(w, res_graph.resCap(e));
}
@@ -303,9 +302,9 @@
if (_augment) {
Node n=t;
- Number augment_value=free.get(t);
- while (res_graph.valid(pred.get(n))) {
- ResGWEdge e=pred.get(n);
+ Number augment_value=free[t];
+ while (res_graph.valid(pred[n])) {
+ ResGWEdge e=pred[n];
res_graph.augment(e, augment_value);
n=res_graph.tail(e);
}
@@ -317,14 +316,19 @@
template<typename MapGraphWrapper>
class DistanceMap {
protected:
- MapGraphWrapper gw;
+ const MapGraphWrapper* g;
typename MapGraphWrapper::NodeMap<int> dist;
public:
- DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
+ DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
- int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
- bool get(const typename MapGraphWrapper::Edge& e) const {
- return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
+ int operator[](const typename MapGraphWrapper::Node& n)
+ { return dist[n]; }
+// int get(const typename MapGraphWrapper::Node& n) const {
+// return dist[n]; }
+// bool get(const typename MapGraphWrapper::Edge& e) const {
+// return (dist.get(g->tail(e))<dist.get(g->head(e))); }
+ bool operator[](const typename MapGraphWrapper::Edge& e) const {
+ return (dist[g->tail(e)]<dist[g->head(e)]);
}
};
@@ -332,7 +336,7 @@
typedef MutableGraph MG;
bool _augment=false;
- ResGW res_graph(gw, *flow, *capacity);
+ ResGW res_graph(*g, *flow, *capacity);
typedef typename ResGW::NodeMap<bool> ReachedMap;
BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
@@ -343,7 +347,7 @@
while ( !bfs.finished() ) {
ResGWOutEdgeIt e=bfs;
if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
- dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+ dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
}
++bfs;
} //computing distances from s in the residual graph
@@ -359,8 +363,8 @@
}
}
- typename MG::Node sF=res_graph_to_F.get(s);
- typename MG::Node tF=res_graph_to_F.get(t);
+ typename MG::Node sF=res_graph_to_F[s];
+ typename MG::Node tF=res_graph_to_F[t];
typename MG::EdgeMap<ResGWEdge> original_edge(F);
typename MG::EdgeMap<Number> residual_capacity(F);
@@ -370,7 +374,7 @@
typename FilterResGW::EdgeIt e;
for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
//if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
- typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+ 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.set(f, e);
residual_capacity.update();
@@ -400,10 +404,10 @@
typename MG::Node v=F.aNode(dfs);
typename MG::Node w=F.bNode(dfs);
pred.set(w, dfs);
- if (F.valid(pred.get(v))) {
- free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+ if (F.valid(pred[v])) {
+ free.set(w, std::min(free[v], residual_capacity[dfs]));
} else {
- free.set(w, residual_capacity.get(dfs));
+ free.set(w, residual_capacity[dfs]);
}
if (w==tF) {
__augment=true;
@@ -419,15 +423,15 @@
if (__augment) {
typename MG::Node n=tF;
- Number augment_value=free.get(tF);
- while (F.valid(pred.get(n))) {
- typename MG::Edge e=pred.get(n);
- res_graph.augment(original_edge.get(e), augment_value);
+ Number augment_value=free[tF];
+ while (F.valid(pred[n])) {
+ typename MG::Edge e=pred[n];
+ res_graph.augment(original_edge[e], augment_value);
n=F.tail(e);
- if (residual_capacity.get(e)==augment_value)
+ if (residual_capacity[e]==augment_value)
F.erase(e);
else
- residual_capacity.set(e, residual_capacity.get(e)-augment_value);
+ residual_capacity.set(e, residual_capacity[e]-augment_value);
}
}
@@ -440,7 +444,7 @@
typedef MutableGraph MG;
bool _augment=false;
- ResGW res_graph(gw, *flow, *capacity);
+ ResGW res_graph(*g, *flow, *capacity);
//bfs for distances on the residual graph
typedef typename ResGW::NodeMap<bool> ReachedMap;
@@ -459,8 +463,8 @@
}
}
- typename MG::Node sF=res_graph_to_F.get(s);
- typename MG::Node tF=res_graph_to_F.get(t);
+ typename MG::Node sF=res_graph_to_F[s];
+ typename MG::Node tF=res_graph_to_F[t];
typename MG::EdgeMap<ResGWEdge> original_edge(F);
typename MG::EdgeMap<Number> residual_capacity(F);
@@ -468,15 +472,15 @@
ResGWOutEdgeIt e=bfs;
if (res_graph.valid(e)) {
if (bfs.isBNodeNewlyReached()) {
- dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
- typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+ 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.set(f, e);
residual_capacity.update();
residual_capacity.set(f, res_graph.resCap(e));
} else {
- if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
- typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+ 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.set(f, e);
residual_capacity.update();
@@ -508,10 +512,10 @@
typename MG::Node v=F.aNode(dfs);
typename MG::Node w=F.bNode(dfs);
pred.set(w, dfs);
- if (F.valid(pred.get(v))) {
- free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+ if (F.valid(pred[v])) {
+ free.set(w, std::min(free[v], residual_capacity[dfs]));
} else {
- free.set(w, residual_capacity.get(dfs));
+ free.set(w, residual_capacity[dfs]);
}
if (w==tF) {
__augment=true;
@@ -527,15 +531,15 @@
if (__augment) {
typename MG::Node n=tF;
- Number augment_value=free.get(tF);
- while (F.valid(pred.get(n))) {
- typename MG::Edge e=pred.get(n);
- res_graph.augment(original_edge.get(e), augment_value);
+ Number augment_value=free[tF];
+ while (F.valid(pred[n])) {
+ typename MG::Edge e=pred[n];
+ res_graph.augment(original_edge[e], augment_value);
n=F.tail(e);
- if (residual_capacity.get(e)==augment_value)
+ if (residual_capacity[e]==augment_value)
F.erase(e);
else
- residual_capacity.set(e, residual_capacity.get(e)-augment_value);
+ residual_capacity.set(e, residual_capacity[e]-augment_value);
}
}
@@ -547,7 +551,7 @@
bool augmentOnBlockingFlow2() {
bool _augment=false;
- ResGW res_graph(gw, *flow, *capacity);
+ ResGW res_graph(*g, *flow, *capacity);
typedef typename ResGW::NodeMap<bool> ReachedMap;
BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
@@ -557,7 +561,7 @@
while ( !bfs.finished() ) {
ResGWOutEdgeIt e=bfs;
if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
- dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+ dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
}
++bfs;
} //computing distances from s in the residual graph
@@ -610,8 +614,8 @@
typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
- if (erasing_res_graph.valid(pred.get(v))) {
- free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
+ if (erasing_res_graph.valid(pred[v])) {
+ free.set(w, std::min(free[v], res_graph.resCap(dfs)));
} else {
free.set(w, res_graph.resCap(dfs));
}
@@ -629,9 +633,9 @@
if (__augment) {
typename ErasingResGW::Node n=t;
- Number augment_value=free.get(n);
- while (erasing_res_graph.valid(pred.get(n))) {
- typename ErasingResGW::OutEdgeIt e=pred.get(n);
+ Number augment_value=free[n];
+ while (erasing_res_graph.valid(pred[n])) {
+ typename ErasingResGW::OutEdgeIt e=pred[n];
res_graph.augment(e, augment_value);
n=erasing_res_graph.tail(e);
if (res_graph.resCap(e)==0)
@@ -644,95 +648,6 @@
return _augment;
}
-// bool augmentOnBlockingFlow2() {
-// bool _augment=false;
-
-// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
-// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
-// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
-// typedef typename EAugGraph::Edge EAugEdge;
-
-// EAugGraph res_graph(*G, *flow, *capacity);
-
-// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
-// BfsIterator5<
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
-// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
-
-// bfs.pushAndSetReached(s);
-
-// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
-// NodeMap<int>& dist=res_graph.dist;
-
-// while ( !bfs.finished() ) {
-// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
-// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
-// }
-// ++bfs;
-// } //computing distances from s in the residual graph
-
-// bool __augment=true;
-
-// while (__augment) {
-
-// __augment=false;
-// //computing blocking flow with dfs
-// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
-// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
-// dfs(res_graph);
-// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
-// pred.set(s, EAugEdge(INVALID));
-// //invalid iterators for sources
-
-// typename EAugGraph::NodeMap<Number> free(res_graph);
-
-// dfs.pushAndSetReached(s);
-// while (!dfs.finished()) {
-// ++dfs;
-// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
-// if (dfs.isBNodeNewlyReached()) {
-
-// typename EAugGraph::Node v=res_graph.aNode(dfs);
-// typename EAugGraph::Node w=res_graph.bNode(dfs);
-
-// pred.set(w, EAugOutEdgeIt(dfs));
-// if (res_graph.valid(pred.get(v))) {
-// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
-// } else {
-// free.set(w, res_graph.free(dfs));
-// }
-
-// if (w==t) {
-// __augment=true;
-// _augment=true;
-// break;
-// }
-// } else {
-// res_graph.erase(dfs);
-// }
-// }
-
-// }
-
-// if (__augment) {
-// typename EAugGraph::Node n=t;
-// Number augment_value=free.get(t);
-// while (res_graph.valid(pred.get(n))) {
-// EAugEdge e=pred.get(n);
-// res_graph.augment(e, augment_value);
-// n=res_graph.tail(e);
-// if (res_graph.free(e)==0)
-// res_graph.erase(e);
-// }
-// }
-
-// }
-
-// return _augment;
-// }
-
void run() {
//int num_of_augmentations=0;
while (augmentOnShortestPath()) {
@@ -754,8 +669,8 @@
Number flowValue() {
Number a=0;
OutEdgeIt e;
- for(gw.first(e, s); gw.valid(e); gw.next(e)) {
- a+=flow->get(e);
+ for(g->first(e, s); g->valid(e); g->next(e)) {
+ a+=(*flow)[e];
}
return a;
}
diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/edmonds_karp_demo.cc
--- a/src/work/marci/edmonds_karp_demo.cc Mon Apr 05 15:31:21 2004 +0000
+++ b/src/work/marci/edmonds_karp_demo.cc Mon Apr 05 16:52:46 2004 +0000
@@ -3,11 +3,11 @@
#include <fstream>
#include <list_graph.h>
-#include <smart_graph.h>
+//#include <smart_graph.h>
#include <dimacs.h>
#include <edmonds_karp.h>
#include <time_measure.h>
-#include <graph_wrapper.h>
+//#include <graph_wrapper.h>
class CM {
public:
@@ -90,17 +90,14 @@
{
- typedef TrivGraphWrapper<const Graph> GW;
- GW gw(G);
std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
- GW::EdgeMap<int> flow(gw); //0 flow
+ Graph::EdgeMap<int> flow(G); //0 flow
Timer ts;
ts.reset();
- typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
- EMW cw(cap);
- MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
+ MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+ max_flow_test(G, s, t, flow, cap);
int i=0;
while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
@@ -121,17 +118,14 @@
}
{
- typedef TrivGraphWrapper<const Graph> GW;
- GW gw(G);
std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
- GW::EdgeMap<int> flow(gw); //0 flow
+ Graph::EdgeMap<int> flow(G); //0 flow
Timer ts;
ts.reset();
- typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
- EMW cw(cap);
- MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
+ MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+ max_flow_test(G, s, t, flow, cap);
int i=0;
while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
@@ -152,17 +146,14 @@
}
{
- typedef TrivGraphWrapper<const Graph> GW;
- GW gw(G);
std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
- GW::EdgeMap<int> flow(gw); //0 flow
+ Graph::EdgeMap<int> flow(G); //0 flow
Timer ts;
ts.reset();
- typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
- EMW cw(cap);
- MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
+ MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+ max_flow_test(G, s, t, flow, cap);
int i=0;
while (max_flow_test.augmentOnBlockingFlow2()) {
// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
@@ -183,17 +174,14 @@
}
{
- typedef TrivGraphWrapper<const Graph> GW;
- GW gw(G);
std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
- GW::EdgeMap<int> flow(gw); //0 flow
+ Graph::EdgeMap<int> flow(G); //0 flow
Timer ts;
ts.reset();
- typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
- EMW cw(cap);
- MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw);
+ MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+ max_flow_test(G, s, t, flow, cap);
int i=0;
while (max_flow_test.augmentOnShortestPath()) {
// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/experiment/iterator_bfs_demo.cc
--- a/src/work/marci/experiment/iterator_bfs_demo.cc Mon Apr 05 15:31:21 2004 +0000
+++ b/src/work/marci/experiment/iterator_bfs_demo.cc Mon Apr 05 16:52:46 2004 +0000
@@ -5,8 +5,8 @@
#include <list_graph.h>
//#include <smart_graph.h>
-#include <bfs_iterator_1.h>
-#include <graph_wrapper_1.h>
+#include <bfs_iterator.h>
+#include <graph_wrapper.h>
using namespace hugo;
using std::cout;
diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/experiment/iterator_bfs_demo_1.cc
--- a/src/work/marci/experiment/iterator_bfs_demo_1.cc Mon Apr 05 15:31:21 2004 +0000
+++ b/src/work/marci/experiment/iterator_bfs_demo_1.cc Mon Apr 05 16:52:46 2004 +0000
@@ -5,8 +5,8 @@
#include <list_graph.h>
#include <smart_graph.h>
-#include <bfs_iterator.h>
-#include <graph_wrapper.h>
+#include <bfs_iterator_1.h>
+#include <graph_wrapper_1.h>
using namespace hugo;
using std::cout;
diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/graph_wrapper.h
--- a/src/work/marci/graph_wrapper.h Mon Apr 05 15:31:21 2004 +0000
+++ b/src/work/marci/graph_wrapper.h Mon Apr 05 16:52:46 2004 +0000
@@ -12,7 +12,12 @@
Graph* graph;
public:
- typedef Graph BaseGraph;
+ typedef Graph ParentGraph;
+
+// TrivGraphWrapper() : graph(0) { }
+ TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
+// void setGraph(Graph& _graph) { graph = &_graph; }
+// Graph& getGraph() const { return *graph; }
typedef typename Graph::Node Node;
class NodeIt : public Graph::NodeIt {
@@ -24,7 +29,6 @@
Graph::NodeIt(*(_G.graph)) { }
};
typedef typename Graph::Edge Edge;
- //typedef typename Graph::OutEdgeIt OutEdgeIt;
class OutEdgeIt : public Graph::OutEdgeIt {
public:
OutEdgeIt() { }
@@ -33,7 +37,6 @@
OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
Graph::OutEdgeIt(*(_G.graph), n) { }
};
- //typedef typename Graph::InEdgeIt InEdgeIt;
class InEdgeIt : public Graph::InEdgeIt {
public:
InEdgeIt() { }
@@ -43,7 +46,6 @@
Graph::InEdgeIt(*(_G.graph), n) { }
};
//typedef typename Graph::SymEdgeIt SymEdgeIt;
- //typedef typename Graph::EdgeIt EdgeIt;
class EdgeIt : public Graph::EdgeIt {
public:
EdgeIt() { }
@@ -53,12 +55,6 @@
Graph::EdgeIt(*(_G.graph)) { }
};
- //TrivGraphWrapper() : graph(0) { }
- TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
-
-// void setGraph(Graph& _graph) { graph = &_graph; }
-// Graph& getGraph() const { return (*graph); }
-
NodeIt& first(NodeIt& i) const {
i=NodeIt(*this);
return i;
@@ -68,7 +64,6 @@
return i;
}
// template<typename I> I& first(I& i) const {
-// //return graph->first(i);
// i=I(*this);
// return i;
// }
@@ -81,7 +76,6 @@
return i;
}
// template<typename I, typename P> I& first(I& i, const P& p) const {
-// //return graph->first(i, p);
// i=I(*this, p);
// return i;
// }
@@ -91,16 +85,16 @@
template<typename I> I& next(I &i) const { graph->next(i); return i; }
template< typename It > It first() const {
- It e; first(e); return e; }
+ It e; this->first(e); return e; }
template< typename It > It first(const Node& v) const {
- It e; first(e, v); return e; }
+ It e; this->first(e, v); return e; }
Node head(const Edge& e) const { return graph->head(e); }
Node tail(const Edge& e) const { return graph->tail(e); }
- template<typename I> bool valid(const I& i) const
- { return graph->valid(i); }
+ template<typename I> bool valid(const I& i) const {
+ return graph->valid(i); }
//template<typename I> void setInvalid(const I &i);
//{ return graph->setInvalid(i); }
@@ -137,107 +131,103 @@
Graph::EdgeMap<T>(*(_G.graph), a) { }
};
- template<typename Map, typename T> class NodeMapWrapper {
- protected:
- Map* map;
- public:
- NodeMapWrapper(Map& _map) : map(&_map) { }
- //template<typename T>
- void set(Node n, T a) { map->set(n, a); }
- //template<typename T>
- T get(Node n) const { return map->get(n); }
- };
+// template<typename Map, typename T> class NodeMapWrapper {
+// protected:
+// Map* map;
+// public:
+// NodeMapWrapper(Map& _map) : map(&_map) { }
+// void set(Node n, T a) { map->set(n, a); }
+// T get(Node n) const { return map->get(n); }
+// };
- template<typename Map, typename T> class EdgeMapWrapper {
- protected:
- Map* map;
- public:
- EdgeMapWrapper(Map& _map) : map(&_map) { }
- //template<typename T>
- void set(Edge n, T a) { map->set(n, a); }
- //template<typename T>
- T get(Edge n) const { return map->get(n); }
- };
+// template<typename Map, typename T> class EdgeMapWrapper {
+// protected:
+// Map* map;
+// public:
+// EdgeMapWrapper(Map& _map) : map(&_map) { }
+// void set(Edge n, T a) { map->set(n, a); }
+// T get(Edge n) const { return map->get(n); }
+// };
};
- template<typename GraphWrapper>
- class GraphWrapperSkeleton {
+
+ template<typename Graph>
+ class GraphWrapper {
protected:
- GraphWrapper gw;
+ Graph* graph;
public:
- //typedef typename GraphWrapper::BaseGraph BaseGraph;
+ typedef Graph ParentGraph;
-// typedef typename GraphWrapper::Node Node;
-// typedef typename GraphWrapper::NodeIt NodeIt;
-
-// typedef typename GraphWrapper::Edge Edge;
-// typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
-// typedef typename GraphWrapper::InEdgeIt InEdgeIt;
-// //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
-// typedef typename GraphWrapper::EdgeIt EdgeIt;
-
- typedef typename GraphWrapper::Node Node;
- class NodeIt : public GraphWrapper::NodeIt {
+// GraphWrapper() : graph(0) { }
+ GraphWrapper(Graph& _graph) : graph(&_graph) { }
+// void setGraph(Graph& _graph) { graph=&_graph; }
+// Graph& getGraph() const { return *graph; }
+
+ typedef typename Graph::Node Node;
+ class NodeIt : public Graph::NodeIt {
public:
NodeIt() { }
- NodeIt(const typename GraphWrapper::NodeIt& n) :
- GraphWrapper::NodeIt(n) { }
- NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
- NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
- GraphWrapper::NodeIt(_G.gw) { }
+ NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
+ NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
+ NodeIt(const GraphWrapper<Graph>& _G) :
+ Graph::NodeIt(*(_G.graph)) { }
};
- typedef typename GraphWrapper::Edge Edge;
- //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
- class OutEdgeIt : public GraphWrapper::OutEdgeIt {
+ typedef typename Graph::Edge Edge;
+ class OutEdgeIt : public Graph::OutEdgeIt {
public:
OutEdgeIt() { }
- OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
- GraphWrapper::OutEdgeIt(e) { }
- OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
- OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
- GraphWrapper::OutEdgeIt(_G.gw, n) { }
+ OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
+ OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
+ OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
+ Graph::OutEdgeIt(*(_G.graph), n) { }
};
- //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
- class InEdgeIt : public GraphWrapper::InEdgeIt {
+ class InEdgeIt : public Graph::InEdgeIt {
public:
InEdgeIt() { }
- InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
- GraphWrapper::InEdgeIt(e) { }
- InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
- InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
- GraphWrapper::InEdgeIt(_G.gw, n) { }
+ InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
+ InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
+ InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
+ Graph::InEdgeIt(*(_G.graph), n) { }
};
- //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
- //typedef typename GraphWrapper::EdgeIt EdgeIt;
- class EdgeIt : public GraphWrapper::EdgeIt {
+ //typedef typename Graph::SymEdgeIt SymEdgeIt;
+ class EdgeIt : public Graph::EdgeIt {
public:
EdgeIt() { }
- EdgeIt(const typename GraphWrapper::EdgeIt& e) :
- GraphWrapper::EdgeIt(e) { }
- EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
- EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
- GraphWrapper::EdgeIt(_G.gw) { }
+ EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
+ EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
+ EdgeIt(const GraphWrapper<Graph>& _G) :
+ Graph::EdgeIt(*(_G.graph)) { }
};
-
-
- //GraphWrapperSkeleton() : gw() { }
- GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
-
- //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
- //BaseGraph& getGraph() const { return gw.getGraph(); }
-
- template<typename I> I& first(I& i) const {
- i=I(*this);
+
+ NodeIt& first(NodeIt& i) const {
+ i=NodeIt(*this);
return i;
}
- template<typename I, typename P> I& first(I& i, const P& p) const {
- i=I(*this, p);
- return i;
+ EdgeIt& first(EdgeIt& i) const {
+ i=EdgeIt(*this);
+ return i;
}
+// template<typename I> I& first(I& i) const {
+// i=I(*this);
+// return i;
+// }
+ OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
+ i=OutEdgeIt(*this, p);
+ return i;
+ }
+ InEdgeIt& first(InEdgeIt& i, const Node& p) const {
+ i=InEdgeIt(*this, p);
+ return i;
+ }
+// template<typename I, typename P> I& first(I& i, const P& p) const {
+// i=I(*this, p);
+// return i;
+// }
-// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
- template<typename I> I& next(I &i) const { gw.next(i); return i; }
+// template<typename I> I getNext(const I& i) const {
+// return gw.getNext(i); }
+ template<typename I> I& next(I &i) const { graph->next(i); return i; }
template< typename It > It first() const {
It e; this->first(e); return e; }
@@ -245,45 +235,49 @@
template< typename It > It first(const Node& v) const {
It e; this->first(e, v); return e; }
- Node head(const Edge& e) const { return gw.head(e); }
- Node tail(const Edge& e) const { return gw.tail(e); }
+ Node head(const Edge& e) const { return graph->head(e); }
+ Node tail(const Edge& e) const { return graph->tail(e); }
- template<typename I> bool valid(const I& i) const { return gw.valid(i); }
+ template<typename I> bool valid(const I& i) const {
+ return graph->valid(i); }
//template<typename I> void setInvalid(const I &i);
//{ return graph->setInvalid(i); }
- int nodeNum() const { return gw.nodeNum(); }
- int edgeNum() const { return gw.edgeNum(); }
+ int nodeNum() const { return graph->nodeNum(); }
+ int edgeNum() const { return graph->edgeNum(); }
- template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
- template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
+ template<typename I> Node aNode(const I& e) const {
+ return graph->aNode(e); }
+ template<typename I> Node bNode(const I& e) const {
+ return graph->bNode(e); }
- Node addNode() const { return gw.addNode(); }
+ Node addNode() const { return graph->addNode(); }
Edge addEdge(const Node& tail, const Node& head) const {
- return gw.addEdge(tail, head); }
+ return graph->addEdge(tail, head); }
- template<typename I> void erase(const I& i) const { gw.erase(i); }
+ template<typename I> void erase(const I& i) const { graph->erase(i); }
- void clear() const { gw.clear(); }
+ void clear() const { graph->clear(); }
- template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
+ template<typename T> class NodeMap : public Graph::NodeMap<T> {
public:
- NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
- GraphWrapper::NodeMap<T>(_G.gw) { }
- NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
- GraphWrapper::NodeMap<T>(_G.gw, a) { }
+ NodeMap(const GraphWrapper<Graph>& _G) :
+ Graph::NodeMap<T>(*(_G.graph)) { }
+ NodeMap(const GraphWrapper<Graph>& _G, T a) :
+ Graph::NodeMap<T>(*(_G.graph), a) { }
};
- template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
+ template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
public:
- EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
- GraphWrapper::EdgeMap<T>(_G.gw) { }
- EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
- GraphWrapper::EdgeMap<T>(_G.gw, a) { }
+ EdgeMap(const GraphWrapper<Graph>& _G) :
+ Graph::EdgeMap<T>(*(_G.graph)) { }
+ EdgeMap(const GraphWrapper<Graph>& _G, T a) :
+ Graph::EdgeMap<T>(*(_G.graph), a) { }
};
};
+
// template<typename Graph>
// class RevGraphWrapper
// {
@@ -291,7 +285,7 @@
// Graph* graph;
// public:
-// typedef Graph BaseGraph;
+// typedef Graph ParentGraph;
// typedef typename Graph::Node Node;
// typedef typename Graph::NodeIt NodeIt;
@@ -364,139 +358,59 @@
// };
// };
-// template<typename /*Graph*/GraphWrapper
-// /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >
-// class RevGraphWrapper :
-// public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {
-// protected:
-// //Graph* graph;
-
-// public:
-// //typedef Graph BaseGraph;
-// //typedef typename Graph::Node Node;
-// //typedef typename Graph::NodeIt NodeIt;
-
-// //typedef typename Graph::Edge Edge;
-// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
-// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;
-// //typedef typename Graph::SymEdgeIt SymEdgeIt;
-// //typedef typename Graph::EdgeIt EdgeIt;
-
-// //RevGraphWrapper() : graph(0) { }
-// RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }
-
-// //void setGraph(Graph& _graph) { graph = &_graph; }
-// //Graph& getGraph() const { return (*graph); }
-
-// //template<typename I> I& first(I& i) const { return graph->first(i); }
-// //template<typename I, typename P> I& first(I& i, const P& p) const {
-// // return graph->first(i, p); }
-
-// //template<typename I> I getNext(const I& i) const {
-// // return graph->getNext(i); }
-// //template<typename I> I& next(I &i) const { return graph->next(i); }
-
-// //template< typename It > It first() const {
-// // It e; first(e); return e; }
-
-// //template< typename It > It first(const Node& v) const {
-// // It e; first(e, v); return e; }
-
-// //Node head(const Edge& e) const { return graph->tail(e); }
-// //Node tail(const Edge& e) const { return graph->head(e); }
-
-// //template<typename I> bool valid(const I& i) const
-// // { return graph->valid(i); }
-
-// //template<typename I> void setInvalid(const I &i);
-// //{ return graph->setInvalid(i); }
-
-// //template<typename I> Node aNode(const I& e) const {
-// // return graph->aNode(e); }
-// //template<typename I> Node bNode(const I& e) const {
-// // return graph->bNode(e); }
-
-// //Node addNode() const { return graph->addNode(); }
-// //Edge addEdge(const Node& tail, const Node& head) const {
-// // return graph->addEdge(tail, head); }
-
-// //int nodeNum() const { return graph->nodeNum(); }
-// //int edgeNum() const { return graph->edgeNum(); }
-
-// //template<typename I> void erase(const I& i) const { graph->erase(i); }
-
-// //void clear() const { graph->clear(); }
-
-// template<typename T> class NodeMap :
-// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>
-// {
-// public:
-// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
-// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
-// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
-// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
-// };
-
-// template<typename T> class EdgeMap :
-// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
-// public:
-// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
-// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
-// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
-// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
-// };
-// };
-
- template<typename GraphWrapper>
- class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
+ template<typename Graph>
+ class RevGraphWrapper : public GraphWrapper<Graph> {
public:
- typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
+ typedef typename GraphWrapper<Graph>::Node Node;
+ typedef typename GraphWrapper<Graph>::Edge Edge;
//FIXME
- //If GraphWrapper::OutEdgeIt is not defined
+ //If Graph::OutEdgeIt is not defined
//and we do not want to use RevGraphWrapper::InEdgeIt,
//this won't work, because of typedef
//OR
//graphs have to define their non-existing iterators to void
//Unfortunately all the typedefs are instantiated in templates,
//unlike other stuff
- typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;
+ typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
+ typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
- RevGraphWrapper(GraphWrapper _gw) :
- GraphWrapperSkeleton<GraphWrapper>(_gw) { }
+// RevGraphWrapper() : GraphWrapper<Graph>() { }
+ RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
Node head(const Edge& e) const
- { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }
+ { return GraphWrapper<Graph>::tail(e); }
Node tail(const Edge& e) const
- { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
+ { return GraphWrapper<Graph>::head(e); }
};
//Subgraph on the same node-set and partial edge-set
- template<typename GraphWrapper, typename EdgeFilterMap>
- class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
+ template<typename Graph, typename EdgeFilterMap>
+ class SubGraphWrapper : public GraphWrapper<Graph> {
protected:
EdgeFilterMap* filter_map;
public:
- typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
+ typedef typename GraphWrapper<Graph>::Node Node;
+ typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
+ typedef typename GraphWrapper<Graph>::Edge Edge;
+ typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
+ typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
+ typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
- SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
- GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }
+// SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
+ SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) :
+ GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { }
template<typename I> I& first(I& i) const {
- gw.first(i);
- while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+ graph->first(i);
+ //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
+ while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
return i;
}
template<typename I, typename P> I& first(I& i, const P& p) const {
- gw.first(i, p);
- while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+ graph->first(i, p);
+// while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
+ while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
return i;
}
@@ -504,8 +418,9 @@
// return gw.getNext(i);
//}
template<typename I> I& next(I &i) const {
- gw.next(i);
- while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+ graph->next(i);
+// while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
+ while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
return i;
}
@@ -523,7 +438,7 @@
// GraphWrapper gw;
// public:
-// typedef GraphWrapper BaseGraph;
+// typedef GraphWrapper ParentGraph;
// typedef typename GraphWrapper::Node Node;
// typedef typename GraphWrapper::NodeIt NodeIt;
@@ -676,39 +591,21 @@
// };
- template<typename GraphWrapper>
- class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
+ template<typename Graph>
+ class UndirGraphWrapper : public GraphWrapper<Graph> {
protected:
-// GraphWrapper gw;
+ typedef typename Graph::Edge GraphEdge;
+ typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
+ typedef typename Graph::InEdgeIt GraphInEdgeIt;
+ public:
+ typedef typename GraphWrapper<Graph>::Node Node;
+ typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
- public:
- //typedef GraphWrapper BaseGraph;
+// UndirGraphWrapper() : GraphWrapper<Graph>() { }
+ UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
- typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
-
- //private:
- //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy
- //legyenek, at kell irni
- typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
- GraphWrapper::Edge GraphEdge;
- typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
- GraphWrapper::OutEdgeIt GraphOutEdgeIt;
- typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
- GraphWrapper::InEdgeIt GraphInEdgeIt;
- //public:
-
- //UndirGraphWrapper() : graph(0) { }
- UndirGraphWrapper(GraphWrapper _gw) :
- GraphWrapperSkeleton<GraphWrapper>(_gw) { }
-
- //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
-
- //void setGraph(Graph& _graph) { graph = &_graph; }
- //Graph& getGraph() const { return (*graph); }
-
class Edge {
- friend class UndirGraphWrapper<GraphWrapper>;
+ friend class UndirGraphWrapper<Graph>;
protected:
bool out_or_in; //true iff out
GraphOutEdgeIt out;
@@ -741,42 +638,42 @@
};
class OutEdgeIt : public Edge {
- friend class UndirGraphWrapper<GraphWrapper>;
+ friend class UndirGraphWrapper<Graph>;
public:
OutEdgeIt() : Edge() { }
OutEdgeIt(const Invalid& i) : Edge(i) { }
- OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
+ OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
: Edge() {
- out_or_in=true; _G.gw.first(out, n);
- if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); }
+ out_or_in=true; _G.graph->first(out, n);
+ if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
}
};
typedef OutEdgeIt InEdgeIt;
class EdgeIt : public Edge {
- friend class UndirGraphWrapper<GraphWrapper>;
+ friend class UndirGraphWrapper<Graph>;
protected:
NodeIt v;
public:
EdgeIt() : Edge() { }
EdgeIt(const Invalid& i) : Edge(i) { }
- EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
+ EdgeIt(const UndirGraphWrapper<Graph>& _G)
: Edge() {
out_or_in=true;
//Node v;
_G.first(v);
- if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
- while (_G.valid(v) && !_G.gw.valid(out)) {
- _G.gw.next(v);
- if (_G.valid(v)) _G.gw.first(out);
+ if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
+ while (_G.valid(v) && !_G.graph->valid(out)) {
+ _G.graph->next(v);
+ if (_G.valid(v)) _G.graph->first(out);
}
}
};
OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
- e.out_or_in=true; gw.first(e.out, n);
- if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }
+ e.out_or_in=true; graph->first(e.out, n);
+ if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }
return e;
}
@@ -784,47 +681,47 @@
e.out_or_in=true;
//NodeIt v;
first(e.v);
- if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
- while (valid(e.v) && !gw.valid(e.out)) {
- gw.next(e.v);
- if (valid(e.v)) gw.first(e.out, e.v);
+ if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;
+ while (valid(e.v) && !graph->valid(e.out)) {
+ graph->next(e.v);
+ if (valid(e.v)) graph->first(e.out, e.v);
}
return e;
}
- template<typename I> I& first(I& i) const { gw.first(i); return i; }
+ template<typename I> I& first(I& i) const { graph->first(i); return i; }
template<typename I, typename P> I& first(I& i, const P& p) const {
- gw.first(i, p); return i; }
+ graph->first(i, p); return i; }
OutEdgeIt& next(OutEdgeIt& e) const {
if (e.out_or_in) {
- Node n=gw.tail(e.out);
- gw.next(e.out);
- if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
+ Node n=graph->tail(e.out);
+ graph->next(e.out);
+ if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
} else {
- gw.next(e.in);
+ graph->next(e.in);
}
return e;
}
EdgeIt& next(EdgeIt& e) const {
//NodeIt v=tail(e);
- gw.next(e.out);
- while (valid(e.v) && !gw.valid(e.out)) {
+ graph->next(e.out);
+ while (valid(e.v) && !graph->valid(e.out)) {
next(e.v);
- if (valid(e.v)) gw.first(e.out, e.v);
+ if (valid(e.v)) graph->first(e.out, e.v);
}
return e;
}
- template<typename I> I& next(I &i) const { return gw.next(i); }
+ template<typename I> I& next(I &i) const { return graph->next(i); }
// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
template< typename It > It first() const {
- It e; first(e); return e; }
+ It e; this->first(e); return e; }
template< typename It > It first(const Node& v) const {
- It e; first(e, v); return e; }
+ It e; this->first(e, v); return e; }
// Node head(const Edge& e) const { return gw.head(e); }
// Node tail(const Edge& e) const { return gw.tail(e); }
@@ -841,9 +738,9 @@
// return graph->bNode(e); }
Node aNode(const OutEdgeIt& e) const {
- if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
+ if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
Node bNode(const OutEdgeIt& e) const {
- if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
+ if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
// Node addNode() const { return gw.addNode(); }
@@ -855,21 +752,21 @@
// void clear() const { gw.clear(); }
-// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
+// template<typename T> class NodeMap : public Graph::NodeMap<T> {
// public:
-// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
-// GraphWrapper::NodeMap<T>(_G.gw) { }
-// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
-// GraphWrapper::NodeMap<T>(_G.gw, a) { }
+// NodeMap(const UndirGraphWrapper<Graph>& _G) :
+// Graph::NodeMap<T>(_G.gw) { }
+// NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
+// Graph::NodeMap<T>(_G.gw, a) { }
// };
// template<typename T> class EdgeMap :
-// public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
+// public GraphWrapperSkeleton<Graph>::EdgeMap<T> {
// public:
-// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
-// GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
-// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
-// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
+// EdgeMap(const UndirGraphWrapper<Graph>& _G) :
+// GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }
+// EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
+// Graph::EdgeMap<T>(_G.gw, a) { }
// };
};
@@ -883,7 +780,7 @@
// Graph* graph;
// public:
-// typedef Graph BaseGraph;
+// typedef Graph ParentGraph;
// typedef typename Graph::Node Node;
// typedef typename Graph::Edge Edge;
@@ -946,32 +843,22 @@
// };
- template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
- class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{
+ template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+ class ResGraphWrapper : public GraphWrapper<Graph>{
public:
- //typedef Graph BaseGraph;
- //typedef TrivGraphWrapper<const Graph> GraphWrapper;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
- private:
- typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
- GraphWrapper::OutEdgeIt OldOutEdgeIt;
- typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
- GraphWrapper::InEdgeIt OldInEdgeIt;
+ typedef typename GraphWrapper<Graph>::Node Node;
+ typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
protected:
- //const Graph* graph;
- //GraphWrapper gw;
+ typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
+ typedef typename Graph::InEdgeIt GraphInEdgeIt;
+ typedef typename Graph::Edge GraphEdge;
FlowMap* flow;
const CapacityMap* capacity;
public:
- ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,
+ ResGraphWrapper(Graph& _graph, FlowMap& _flow,
const CapacityMap& _capacity) :
- GraphWrapperSkeleton<GraphWrapper>(_gw),
- flow(&_flow), capacity(&_capacity) { }
-
- //void setGraph(const Graph& _graph) { graph = &_graph; }
- //const Graph& getGraph() const { return (*graph); }
+ GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
class Edge;
class OutEdgeIt;
@@ -979,11 +866,11 @@
friend class OutEdgeIt;
class Edge {
- friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
+ friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
protected:
bool out_or_in; //true, iff out
- OldOutEdgeIt out;
- OldInEdgeIt in;
+ GraphOutEdgeIt out;
+ GraphInEdgeIt in;
public:
Edge() : out_or_in(true) { }
Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
@@ -1001,24 +888,27 @@
else
return (u.out_or_in || u.in!=v.in);
}
+ operator GraphEdge() const {
+ if (out_or_in) return(out); else return(in);
+ }
};
class OutEdgeIt : public Edge {
- friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
+ friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
public:
OutEdgeIt() { }
//FIXME
OutEdgeIt(const Edge& e) : Edge(e) { }
OutEdgeIt(const Invalid& i) : Edge(i) { }
protected:
- OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
- resG.gw.first(out, v);
- while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
- if (!resG.gw.valid(out)) {
+ OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
+ resG.graph->first(out, v);
+ while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
+ if (!resG.graph->valid(out)) {
out_or_in=0;
- resG.gw.first(in, v);
- while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
+ resG.graph->first(in, v);
+ while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
}
}
// public:
@@ -1044,30 +934,30 @@
typedef void InEdgeIt;
class EdgeIt : public Edge {
- friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
+ friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
NodeIt v;
public:
EdgeIt() { }
//EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
EdgeIt(const Invalid& i) : Edge(i) { }
- EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
- resG.gw.first(v);
- if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
- while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
- while (resG.gw.valid(v) && !resG.gw.valid(out)) {
- resG.gw.next(v);
- if (resG.gw.valid(v)) resG.gw.first(out, v);
- while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
+ EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
+ resG.graph->first(v);
+ if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
+ while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
+ while (resG.graph->valid(v) && !resG.graph->valid(out)) {
+ resG.graph->next(v);
+ if (resG.graph->valid(v)) resG.graph->first(out, v);
+ while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
}
- if (!resG.gw.valid(out)) {
+ if (!resG.graph->valid(out)) {
out_or_in=0;
- resG.gw.first(v);
- if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
- while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
- while (resG.gw.valid(v) && !resG.gw.valid(in)) {
- resG.gw.next(v);
- if (resG.gw.valid(v)) resG.gw.first(in, v);
- while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
+ resG.graph->first(v);
+ if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
+ while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
+ while (resG.graph->valid(v) && !resG.graph->valid(in)) {
+ resG.graph->next(v);
+ if (resG.graph->valid(v)) resG.graph->first(in, v);
+ while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
}
}
}
@@ -1083,7 +973,7 @@
// if (!out.valid()) {
// out_or_in=0;
// G->first(v);
-// if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
+// if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
// while (v.valid() && !in.valid()) {
// ++v;
@@ -1104,7 +994,7 @@
// }
};
- NodeIt& first(NodeIt& v) const { gw.first(v); return v; }
+ NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
OutEdgeIt& first(OutEdgeIt& e, Node v) const {
e=OutEdgeIt(*this, v);
return e;
@@ -1114,52 +1004,52 @@
return e;
}
- NodeIt& next(NodeIt& n) const { return gw.next(n); }
+ NodeIt& next(NodeIt& n) const { return graph->next(n); }
OutEdgeIt& next(OutEdgeIt& e) const {
if (e.out_or_in) {
- Node v=gw.aNode(e.out);
- gw.next(e.out);
- while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
- if (!gw.valid(e.out)) {
+ Node v=graph->aNode(e.out);
+ graph->next(e.out);
+ while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
+ if (!graph->valid(e.out)) {
e.out_or_in=0;
- gw.first(e.in, v);
- while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
+ graph->first(e.in, v);
+ while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
}
} else {
- gw.next(e.in);
- while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
+ graph->next(e.in);
+ while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
}
return e;
}
EdgeIt& next(EdgeIt& e) const {
if (e.out_or_in) {
- gw.next(e.out);
- while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
- while (gw.valid(e.v) && !gw.valid(e.out)) {
- gw.next(e.v);
- if (gw.valid(e.v)) gw.first(e.out, e.v);
- while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
+ graph->next(e.out);
+ while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
+ while (graph->valid(e.v) && !graph->valid(e.out)) {
+ graph->next(e.v);
+ if (graph->valid(e.v)) graph->first(e.out, e.v);
+ while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
}
- if (!gw.valid(e.out)) {
+ if (!graph->valid(e.out)) {
e.out_or_in=0;
- gw.first(e.v);
- if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
- while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
- while (gw.valid(e.v) && !gw.valid(e.in)) {
- gw.next(e.v);
- if (gw.valid(e.v)) gw.first(e.in, e.v);
- while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
+ graph->first(e.v);
+ if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
+ while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
+ while (graph->valid(e.v) && !graph->valid(e.in)) {
+ graph->next(e.v);
+ if (graph->valid(e.v)) graph->first(e.in, e.v);
+ while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
}
}
} else {
- gw.next(e.in);
- while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
- while (gw.valid(e.v) && !gw.valid(e.in)) {
- gw.next(e.v);
- if (gw.valid(e.v)) gw.first(e.in, e.v);
- while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
+ graph->next(e.in);
+ while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
+ while (graph->valid(e.v) && !graph->valid(e.in)) {
+ graph->next(e.v);
+ if (graph->valid(e.v)) graph->first(e.in, e.v);
+ while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
}
}
return e;
@@ -1181,54 +1071,60 @@
}
Node tail(Edge e) const {
- return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
+ return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
Node head(Edge e) const {
- return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
+ return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
Node aNode(OutEdgeIt e) const {
- return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
+ return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
Node bNode(OutEdgeIt e) const {
- return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
+ return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
- int nodeNum() const { return gw.nodeNum(); }
+ int nodeNum() const { return graph->nodeNum(); }
//FIXME
- //int edgeNum() const { return gw.edgeNum(); }
+ //int edgeNum() const { return graph->edgeNum(); }
- int id(Node v) const { return gw.id(v); }
+ int id(Node v) const { return graph->id(v); }
- bool valid(Node n) const { return gw.valid(n); }
+ bool valid(Node n) const { return graph->valid(n); }
bool valid(Edge e) const {
- return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }
+ return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
void augment(const Edge& e, Number a) const {
if (e.out_or_in)
- flow->set(e.out, flow->get(e.out)+a);
+// flow->set(e.out, flow->get(e.out)+a);
+ flow->set(e.out, (*flow)[e.out]+a);
else
- flow->set(e.in, flow->get(e.in)-a);
+// flow->set(e.in, flow->get(e.in)-a);
+ flow->set(e.in, (*flow)[e.in]-a);
}
Number resCap(const Edge& e) const {
if (e.out_or_in)
- return (capacity->get(e.out)-flow->get(e.out));
+// return (capacity->get(e.out)-flow->get(e.out));
+ return ((*capacity)[e.out]-(*flow)[e.out]);
else
- return (flow->get(e.in));
+// return (flow->get(e.in));
+ return ((*flow)[e.in]);
}
- Number resCap(OldOutEdgeIt out) const {
- return (capacity->get(out)-flow->get(out));
+ Number resCap(GraphOutEdgeIt out) const {
+// return (capacity->get(out)-flow->get(out));
+ return ((*capacity)[out]-(*flow)[out]);
}
- Number resCap(OldInEdgeIt in) const {
- return (flow->get(in));
+ Number resCap(GraphInEdgeIt in) const {
+// return (flow->get(in));
+ return ((*flow)[in]);
}
-// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
+// template<typename T> class NodeMap : public Graph::NodeMap<T> {
// public:
-// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
-// : GraphWrapper::NodeMap<T>(_G.gw) { }
-// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
-// T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
+// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
+// : Graph::NodeMap<T>(_G.gw) { }
+// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
+// T a) : Graph::NodeMap<T>(_G.gw, a) { }
// };
// template <typename T>
@@ -1243,53 +1139,59 @@
template <typename T>
class EdgeMap {
- typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
+ typename Graph::EdgeMap<T> forward_map, backward_map;
public:
- EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
- EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
+ EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
+ EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
void set(Edge e, T a) {
if (e.out_or_in)
forward_map.set(e.out, a);
else
backward_map.set(e.in, a);
}
- T get(Edge e) {
+ T operator[](Edge e) const {
if (e.out_or_in)
- return forward_map.get(e.out);
+ return forward_map[e.out];
else
- return backward_map.get(e.in);
+ return backward_map[e.in];
}
+// T get(Edge e) const {
+// if (e.out_or_in)
+// return forward_map.get(e.out);
+// else
+// return backward_map.get(e.in);
+// }
};
};
- //Subgraph on the same node-set and partial edge-set
- template<typename GraphWrapper, typename FirstOutEdgesMap>
- class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
+ //ErasingFirstGraphWrapper for blocking flows
+ template<typename Graph, typename FirstOutEdgesMap>
+ class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
protected:
FirstOutEdgesMap* first_out_edges;
public:
- typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
- typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
+ typedef typename GraphWrapper<Graph>::Node Node;
+ typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
+ typedef typename GraphWrapper<Graph>::Edge Edge;
+ typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
+ typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
+ typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
- ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :
- GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }
+ ErasingFirstGraphWrapper(Graph& _graph,
+ FirstOutEdgesMap& _first_out_edges) :
+ GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
template<typename I> I& first(I& i) const {
- gw.first(i);
- //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+ graph->first(i);
return i;
}
OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
- e=first_out_edges->get(n);
+// e=first_out_edges->get(n);
+ e=(*first_out_edges)[n];
return e;
}
template<typename I, typename P> I& first(I& i, const P& p) const {
- gw.first(i, p);
- //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+ graph->first(i, p);
return i;
}
@@ -1297,8 +1199,7 @@
// return gw.getNext(i);
//}
template<typename I> I& next(I &i) const {
- gw.next(i);
- //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+ graph->next(i);
return i;
}
@@ -1315,246 +1216,6 @@
}
};
-// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
-// class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
-// protected:
-// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
-// //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
-// public:
-// ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
-// const CapacityMap& _capacity) :
-// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
-// first_out_edges(*this) /*, dist(*this)*/ {
-// for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
-// OutEdgeIt e;
-// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
-// first_out_edges.set(n, e);
-// }
-// }
-
-// //void setGraph(Graph& _graph) { graph = &_graph; }
-// //Graph& getGraph() const { return (*graph); }
-
-// //TrivGraphWrapper() : graph(0) { }
-// //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
-
-// //typedef Graph BaseGraph;
-
-// //typedef typename Graph::Node Node;
-// //typedef typename Graph::NodeIt NodeIt;
-
-// //typedef typename Graph::Edge Edge;
-// //typedef typename Graph::OutEdgeIt OutEdgeIt;
-// //typedef typename Graph::InEdgeIt InEdgeIt;
-// //typedef typename Graph::SymEdgeIt SymEdgeIt;
-// //typedef typename Graph::EdgeIt EdgeIt;
-
-// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
-// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
-
-// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
-// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
-// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
-// //typedef typename Graph::SymEdgeIt SymEdgeIt;
-// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
-
-// NodeIt& first(NodeIt& n) const {
-// return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
-// }
-
-// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
-// e=first_out_edges.get(n);
-// return e;
-// }
-
-// //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
-// //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
-// // return first(i, p); }
-
-// //template<typename I> I getNext(const I& i) const {
-// // return gw.getNext(i); }
-// //template<typename I> I& next(I &i) const { return gw.next(i); }
-
-// template< typename It > It first() const {
-// It e; first(e); return e; }
-
-// template< typename It > It first(const Node& v) const {
-// It e; first(e, v); return e; }
-
-// //Node head(const Edge& e) const { return gw.head(e); }
-// //Node tail(const Edge& e) const { return gw.tail(e); }
-
-// //template<typename I> bool valid(const I& i) const
-// // { return gw.valid(i); }
-
-// //int nodeNum() const { return gw.nodeNum(); }
-// //int edgeNum() const { return gw.edgeNum(); }
-
-// //template<typename I> Node aNode(const I& e) const {
-// // return gw.aNode(e); }
-// //template<typename I> Node bNode(const I& e) const {
-// // return gw.bNode(e); }
-
-// //Node addNode() const { return gw.addNode(); }
-// //Edge addEdge(const Node& tail, const Node& head) const {
-// // return gw.addEdge(tail, head); }
-
-// //void erase(const OutEdgeIt& e) {
-// // first_out_edge(this->tail(e))=e;
-// //}
-// void erase(const Edge& e) {
-// OutEdgeIt f(e);
-// next(f);
-// first_out_edges.set(this->tail(e), f);
-// }
-// //template<typename I> void erase(const I& i) const { gw.erase(i); }
-
-// //void clear() const { gw.clear(); }
-
-// template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
-// public:
-// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
-// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
-// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
-// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
-// };
-
-// template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
-// public:
-// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
-// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
-// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
-// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
-// };
-// };
-
-// template<typename GraphWrapper>
-// class FilterGraphWrapper {
-// };
-
-// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
-// class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
-
-// //Graph* graph;
-
-// public:
-// //typedef Graph BaseGraph;
-
-// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
-// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
-
-// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
-// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
-// //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
-// //typedef typename Graph::SymEdgeIt SymEdgeIt;
-// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
-
-// //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
-
-// public:
-// FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
-// const CapacityMap& _capacity) :
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
-// }
-
-// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
-// while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
-// return e;
-// }
-
-// NodeIt& next(NodeIt& e) const {
-// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
-// }
-
-// OutEdgeIt& next(OutEdgeIt& e) const {
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
-// while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
-// return e;
-// }
-
-// NodeIt& first(NodeIt& n) const {
-// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
-// }
-
-// void erase(const Edge& e) {
-// OutEdgeIt f(e);
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
-// while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
-// first_out_edges.set(this->tail(e), f);
-// }
-
-// //TrivGraphWrapper() : graph(0) { }
-// //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
-
-// //void setGraph(Graph& _graph) { graph = &_graph; }
-// //Graph& getGraph() const { return (*graph); }
-
-// //template<typename I> I& first(I& i) const { return gw.first(i); }
-// //template<typename I, typename P> I& first(I& i, const P& p) const {
-// // return gw.first(i, p); }
-
-// //template<typename I> I getNext(const I& i) const {
-// // return gw.getNext(i); }
-// //template<typename I> I& next(I &i) const { return gw.next(i); }
-
-// template< typename It > It first() const {
-// It e; first(e); return e; }
-
-// template< typename It > It first(const Node& v) const {
-// It e; first(e, v); return e; }
-
-// //Node head(const Edge& e) const { return gw.head(e); }
-// //Node tail(const Edge& e) const { return gw.tail(e); }
-
-// //template<typename I> bool valid(const I& i) const
-// // { return gw.valid(i); }
-
-// //template<typename I> void setInvalid(const I &i);
-// //{ return gw.setInvalid(i); }
-
-// //int nodeNum() const { return gw.nodeNum(); }
-// //int edgeNum() const { return gw.edgeNum(); }
-
-// //template<typename I> Node aNode(const I& e) const {
-// // return gw.aNode(e); }
-// //template<typename I> Node bNode(const I& e) const {
-// // return gw.bNode(e); }
-
-// //Node addNode() const { return gw.addNode(); }
-// //Edge addEdge(const Node& tail, const Node& head) const {
-// // return gw.addEdge(tail, head); }
-
-// //template<typename I> void erase(const I& i) const { gw.erase(i); }
-
-// //void clear() const { gw.clear(); }
-
-// template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
-// public:
-// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
-// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
-// };
-
-// template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
-// public:
-// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
-// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
-// };
-
-// public:
-// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
-
-// };
-
-
-
// // FIXME: comparison should be made better!!!
// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
// class ResGraphWrapper
@@ -1562,7 +1223,7 @@
// Graph* graph;
// public:
-// typedef Graph BaseGraph;
+// typedef Graph ParentGraph;
// typedef typename Graph::Node Node;
// typedef typename Graph::Edge Edge;
diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/makefile
--- a/src/work/marci/makefile Mon Apr 05 15:31:21 2004 +0000
+++ b/src/work/marci/makefile Mon Apr 05 16:52:46 2004 +0000
@@ -2,6 +2,8 @@
CXX2 = g++-2.95
#CXX3.3 = g++
CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
+CXX=$(CXX3)
+CC=$(CXX)
#CXXFLAGS = -W -Wall -ansi -pedantic -I. -I.. -I../alpar
#LEDAROOT ?= /ledasrc/LEDA-4.1
BOOSTROOT ?= /home/marci/boost
@@ -10,13 +12,13 @@
CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = edmonds_karp_demo gw_vs_not
-#preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
+BINARIES = edmonds_karp_demo iterator_bfs_demo
+#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
all: $(BINARIES)
.depend dep depend:
- -g++ $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
+ -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
# -g++ $(INCLUDEDIRS) $(LEDAINCLUDE) -M $(LEDABINARIES:=.cc) >> .depend #2>/dev/null