1.1 --- a/src/work/jacint/makefile Mon Apr 05 18:24:37 2004 +0000
1.2 +++ b/src/work/jacint/makefile Tue Apr 06 12:00:34 2004 +0000
1.3 @@ -1,23 +1,29 @@
1.4 CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
1.5 CXX2 = g++-2.95
1.6 -CXXFLAGS = -W -Wall -ansi -pedantic -O3 -I. -I.. -I../marci -I../alpar -I../../include
1.7 +CXX=$(CXX3)
1.8 +CC=$(CXX)
1.9 +INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos}
1.10 +CXXFLAGS = -W -Wall -ansi -pedantic -O3 $(INCLUDEDIRS)
1.11 LEDAROOT ?= /ledasrc/LEDA-4.1
1.12
1.13 -BINARIES = dijkstra prim preflow
1.14 +BINARIES = preflow #dijkstra prim
1.15
1.16 all: $(BINARIES)
1.17
1.18 +.depend dep depend:
1.19 + -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
1.20 +
1.21 makefile: .depend
1.22 sinclude .depend
1.23
1.24 -preflow:
1.25 - $(CXX3) $(CXXFLAGS) -o preflow preflow.cc
1.26 -
1.27 -dijkstra:
1.28 - $(CXX3) $(CXXFLAGS) -o dijkstra dijkstra.cc
1.29 -
1.30 -prim:
1.31 - $(CXX3) $(CXXFLAGS) -o prim prim.cc
1.32 +#preflow:
1.33 +# $(CXX3) $(CXXFLAGS) -o preflow preflow.cc
1.34 +#
1.35 +#dijkstra:
1.36 +# $(CXX3) $(CXXFLAGS) -o dijkstra dijkstra.cc
1.37 +#
1.38 +#prim:
1.39 +# $(CXX3) $(CXXFLAGS) -o prim prim.cc
1.40
1.41 clean:
1.42 $(RM) *.o $(BINARIES) .depend
2.1 --- a/src/work/marci/edmonds_karp.h Mon Apr 05 18:24:37 2004 +0000
2.2 +++ b/src/work/marci/edmonds_karp.h Tue Apr 06 12:00:34 2004 +0000
2.3 @@ -9,6 +9,7 @@
2.4 #include <bfs_iterator.h>
2.5 #include <invalid.h>
2.6 #include <graph_wrapper.h>
2.7 +#include <maps.h>
2.8
2.9 namespace hugo {
2.10
2.11 @@ -353,8 +354,10 @@
2.12 } //computing distances from s in the residual graph
2.13
2.14 MG F;
2.15 - typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
2.16 - FilterResGW filter_res_graph(res_graph, dist);
2.17 + ConstMap<typename ResGW::Node, bool> true_map(true);
2.18 + typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
2.19 + DistanceMap<ResGW> > FilterResGW;
2.20 + FilterResGW filter_res_graph(res_graph, true_map, dist);
2.21 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
2.22 {
2.23 typename ResGW::NodeIt n;
2.24 @@ -567,8 +570,10 @@
2.25 } //computing distances from s in the residual graph
2.26
2.27 //Subgraph containing the edges on some shortest paths
2.28 - typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
2.29 - FilterResGW filter_res_graph(res_graph, dist);
2.30 + ConstMap<typename ResGW::Node, bool> true_map(true);
2.31 + typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
2.32 + DistanceMap<ResGW> > FilterResGW;
2.33 + FilterResGW filter_res_graph(res_graph, true_map, dist);
2.34
2.35 //Subgraph, which is able to delete edges which are already
2.36 //met by the dfs
2.37 @@ -591,16 +596,16 @@
2.38 while (__augment) {
2.39
2.40 __augment=false;
2.41 - //computing blocking flow with dfs
2.42 + //computing blocking flow with dfs
2.43 typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
2.44 - DfsIterator5< ErasingResGW, BlockingReachedMap >
2.45 - dfs(erasing_res_graph);
2.46 + DfsIterator5< ErasingResGW, BlockingReachedMap >
2.47 + dfs(erasing_res_graph);
2.48 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
2.49 pred(erasing_res_graph);
2.50 pred.set(s, INVALID);
2.51 - //invalid iterators for sources
2.52 + //invalid iterators for sources
2.53
2.54 - typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
2.55 + typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
2.56
2.57 dfs.pushAndSetReached(s);
2.58 while (!dfs.finished()) {
2.59 @@ -608,7 +613,7 @@
2.60 if (erasing_res_graph.valid(
2.61 /*typename ErasingResGW::OutEdgeIt*/(dfs)))
2.62 {
2.63 - if (dfs.isBNodeNewlyReached()) {
2.64 + if (dfs.isBNodeNewlyReached()) {
2.65
2.66 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
2.67 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
2.68 @@ -625,14 +630,14 @@
2.69 _augment=true;
2.70 break;
2.71 }
2.72 - } else {
2.73 - erasing_res_graph.erase(dfs);
2.74 + } else {
2.75 + erasing_res_graph.erase(dfs);
2.76 }
2.77 }
2.78 }
2.79
2.80 - if (__augment) {
2.81 - typename ErasingResGW::Node n=t;
2.82 + if (__augment) {
2.83 + typename ErasingResGW::Node n=t;
2.84 Number augment_value=free[n];
2.85 while (erasing_res_graph.valid(pred[n])) {
2.86 typename ErasingResGW::OutEdgeIt e=pred[n];
2.87 @@ -640,8 +645,8 @@
2.88 n=erasing_res_graph.tail(e);
2.89 if (res_graph.resCap(e)==0)
2.90 erasing_res_graph.erase(e);
2.91 - }
2.92 - }
2.93 + }
2.94 + }
2.95
2.96 } //while (__augment)
2.97
3.1 --- a/src/work/marci/edmonds_karp_demo.cc Mon Apr 05 18:24:37 2004 +0000
3.2 +++ b/src/work/marci/edmonds_karp_demo.cc Tue Apr 06 12:00:34 2004 +0000
3.3 @@ -8,11 +8,7 @@
3.4 #include <edmonds_karp.h>
3.5 #include <time_measure.h>
3.6 //#include <graph_wrapper.h>
3.7 -
3.8 -class CM {
3.9 -public:
3.10 - template<typename T> int get(T) const {return 1;}
3.11 -};
3.12 +#include <preflow.h>
3.13
3.14 using namespace hugo;
3.15
3.16 @@ -88,9 +84,37 @@
3.17 // //cgw.erase(csw);
3.18 // std::cout << "p2:" << cgw.nodeNum() << std::endl;
3.19
3.20 + {
3.21 + std::cout << "preflow ..." << std::endl;
3.22 + Graph::EdgeMap<int> flow(G); //0 flow
3.23 +
3.24 + Timer ts;
3.25 + ts.reset();
3.26 +
3.27 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.28 + max_flow_test(G, s, t, cap, flow);
3.29 + max_flow_test.run();
3.30 +// int i=0;
3.31 +// while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
3.32 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
3.33 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.34 +// }
3.35 +// std::cout<<std::endl;
3.36 +// ++i;
3.37 +// }
3.38 +
3.39 +// std::cout << "maximum flow: "<< std::endl;
3.40 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
3.41 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.42 +// }
3.43 +// std::cout<<std::endl;
3.44 + std::cout << "elapsed time: " << ts << std::endl;
3.45 +// std::cout << "number of augmentation phases: " << i << std::endl;
3.46 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.47 + }
3.48
3.49 {
3.50 - std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
3.51 + std::cout << "physical blocking flow augmentation ..." << std::endl;
3.52 Graph::EdgeMap<int> flow(G); //0 flow
3.53
3.54 Timer ts;
3.55 @@ -118,7 +142,7 @@
3.56 }
3.57
3.58 {
3.59 - std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
3.60 + std::cout << "faster physical blocking flow augmentation ..." << std::endl;
3.61 Graph::EdgeMap<int> flow(G); //0 flow
3.62
3.63 Timer ts;
3.64 @@ -146,7 +170,7 @@
3.65 }
3.66
3.67 {
3.68 - std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
3.69 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
3.70 Graph::EdgeMap<int> flow(G); //0 flow
3.71
3.72 Timer ts;
3.73 @@ -174,7 +198,7 @@
3.74 }
3.75
3.76 {
3.77 - std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
3.78 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
3.79 Graph::EdgeMap<int> flow(G); //0 flow
3.80
3.81 Timer ts;
4.1 --- a/src/work/marci/graph_wrapper.h Mon Apr 05 18:24:37 2004 +0000
4.2 +++ b/src/work/marci/graph_wrapper.h Tue Apr 06 12:00:34 2004 +0000
4.3 @@ -12,6 +12,7 @@
4.4 Graph* graph;
4.5
4.6 public:
4.7 +// typedef Graph BaseGraph;
4.8 typedef Graph ParentGraph;
4.9
4.10 // TrivGraphWrapper() : graph(0) { }
4.11 @@ -24,9 +25,13 @@
4.12 public:
4.13 NodeIt() { }
4.14 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
4.15 +// NodeIt(const typename BaseGraph::NodeIt& n) : Graph::NodeIt(n) { }
4.16 NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
4.17 NodeIt(const TrivGraphWrapper<Graph>& _G) :
4.18 Graph::NodeIt(*(_G.graph)) { }
4.19 +// operator typename BaseGraph::NodeIt() {
4.20 +// return typename BaseGraph::NodeIt(this->Graph::NodeIt);
4.21 +// }
4.22 };
4.23 typedef typename Graph::Edge Edge;
4.24 class OutEdgeIt : public Graph::OutEdgeIt {
4.25 @@ -59,10 +64,6 @@
4.26 i=NodeIt(*this);
4.27 return i;
4.28 }
4.29 - EdgeIt& first(EdgeIt& i) const {
4.30 - i=EdgeIt(*this);
4.31 - return i;
4.32 - }
4.33 // template<typename I> I& first(I& i) const {
4.34 // i=I(*this);
4.35 // return i;
4.36 @@ -75,6 +76,10 @@
4.37 i=InEdgeIt(*this, p);
4.38 return i;
4.39 }
4.40 + EdgeIt& first(EdgeIt& i) const {
4.41 + i=EdgeIt(*this);
4.42 + return i;
4.43 + }
4.44 // template<typename I, typename P> I& first(I& i, const P& p) const {
4.45 // i=I(*this, p);
4.46 // return i;
4.47 @@ -82,7 +87,11 @@
4.48
4.49 // template<typename I> I getNext(const I& i) const {
4.50 // return graph->getNext(i); }
4.51 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
4.52 +// template<typename I> I& next(I &i) const { graph->next(i); return i; }
4.53 + NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
4.54 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
4.55 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
4.56 + EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
4.57
4.58 template< typename It > It first() const {
4.59 It e; this->first(e); return e; }
4.60 @@ -157,6 +166,7 @@
4.61 Graph* graph;
4.62
4.63 public:
4.64 + typedef Graph BaseGraph;
4.65 typedef Graph ParentGraph;
4.66
4.67 // GraphWrapper() : graph(0) { }
4.68 @@ -204,10 +214,6 @@
4.69 i=NodeIt(*this);
4.70 return i;
4.71 }
4.72 - EdgeIt& first(EdgeIt& i) const {
4.73 - i=EdgeIt(*this);
4.74 - return i;
4.75 - }
4.76 // template<typename I> I& first(I& i) const {
4.77 // i=I(*this);
4.78 // return i;
4.79 @@ -220,6 +226,10 @@
4.80 i=InEdgeIt(*this, p);
4.81 return i;
4.82 }
4.83 + EdgeIt& first(EdgeIt& i) const {
4.84 + i=EdgeIt(*this);
4.85 + return i;
4.86 + }
4.87 // template<typename I, typename P> I& first(I& i, const P& p) const {
4.88 // i=I(*this, p);
4.89 // return i;
4.90 @@ -227,7 +237,11 @@
4.91
4.92 // template<typename I> I getNext(const I& i) const {
4.93 // return gw.getNext(i); }
4.94 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
4.95 +// template<typename I> I& next(I &i) const { graph->next(i); return i; }
4.96 + NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
4.97 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
4.98 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
4.99 + EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
4.100
4.101 template< typename It > It first() const {
4.102 It e; this->first(e); return e; }
4.103 @@ -385,44 +399,138 @@
4.104 };
4.105
4.106 //Subgraph on the same node-set and partial edge-set
4.107 - template<typename Graph, typename EdgeFilterMap>
4.108 + template<typename Graph, typename NodeFilterMap,
4.109 + typename EdgeFilterMap>
4.110 class SubGraphWrapper : public GraphWrapper<Graph> {
4.111 protected:
4.112 - EdgeFilterMap* filter_map;
4.113 + NodeFilterMap* node_filter_map;
4.114 + EdgeFilterMap* edge_filter_map;
4.115 public:
4.116 - typedef typename GraphWrapper<Graph>::Node Node;
4.117 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
4.118 - typedef typename GraphWrapper<Graph>::Edge Edge;
4.119 - typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
4.120 - typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
4.121 - typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
4.122 +// SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
4.123 + SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
4.124 + EdgeFilterMap& _edge_filter_map) :
4.125 + GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
4.126 + edge_filter_map(&_edge_filter_map) { }
4.127
4.128 -// SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
4.129 - SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) :
4.130 - GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { }
4.131
4.132 - template<typename I> I& first(I& i) const {
4.133 - graph->first(i);
4.134 - //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
4.135 - while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
4.136 + typedef typename Graph::Node Node;
4.137 + class NodeIt : public Graph::NodeIt {
4.138 +// typedef typename Graph::NodeIt GraphNodeIt;
4.139 + public:
4.140 + NodeIt() { }
4.141 + NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
4.142 + NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
4.143 + NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
4.144 + Graph::NodeIt(*(_G.graph)) {
4.145 + while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
4.146 + !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
4.147 + _G.graph->next((*this)/*.GraphNodeIt*/);
4.148 + }
4.149 + };
4.150 + typedef typename Graph::Edge Edge;
4.151 + class OutEdgeIt : public Graph::OutEdgeIt {
4.152 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
4.153 + public:
4.154 + OutEdgeIt() { }
4.155 + OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
4.156 + OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
4.157 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
4.158 + _G, const Node& n) :
4.159 + Graph::OutEdgeIt(*(_G.graph), n) {
4.160 + while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
4.161 + !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
4.162 + _G.graph->next((*this)/*.GraphOutEdgeIt*/);
4.163 + }
4.164 + };
4.165 + class InEdgeIt : public Graph::InEdgeIt {
4.166 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
4.167 + public:
4.168 + InEdgeIt() { }
4.169 + InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
4.170 + InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
4.171 + InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
4.172 + const Node& n) :
4.173 + Graph::InEdgeIt(*(_G.graph), n) {
4.174 + while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
4.175 + !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
4.176 + _G.graph->next((*this)/*.GraphInEdgeIt*/);
4.177 + }
4.178 + };
4.179 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.180 + class EdgeIt : public Graph::EdgeIt {
4.181 +// typedef typename Graph::EdgeIt GraphEdgeIt;
4.182 + public:
4.183 + EdgeIt() { }
4.184 + EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
4.185 + EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
4.186 + EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
4.187 + Graph::EdgeIt(*(_G.graph)) {
4.188 + while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
4.189 + !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
4.190 + _G.graph->next((*this)/*.GraphEdgeIt*/);
4.191 + }
4.192 + };
4.193 +
4.194 + NodeIt& first(NodeIt& i) const {
4.195 + i=NodeIt(*this);
4.196 return i;
4.197 }
4.198 - template<typename I, typename P> I& first(I& i, const P& p) const {
4.199 - graph->first(i, p);
4.200 -// while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
4.201 - while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
4.202 + OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
4.203 + i=OutEdgeIt(*this, n);
4.204 + return i;
4.205 + }
4.206 + InEdgeIt& first(InEdgeIt& i, const Node& n) const {
4.207 + i=InEdgeIt(*this, n);
4.208 + return i;
4.209 + }
4.210 + EdgeIt& first(EdgeIt& i) const {
4.211 + i=EdgeIt(*this);
4.212 return i;
4.213 }
4.214
4.215 +// template<typename I> I& first(I& i) const {
4.216 +// graph->first(i);
4.217 +// //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
4.218 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
4.219 +// return i;
4.220 +// }
4.221 +// template<typename I, typename P> I& first(I& i, const P& p) const {
4.222 +// graph->first(i, p);
4.223 +// // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
4.224 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
4.225 +// return i;
4.226 +// }
4.227 +
4.228 + NodeIt& next(NodeIt& i) const {
4.229 + graph->next(i);
4.230 + while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
4.231 + return i;
4.232 + }
4.233 + OutEdgeIt& next(OutEdgeIt& i) const {
4.234 + graph->next(i);
4.235 + while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
4.236 + return i;
4.237 + }
4.238 + InEdgeIt& next(InEdgeIt& i) const {
4.239 + graph->next(i);
4.240 + while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
4.241 + return i;
4.242 + }
4.243 + EdgeIt& next(EdgeIt& i) const {
4.244 + graph->next(i);
4.245 + while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
4.246 + return i;
4.247 + }
4.248 +
4.249 //template<typename I> I getNext(const I& i) const {
4.250 // return gw.getNext(i);
4.251 //}
4.252 - template<typename I> I& next(I &i) const {
4.253 - graph->next(i);
4.254 -// while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
4.255 - while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
4.256 - return i;
4.257 - }
4.258 +// template<typename I> I& next(I &i) const {
4.259 +// graph->next(i);
4.260 +// // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
4.261 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
4.262 +// return i;
4.263 +// }
4.264
4.265 template< typename It > It first() const {
4.266 It e; this->first(e); return e; }
4.267 @@ -844,10 +952,7 @@
4.268
4.269
4.270 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.271 - class ResGraphWrapper : public GraphWrapper<Graph>{
4.272 - public:
4.273 - typedef typename GraphWrapper<Graph>::Node Node;
4.274 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
4.275 + class ResGraphWrapper : public GraphWrapper<Graph> {
4.276 protected:
4.277 typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
4.278 typedef typename Graph::InEdgeIt GraphInEdgeIt;
4.279 @@ -865,6 +970,8 @@
4.280 friend class Edge;
4.281 friend class OutEdgeIt;
4.282
4.283 + typedef typename GraphWrapper<Graph>::Node Node;
4.284 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
4.285 class Edge {
4.286 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.287 protected:
4.288 @@ -892,8 +999,6 @@
4.289 if (out_or_in) return(out); else return(in);
4.290 }
4.291 };
4.292 -
4.293 -
4.294 class OutEdgeIt : public Edge {
4.295 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.296 public:
4.297 @@ -930,7 +1035,7 @@
4.298 };
4.299
4.300 //FIXME This is just for having InEdgeIt
4.301 - typedef void InEdgeIt;
4.302 +// class InEdgeIt : public Edge { };
4.303
4.304 class EdgeIt : public Edge {
4.305 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.306 @@ -993,18 +1098,25 @@
4.307 // }
4.308 };
4.309
4.310 - NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
4.311 - OutEdgeIt& first(OutEdgeIt& e, Node v) const {
4.312 - e=OutEdgeIt(*this, v);
4.313 - return e;
4.314 + NodeIt& first(NodeIt& i) const {
4.315 + i=NodeIt(*this);
4.316 + return i;
4.317 }
4.318 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
4.319 + i=OutEdgeIt(*this, p);
4.320 + return i;
4.321 + }
4.322 + //FIXME Not yet implemented
4.323 + //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
4.324 + //i=InEdgeIt(*this, p);
4.325 + // return i;
4.326 + //}
4.327 EdgeIt& first(EdgeIt& e) const {
4.328 e=EdgeIt(*this);
4.329 return e;
4.330 }
4.331
4.332 NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
4.333 -
4.334 OutEdgeIt& next(OutEdgeIt& e) const {
4.335 if (e.out_or_in) {
4.336 Node v=graph->aNode(e.out);
4.337 @@ -1021,7 +1133,10 @@
4.338 }
4.339 return e;
4.340 }
4.341 -
4.342 + //FIXME Not yet implemented
4.343 + //InEdgeIt& next(InEdgeIt& e) const {
4.344 + // return e;
4.345 + //}
4.346 EdgeIt& next(EdgeIt& e) const {
4.347 if (e.out_or_in) {
4.348 graph->next(e.out);
4.349 @@ -1169,38 +1284,106 @@
4.350 protected:
4.351 FirstOutEdgesMap* first_out_edges;
4.352 public:
4.353 - typedef typename GraphWrapper<Graph>::Node Node;
4.354 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
4.355 - typedef typename GraphWrapper<Graph>::Edge Edge;
4.356 - typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
4.357 - typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
4.358 - typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
4.359 -
4.360 ErasingFirstGraphWrapper(Graph& _graph,
4.361 FirstOutEdgesMap& _first_out_edges) :
4.362 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
4.363
4.364 - template<typename I> I& first(I& i) const {
4.365 - graph->first(i);
4.366 + typedef typename Graph::Node Node;
4.367 + class NodeIt : public Graph::NodeIt {
4.368 + public:
4.369 + NodeIt() { }
4.370 + NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
4.371 + NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
4.372 + NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
4.373 + Graph::NodeIt(*(_G.graph)) { }
4.374 + };
4.375 + typedef typename Graph::Edge Edge;
4.376 + class OutEdgeIt : public Graph::OutEdgeIt {
4.377 + public:
4.378 + OutEdgeIt() { }
4.379 + OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
4.380 + OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
4.381 + OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
4.382 + const Node& n) :
4.383 + Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
4.384 + };
4.385 + class InEdgeIt : public Graph::InEdgeIt {
4.386 + public:
4.387 + InEdgeIt() { }
4.388 + InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
4.389 + InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
4.390 + InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
4.391 + const Node& n) :
4.392 + Graph::InEdgeIt(*(_G.graph), n) { }
4.393 + };
4.394 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.395 + class EdgeIt : public Graph::EdgeIt {
4.396 + public:
4.397 + EdgeIt() { }
4.398 + EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
4.399 + EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
4.400 + EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
4.401 + Graph::EdgeIt(*(_G.graph)) { }
4.402 + };
4.403 +
4.404 + NodeIt& first(NodeIt& i) const {
4.405 + i=NodeIt(*this);
4.406 return i;
4.407 }
4.408 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
4.409 -// e=first_out_edges->get(n);
4.410 - e=(*first_out_edges)[n];
4.411 - return e;
4.412 - }
4.413 - template<typename I, typename P> I& first(I& i, const P& p) const {
4.414 - graph->first(i, p);
4.415 + OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
4.416 + i=OutEdgeIt(*this, n);
4.417 +// i=(*first_out_edges)[n];
4.418 return i;
4.419 }
4.420 + InEdgeIt& first(InEdgeIt& i, const Node& n) const {
4.421 + i=InEdgeIt(*this, n);
4.422 + return i;
4.423 + }
4.424 + EdgeIt& first(EdgeIt& i) const {
4.425 + i=EdgeIt(*this);
4.426 + return i;
4.427 + }
4.428 +
4.429 +// template<typename I> I& first(I& i) const {
4.430 +// graph->first(i);
4.431 +// return i;
4.432 +// }
4.433 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
4.434 +// // e=first_out_edges->get(n);
4.435 +// e=(*first_out_edges)[n];
4.436 +// return e;
4.437 +// }
4.438 +// template<typename I, typename P> I& first(I& i, const P& p) const {
4.439 +// graph->first(i, p);
4.440 +// return i;
4.441 +// }
4.442
4.443 //template<typename I> I getNext(const I& i) const {
4.444 // return gw.getNext(i);
4.445 //}
4.446 - template<typename I> I& next(I &i) const {
4.447 +
4.448 +
4.449 + NodeIt& next(NodeIt& i) const {
4.450 graph->next(i);
4.451 return i;
4.452 }
4.453 + OutEdgeIt& next(OutEdgeIt& i) const {
4.454 + graph->next(i);
4.455 + return i;
4.456 + }
4.457 + InEdgeIt& next(InEdgeIt& i) const {
4.458 + graph->next(i);
4.459 + return i;
4.460 + }
4.461 + EdgeIt& next(EdgeIt& i) const {
4.462 + graph->next(i);
4.463 + return i;
4.464 + }
4.465 +
4.466 +// template<typename I> I& next(I &i) const {
4.467 +// graph->next(i);
4.468 +// return i;
4.469 +// }
4.470
4.471 template< typename It > It first() const {
4.472 It e; this->first(e); return e; }