1.1 --- a/src/include/skeletons/graph.h Mon Apr 05 14:01:41 2004 +0000
1.2 +++ b/src/include/skeletons/graph.h Mon Apr 05 14:19:02 2004 +0000
1.3 @@ -1,6 +1,6 @@
1.4 // -*- c++ -*-
1.5 -#ifndef HUGO_EMPTYGRAPH_H
1.6 -#define HUGO_EMPTYGRAPH_H
1.7 +#ifndef HUGO_GRAPH_H
1.8 +#define HUGO_GRAPH_H
1.9
1.10 ///\file
1.11 ///\brief Declaration of GraphSkeleton.
1.12 @@ -390,4 +390,4 @@
1.13
1.14 // }
1.15
1.16 -#endif // HUGO_EMPTYGRAPH_H
1.17 +#endif // HUGO_GRAPH_H
2.1 --- a/src/work/marci/experiment/bfs_iterator_1.h Mon Apr 05 14:01:41 2004 +0000
2.2 +++ b/src/work/marci/experiment/bfs_iterator_1.h Mon Apr 05 14:19:02 2004 +0000
2.3 @@ -630,39 +630,33 @@
2.4 // };
2.5
2.6
2.7 - template <typename GraphWrapper, /*typename OutEdgeIt,*/
2.8 - typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
2.9 + template <typename Graph, /*typename OutEdgeIt,*/
2.10 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
2.11 class BfsIterator5 {
2.12 - typedef typename GraphWrapper::Node Node;
2.13 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
2.14 - const GraphWrapper* g;
2.15 + protected:
2.16 + typedef typename Graph::Node Node;
2.17 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.18 + const Graph* graph;
2.19 std::queue<Node> bfs_queue;
2.20 ReachedMap& reached;
2.21 bool b_node_newly_reached;
2.22 OutEdgeIt actual_edge;
2.23 bool own_reached_map;
2.24 public:
2.25 - BfsIterator5(const GraphWrapper& _g, ReachedMap& _reached) :
2.26 - g(&_g), reached(_reached),
2.27 + BfsIterator5(const Graph& _graph, ReachedMap& _reached) :
2.28 + graph(&_graph), reached(_reached),
2.29 own_reached_map(false) { }
2.30 - BfsIterator5(const GraphWrapper& _g) :
2.31 - g(&_g), reached(*(new ReachedMap(*g /*, false*/))),
2.32 + BfsIterator5(const Graph& _graph) :
2.33 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
2.34 own_reached_map(true) { }
2.35 -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
2.36 -// ReachedMap& _reached) :
2.37 -// G(_G), reached(_reached),
2.38 -// own_reached_map(false) { }
2.39 -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
2.40 -// G(_G), reached(*(new ReachedMap(G /*, false*/))),
2.41 -// own_reached_map(true) { }
2.42 ~BfsIterator5() { if (own_reached_map) delete &reached; }
2.43 void pushAndSetReached(Node s) {
2.44 reached.set(s, true);
2.45 if (bfs_queue.empty()) {
2.46 bfs_queue.push(s);
2.47 - g->first(actual_edge, s);
2.48 - if (g->valid(actual_edge)) {
2.49 - Node w=g->bNode(actual_edge);
2.50 + graph->first(actual_edge, s);
2.51 + if (graph->valid(actual_edge)) {
2.52 + Node w=graph->bNode(actual_edge);
2.53 if (!reached.get(w)) {
2.54 bfs_queue.push(w);
2.55 reached.set(w, true);
2.56 @@ -675,12 +669,12 @@
2.57 bfs_queue.push(s);
2.58 }
2.59 }
2.60 - BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
2.61 + BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
2.62 operator++() {
2.63 - if (g->valid(actual_edge)) {
2.64 - g->next(actual_edge);
2.65 - if (g->valid(actual_edge)) {
2.66 - Node w=g->bNode(actual_edge);
2.67 + if (graph->valid(actual_edge)) {
2.68 + graph->next(actual_edge);
2.69 + if (graph->valid(actual_edge)) {
2.70 + Node w=graph->bNode(actual_edge);
2.71 if (!reached.get(w)) {
2.72 bfs_queue.push(w);
2.73 reached.set(w, true);
2.74 @@ -692,9 +686,9 @@
2.75 } else {
2.76 bfs_queue.pop();
2.77 if (!bfs_queue.empty()) {
2.78 - g->first(actual_edge, bfs_queue.front());
2.79 - if (g->valid(actual_edge)) {
2.80 - Node w=g->bNode(actual_edge);
2.81 + graph->first(actual_edge, bfs_queue.front());
2.82 + if (graph->valid(actual_edge)) {
2.83 + Node w=graph->bNode(actual_edge);
2.84 if (!reached.get(w)) {
2.85 bfs_queue.push(w);
2.86 reached.set(w, true);
2.87 @@ -710,9 +704,9 @@
2.88 bool finished() const { return bfs_queue.empty(); }
2.89 operator OutEdgeIt () const { return actual_edge; }
2.90 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
2.91 - bool isANodeExamined() const { return !(g->valid(actual_edge)); }
2.92 + bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
2.93 Node aNode() const { return bfs_queue.front(); }
2.94 - Node bNode() const { return g->bNode(actual_edge); }
2.95 + Node bNode() const { return graph->bNode(actual_edge); }
2.96 const ReachedMap& getReachedMap() const { return reached; }
2.97 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
2.98 };
2.99 @@ -773,12 +767,13 @@
2.100 // const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
2.101 // };
2.102
2.103 - template <typename GraphWrapper, /*typename OutEdgeIt,*/
2.104 - typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
2.105 + template <typename Graph, /*typename OutEdgeIt,*/
2.106 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
2.107 class DfsIterator5 {
2.108 - typedef typename GraphWrapper::Node Node;
2.109 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
2.110 - const GraphWrapper* g;
2.111 + protected:
2.112 + typedef typename Graph::Node Node;
2.113 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.114 + const Graph* graph;
2.115 std::stack<OutEdgeIt> dfs_stack;
2.116 bool b_node_newly_reached;
2.117 OutEdgeIt actual_edge;
2.118 @@ -786,36 +781,36 @@
2.119 ReachedMap& reached;
2.120 bool own_reached_map;
2.121 public:
2.122 - DfsIterator5(const GraphWrapper& _g, ReachedMap& _reached) :
2.123 - g(&_g), reached(_reached),
2.124 + DfsIterator5(const Graph& _graph, ReachedMap& _reached) :
2.125 + graph(&_graph), reached(_reached),
2.126 own_reached_map(false) { }
2.127 - DfsIterator5(const GraphWrapper& _g) :
2.128 - g(&_g), reached(*(new ReachedMap(*g /*, false*/))),
2.129 + DfsIterator5(const Graph& _graph) :
2.130 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
2.131 own_reached_map(true) { }
2.132 ~DfsIterator5() { if (own_reached_map) delete &reached; }
2.133 void pushAndSetReached(Node s) {
2.134 actual_node=s;
2.135 reached.set(s, true);
2.136 OutEdgeIt e;
2.137 - g->first(e, s);
2.138 + graph->first(e, s);
2.139 dfs_stack.push(e);
2.140 }
2.141 - DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
2.142 + DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
2.143 operator++() {
2.144 actual_edge=dfs_stack.top();
2.145 //actual_node=G.aNode(actual_edge);
2.146 - if (g->valid(actual_edge)/*.valid()*/) {
2.147 - Node w=g->bNode(actual_edge);
2.148 + if (graph->valid(actual_edge)/*.valid()*/) {
2.149 + Node w=graph->bNode(actual_edge);
2.150 actual_node=w;
2.151 if (!reached.get(w)) {
2.152 OutEdgeIt e;
2.153 - g->first(e, w);
2.154 + graph->first(e, w);
2.155 dfs_stack.push(e);
2.156 reached.set(w, true);
2.157 b_node_newly_reached=true;
2.158 } else {
2.159 - actual_node=g->aNode(actual_edge);
2.160 - g->next(dfs_stack.top());
2.161 + actual_node=graph->aNode(actual_edge);
2.162 + graph->next(dfs_stack.top());
2.163 b_node_newly_reached=false;
2.164 }
2.165 } else {
2.166 @@ -827,7 +822,7 @@
2.167 bool finished() const { return dfs_stack.empty(); }
2.168 operator OutEdgeIt () const { return actual_edge; }
2.169 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
2.170 - bool isANodeExamined() const { return !(g->valid(actual_edge)); }
2.171 + bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
2.172 Node aNode() const { return actual_node; /*FIXME*/}
2.173 Node bNode() const { return G.bNode(actual_edge); }
2.174 const ReachedMap& getReachedMap() const { return reached; }
3.1 --- a/src/work/marci/experiment/edmonds_karp_1.h Mon Apr 05 14:01:41 2004 +0000
3.2 +++ b/src/work/marci/experiment/edmonds_karp_1.h Mon Apr 05 14:19:02 2004 +0000
3.3 @@ -248,28 +248,25 @@
3.4 };
3.5
3.6
3.7 - template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
3.8 + template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.9 class MaxFlow {
3.10 protected:
3.11 - typedef GraphWrapper GW;
3.12 - typedef typename GW::Node Node;
3.13 - typedef typename GW::Edge Edge;
3.14 - typedef typename GW::EdgeIt EdgeIt;
3.15 - typedef typename GW::OutEdgeIt OutEdgeIt;
3.16 - typedef typename GW::InEdgeIt InEdgeIt;
3.17 - //const Graph* G;
3.18 - //GW gw;
3.19 - const GW* g;
3.20 + typedef typename Graph::Node Node;
3.21 + typedef typename Graph::Edge Edge;
3.22 + typedef typename Graph::EdgeIt EdgeIt;
3.23 + typedef typename Graph::OutEdgeIt OutEdgeIt;
3.24 + typedef typename Graph::InEdgeIt InEdgeIt;
3.25 + const Graph* g;
3.26 Node s;
3.27 Node t;
3.28 FlowMap* flow;
3.29 const CapacityMap* capacity;
3.30 - typedef ResGraphWrapper<const GW, Number, FlowMap, CapacityMap > ResGW;
3.31 + typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
3.32 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
3.33 typedef typename ResGW::Edge ResGWEdge;
3.34 public:
3.35
3.36 - MaxFlow(const GW& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
3.37 + MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
3.38 g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
3.39
3.40 bool augmentOnShortestPath() {
3.41 @@ -646,95 +643,6 @@
3.42 return _augment;
3.43 }
3.44
3.45 -// bool augmentOnBlockingFlow2() {
3.46 -// bool _augment=false;
3.47 -
3.48 -// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
3.49 -// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
3.50 -// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
3.51 -// typedef typename EAugGraph::Edge EAugEdge;
3.52 -
3.53 -// EAugGraph res_graph(*G, *flow, *capacity);
3.54 -
3.55 -// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
3.56 -// BfsIterator5<
3.57 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
3.58 -// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
3.59 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
3.60 -
3.61 -// bfs.pushAndSetReached(s);
3.62 -
3.63 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
3.64 -// NodeMap<int>& dist=res_graph.dist;
3.65 -
3.66 -// while ( !bfs.finished() ) {
3.67 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
3.68 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
3.69 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
3.70 -// }
3.71 -// ++bfs;
3.72 -// } //computing distances from s in the residual graph
3.73 -
3.74 -// bool __augment=true;
3.75 -
3.76 -// while (__augment) {
3.77 -
3.78 -// __augment=false;
3.79 -// //computing blocking flow with dfs
3.80 -// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
3.81 -// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
3.82 -// dfs(res_graph);
3.83 -// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
3.84 -// pred.set(s, EAugEdge(INVALID));
3.85 -// //invalid iterators for sources
3.86 -
3.87 -// typename EAugGraph::NodeMap<Number> free(res_graph);
3.88 -
3.89 -// dfs.pushAndSetReached(s);
3.90 -// while (!dfs.finished()) {
3.91 -// ++dfs;
3.92 -// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
3.93 -// if (dfs.isBNodeNewlyReached()) {
3.94 -
3.95 -// typename EAugGraph::Node v=res_graph.aNode(dfs);
3.96 -// typename EAugGraph::Node w=res_graph.bNode(dfs);
3.97 -
3.98 -// pred.set(w, EAugOutEdgeIt(dfs));
3.99 -// if (res_graph.valid(pred.get(v))) {
3.100 -// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
3.101 -// } else {
3.102 -// free.set(w, res_graph.free(dfs));
3.103 -// }
3.104 -
3.105 -// if (w==t) {
3.106 -// __augment=true;
3.107 -// _augment=true;
3.108 -// break;
3.109 -// }
3.110 -// } else {
3.111 -// res_graph.erase(dfs);
3.112 -// }
3.113 -// }
3.114 -
3.115 -// }
3.116 -
3.117 -// if (__augment) {
3.118 -// typename EAugGraph::Node n=t;
3.119 -// Number augment_value=free.get(t);
3.120 -// while (res_graph.valid(pred.get(n))) {
3.121 -// EAugEdge e=pred.get(n);
3.122 -// res_graph.augment(e, augment_value);
3.123 -// n=res_graph.tail(e);
3.124 -// if (res_graph.free(e)==0)
3.125 -// res_graph.erase(e);
3.126 -// }
3.127 -// }
3.128 -
3.129 -// }
3.130 -
3.131 -// return _augment;
3.132 -// }
3.133 -
3.134 void run() {
3.135 //int num_of_augmentations=0;
3.136 while (augmentOnShortestPath()) {
4.1 --- a/src/work/marci/experiment/graph_wrapper_1.h Mon Apr 05 14:01:41 2004 +0000
4.2 +++ b/src/work/marci/experiment/graph_wrapper_1.h Mon Apr 05 14:19:02 2004 +0000
4.3 @@ -14,6 +14,11 @@
4.4 public:
4.5 typedef Graph BaseGraph;
4.6
4.7 +// TrivGraphWrapper() : graph(0) { }
4.8 + TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.9 +// void setGraph(Graph& _graph) { graph = &_graph; }
4.10 +// Graph& getGraph() const { return *graph; }
4.11 +
4.12 typedef typename Graph::Node Node;
4.13 class NodeIt : public Graph::NodeIt {
4.14 public:
4.15 @@ -24,7 +29,6 @@
4.16 Graph::NodeIt(*(_G.graph)) { }
4.17 };
4.18 typedef typename Graph::Edge Edge;
4.19 - //typedef typename Graph::OutEdgeIt OutEdgeIt;
4.20 class OutEdgeIt : public Graph::OutEdgeIt {
4.21 public:
4.22 OutEdgeIt() { }
4.23 @@ -33,7 +37,6 @@
4.24 OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
4.25 Graph::OutEdgeIt(*(_G.graph), n) { }
4.26 };
4.27 - //typedef typename Graph::InEdgeIt InEdgeIt;
4.28 class InEdgeIt : public Graph::InEdgeIt {
4.29 public:
4.30 InEdgeIt() { }
4.31 @@ -43,7 +46,6 @@
4.32 Graph::InEdgeIt(*(_G.graph), n) { }
4.33 };
4.34 //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.35 - //typedef typename Graph::EdgeIt EdgeIt;
4.36 class EdgeIt : public Graph::EdgeIt {
4.37 public:
4.38 EdgeIt() { }
4.39 @@ -53,12 +55,6 @@
4.40 Graph::EdgeIt(*(_G.graph)) { }
4.41 };
4.42
4.43 - //TrivGraphWrapper() : graph(0) { }
4.44 - TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.45 -
4.46 -// void setGraph(Graph& _graph) { graph = &_graph; }
4.47 -// Graph& getGraph() const { return (*graph); }
4.48 -
4.49 NodeIt& first(NodeIt& i) const {
4.50 i=NodeIt(*this);
4.51 return i;
4.52 @@ -68,7 +64,6 @@
4.53 return i;
4.54 }
4.55 // template<typename I> I& first(I& i) const {
4.56 -// //return graph->first(i);
4.57 // i=I(*this);
4.58 // return i;
4.59 // }
4.60 @@ -81,7 +76,6 @@
4.61 return i;
4.62 }
4.63 // template<typename I, typename P> I& first(I& i, const P& p) const {
4.64 -// //return graph->first(i, p);
4.65 // i=I(*this, p);
4.66 // return i;
4.67 // }
4.68 @@ -91,16 +85,16 @@
4.69 template<typename I> I& next(I &i) const { graph->next(i); return i; }
4.70
4.71 template< typename It > It first() const {
4.72 - It e; first(e); return e; }
4.73 + It e; this->first(e); return e; }
4.74
4.75 template< typename It > It first(const Node& v) const {
4.76 - It e; first(e, v); return e; }
4.77 + It e; this->first(e, v); return e; }
4.78
4.79 Node head(const Edge& e) const { return graph->head(e); }
4.80 Node tail(const Edge& e) const { return graph->tail(e); }
4.81
4.82 - template<typename I> bool valid(const I& i) const
4.83 - { return graph->valid(i); }
4.84 + template<typename I> bool valid(const I& i) const {
4.85 + return graph->valid(i); }
4.86
4.87 //template<typename I> void setInvalid(const I &i);
4.88 //{ return graph->setInvalid(i); }
4.89 @@ -142,9 +136,7 @@
4.90 Map* map;
4.91 public:
4.92 NodeMapWrapper(Map& _map) : map(&_map) { }
4.93 - //template<typename T>
4.94 void set(Node n, T a) { map->set(n, a); }
4.95 - //template<typename T>
4.96 T get(Node n) const { return map->get(n); }
4.97 };
4.98
4.99 @@ -153,91 +145,89 @@
4.100 Map* map;
4.101 public:
4.102 EdgeMapWrapper(Map& _map) : map(&_map) { }
4.103 - //template<typename T>
4.104 void set(Edge n, T a) { map->set(n, a); }
4.105 - //template<typename T>
4.106 T get(Edge n) const { return map->get(n); }
4.107 };
4.108 };
4.109
4.110 - template<typename GraphWrapper>
4.111 - class GraphWrapperSkeleton {
4.112 +
4.113 + template<typename Graph>
4.114 + class GraphWrapper {
4.115 protected:
4.116 - GraphWrapper gw;
4.117 + Graph* graph;
4.118
4.119 public:
4.120 - //typedef typename GraphWrapper::BaseGraph BaseGraph;
4.121 + typedef Graph BaseGraph;
4.122
4.123 -// typedef typename GraphWrapper::Node Node;
4.124 -// typedef typename GraphWrapper::NodeIt NodeIt;
4.125 -
4.126 -// typedef typename GraphWrapper::Edge Edge;
4.127 -// typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
4.128 -// typedef typename GraphWrapper::InEdgeIt InEdgeIt;
4.129 -// //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
4.130 -// typedef typename GraphWrapper::EdgeIt EdgeIt;
4.131 -
4.132 - typedef typename GraphWrapper::Node Node;
4.133 - class NodeIt : public GraphWrapper::NodeIt {
4.134 +// GraphWrapper() : graph(0) { }
4.135 + GraphWrapper(Graph& _graph) : graph(&_graph) { }
4.136 +// void setGraph(Graph& _graph) { graph=&_graph; }
4.137 +// Graph& getGraph() const { return *graph; }
4.138 +
4.139 + typedef typename Graph::Node Node;
4.140 + class NodeIt : public Graph::NodeIt {
4.141 public:
4.142 NodeIt() { }
4.143 - NodeIt(const typename GraphWrapper::NodeIt& n) :
4.144 - GraphWrapper::NodeIt(n) { }
4.145 - NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
4.146 - NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
4.147 - GraphWrapper::NodeIt(_G.gw) { }
4.148 + NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
4.149 + NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
4.150 + NodeIt(const GraphWrapper<Graph>& _G) :
4.151 + Graph::NodeIt(*(_G.graph)) { }
4.152 };
4.153 - typedef typename GraphWrapper::Edge Edge;
4.154 - //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
4.155 - class OutEdgeIt : public GraphWrapper::OutEdgeIt {
4.156 + typedef typename Graph::Edge Edge;
4.157 + class OutEdgeIt : public Graph::OutEdgeIt {
4.158 public:
4.159 OutEdgeIt() { }
4.160 - OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
4.161 - GraphWrapper::OutEdgeIt(e) { }
4.162 - OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
4.163 - OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
4.164 - GraphWrapper::OutEdgeIt(_G.gw, n) { }
4.165 + OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
4.166 + OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
4.167 + OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
4.168 + Graph::OutEdgeIt(*(_G.graph), n) { }
4.169 };
4.170 - //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
4.171 - class InEdgeIt : public GraphWrapper::InEdgeIt {
4.172 + class InEdgeIt : public Graph::InEdgeIt {
4.173 public:
4.174 InEdgeIt() { }
4.175 - InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
4.176 - GraphWrapper::InEdgeIt(e) { }
4.177 - InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
4.178 - InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
4.179 - GraphWrapper::InEdgeIt(_G.gw, n) { }
4.180 + InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
4.181 + InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
4.182 + InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
4.183 + Graph::InEdgeIt(*(_G.graph), n) { }
4.184 };
4.185 - //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
4.186 - //typedef typename GraphWrapper::EdgeIt EdgeIt;
4.187 - class EdgeIt : public GraphWrapper::EdgeIt {
4.188 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.189 + class EdgeIt : public Graph::EdgeIt {
4.190 public:
4.191 EdgeIt() { }
4.192 - EdgeIt(const typename GraphWrapper::EdgeIt& e) :
4.193 - GraphWrapper::EdgeIt(e) { }
4.194 - EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
4.195 - EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
4.196 - GraphWrapper::EdgeIt(_G.gw) { }
4.197 + EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
4.198 + EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
4.199 + EdgeIt(const GraphWrapper<Graph>& _G) :
4.200 + Graph::EdgeIt(*(_G.graph)) { }
4.201 };
4.202 -
4.203 -
4.204 - //GraphWrapperSkeleton() : gw() { }
4.205 - GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
4.206 -
4.207 - //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
4.208 - //BaseGraph& getGraph() const { return gw.getGraph(); }
4.209 -
4.210 - template<typename I> I& first(I& i) const {
4.211 - i=I(*this);
4.212 +
4.213 + NodeIt& first(NodeIt& i) const {
4.214 + i=NodeIt(*this);
4.215 return i;
4.216 }
4.217 - template<typename I, typename P> I& first(I& i, const P& p) const {
4.218 - i=I(*this, p);
4.219 - return i;
4.220 + EdgeIt& first(EdgeIt& i) const {
4.221 + i=EdgeIt(*this);
4.222 + return i;
4.223 }
4.224 +// template<typename I> I& first(I& i) const {
4.225 +// i=I(*this);
4.226 +// return i;
4.227 +// }
4.228 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
4.229 + i=OutEdgeIt(*this, p);
4.230 + return i;
4.231 + }
4.232 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
4.233 + i=InEdgeIt(*this, p);
4.234 + return i;
4.235 + }
4.236 +// template<typename I, typename P> I& first(I& i, const P& p) const {
4.237 +// i=I(*this, p);
4.238 +// return i;
4.239 +// }
4.240
4.241 -// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
4.242 - template<typename I> I& next(I &i) const { gw.next(i); return i; }
4.243 +// template<typename I> I getNext(const I& i) const {
4.244 +// return gw.getNext(i); }
4.245 + template<typename I> I& next(I &i) const { graph->next(i); return i; }
4.246
4.247 template< typename It > It first() const {
4.248 It e; this->first(e); return e; }
4.249 @@ -245,166 +235,45 @@
4.250 template< typename It > It first(const Node& v) const {
4.251 It e; this->first(e, v); return e; }
4.252
4.253 - Node head(const Edge& e) const { return gw.head(e); }
4.254 - Node tail(const Edge& e) const { return gw.tail(e); }
4.255 + Node head(const Edge& e) const { return graph->head(e); }
4.256 + Node tail(const Edge& e) const { return graph->tail(e); }
4.257
4.258 - template<typename I> bool valid(const I& i) const { return gw.valid(i); }
4.259 + template<typename I> bool valid(const I& i) const {
4.260 + return graph->valid(i); }
4.261
4.262 //template<typename I> void setInvalid(const I &i);
4.263 //{ return graph->setInvalid(i); }
4.264
4.265 - int nodeNum() const { return gw.nodeNum(); }
4.266 - int edgeNum() const { return gw.edgeNum(); }
4.267 + int nodeNum() const { return graph->nodeNum(); }
4.268 + int edgeNum() const { return graph->edgeNum(); }
4.269
4.270 - template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
4.271 - template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
4.272 + template<typename I> Node aNode(const I& e) const {
4.273 + return graph->aNode(e); }
4.274 + template<typename I> Node bNode(const I& e) const {
4.275 + return graph->bNode(e); }
4.276
4.277 - Node addNode() const { return gw.addNode(); }
4.278 + Node addNode() const { return graph->addNode(); }
4.279 Edge addEdge(const Node& tail, const Node& head) const {
4.280 - return gw.addEdge(tail, head); }
4.281 + return graph->addEdge(tail, head); }
4.282
4.283 - template<typename I> void erase(const I& i) const { gw.erase(i); }
4.284 + template<typename I> void erase(const I& i) const { graph->erase(i); }
4.285
4.286 - void clear() const { gw.clear(); }
4.287 + void clear() const { graph->clear(); }
4.288
4.289 - template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
4.290 + template<typename T> class NodeMap : public Graph::NodeMap<T> {
4.291 public:
4.292 - NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
4.293 - GraphWrapper::NodeMap<T>(_G.gw) { }
4.294 - NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
4.295 - GraphWrapper::NodeMap<T>(_G.gw, a) { }
4.296 + NodeMap(const GraphWrapper<Graph>& _G) :
4.297 + Graph::NodeMap<T>(*(_G.graph)) { }
4.298 + NodeMap(const GraphWrapper<Graph>& _G, T a) :
4.299 + Graph::NodeMap<T>(*(_G.graph), a) { }
4.300 };
4.301
4.302 - template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
4.303 + template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
4.304 public:
4.305 - EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
4.306 - GraphWrapper::EdgeMap<T>(_G.gw) { }
4.307 - EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
4.308 - GraphWrapper::EdgeMap<T>(_G.gw, a) { }
4.309 - };
4.310 - };
4.311 -
4.312 - template<typename GraphWrapper>
4.313 - class GraphWrapperSkeleton1 {
4.314 - protected:
4.315 - GraphWrapper* g;
4.316 -
4.317 - public:
4.318 - //typedef typename GraphWrapper::BaseGraph BaseGraph;
4.319 -
4.320 -// typedef typename GraphWrapper::Node Node;
4.321 -// typedef typename GraphWrapper::NodeIt NodeIt;
4.322 -
4.323 -// typedef typename GraphWrapper::Edge Edge;
4.324 -// typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
4.325 -// typedef typename GraphWrapper::InEdgeIt InEdgeIt;
4.326 -// //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
4.327 -// typedef typename GraphWrapper::EdgeIt EdgeIt;
4.328 -
4.329 - typedef typename GraphWrapper::Node Node;
4.330 - class NodeIt : public GraphWrapper::NodeIt {
4.331 - public:
4.332 - NodeIt() { }
4.333 - NodeIt(const typename GraphWrapper::NodeIt& n) :
4.334 - GraphWrapper::NodeIt(n) { }
4.335 - NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
4.336 - NodeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G) :
4.337 - GraphWrapper::NodeIt(*(_G.g)) { }
4.338 - };
4.339 - typedef typename GraphWrapper::Edge Edge;
4.340 - //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
4.341 - class OutEdgeIt : public GraphWrapper::OutEdgeIt {
4.342 - public:
4.343 - OutEdgeIt() { }
4.344 - OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
4.345 - GraphWrapper::OutEdgeIt(e) { }
4.346 - OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
4.347 - OutEdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G, const Node& n) :
4.348 - GraphWrapper::OutEdgeIt(*(_G.g), n) { }
4.349 - };
4.350 - //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
4.351 - class InEdgeIt : public GraphWrapper::InEdgeIt {
4.352 - public:
4.353 - InEdgeIt() { }
4.354 - InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
4.355 - GraphWrapper::InEdgeIt(e) { }
4.356 - InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
4.357 - InEdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G, const Node& n) :
4.358 - GraphWrapper::InEdgeIt(*(_G.g), n) { }
4.359 - };
4.360 - //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
4.361 - //typedef typename GraphWrapper::EdgeIt EdgeIt;
4.362 - class EdgeIt : public GraphWrapper::EdgeIt {
4.363 - public:
4.364 - EdgeIt() { }
4.365 - EdgeIt(const typename GraphWrapper::EdgeIt& e) :
4.366 - GraphWrapper::EdgeIt(e) { }
4.367 - EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
4.368 - EdgeIt(const GraphWrapperSkeleton1<GraphWrapper>& _G) :
4.369 - GraphWrapper::EdgeIt(*(_G.g)) { }
4.370 - };
4.371 -
4.372 -
4.373 - //GraphWrapperSkeleton() : gw() { }
4.374 - GraphWrapperSkeleton1(GraphWrapper& _gw) : g(&_gw) { }
4.375 -
4.376 - //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
4.377 - //BaseGraph& getGraph() const { return gw.getGraph(); }
4.378 -
4.379 - template<typename I> I& first(I& i) const {
4.380 - i=I(*this);
4.381 - return i;
4.382 - }
4.383 - template<typename I, typename P> I& first(I& i, const P& p) const {
4.384 - i=I(*this, p);
4.385 - return i;
4.386 - }
4.387 -
4.388 -// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
4.389 - template<typename I> I& next(I &i) const { g->next(i); return i; }
4.390 -
4.391 - template< typename It > It first() const {
4.392 - It e; this->first(e); return e; }
4.393 -
4.394 - template< typename It > It first(const Node& v) const {
4.395 - It e; this->first(e, v); return e; }
4.396 -
4.397 - Node head(const Edge& e) const { return g->head(e); }
4.398 - Node tail(const Edge& e) const { return g->tail(e); }
4.399 -
4.400 - template<typename I> bool valid(const I& i) const { return g->valid(i); }
4.401 -
4.402 - //template<typename I> void setInvalid(const I &i);
4.403 - //{ return graph->setInvalid(i); }
4.404 -
4.405 - int nodeNum() const { return g->nodeNum(); }
4.406 - int edgeNum() const { return g->edgeNum(); }
4.407 -
4.408 - template<typename I> Node aNode(const I& e) const { return g->aNode(e); }
4.409 - template<typename I> Node bNode(const I& e) const { return g->bNode(e); }
4.410 -
4.411 - Node addNode() const { return g->addNode(); }
4.412 - Edge addEdge(const Node& tail, const Node& head) const {
4.413 - return g->addEdge(tail, head); }
4.414 -
4.415 - template<typename I> void erase(const I& i) const { g->erase(i); }
4.416 -
4.417 - void clear() const { g->clear(); }
4.418 -
4.419 - template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
4.420 - public:
4.421 - NodeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G) :
4.422 - GraphWrapper::NodeMap<T>(*(_G.g)) { }
4.423 - NodeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G, T a) :
4.424 - GraphWrapper::NodeMap<T>(*(_G.g), a) { }
4.425 - };
4.426 -
4.427 - template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
4.428 - public:
4.429 - EdgeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G) :
4.430 - GraphWrapper::EdgeMap<T>(*(_G.g)) { }
4.431 - EdgeMap(const GraphWrapperSkeleton1<GraphWrapper>& _G, T a) :
4.432 - GraphWrapper::EdgeMap<T>(*(_G.g), a) { }
4.433 + EdgeMap(const GraphWrapper<Graph>& _G) :
4.434 + Graph::EdgeMap<T>(*(_G.graph)) { }
4.435 + EdgeMap(const GraphWrapper<Graph>& _G, T a) :
4.436 + Graph::EdgeMap<T>(*(_G.graph), a) { }
4.437 };
4.438 };
4.439
4.440 @@ -489,139 +358,57 @@
4.441 // };
4.442 // };
4.443
4.444 -// template<typename /*Graph*/GraphWrapper
4.445 -// /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >
4.446 -// class RevGraphWrapper :
4.447 -// public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {
4.448 -// protected:
4.449 -// //Graph* graph;
4.450 -
4.451 -// public:
4.452 -// //typedef Graph BaseGraph;
4.453
4.454 -// //typedef typename Graph::Node Node;
4.455 -// //typedef typename Graph::NodeIt NodeIt;
4.456 -
4.457 -// //typedef typename Graph::Edge Edge;
4.458 -// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
4.459 -// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;
4.460 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.461 -// //typedef typename Graph::EdgeIt EdgeIt;
4.462 -
4.463 -// //RevGraphWrapper() : graph(0) { }
4.464 -// RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }
4.465 -
4.466 -// //void setGraph(Graph& _graph) { graph = &_graph; }
4.467 -// //Graph& getGraph() const { return (*graph); }
4.468 -
4.469 -// //template<typename I> I& first(I& i) const { return graph->first(i); }
4.470 -// //template<typename I, typename P> I& first(I& i, const P& p) const {
4.471 -// // return graph->first(i, p); }
4.472 -
4.473 -// //template<typename I> I getNext(const I& i) const {
4.474 -// // return graph->getNext(i); }
4.475 -// //template<typename I> I& next(I &i) const { return graph->next(i); }
4.476 -
4.477 -// //template< typename It > It first() const {
4.478 -// // It e; first(e); return e; }
4.479 -
4.480 -// //template< typename It > It first(const Node& v) const {
4.481 -// // It e; first(e, v); return e; }
4.482 -
4.483 -// //Node head(const Edge& e) const { return graph->tail(e); }
4.484 -// //Node tail(const Edge& e) const { return graph->head(e); }
4.485 -
4.486 -// //template<typename I> bool valid(const I& i) const
4.487 -// // { return graph->valid(i); }
4.488 -
4.489 -// //template<typename I> void setInvalid(const I &i);
4.490 -// //{ return graph->setInvalid(i); }
4.491 -
4.492 -// //template<typename I> Node aNode(const I& e) const {
4.493 -// // return graph->aNode(e); }
4.494 -// //template<typename I> Node bNode(const I& e) const {
4.495 -// // return graph->bNode(e); }
4.496 -
4.497 -// //Node addNode() const { return graph->addNode(); }
4.498 -// //Edge addEdge(const Node& tail, const Node& head) const {
4.499 -// // return graph->addEdge(tail, head); }
4.500 -
4.501 -// //int nodeNum() const { return graph->nodeNum(); }
4.502 -// //int edgeNum() const { return graph->edgeNum(); }
4.503 -
4.504 -// //template<typename I> void erase(const I& i) const { graph->erase(i); }
4.505 -
4.506 -// //void clear() const { graph->clear(); }
4.507 -
4.508 -// template<typename T> class NodeMap :
4.509 -// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>
4.510 -// {
4.511 -// public:
4.512 -// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
4.513 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
4.514 -// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
4.515 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
4.516 -// };
4.517 -
4.518 -// template<typename T> class EdgeMap :
4.519 -// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
4.520 -// public:
4.521 -// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
4.522 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
4.523 -// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
4.524 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
4.525 -// };
4.526 -// };
4.527 -
4.528 - template<typename GraphWrapper>
4.529 - class RevGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {
4.530 + template<typename Graph>
4.531 + class RevGraphWrapper : public GraphWrapper<Graph> {
4.532 public:
4.533 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
4.534 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge;
4.535 + typedef typename GraphWrapper<Graph>::Node Node;
4.536 + typedef typename GraphWrapper<Graph>::Edge Edge;
4.537 //FIXME
4.538 - //If GraphWrapper::OutEdgeIt is not defined
4.539 + //If Graph::OutEdgeIt is not defined
4.540 //and we do not want to use RevGraphWrapper::InEdgeIt,
4.541 //this won't work, because of typedef
4.542 //OR
4.543 //graphs have to define their non-existing iterators to void
4.544 //Unfortunately all the typedefs are instantiated in templates,
4.545 //unlike other stuff
4.546 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt InEdgeIt;
4.547 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt OutEdgeIt;
4.548 + typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
4.549 + typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
4.550
4.551 - RevGraphWrapper(GraphWrapper& _gw) :
4.552 - GraphWrapperSkeleton1<GraphWrapper>(_gw) { }
4.553 +// RevGraphWrapper() : GraphWrapper<Graph>() { }
4.554 + RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
4.555
4.556 Node head(const Edge& e) const
4.557 - { return GraphWrapperSkeleton1<GraphWrapper>::tail(e); }
4.558 + { return GraphWrapper<Graph>::tail(e); }
4.559 Node tail(const Edge& e) const
4.560 - { return GraphWrapperSkeleton1<GraphWrapper>::head(e); }
4.561 + { return GraphWrapper<Graph>::head(e); }
4.562 };
4.563
4.564 //Subgraph on the same node-set and partial edge-set
4.565 - template<typename GraphWrapper, typename EdgeFilterMap>
4.566 - class SubGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {
4.567 + template<typename Graph, typename EdgeFilterMap>
4.568 + class SubGraphWrapper : public GraphWrapper<Graph> {
4.569 protected:
4.570 EdgeFilterMap* filter_map;
4.571 public:
4.572 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
4.573 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;
4.574 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge;
4.575 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::EdgeIt EdgeIt;
4.576 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt InEdgeIt;
4.577 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt OutEdgeIt;
4.578 + typedef typename GraphWrapper<Graph>::Node Node;
4.579 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
4.580 + typedef typename GraphWrapper<Graph>::Edge Edge;
4.581 + typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
4.582 + typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
4.583 + typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
4.584
4.585 - SubGraphWrapper(GraphWrapper& _gw, EdgeFilterMap& _filter_map) :
4.586 - GraphWrapperSkeleton1<GraphWrapper>(_gw), filter_map(&_filter_map) { }
4.587 +// SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
4.588 + SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) :
4.589 + GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { }
4.590
4.591 template<typename I> I& first(I& i) const {
4.592 - g->first(i);
4.593 - while (g->valid(i) && !filter_map->get(i)) { g->next(i); }
4.594 + graph->first(i);
4.595 + while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
4.596 return i;
4.597 }
4.598 template<typename I, typename P> I& first(I& i, const P& p) const {
4.599 - g->first(i, p);
4.600 - while (g->valid(i) && !filter_map->get(i)) { g->next(i); }
4.601 + graph->first(i, p);
4.602 + while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
4.603 return i;
4.604 }
4.605
4.606 @@ -629,8 +416,8 @@
4.607 // return gw.getNext(i);
4.608 //}
4.609 template<typename I> I& next(I &i) const {
4.610 - g->next(i);
4.611 - while (g->valid(i) && !filter_map->get(i)) { g->next(i); }
4.612 + graph->next(i);
4.613 + while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
4.614 return i;
4.615 }
4.616
4.617 @@ -801,39 +588,21 @@
4.618 // };
4.619
4.620
4.621 - template<typename GraphWrapper>
4.622 - class UndirGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {
4.623 + template<typename Graph>
4.624 + class UndirGraphWrapper : public GraphWrapper<Graph> {
4.625 protected:
4.626 -// GraphWrapper gw;
4.627 + typedef typename Graph::Edge GraphEdge;
4.628 + typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
4.629 + typedef typename Graph::InEdgeIt GraphInEdgeIt;
4.630 + public:
4.631 + typedef typename GraphWrapper<Graph>::Node Node;
4.632 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
4.633
4.634 - public:
4.635 - //typedef GraphWrapper BaseGraph;
4.636 +// UndirGraphWrapper() : GraphWrapper<Graph>() { }
4.637 + UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
4.638
4.639 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
4.640 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;
4.641 -
4.642 - //private:
4.643 - //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy
4.644 - //legyenek, at kell irni
4.645 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
4.646 - GraphWrapper::Edge GraphEdge;
4.647 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
4.648 - GraphWrapper::OutEdgeIt GraphOutEdgeIt;
4.649 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
4.650 - GraphWrapper::InEdgeIt GraphInEdgeIt;
4.651 - //public:
4.652 -
4.653 - //UndirGraphWrapper() : graph(0) { }
4.654 - UndirGraphWrapper(GraphWrapper& _gw) :
4.655 - GraphWrapperSkeleton1<GraphWrapper>(_gw) { }
4.656 -
4.657 - //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
4.658 -
4.659 - //void setGraph(Graph& _graph) { graph = &_graph; }
4.660 - //Graph& getGraph() const { return (*graph); }
4.661 -
4.662 class Edge {
4.663 - friend class UndirGraphWrapper<GraphWrapper>;
4.664 + friend class UndirGraphWrapper<Graph>;
4.665 protected:
4.666 bool out_or_in; //true iff out
4.667 GraphOutEdgeIt out;
4.668 @@ -866,42 +635,42 @@
4.669 };
4.670
4.671 class OutEdgeIt : public Edge {
4.672 - friend class UndirGraphWrapper<GraphWrapper>;
4.673 + friend class UndirGraphWrapper<Graph>;
4.674 public:
4.675 OutEdgeIt() : Edge() { }
4.676 OutEdgeIt(const Invalid& i) : Edge(i) { }
4.677 - OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
4.678 + OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
4.679 : Edge() {
4.680 - out_or_in=true; _G.g->first(out, n);
4.681 - if (!(_G.g->valid(out))) { out_or_in=false; _G.g->first(in, n); }
4.682 + out_or_in=true; _G.graph->first(out, n);
4.683 + if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
4.684 }
4.685 };
4.686
4.687 typedef OutEdgeIt InEdgeIt;
4.688
4.689 class EdgeIt : public Edge {
4.690 - friend class UndirGraphWrapper<GraphWrapper>;
4.691 + friend class UndirGraphWrapper<Graph>;
4.692 protected:
4.693 NodeIt v;
4.694 public:
4.695 EdgeIt() : Edge() { }
4.696 EdgeIt(const Invalid& i) : Edge(i) { }
4.697 - EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
4.698 + EdgeIt(const UndirGraphWrapper<Graph>& _G)
4.699 : Edge() {
4.700 out_or_in=true;
4.701 //Node v;
4.702 _G.first(v);
4.703 - if (_G.valid(v)) _G.g->first(out); else out=INVALID;
4.704 - while (_G.valid(v) && !_G.g->valid(out)) {
4.705 - _G.g->next(v);
4.706 - if (_G.valid(v)) _G.g->first(out);
4.707 + if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
4.708 + while (_G.valid(v) && !_G.graph->valid(out)) {
4.709 + _G.graph->next(v);
4.710 + if (_G.valid(v)) _G.graph->first(out);
4.711 }
4.712 }
4.713 };
4.714
4.715 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
4.716 - e.out_or_in=true; g->first(e.out, n);
4.717 - if (!(g->valid(e.out))) { e.out_or_in=false; g->first(e.in, n); }
4.718 + e.out_or_in=true; graph->first(e.out, n);
4.719 + if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }
4.720 return e;
4.721 }
4.722
4.723 @@ -909,47 +678,47 @@
4.724 e.out_or_in=true;
4.725 //NodeIt v;
4.726 first(e.v);
4.727 - if (valid(e.v)) g->first(e.out, e.v); else e.out=INVALID;
4.728 - while (valid(e.v) && !g->valid(e.out)) {
4.729 - g->next(e.v);
4.730 - if (valid(e.v)) g->first(e.out, e.v);
4.731 + if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;
4.732 + while (valid(e.v) && !graph->valid(e.out)) {
4.733 + graph->next(e.v);
4.734 + if (valid(e.v)) graph->first(e.out, e.v);
4.735 }
4.736 return e;
4.737 }
4.738
4.739 - template<typename I> I& first(I& i) const { g->first(i); return i; }
4.740 + template<typename I> I& first(I& i) const { graph->first(i); return i; }
4.741 template<typename I, typename P> I& first(I& i, const P& p) const {
4.742 - g->first(i, p); return i; }
4.743 + graph->first(i, p); return i; }
4.744
4.745 OutEdgeIt& next(OutEdgeIt& e) const {
4.746 if (e.out_or_in) {
4.747 - Node n=g->tail(e.out);
4.748 - g->next(e.out);
4.749 - if (!g->valid(e.out)) { e.out_or_in=false; g->first(e.in, n); }
4.750 + Node n=graph->tail(e.out);
4.751 + graph->next(e.out);
4.752 + if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
4.753 } else {
4.754 - g->next(e.in);
4.755 + graph->next(e.in);
4.756 }
4.757 return e;
4.758 }
4.759
4.760 EdgeIt& next(EdgeIt& e) const {
4.761 //NodeIt v=tail(e);
4.762 - g->next(e.out);
4.763 - while (valid(e.v) && !g->valid(e.out)) {
4.764 + graph->next(e.out);
4.765 + while (valid(e.v) && !graph->valid(e.out)) {
4.766 next(e.v);
4.767 - if (valid(e.v)) g->first(e.out, e.v);
4.768 + if (valid(e.v)) graph->first(e.out, e.v);
4.769 }
4.770 return e;
4.771 }
4.772
4.773 - template<typename I> I& next(I &i) const { return g->next(i); }
4.774 + template<typename I> I& next(I &i) const { return graph->next(i); }
4.775 // template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
4.776
4.777 template< typename It > It first() const {
4.778 - It e; first(e); return e; }
4.779 + It e; this->first(e); return e; }
4.780
4.781 template< typename It > It first(const Node& v) const {
4.782 - It e; first(e, v); return e; }
4.783 + It e; this->first(e, v); return e; }
4.784
4.785 // Node head(const Edge& e) const { return gw.head(e); }
4.786 // Node tail(const Edge& e) const { return gw.tail(e); }
4.787 @@ -966,9 +735,9 @@
4.788 // return graph->bNode(e); }
4.789
4.790 Node aNode(const OutEdgeIt& e) const {
4.791 - if (e.out_or_in) return g->tail(e); else return g->head(e); }
4.792 + if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
4.793 Node bNode(const OutEdgeIt& e) const {
4.794 - if (e.out_or_in) return g->head(e); else return g->tail(e); }
4.795 + if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
4.796
4.797 // Node addNode() const { return gw.addNode(); }
4.798
4.799 @@ -980,21 +749,21 @@
4.800
4.801 // void clear() const { gw.clear(); }
4.802
4.803 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
4.804 +// template<typename T> class NodeMap : public Graph::NodeMap<T> {
4.805 // public:
4.806 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
4.807 -// GraphWrapper::NodeMap<T>(_G.gw) { }
4.808 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
4.809 -// GraphWrapper::NodeMap<T>(_G.gw, a) { }
4.810 +// NodeMap(const UndirGraphWrapper<Graph>& _G) :
4.811 +// Graph::NodeMap<T>(_G.gw) { }
4.812 +// NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
4.813 +// Graph::NodeMap<T>(_G.gw, a) { }
4.814 // };
4.815
4.816 // template<typename T> class EdgeMap :
4.817 -// public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
4.818 +// public GraphWrapperSkeleton<Graph>::EdgeMap<T> {
4.819 // public:
4.820 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
4.821 -// GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
4.822 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
4.823 -// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
4.824 +// EdgeMap(const UndirGraphWrapper<Graph>& _G) :
4.825 +// GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }
4.826 +// EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
4.827 +// Graph::EdgeMap<T>(_G.gw, a) { }
4.828 // };
4.829 };
4.830
4.831 @@ -1071,32 +840,21 @@
4.832 // };
4.833
4.834
4.835 - template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
4.836 - class ResGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper>{
4.837 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.838 + class ResGraphWrapper : public GraphWrapper<Graph>{
4.839 public:
4.840 - //typedef Graph BaseGraph;
4.841 - //typedef TrivGraphWrapper<const Graph> GraphWrapper;
4.842 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
4.843 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;
4.844 - private:
4.845 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
4.846 - GraphWrapper::OutEdgeIt OldOutEdgeIt;
4.847 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
4.848 - GraphWrapper::InEdgeIt OldInEdgeIt;
4.849 + typedef typename GraphWrapper<Graph>::Node Node;
4.850 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
4.851 protected:
4.852 - //const Graph* graph;
4.853 - //GraphWrapper gw;
4.854 + typedef typename Graph::OutEdgeIt OldOutEdgeIt;
4.855 + typedef typename Graph::InEdgeIt OldInEdgeIt;
4.856 FlowMap* flow;
4.857 const CapacityMap* capacity;
4.858 public:
4.859
4.860 - ResGraphWrapper(GraphWrapper& _gw, FlowMap& _flow,
4.861 + ResGraphWrapper(Graph& _graph, FlowMap& _flow,
4.862 const CapacityMap& _capacity) :
4.863 - GraphWrapperSkeleton1<GraphWrapper>(_gw),
4.864 - flow(&_flow), capacity(&_capacity) { }
4.865 -
4.866 - //void setGraph(const Graph& _graph) { graph = &_graph; }
4.867 - //const Graph& getGraph() const { return (*graph); }
4.868 + GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
4.869
4.870 class Edge;
4.871 class OutEdgeIt;
4.872 @@ -1104,7 +862,7 @@
4.873 friend class OutEdgeIt;
4.874
4.875 class Edge {
4.876 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
4.877 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.878 protected:
4.879 bool out_or_in; //true, iff out
4.880 OldOutEdgeIt out;
4.881 @@ -1130,20 +888,20 @@
4.882
4.883
4.884 class OutEdgeIt : public Edge {
4.885 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
4.886 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.887 public:
4.888 OutEdgeIt() { }
4.889 //FIXME
4.890 OutEdgeIt(const Edge& e) : Edge(e) { }
4.891 OutEdgeIt(const Invalid& i) : Edge(i) { }
4.892 protected:
4.893 - OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
4.894 - resG.g->first(out, v);
4.895 - while( resG.g->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }
4.896 - if (!resG.g->valid(out)) {
4.897 + OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
4.898 + resG.graph->first(out, v);
4.899 + while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
4.900 + if (!resG.graph->valid(out)) {
4.901 out_or_in=0;
4.902 - resG.g->first(in, v);
4.903 - while( resG.g->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }
4.904 + resG.graph->first(in, v);
4.905 + while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
4.906 }
4.907 }
4.908 // public:
4.909 @@ -1169,30 +927,30 @@
4.910 typedef void InEdgeIt;
4.911
4.912 class EdgeIt : public Edge {
4.913 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
4.914 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.915 NodeIt v;
4.916 public:
4.917 EdgeIt() { }
4.918 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
4.919 EdgeIt(const Invalid& i) : Edge(i) { }
4.920 - EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
4.921 - resG.g->first(v);
4.922 - if (resG.g->valid(v)) resG.g->first(out, v); else out=INVALID;
4.923 - while (resG.g->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }
4.924 - while (resG.g->valid(v) && !resG.g->valid(out)) {
4.925 - resG.g->next(v);
4.926 - if (resG.g->valid(v)) resG.g->first(out, v);
4.927 - while (resG.g->valid(out) && !(resG.resCap(out)>0) ) { resG.g->next(out); }
4.928 + EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
4.929 + resG.graph->first(v);
4.930 + if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
4.931 + while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
4.932 + while (resG.graph->valid(v) && !resG.graph->valid(out)) {
4.933 + resG.graph->next(v);
4.934 + if (resG.graph->valid(v)) resG.graph->first(out, v);
4.935 + while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
4.936 }
4.937 - if (!resG.g->valid(out)) {
4.938 + if (!resG.graph->valid(out)) {
4.939 out_or_in=0;
4.940 - resG.g->first(v);
4.941 - if (resG.g->valid(v)) resG.g->first(in, v); else in=INVALID;
4.942 - while (resG.g->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }
4.943 - while (resG.g->valid(v) && !resG.g->valid(in)) {
4.944 - resG.g->next(v);
4.945 - if (resG.g->valid(v)) resG.g->first(in, v);
4.946 - while (resG.g->valid(in) && !(resG.resCap(in)>0) ) { resG.g->next(in); }
4.947 + resG.graph->first(v);
4.948 + if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
4.949 + while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
4.950 + while (resG.graph->valid(v) && !resG.graph->valid(in)) {
4.951 + resG.graph->next(v);
4.952 + if (resG.graph->valid(v)) resG.graph->first(in, v);
4.953 + while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
4.954 }
4.955 }
4.956 }
4.957 @@ -1229,7 +987,7 @@
4.958 // }
4.959 };
4.960
4.961 - NodeIt& first(NodeIt& v) const { g->first(v); return v; }
4.962 + NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
4.963 OutEdgeIt& first(OutEdgeIt& e, Node v) const {
4.964 e=OutEdgeIt(*this, v);
4.965 return e;
4.966 @@ -1239,52 +997,52 @@
4.967 return e;
4.968 }
4.969
4.970 - NodeIt& next(NodeIt& n) const { return g->next(n); }
4.971 + NodeIt& next(NodeIt& n) const { return graph->next(n); }
4.972
4.973 OutEdgeIt& next(OutEdgeIt& e) const {
4.974 if (e.out_or_in) {
4.975 - Node v=g->aNode(e.out);
4.976 - g->next(e.out);
4.977 - while( g->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }
4.978 - if (!g->valid(e.out)) {
4.979 + Node v=graph->aNode(e.out);
4.980 + graph->next(e.out);
4.981 + while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
4.982 + if (!graph->valid(e.out)) {
4.983 e.out_or_in=0;
4.984 - g->first(e.in, v);
4.985 - while( g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
4.986 + graph->first(e.in, v);
4.987 + while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
4.988 }
4.989 } else {
4.990 - g->next(e.in);
4.991 - while( g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
4.992 + graph->next(e.in);
4.993 + while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
4.994 }
4.995 return e;
4.996 }
4.997
4.998 EdgeIt& next(EdgeIt& e) const {
4.999 if (e.out_or_in) {
4.1000 - g->next(e.out);
4.1001 - while (g->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }
4.1002 - while (g->valid(e.v) && !g->valid(e.out)) {
4.1003 - g->next(e.v);
4.1004 - if (g->valid(e.v)) g->first(e.out, e.v);
4.1005 - while (g->valid(e.out) && !(resCap(e.out)>0) ) { g->next(e.out); }
4.1006 + graph->next(e.out);
4.1007 + while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
4.1008 + while (graph->valid(e.v) && !graph->valid(e.out)) {
4.1009 + graph->next(e.v);
4.1010 + if (graph->valid(e.v)) graph->first(e.out, e.v);
4.1011 + while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
4.1012 }
4.1013 - if (!g->valid(e.out)) {
4.1014 + if (!graph->valid(e.out)) {
4.1015 e.out_or_in=0;
4.1016 - g->first(e.v);
4.1017 - if (g->valid(e.v)) g->first(e.in, e.v); else e.in=INVALID;
4.1018 - while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
4.1019 - while (g->valid(e.v) && !g->valid(e.in)) {
4.1020 - g->next(e.v);
4.1021 - if (g->valid(e.v)) g->first(e.in, e.v);
4.1022 - while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
4.1023 + graph->first(e.v);
4.1024 + if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
4.1025 + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
4.1026 + while (graph->valid(e.v) && !graph->valid(e.in)) {
4.1027 + graph->next(e.v);
4.1028 + if (graph->valid(e.v)) graph->first(e.in, e.v);
4.1029 + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
4.1030 }
4.1031 }
4.1032 } else {
4.1033 - g->next(e.in);
4.1034 - while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
4.1035 - while (g->valid(e.v) && !g->valid(e.in)) {
4.1036 - g->next(e.v);
4.1037 - if (g->valid(e.v)) g->first(e.in, e.v);
4.1038 - while (g->valid(e.in) && !(resCap(e.in)>0) ) { g->next(e.in); }
4.1039 + graph->next(e.in);
4.1040 + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
4.1041 + while (graph->valid(e.v) && !graph->valid(e.in)) {
4.1042 + graph->next(e.v);
4.1043 + if (graph->valid(e.v)) graph->first(e.in, e.v);
4.1044 + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
4.1045 }
4.1046 }
4.1047 return e;
4.1048 @@ -1306,25 +1064,25 @@
4.1049 }
4.1050
4.1051 Node tail(Edge e) const {
4.1052 - return ((e.out_or_in) ? g->aNode(e.out) : g->aNode(e.in)); }
4.1053 + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
4.1054 Node head(Edge e) const {
4.1055 - return ((e.out_or_in) ? g->bNode(e.out) : g->bNode(e.in)); }
4.1056 + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
4.1057
4.1058 Node aNode(OutEdgeIt e) const {
4.1059 - return ((e.out_or_in) ? g->aNode(e.out) : g->aNode(e.in)); }
4.1060 + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
4.1061 Node bNode(OutEdgeIt e) const {
4.1062 - return ((e.out_or_in) ? g->bNode(e.out) : g->bNode(e.in)); }
4.1063 + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
4.1064
4.1065 - int nodeNum() const { return g->nodeNum(); }
4.1066 + int nodeNum() const { return graph->nodeNum(); }
4.1067 //FIXME
4.1068 - //int edgeNum() const { return g->edgeNum(); }
4.1069 + //int edgeNum() const { return graph->edgeNum(); }
4.1070
4.1071
4.1072 - int id(Node v) const { return g->id(v); }
4.1073 + int id(Node v) const { return graph->id(v); }
4.1074
4.1075 - bool valid(Node n) const { return g->valid(n); }
4.1076 + bool valid(Node n) const { return graph->valid(n); }
4.1077 bool valid(Edge e) const {
4.1078 - return e.out_or_in ? g->valid(e.out) : g->valid(e.in); }
4.1079 + return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
4.1080
4.1081 void augment(const Edge& e, Number a) const {
4.1082 if (e.out_or_in)
4.1083 @@ -1348,12 +1106,12 @@
4.1084 return (flow->get(in));
4.1085 }
4.1086
4.1087 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
4.1088 +// template<typename T> class NodeMap : public Graph::NodeMap<T> {
4.1089 // public:
4.1090 -// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
4.1091 -// : GraphWrapper::NodeMap<T>(_G.gw) { }
4.1092 -// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
4.1093 -// T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
4.1094 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
4.1095 +// : Graph::NodeMap<T>(_G.gw) { }
4.1096 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
4.1097 +// T a) : Graph::NodeMap<T>(_G.gw, a) { }
4.1098 // };
4.1099
4.1100 // template <typename T>
4.1101 @@ -1368,10 +1126,10 @@
4.1102
4.1103 template <typename T>
4.1104 class EdgeMap {
4.1105 - typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
4.1106 + typename Graph::EdgeMap<T> forward_map, backward_map;
4.1107 public:
4.1108 - EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
4.1109 - EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
4.1110 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
4.1111 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
4.1112 void set(Edge e, T a) {
4.1113 if (e.out_or_in)
4.1114 forward_map.set(e.out, a);
4.1115 @@ -1387,25 +1145,25 @@
4.1116 };
4.1117 };
4.1118
4.1119 - //Subgraph on the same node-set and partial edge-set
4.1120 - template<typename GraphWrapper, typename FirstOutEdgesMap>
4.1121 - class ErasingFirstGraphWrapper : public GraphWrapperSkeleton1<GraphWrapper> {
4.1122 + //ErasingFirstGraphWrapper for blocking flows
4.1123 + template<typename Graph, typename FirstOutEdgesMap>
4.1124 + class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
4.1125 protected:
4.1126 FirstOutEdgesMap* first_out_edges;
4.1127 public:
4.1128 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::Node Node;
4.1129 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::NodeIt NodeIt;
4.1130 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::Edge Edge;
4.1131 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::EdgeIt EdgeIt;
4.1132 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::InEdgeIt InEdgeIt;
4.1133 - typedef typename GraphWrapperSkeleton1<GraphWrapper>::OutEdgeIt OutEdgeIt;
4.1134 + typedef typename GraphWrapper<Graph>::Node Node;
4.1135 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
4.1136 + typedef typename GraphWrapper<Graph>::Edge Edge;
4.1137 + typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
4.1138 + typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
4.1139 + typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
4.1140
4.1141 - ErasingFirstGraphWrapper(GraphWrapper& _gw, FirstOutEdgesMap& _first_out_edges) :
4.1142 - GraphWrapperSkeleton1<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }
4.1143 + ErasingFirstGraphWrapper(Graph& _graph,
4.1144 + FirstOutEdgesMap& _first_out_edges) :
4.1145 + GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
4.1146
4.1147 template<typename I> I& first(I& i) const {
4.1148 - g->first(i);
4.1149 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
4.1150 + graph->first(i);
4.1151 return i;
4.1152 }
4.1153 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
4.1154 @@ -1413,8 +1171,7 @@
4.1155 return e;
4.1156 }
4.1157 template<typename I, typename P> I& first(I& i, const P& p) const {
4.1158 - g->first(i, p);
4.1159 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
4.1160 + graph->first(i, p);
4.1161 return i;
4.1162 }
4.1163
4.1164 @@ -1422,8 +1179,7 @@
4.1165 // return gw.getNext(i);
4.1166 //}
4.1167 template<typename I> I& next(I &i) const {
4.1168 - g->next(i);
4.1169 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
4.1170 + graph->next(i);
4.1171 return i;
4.1172 }
4.1173
4.1174 @@ -1440,246 +1196,6 @@
4.1175 }
4.1176 };
4.1177
4.1178 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.1179 -// class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
4.1180 -// protected:
4.1181 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
4.1182 -// //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
4.1183 -// public:
4.1184 -// ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
4.1185 -// const CapacityMap& _capacity) :
4.1186 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
4.1187 -// first_out_edges(*this) /*, dist(*this)*/ {
4.1188 -// for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
4.1189 -// OutEdgeIt e;
4.1190 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
4.1191 -// first_out_edges.set(n, e);
4.1192 -// }
4.1193 -// }
4.1194 -
4.1195 -// //void setGraph(Graph& _graph) { graph = &_graph; }
4.1196 -// //Graph& getGraph() const { return (*graph); }
4.1197 -
4.1198 -// //TrivGraphWrapper() : graph(0) { }
4.1199 -// //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.1200 -
4.1201 -// //typedef Graph BaseGraph;
4.1202 -
4.1203 -// //typedef typename Graph::Node Node;
4.1204 -// //typedef typename Graph::NodeIt NodeIt;
4.1205 -
4.1206 -// //typedef typename Graph::Edge Edge;
4.1207 -// //typedef typename Graph::OutEdgeIt OutEdgeIt;
4.1208 -// //typedef typename Graph::InEdgeIt InEdgeIt;
4.1209 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.1210 -// //typedef typename Graph::EdgeIt EdgeIt;
4.1211 -
4.1212 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
4.1213 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
4.1214 -
4.1215 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
4.1216 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
4.1217 -// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
4.1218 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.1219 -// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
4.1220 -
4.1221 -// NodeIt& first(NodeIt& n) const {
4.1222 -// return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
4.1223 -// }
4.1224 -
4.1225 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
4.1226 -// e=first_out_edges.get(n);
4.1227 -// return e;
4.1228 -// }
4.1229 -
4.1230 -// //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
4.1231 -// //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
4.1232 -// // return first(i, p); }
4.1233 -
4.1234 -// //template<typename I> I getNext(const I& i) const {
4.1235 -// // return gw.getNext(i); }
4.1236 -// //template<typename I> I& next(I &i) const { return gw.next(i); }
4.1237 -
4.1238 -// template< typename It > It first() const {
4.1239 -// It e; first(e); return e; }
4.1240 -
4.1241 -// template< typename It > It first(const Node& v) const {
4.1242 -// It e; first(e, v); return e; }
4.1243 -
4.1244 -// //Node head(const Edge& e) const { return gw.head(e); }
4.1245 -// //Node tail(const Edge& e) const { return gw.tail(e); }
4.1246 -
4.1247 -// //template<typename I> bool valid(const I& i) const
4.1248 -// // { return gw.valid(i); }
4.1249 -
4.1250 -// //int nodeNum() const { return gw.nodeNum(); }
4.1251 -// //int edgeNum() const { return gw.edgeNum(); }
4.1252 -
4.1253 -// //template<typename I> Node aNode(const I& e) const {
4.1254 -// // return gw.aNode(e); }
4.1255 -// //template<typename I> Node bNode(const I& e) const {
4.1256 -// // return gw.bNode(e); }
4.1257 -
4.1258 -// //Node addNode() const { return gw.addNode(); }
4.1259 -// //Edge addEdge(const Node& tail, const Node& head) const {
4.1260 -// // return gw.addEdge(tail, head); }
4.1261 -
4.1262 -// //void erase(const OutEdgeIt& e) {
4.1263 -// // first_out_edge(this->tail(e))=e;
4.1264 -// //}
4.1265 -// void erase(const Edge& e) {
4.1266 -// OutEdgeIt f(e);
4.1267 -// next(f);
4.1268 -// first_out_edges.set(this->tail(e), f);
4.1269 -// }
4.1270 -// //template<typename I> void erase(const I& i) const { gw.erase(i); }
4.1271 -
4.1272 -// //void clear() const { gw.clear(); }
4.1273 -
4.1274 -// template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
4.1275 -// public:
4.1276 -// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
4.1277 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
4.1278 -// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
4.1279 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
4.1280 -// };
4.1281 -
4.1282 -// template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
4.1283 -// public:
4.1284 -// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
4.1285 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
4.1286 -// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
4.1287 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
4.1288 -// };
4.1289 -// };
4.1290 -
4.1291 -// template<typename GraphWrapper>
4.1292 -// class FilterGraphWrapper {
4.1293 -// };
4.1294 -
4.1295 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.1296 -// class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
4.1297 -
4.1298 -// //Graph* graph;
4.1299 -
4.1300 -// public:
4.1301 -// //typedef Graph BaseGraph;
4.1302 -
4.1303 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
4.1304 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
4.1305 -
4.1306 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
4.1307 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
4.1308 -// //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
4.1309 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.1310 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
4.1311 -
4.1312 -// //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
4.1313 -
4.1314 -// public:
4.1315 -// FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
4.1316 -// const CapacityMap& _capacity) :
4.1317 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
4.1318 -// }
4.1319 -
4.1320 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
4.1321 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
4.1322 -// while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
4.1323 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
4.1324 -// return e;
4.1325 -// }
4.1326 -
4.1327 -// NodeIt& next(NodeIt& e) const {
4.1328 -// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
4.1329 -// }
4.1330 -
4.1331 -// OutEdgeIt& next(OutEdgeIt& e) const {
4.1332 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
4.1333 -// while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
4.1334 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
4.1335 -// return e;
4.1336 -// }
4.1337 -
4.1338 -// NodeIt& first(NodeIt& n) const {
4.1339 -// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
4.1340 -// }
4.1341 -
4.1342 -// void erase(const Edge& e) {
4.1343 -// OutEdgeIt f(e);
4.1344 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
4.1345 -// while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
4.1346 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
4.1347 -// first_out_edges.set(this->tail(e), f);
4.1348 -// }
4.1349 -
4.1350 -// //TrivGraphWrapper() : graph(0) { }
4.1351 -// //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.1352 -
4.1353 -// //void setGraph(Graph& _graph) { graph = &_graph; }
4.1354 -// //Graph& getGraph() const { return (*graph); }
4.1355 -
4.1356 -// //template<typename I> I& first(I& i) const { return gw.first(i); }
4.1357 -// //template<typename I, typename P> I& first(I& i, const P& p) const {
4.1358 -// // return gw.first(i, p); }
4.1359 -
4.1360 -// //template<typename I> I getNext(const I& i) const {
4.1361 -// // return gw.getNext(i); }
4.1362 -// //template<typename I> I& next(I &i) const { return gw.next(i); }
4.1363 -
4.1364 -// template< typename It > It first() const {
4.1365 -// It e; first(e); return e; }
4.1366 -
4.1367 -// template< typename It > It first(const Node& v) const {
4.1368 -// It e; first(e, v); return e; }
4.1369 -
4.1370 -// //Node head(const Edge& e) const { return gw.head(e); }
4.1371 -// //Node tail(const Edge& e) const { return gw.tail(e); }
4.1372 -
4.1373 -// //template<typename I> bool valid(const I& i) const
4.1374 -// // { return gw.valid(i); }
4.1375 -
4.1376 -// //template<typename I> void setInvalid(const I &i);
4.1377 -// //{ return gw.setInvalid(i); }
4.1378 -
4.1379 -// //int nodeNum() const { return gw.nodeNum(); }
4.1380 -// //int edgeNum() const { return gw.edgeNum(); }
4.1381 -
4.1382 -// //template<typename I> Node aNode(const I& e) const {
4.1383 -// // return gw.aNode(e); }
4.1384 -// //template<typename I> Node bNode(const I& e) const {
4.1385 -// // return gw.bNode(e); }
4.1386 -
4.1387 -// //Node addNode() const { return gw.addNode(); }
4.1388 -// //Edge addEdge(const Node& tail, const Node& head) const {
4.1389 -// // return gw.addEdge(tail, head); }
4.1390 -
4.1391 -// //template<typename I> void erase(const I& i) const { gw.erase(i); }
4.1392 -
4.1393 -// //void clear() const { gw.clear(); }
4.1394 -
4.1395 -// template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
4.1396 -// public:
4.1397 -// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
4.1398 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
4.1399 -// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
4.1400 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
4.1401 -// };
4.1402 -
4.1403 -// template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
4.1404 -// public:
4.1405 -// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
4.1406 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
4.1407 -// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
4.1408 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
4.1409 -// };
4.1410 -
4.1411 -// public:
4.1412 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
4.1413 -
4.1414 -// };
4.1415 -
4.1416 -
4.1417 -
4.1418 // // FIXME: comparison should be made better!!!
4.1419 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
4.1420 // class ResGraphWrapper