Nicer and more documented graph_wrapper.h file.
These are only the first steps for making this file more beautiful.
1.1 --- a/src/hugo/graph_wrapper.h Thu Sep 02 17:30:06 2004 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Thu Sep 02 17:56:40 2004 +0000
1.3 @@ -100,17 +100,6 @@
1.4 // Graph& getGraph() const { return *graph; }
1.5
1.6 typedef typename Graph::Node Node;
1.7 -// class Node : public Graph::Node {
1.8 -// friend class GraphWrapper<Graph>;
1.9 -// public:
1.10 -// Node() { }
1.11 -// Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
1.12 -// // /// \bug construction throughrthr multiple levels should be
1.13 -// // /// handled better
1.14 -// // Node(const typename ParentGraph::ParentGraph::Node& _n) :
1.15 -// // Graph::Node(_n) { }
1.16 -// Node(const Invalid& i) : Graph::Node(i) { }
1.17 -// };
1.18 class NodeIt : public Node {
1.19 const GraphWrapper<Graph>* gw;
1.20 friend class GraphWrapper<Graph>;
1.21 @@ -129,13 +118,6 @@
1.22 }
1.23 };
1.24 typedef typename Graph::Edge Edge;
1.25 -// class Edge : public Graph::Edge {
1.26 -// friend class GraphWrapper<Graph>;
1.27 -// public:
1.28 -// Edge() { }
1.29 -// Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
1.30 -// Edge(const Invalid& i) : Graph::Edge(i) { }
1.31 -// };
1.32 class OutEdgeIt : public Edge {
1.33 const GraphWrapper<Graph>* gw;
1.34 friend class GraphWrapper<Graph>;
1.35 @@ -277,13 +259,10 @@
1.36
1.37 typedef typename GraphWrapper<Graph>::Node Node;
1.38 typedef typename GraphWrapper<Graph>::Edge Edge;
1.39 - //If Graph::OutEdgeIt is not defined
1.40 - //and we do not want to use RevGraphWrapper::InEdgeIt,
1.41 - //the typdef techinque does not work.
1.42 - //Unfortunately all the typedefs are instantiated in templates.
1.43 - //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
1.44 - //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
1.45 -
1.46 + //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
1.47 + //because this does not work is some of them are not defined in the
1.48 + //original graph. The problem with this is that typedef-ed stuff
1.49 + //are instantiated in c++.
1.50 class OutEdgeIt : public Edge {
1.51 const RevGraphWrapper<Graph>* gw;
1.52 friend class GraphWrapper<Graph>;
1.53 @@ -382,21 +361,6 @@
1.54 edge_filter_map(&_edge_filter_map) { }
1.55
1.56 typedef typename GraphWrapper<Graph>::Node Node;
1.57 -// class NodeIt {
1.58 -// friend class GraphWrapper<Graph>;
1.59 -// friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.60 -// typename Graph::NodeIt n;
1.61 -// public:
1.62 -// NodeIt() { }
1.63 -// NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.64 -// NodeIt(const Invalid& i) : n(i) { }
1.65 -// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.66 -// n(*(_G.graph)) {
1.67 -// while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
1.68 -// _G.graph->next(n);
1.69 -// }
1.70 -// operator Node() const { return Node(typename Graph::Node(n)); }
1.71 -// };
1.72 class NodeIt : public Node {
1.73 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
1.74 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.75 @@ -560,21 +524,19 @@
1.76 /// Returns true if \c n is hidden.
1.77 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
1.78
1.79 - /// This is a linear time operation and works only if
1.80 - /// NodeIt is defined.
1.81 + /// \warning This is a linear time operation and works only if
1.82 + /// \c Graph::NodeIt is defined.
1.83 int nodeNum() const {
1.84 int i=0;
1.85 - NodeIt n;
1.86 - for (this->first(n); this->valid(n); this->next(n)) ++i;
1.87 + for (NodeIt n(*this); n!=INVALID; ++n) ++i;
1.88 return i;
1.89 }
1.90
1.91 - /// This is a linear time operation and works only if
1.92 - /// EdgeIt is defined.
1.93 + /// \warning This is a linear time operation and works only if
1.94 + /// \c Graph::EdgeIt is defined.
1.95 int edgeNum() const {
1.96 int i=0;
1.97 - EdgeIt e;
1.98 - for (this->first(e); this->valid(e); this->next(e)) ++i;
1.99 + for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1.100 return i;
1.101 }
1.102
1.103 @@ -689,15 +651,31 @@
1.104
1.105
1.106 ///\brief A wrapper for composing a subgraph of a
1.107 - /// bidirected graph composed from a directed one.
1.108 - /// experimental, for fezso's sake.
1.109 + /// bidirected graph made from a directed one.
1.110 ///
1.111 - /// A wrapper for composing a subgraps of a
1.112 - /// bidirected graph composed from a directed one.
1.113 - /// experimental, for fezso's sake.
1.114 - /// A bidirected graph is composed over the directed one without physical
1.115 - /// storage. As the oppositely directed edges are logically different ones
1.116 - /// the maps are able to attach different values for them.
1.117 + /// Suppose that for a directed graph $G=(V, A)$,
1.118 + /// two predicates on the edge-set, $forward_filter$, and $backward_filter$
1.119 + /// is given, and we are dealing with the directed graph
1.120 + /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$.
1.121 + /// The purpose of writing + instead of union is because parallel
1.122 + /// edges can arose.
1.123 + /// In other words, a subgraph of the bidirected graph obtained, which
1.124 + /// is given by orienting the edges of the original graph in both directions.
1.125 + /// An example for such a construction is the \c RevGraphWrapper where the
1.126 + /// forward_filter is everywhere false and the backward_filter is
1.127 + /// everywhere true. We note that for sake of efficiency,
1.128 + /// \c RevGraphWrapper is implemented in a different way.
1.129 + /// But BidirGraphWrapper is obtained from
1.130 + /// SubBidirGraphWrapper by considering everywhere true
1.131 + /// predicates both forward_filter and backward_filter.
1.132 + /// Finally, one of the most important applications of SubBidirGraphWrapper
1.133 + /// is ResGraphWrapper, which stands for the residual graph in directed
1.134 + /// flow and circulation problems.
1.135 + /// As wrappers usually, the SubBidirGraphWrapper implements the
1.136 + /// above mentioned graph structure without its physical storage,
1.137 + /// that is the whole stuff eats constant memory.
1.138 + /// As the oppositely directed edges are logical different,
1.139 + /// the maps are able to attach different values for them.
1.140 template<typename Graph,
1.141 typename ForwardFilterMap, typename BackwardFilterMap>
1.142 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
1.143 @@ -707,8 +685,7 @@
1.144 ForwardFilterMap* forward_filter;
1.145 BackwardFilterMap* backward_filter;
1.146
1.147 - SubBidirGraphWrapper() : GraphWrapper<Graph>()/*,
1.148 - capacity(0), flow(0)*/ { }
1.149 + SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
1.150 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
1.151 forward_filter=&_forward_filter;
1.152 }
1.153 @@ -733,25 +710,25 @@
1.154 friend class Edge;
1.155 friend class OutEdgeIt;
1.156
1.157 - //template<typename T> class NodeMap;
1.158 template<typename T> class EdgeMap;
1.159
1.160 typedef typename GraphWrapper<Graph>::Node Node;
1.161 - //typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.162
1.163 typedef typename Graph::Edge GraphEdge;
1.164 + /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
1.165 + /// Graph::Edge. It contains an extra bool flag which shows if the
1.166 + /// edge is the backward version of the original edge.
1.167 class Edge : public Graph::Edge {
1.168 friend class SubBidirGraphWrapper<Graph,
1.169 ForwardFilterMap, BackwardFilterMap>;
1.170 - ///\bug ez nem is kell
1.171 - //template<typename T> friend class NodeMap;
1.172 template<typename T> friend class EdgeMap;
1.173 protected:
1.174 bool backward; //true, iff backward
1.175 -// typename Graph::Edge e;
1.176 public:
1.177 Edge() { }
1.178 - ///\bug =false kell-e? zsoltnak kell az addEdge miatt
1.179 + /// \todo =false is needed, or causes problems?
1.180 + /// If \c _backward is false, then we get an edge corresponding to the
1.181 + /// original one, otherwise its oppositely directed pair is obtained.
1.182 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
1.183 Graph::Edge(e), backward(_backward) { }
1.184 Edge(Invalid i) : Graph::Edge(i), backward(true) { }
1.185 @@ -958,7 +935,6 @@
1.186 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.187 i=OutEdgeIt(*this, p); return i;
1.188 }
1.189 -// FIXME not tested
1.190 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.191 i=InEdgeIt(*this, p); return i;
1.192 }
1.193 @@ -1052,54 +1028,22 @@
1.194 return f;
1.195 }
1.196
1.197 -// int nodeNum() const { return graph->nodeNum(); }
1.198 - //FIXME
1.199 - void edgeNum() const { }
1.200 - //int edgeNum() const { return graph->edgeNum(); }
1.201 -
1.202 -
1.203 -// int id(Node v) const { return graph->id(v); }
1.204 -
1.205 -// bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.206 -// bool valid(Edge e) const {
1.207 -// return this->graph->valid(e);
1.208 -// //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.209 -// }
1.210 + /// \warning This is a linear time operation and works only if
1.211 + /// \c Graph::EdgeIt is defined.
1.212 + int edgeNum() const {
1.213 + int i=0;
1.214 + for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1.215 + return i;
1.216 + }
1.217
1.218 bool forward(const Edge& e) const { return !e.backward; }
1.219 bool backward(const Edge& e) const { return e.backward; }
1.220
1.221 -// void augment(const Edge& e, Number a) const {
1.222 -// if (!e.backward)
1.223 -// // flow->set(e.out, flow->get(e.out)+a);
1.224 -// flow->set(e, (*flow)[e]+a);
1.225 -// else
1.226 -// // flow->set(e.in, flow->get(e.in)-a);
1.227 -// flow->set(e, (*flow)[e]-a);
1.228 -// }
1.229 -
1.230 -// bool enabled(const Edge& e) const {
1.231 -// if (!e.backward)
1.232 -// // return (capacity->get(e.out)-flow->get(e.out));
1.233 -// //return ((*capacity)[e]-(*flow)[e]);
1.234 -// return true;
1.235 -// else
1.236 -// // return (flow->get(e.in));
1.237 -// //return ((*flow)[e]);
1.238 -// return true;
1.239 -// }
1.240 -
1.241 -// Number enabled(typename Graph::OutEdgeIt out) const {
1.242 -// // return (capacity->get(out)-flow->get(out));
1.243 -// return ((*capacity)[out]-(*flow)[out]);
1.244 -// }
1.245 -
1.246 -// Number enabled(typename Graph::InEdgeIt in) const {
1.247 -// // return (flow->get(in));
1.248 -// return ((*flow)[in]);
1.249 -// }
1.250
1.251 template <typename T>
1.252 + /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
1.253 + /// Graph::EdgeMap one for the forward edges and
1.254 + /// one for the backward edges.
1.255 class EdgeMap {
1.256 typename Graph::template EdgeMap<T> forward_map, backward_map;
1.257 public:
1.258 @@ -1113,15 +1057,15 @@
1.259 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1.260 void set(Edge e, T a) {
1.261 if (!e.backward)
1.262 - forward_map.set(e/*.out*/, a);
1.263 + forward_map.set(e, a);
1.264 else
1.265 - backward_map.set(e/*.in*/, a);
1.266 + backward_map.set(e, a);
1.267 }
1.268 T operator[](Edge e) const {
1.269 if (!e.backward)
1.270 - return forward_map[e/*.out*/];
1.271 + return forward_map[e];
1.272 else
1.273 - return backward_map[e/*.in*/];
1.274 + return backward_map[e];
1.275 }
1.276 void update() {
1.277 forward_map.update();
1.278 @@ -1137,12 +1081,9 @@
1.279 };
1.280
1.281
1.282 -
1.283 ///\brief A wrapper for composing bidirected graph from a directed one.
1.284 - /// experimental, for fezso's sake.
1.285 ///
1.286 /// A wrapper for composing bidirected graph from a directed one.
1.287 - /// experimental, for fezso's sake.
1.288 /// A bidirected graph is composed over the directed one without physical
1.289 /// storage. As the oppositely directed edges are logically different ones
1.290 /// the maps are able to attach different values for them.
1.291 @@ -1159,22 +1100,12 @@
1.292 ConstMap<typename Graph::Edge, bool> > Parent;
1.293 protected:
1.294 ConstMap<typename Graph::Edge, bool> cm;
1.295 - //const CapacityMap* capacity;
1.296 - //FlowMap* flow;
1.297
1.298 BidirGraphWrapper() : Parent(), cm(true) {
1.299 Parent::setForwardFilterMap(cm);
1.300 Parent::setBackwardFilterMap(cm);
1.301 }
1.302 -// void setCapacityMap(const CapacityMap& _capacity) {
1.303 -// capacity=&_capacity;
1.304 -// }
1.305 -// void setFlowMap(FlowMap& _flow) {
1.306 -// flow=&_flow;
1.307 -// }
1.308 -
1.309 public:
1.310 -
1.311 BidirGraphWrapper(Graph& _graph) : Parent() {
1.312 Parent::setGraph(_graph);
1.313 Parent::setForwardFilterMap(cm);
1.314 @@ -1188,29 +1119,19 @@
1.315
1.316
1.317
1.318 -
1.319 + // this is a direct implementation of the bidirected-graph wrapper.
1.320 + // in early hugo, it was implemented that way.
1.321 template<typename Graph>
1.322 class OldBidirGraphWrapper : public GraphWrapper<Graph> {
1.323 public:
1.324 typedef GraphWrapper<Graph> Parent;
1.325 protected:
1.326 - //const CapacityMap* capacity;
1.327 - //FlowMap* flow;
1.328 -
1.329 - OldBidirGraphWrapper() : GraphWrapper<Graph>()/*,
1.330 - capacity(0), flow(0)*/ { }
1.331 -// void setCapacityMap(const CapacityMap& _capacity) {
1.332 -// capacity=&_capacity;
1.333 -// }
1.334 -// void setFlowMap(FlowMap& _flow) {
1.335 -// flow=&_flow;
1.336 -// }
1.337 + OldBidirGraphWrapper() : GraphWrapper<Graph>() { }
1.338
1.339 public:
1.340
1.341 - OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
1.342 - FlowMap& _flow*/) :
1.343 - GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
1.344 + OldBidirGraphWrapper(Graph& _graph) :
1.345 + GraphWrapper<Graph>(_graph) { }
1.346
1.347 class Edge;
1.348 class OutEdgeIt;
1.349 @@ -1459,15 +1380,6 @@
1.350 bool forward(const Edge& e) const { return !e.backward; }
1.351 bool backward(const Edge& e) const { return e.backward; }
1.352
1.353 -// void augment(const Edge& e, Number a) const {
1.354 -// if (!e.backward)
1.355 -// // flow->set(e.out, flow->get(e.out)+a);
1.356 -// flow->set(e, (*flow)[e]+a);
1.357 -// else
1.358 -// // flow->set(e.in, flow->get(e.in)-a);
1.359 -// flow->set(e, (*flow)[e]-a);
1.360 -// }
1.361 -
1.362 bool enabled(const Edge& e) const {
1.363 if (!e.backward)
1.364 // return (capacity->get(e.out)-flow->get(e.out));
1.365 @@ -1662,7 +1574,7 @@
1.366
1.367 /// \brief Residual capacity map.
1.368 ///
1.369 - /// In generic residual graphs the residual capacity can be obtained as a map.
1.370 + /// In generic residual graphs the residual capacity can be obtained as a map. Not tested.
1.371 class ResCap {
1.372 protected:
1.373 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1.374 @@ -2007,14 +1919,15 @@
1.375
1.376 /// For blocking flows.
1.377
1.378 - /// This graph wrapper is used for Dinits blocking flow computations.
1.379 + /// This graph wrapper is used for on-the-fly
1.380 + /// Dinits blocking flow computations.
1.381 /// For each node, an out-edge is stored which is used when the
1.382 /// \code
1.383 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1.384 /// \endcode
1.385 /// is called.
1.386 ///
1.387 - ///\author Marton Makai
1.388 + /// \author Marton Makai
1.389 template<typename Graph, typename FirstOutEdgesMap>
1.390 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1.391 public:
1.392 @@ -2027,18 +1940,6 @@
1.393 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1.394
1.395 typedef typename GraphWrapper<Graph>::Node Node;
1.396 -// class NodeIt {
1.397 -// friend class GraphWrapper<Graph>;
1.398 -// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1.399 -// typename Graph::NodeIt n;
1.400 -// public:
1.401 -// NodeIt() { }
1.402 -// NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.403 -// NodeIt(const Invalid& i) : n(i) { }
1.404 -// NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.405 -// n(*(_G.graph)) { }
1.406 -// operator Node() const { return Node(typename Graph::Node(n)); }
1.407 -// };
1.408 typedef typename GraphWrapper<Graph>::Edge Edge;
1.409 class OutEdgeIt : public Edge {
1.410 friend class GraphWrapper<Graph>;