1.1 --- a/lemon/graph_adaptor.h Fri Feb 03 12:20:10 2006 +0000
1.2 +++ b/lemon/graph_adaptor.h Fri Feb 03 14:07:52 2006 +0000
1.3 @@ -38,25 +38,25 @@
1.4
1.5 namespace lemon {
1.6
1.7 - //x\brief Base type for the Graph Adaptors
1.8 - //x\ingroup graph_adaptors
1.9 - //x
1.10 - //xBase type for the Graph Adaptors
1.11 - //x
1.12 - //x\warning Graph adaptors are in even
1.13 - //xmore experimental state than the other
1.14 - //xparts of the lib. Use them at you own risk.
1.15 - //x
1.16 - //xThis is the base type for most of LEMON graph adaptors.
1.17 - //xThis class implements a trivial graph adaptor i.e. it only wraps the
1.18 - //xfunctions and types of the graph. The purpose of this class is to
1.19 - //xmake easier implementing graph adaptors. E.g. if an adaptor is
1.20 - //xconsidered which differs from the wrapped graph only in some of its
1.21 - //xfunctions or types, then it can be derived from GraphAdaptor,
1.22 - //xand only the
1.23 - //xdifferences should be implemented.
1.24 - //x
1.25 - //xauthor Marton Makai
1.26 + ///\brief Base type for the Graph Adaptors
1.27 + ///\ingroup graph_adaptors
1.28 + ///
1.29 + ///Base type for the Graph Adaptors
1.30 + ///
1.31 + ///\warning Graph adaptors are in even
1.32 + ///more experimental state than the other
1.33 + ///parts of the lib. Use them at you own risk.
1.34 + ///
1.35 + ///This is the base type for most of LEMON graph adaptors.
1.36 + ///This class implements a trivial graph adaptor i.e. it only wraps the
1.37 + ///functions and types of the graph. The purpose of this class is to
1.38 + ///make easier implementing graph adaptors. E.g. if an adaptor is
1.39 + ///considered which differs from the wrapped graph only in some of its
1.40 + ///functions or types, then it can be derived from GraphAdaptor,
1.41 + ///and only the
1.42 + ///differences should be implemented.
1.43 + ///
1.44 + ///author Marton Makai
1.45 template<typename _Graph>
1.46 class GraphAdaptorBase {
1.47 public:
1.48 @@ -280,44 +280,44 @@
1.49 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
1.50 }
1.51
1.52 - //x\e
1.53 + ///\e
1.54
1.55 - //x This function hides \c n in the graph, i.e. the iteration
1.56 - //x jumps over it. This is done by simply setting the value of \c n
1.57 - //x to be false in the corresponding node-map.
1.58 + /// This function hides \c n in the graph, i.e. the iteration
1.59 + /// jumps over it. This is done by simply setting the value of \c n
1.60 + /// to be false in the corresponding node-map.
1.61 void hide(const Node& n) const { node_filter_map->set(n, false); }
1.62
1.63 - //x\e
1.64 + ///\e
1.65
1.66 - //x This function hides \c e in the graph, i.e. the iteration
1.67 - //x jumps over it. This is done by simply setting the value of \c e
1.68 - //x to be false in the corresponding edge-map.
1.69 + /// This function hides \c e in the graph, i.e. the iteration
1.70 + /// jumps over it. This is done by simply setting the value of \c e
1.71 + /// to be false in the corresponding edge-map.
1.72 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
1.73
1.74 - //x\e
1.75 + ///\e
1.76
1.77 - //x The value of \c n is set to be true in the node-map which stores
1.78 - //x hide information. If \c n was hidden previuosly, then it is shown
1.79 - //x again
1.80 + /// The value of \c n is set to be true in the node-map which stores
1.81 + /// hide information. If \c n was hidden previuosly, then it is shown
1.82 + /// again
1.83 void unHide(const Node& n) const { node_filter_map->set(n, true); }
1.84
1.85 - //x\e
1.86 + ///\e
1.87
1.88 - //x The value of \c e is set to be true in the edge-map which stores
1.89 - //x hide information. If \c e was hidden previuosly, then it is shown
1.90 - //x again
1.91 + /// The value of \c e is set to be true in the edge-map which stores
1.92 + /// hide information. If \c e was hidden previuosly, then it is shown
1.93 + /// again
1.94 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
1.95
1.96 - //x Returns true if \c n is hidden.
1.97 + /// Returns true if \c n is hidden.
1.98
1.99 - //x\e
1.100 - //x
1.101 + ///\e
1.102 + ///
1.103 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
1.104
1.105 - //x Returns true if \c n is hidden.
1.106 + /// Returns true if \c n is hidden.
1.107
1.108 - //x\e
1.109 - //x
1.110 + ///\e
1.111 + ///
1.112 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
1.113
1.114 typedef False NodeNumTag;
1.115 @@ -386,111 +386,110 @@
1.116 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
1.117 }
1.118
1.119 - //x\e
1.120 + ///\e
1.121
1.122 - //x This function hides \c n in the graph, i.e. the iteration
1.123 - //x jumps over it. This is done by simply setting the value of \c n
1.124 - //x to be false in the corresponding node-map.
1.125 + /// This function hides \c n in the graph, i.e. the iteration
1.126 + /// jumps over it. This is done by simply setting the value of \c n
1.127 + /// to be false in the corresponding node-map.
1.128 void hide(const Node& n) const { node_filter_map->set(n, false); }
1.129
1.130 - //x\e
1.131 + ///\e
1.132
1.133 - //x This function hides \c e in the graph, i.e. the iteration
1.134 - //x jumps over it. This is done by simply setting the value of \c e
1.135 - //x to be false in the corresponding edge-map.
1.136 + /// This function hides \c e in the graph, i.e. the iteration
1.137 + /// jumps over it. This is done by simply setting the value of \c e
1.138 + /// to be false in the corresponding edge-map.
1.139 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
1.140
1.141 - //x\e
1.142 + ///\e
1.143
1.144 - //x The value of \c n is set to be true in the node-map which stores
1.145 - //x hide information. If \c n was hidden previuosly, then it is shown
1.146 - //x again
1.147 + /// The value of \c n is set to be true in the node-map which stores
1.148 + /// hide information. If \c n was hidden previuosly, then it is shown
1.149 + /// again
1.150 void unHide(const Node& n) const { node_filter_map->set(n, true); }
1.151
1.152 - //x\e
1.153 + ///\e
1.154
1.155 - //x The value of \c e is set to be true in the edge-map which stores
1.156 - //x hide information. If \c e was hidden previuosly, then it is shown
1.157 - //x again
1.158 + /// The value of \c e is set to be true in the edge-map which stores
1.159 + /// hide information. If \c e was hidden previuosly, then it is shown
1.160 + /// again
1.161 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
1.162
1.163 - //x Returns true if \c n is hidden.
1.164 + /// Returns true if \c n is hidden.
1.165
1.166 - //x\e
1.167 - //x
1.168 + ///\e
1.169 + ///
1.170 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
1.171
1.172 - //x Returns true if \c n is hidden.
1.173 + /// Returns true if \c n is hidden.
1.174
1.175 - //x\e
1.176 - //x
1.177 + ///\e
1.178 + ///
1.179 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
1.180
1.181 typedef False NodeNumTag;
1.182 typedef False EdgeNumTag;
1.183 };
1.184
1.185 - //x\brief A graph adaptor for hiding nodes and edges from a graph.
1.186 - //x\ingroup graph_adaptors
1.187 - //x
1.188 - //x\warning Graph adaptors are in even more experimental
1.189 - //xstate than the other
1.190 - //xparts of the lib. Use them at you own risk.
1.191 - //x
1.192 - //xSubGraphAdaptor shows the graph with filtered node-set and
1.193 - //xedge-set. If the \c checked parameter is true then it filters the edgeset
1.194 - //xto do not get invalid edges without source or target.
1.195 - //xLet \f$G=(V, A)\f$ be a directed graph
1.196 - //xand suppose that the graph instance \c g of type ListGraph implements
1.197 - //x\f$G\f$.
1.198 - //x/Let moreover \f$b_V\f$ and
1.199 - //x\f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
1.200 - //xSubGraphAdaptor<...>::NodeIt iterates
1.201 - //xon the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
1.202 - //xSubGraphAdaptor<...>::EdgeIt iterates
1.203 - //xon the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
1.204 - //xSubGraphAdaptor<...>::OutEdgeIt and
1.205 - //xSubGraphAdaptor<...>::InEdgeIt iterates
1.206 - //xonly on edges leaving and entering a specific node which have true value.
1.207 - //x
1.208 - //xIf the \c checked template parameter is false then we have to note that
1.209 - //xthe node-iterator cares only the filter on the node-set, and the
1.210 - //xedge-iterator cares only the filter on the edge-set.
1.211 - //xThis way the edge-map
1.212 - //xshould filter all edges which's source or target is filtered by the
1.213 - //xnode-filter.
1.214 - //x\code
1.215 - //xtypedef ListGraph Graph;
1.216 - //xGraph g;
1.217 - //xtypedef Graph::Node Node;
1.218 - //xtypedef Graph::Edge Edge;
1.219 - //xNode u=g.addNode(); //node of id 0
1.220 - //xNode v=g.addNode(); //node of id 1
1.221 - //xNode e=g.addEdge(u, v); //edge of id 0
1.222 - //xNode f=g.addEdge(v, u); //edge of id 1
1.223 - //xGraph::NodeMap<bool> nm(g, true);
1.224 - //xnm.set(u, false);
1.225 - //xGraph::EdgeMap<bool> em(g, true);
1.226 - //xem.set(e, false);
1.227 - //xtypedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
1.228 - //xSubGW gw(g, nm, em);
1.229 - //xfor (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
1.230 - //xstd::cout << ":-)" << std::endl;
1.231 - //xfor (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
1.232 - //x\endcode
1.233 - //xThe output of the above code is the following.
1.234 - //x\code
1.235 - //x1
1.236 - //x:-)
1.237 - //x1
1.238 - //x\endcode
1.239 - //xNote that \c n is of type \c SubGW::NodeIt, but it can be converted to
1.240 - //x\c Graph::Node that is why \c g.id(n) can be applied.
1.241 - //x
1.242 - //xFor other examples see also the documentation of NodeSubGraphAdaptor and
1.243 - //xEdgeSubGraphAdaptor.
1.244 - //x
1.245 - //x\author Marton Makai
1.246 + /// \brief A graph adaptor for hiding nodes and edges from a graph.
1.247 + /// \ingroup graph_adaptors
1.248 + ///
1.249 + /// \warning Graph adaptors are in even more experimental state than the
1.250 + /// other parts of the lib. Use them at you own risk.
1.251 + ///
1.252 + /// SubGraphAdaptor shows the graph with filtered node-set and
1.253 + /// edge-set. If the \c checked parameter is true then it filters the edgeset
1.254 + /// to do not get invalid edges without source or target.
1.255 + /// Let \f$ G=(V, A) \f$ be a directed graph
1.256 + /// and suppose that the graph instance \c g of type ListGraph
1.257 + /// implements \f$ G \f$ .
1.258 + /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
1.259 + /// on the node-set and edge-set.
1.260 + /// SubGraphAdaptor<...>::NodeIt iterates
1.261 + /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
1.262 + /// SubGraphAdaptor<...>::EdgeIt iterates
1.263 + /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$ . Similarly,
1.264 + /// SubGraphAdaptor<...>::OutEdgeIt and
1.265 + /// SubGraphAdaptor<...>::InEdgeIt iterates
1.266 + /// only on edges leaving and entering a specific node which have true value.
1.267 + ///
1.268 + /// If the \c checked template parameter is false then we have to note that
1.269 + /// the node-iterator cares only the filter on the node-set, and the
1.270 + /// edge-iterator cares only the filter on the edge-set.
1.271 + /// This way the edge-map
1.272 + /// should filter all edges which's source or target is filtered by the
1.273 + /// node-filter.
1.274 + /// \code
1.275 + /// typedef ListGraph Graph;
1.276 + /// Graph g;
1.277 + /// typedef Graph::Node Node;
1.278 + /// typedef Graph::Edge Edge;
1.279 + /// Node u=g.addNode(); //node of id 0
1.280 + /// Node v=g.addNode(); //node of id 1
1.281 + /// Node e=g.addEdge(u, v); //edge of id 0
1.282 + /// Node f=g.addEdge(v, u); //edge of id 1
1.283 + /// Graph::NodeMap<bool> nm(g, true);
1.284 + /// nm.set(u, false);
1.285 + /// Graph::EdgeMap<bool> em(g, true);
1.286 + /// em.set(e, false);
1.287 + /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
1.288 + /// SubGW gw(g, nm, em);
1.289 + /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
1.290 + /// std::cout << ":-)" << std::endl;
1.291 + /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
1.292 + /// \endcode
1.293 + /// The output of the above code is the following.
1.294 + /// \code
1.295 + /// 1
1.296 + /// :-)
1.297 + /// 1
1.298 + /// \endcode
1.299 + /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
1.300 + /// \c Graph::Node that is why \c g.id(n) can be applied.
1.301 + ///
1.302 + /// For other examples see also the documentation of NodeSubGraphAdaptor and
1.303 + /// EdgeSubGraphAdaptor.
1.304 + ///
1.305 + /// \author Marton Makai
1.306
1.307 template<typename _Graph, typename NodeFilterMap,
1.308 typename EdgeFilterMap, bool checked = true>
1.309 @@ -514,20 +513,20 @@
1.310
1.311
1.312
1.313 - //x\brief An adaptor for hiding nodes from a graph.
1.314 - //x\ingroup graph_adaptors
1.315 - //x
1.316 - //x\warning Graph adaptors are in even more experimental state
1.317 - //xthan the other
1.318 - //xparts of the lib. Use them at you own risk.
1.319 - //x
1.320 - //xAn adaptor for hiding nodes from a graph.
1.321 - //xThis adaptor specializes SubGraphAdaptor in the way that only
1.322 - //xthe node-set
1.323 - //xcan be filtered. In usual case the checked parameter is true, we get the
1.324 - //xinduced subgraph. But if the checked parameter is false then we can only
1.325 - //xfilter only isolated nodes.
1.326 - //x\author Marton Makai
1.327 + ///\brief An adaptor for hiding nodes from a graph.
1.328 + ///\ingroup graph_adaptors
1.329 + ///
1.330 + ///\warning Graph adaptors are in even more experimental state
1.331 + ///than the other
1.332 + ///parts of the lib. Use them at you own risk.
1.333 + ///
1.334 + ///An adaptor for hiding nodes from a graph.
1.335 + ///This adaptor specializes SubGraphAdaptor in the way that only
1.336 + ///the node-set
1.337 + ///can be filtered. In usual case the checked parameter is true, we get the
1.338 + ///induced subgraph. But if the checked parameter is false then we can only
1.339 + ///filter only isolated nodes.
1.340 + ///\author Marton Makai
1.341 template<typename Graph, typename NodeFilterMap, bool checked = true>
1.342 class NodeSubGraphAdaptor :
1.343 public SubGraphAdaptor<Graph, NodeFilterMap,
1.344 @@ -547,142 +546,142 @@
1.345 };
1.346
1.347
1.348 - //x\brief An adaptor for hiding edges from a graph.
1.349 - //x
1.350 - //x\warning Graph adaptors are in even more experimental state
1.351 - //xthan the other parts of the lib. Use them at you own risk.
1.352 - //x
1.353 - //xAn adaptor for hiding edges from a graph.
1.354 - //xThis adaptor specializes SubGraphAdaptor in the way that
1.355 - //xonly the edge-set
1.356 - //xcan be filtered. The usefulness of this adaptor is demonstrated in the
1.357 - //xproblem of searching a maximum number of edge-disjoint shortest paths
1.358 - //xbetween
1.359 - //xtwo nodes \c s and \c t. Shortest here means being shortest w.r.t.
1.360 - //xnon-negative edge-lengths. Note that
1.361 - //xthe comprehension of the presented solution
1.362 - //xneed's some elementary knowledge from combinatorial optimization.
1.363 - //x
1.364 - //xIf a single shortest path is to be
1.365 - //xsearched between \c s and \c t, then this can be done easily by
1.366 - //xapplying the Dijkstra algorithm. What happens, if a maximum number of
1.367 - //xedge-disjoint shortest paths is to be computed. It can be proved that an
1.368 - //xedge can be in a shortest path if and only
1.369 - //xif it is tight with respect to
1.370 - //xthe potential function computed by Dijkstra.
1.371 - //xMoreover, any path containing
1.372 - //xonly such edges is a shortest one.
1.373 - //xThus we have to compute a maximum number
1.374 - //xof edge-disjoint paths between \c s and \c t in
1.375 - //xthe graph which has edge-set
1.376 - //xall the tight edges. The computation will be demonstrated
1.377 - //xon the following
1.378 - //xgraph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
1.379 - //xThe full source code is available in \ref sub_graph_adaptor_demo.cc.
1.380 - //xIf you are interested in more demo programs, you can use
1.381 - //x\ref dim_to_dot.cc to generate .dot files from dimacs files.
1.382 - //xThe .dot file of the following figure was generated by
1.383 - //xthe demo program \ref dim_to_dot.cc.
1.384 - //x
1.385 - //x\dot
1.386 - //xdigraph lemon_dot_example {
1.387 - //xnode [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.388 - //xn0 [ label="0 (s)" ];
1.389 - //xn1 [ label="1" ];
1.390 - //xn2 [ label="2" ];
1.391 - //xn3 [ label="3" ];
1.392 - //xn4 [ label="4" ];
1.393 - //xn5 [ label="5" ];
1.394 - //xn6 [ label="6 (t)" ];
1.395 - //xedge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.396 - //xn5 -> n6 [ label="9, length:4" ];
1.397 - //xn4 -> n6 [ label="8, length:2" ];
1.398 - //xn3 -> n5 [ label="7, length:1" ];
1.399 - //xn2 -> n5 [ label="6, length:3" ];
1.400 - //xn2 -> n6 [ label="5, length:5" ];
1.401 - //xn2 -> n4 [ label="4, length:2" ];
1.402 - //xn1 -> n4 [ label="3, length:3" ];
1.403 - //xn0 -> n3 [ label="2, length:1" ];
1.404 - //xn0 -> n2 [ label="1, length:2" ];
1.405 - //xn0 -> n1 [ label="0, length:3" ];
1.406 - //x}
1.407 - //x\enddot
1.408 - //x
1.409 - //x\code
1.410 - //xGraph g;
1.411 - //xNode s, t;
1.412 - //xLengthMap length(g);
1.413 - //x
1.414 - //xreadDimacs(std::cin, g, length, s, t);
1.415 - //x
1.416 - //xcout << "edges with lengths (of form id, source--length->target): " << endl;
1.417 - //xfor(EdgeIt e(g); e!=INVALID; ++e)
1.418 - //x cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
1.419 - //x << length[e] << "->" << g.id(g.target(e)) << endl;
1.420 - //x
1.421 - //xcout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
1.422 - //x\endcode
1.423 - //xNext, the potential function is computed with Dijkstra.
1.424 - //x\code
1.425 - //xtypedef Dijkstra<Graph, LengthMap> Dijkstra;
1.426 - //xDijkstra dijkstra(g, length);
1.427 - //xdijkstra.run(s);
1.428 - //x\endcode
1.429 - //xNext, we consrtruct a map which filters the edge-set to the tight edges.
1.430 - //x\code
1.431 - //xtypedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
1.432 - //x TightEdgeFilter;
1.433 - //xTightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
1.434 - //x
1.435 - //xtypedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
1.436 - //xSubGW gw(g, tight_edge_filter);
1.437 - //x\endcode
1.438 - //xThen, the maximum nimber of edge-disjoint \c s-\c t paths are computed
1.439 - //xwith a max flow algorithm Preflow.
1.440 - //x\code
1.441 - //xConstMap<Edge, int> const_1_map(1);
1.442 - //xGraph::EdgeMap<int> flow(g, 0);
1.443 - //x
1.444 - //xPreflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
1.445 - //x preflow(gw, s, t, const_1_map, flow);
1.446 - //xpreflow.run();
1.447 - //x\endcode
1.448 - //xLast, the output is:
1.449 - //x\code
1.450 - //xcout << "maximum number of edge-disjoint shortest path: "
1.451 - //x << preflow.flowValue() << endl;
1.452 - //xcout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
1.453 - //x << endl;
1.454 - //xfor(EdgeIt e(g); e!=INVALID; ++e)
1.455 - //x if (flow[e])
1.456 - //x cout << " " << g.id(g.source(e)) << "--"
1.457 - //x << length[e] << "->" << g.id(g.target(e)) << endl;
1.458 - //x\endcode
1.459 - //xThe program has the following (expected :-)) output:
1.460 - //x\code
1.461 - //xedges with lengths (of form id, source--length->target):
1.462 - //x 9, 5--4->6
1.463 - //x 8, 4--2->6
1.464 - //x 7, 3--1->5
1.465 - //x 6, 2--3->5
1.466 - //x 5, 2--5->6
1.467 - //x 4, 2--2->4
1.468 - //x 3, 1--3->4
1.469 - //x 2, 0--1->3
1.470 - //x 1, 0--2->2
1.471 - //x 0, 0--3->1
1.472 - //xs: 0 t: 6
1.473 - //xmaximum number of edge-disjoint shortest path: 2
1.474 - //xedges of the maximum number of edge-disjoint shortest s-t paths:
1.475 - //x 9, 5--4->6
1.476 - //x 8, 4--2->6
1.477 - //x 7, 3--1->5
1.478 - //x 4, 2--2->4
1.479 - //x 2, 0--1->3
1.480 - //x 1, 0--2->2
1.481 - //x\endcode
1.482 - //x
1.483 - //x\author Marton Makai
1.484 + ///\brief An adaptor for hiding edges from a graph.
1.485 + ///
1.486 + ///\warning Graph adaptors are in even more experimental state
1.487 + ///than the other parts of the lib. Use them at you own risk.
1.488 + ///
1.489 + ///An adaptor for hiding edges from a graph.
1.490 + ///This adaptor specializes SubGraphAdaptor in the way that
1.491 + ///only the edge-set
1.492 + ///can be filtered. The usefulness of this adaptor is demonstrated in the
1.493 + ///problem of searching a maximum number of edge-disjoint shortest paths
1.494 + ///between
1.495 + ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
1.496 + ///non-negative edge-lengths. Note that
1.497 + ///the comprehension of the presented solution
1.498 + ///need's some elementary knowledge from combinatorial optimization.
1.499 + ///
1.500 + ///If a single shortest path is to be
1.501 + ///searched between \c s and \c t, then this can be done easily by
1.502 + ///applying the Dijkstra algorithm. What happens, if a maximum number of
1.503 + ///edge-disjoint shortest paths is to be computed. It can be proved that an
1.504 + ///edge can be in a shortest path if and only
1.505 + ///if it is tight with respect to
1.506 + ///the potential function computed by Dijkstra.
1.507 + ///Moreover, any path containing
1.508 + ///only such edges is a shortest one.
1.509 + ///Thus we have to compute a maximum number
1.510 + ///of edge-disjoint paths between \c s and \c t in
1.511 + ///the graph which has edge-set
1.512 + ///all the tight edges. The computation will be demonstrated
1.513 + ///on the following
1.514 + ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
1.515 + ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
1.516 + ///If you are interested in more demo programs, you can use
1.517 + ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
1.518 + ///The .dot file of the following figure was generated by
1.519 + ///the demo program \ref dim_to_dot.cc.
1.520 + ///
1.521 + ///\dot
1.522 + ///digraph lemon_dot_example {
1.523 + ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.524 + ///n0 [ label="0 (s)" ];
1.525 + ///n1 [ label="1" ];
1.526 + ///n2 [ label="2" ];
1.527 + ///n3 [ label="3" ];
1.528 + ///n4 [ label="4" ];
1.529 + ///n5 [ label="5" ];
1.530 + ///n6 [ label="6 (t)" ];
1.531 + ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.532 + ///n5 -> n6 [ label="9, length:4" ];
1.533 + ///n4 -> n6 [ label="8, length:2" ];
1.534 + ///n3 -> n5 [ label="7, length:1" ];
1.535 + ///n2 -> n5 [ label="6, length:3" ];
1.536 + ///n2 -> n6 [ label="5, length:5" ];
1.537 + ///n2 -> n4 [ label="4, length:2" ];
1.538 + ///n1 -> n4 [ label="3, length:3" ];
1.539 + ///n0 -> n3 [ label="2, length:1" ];
1.540 + ///n0 -> n2 [ label="1, length:2" ];
1.541 + ///n0 -> n1 [ label="0, length:3" ];
1.542 + ///}
1.543 + ///\enddot
1.544 + ///
1.545 + ///\code
1.546 + ///Graph g;
1.547 + ///Node s, t;
1.548 + ///LengthMap length(g);
1.549 + ///
1.550 + ///readDimacs(std::cin, g, length, s, t);
1.551 + ///
1.552 + ///cout << "edges with lengths (of form id, source--length->target): " << endl;
1.553 + ///for(EdgeIt e(g); e!=INVALID; ++e)
1.554 + /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
1.555 + /// << length[e] << "->" << g.id(g.target(e)) << endl;
1.556 + ///
1.557 + ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
1.558 + ///\endcode
1.559 + ///Next, the potential function is computed with Dijkstra.
1.560 + ///\code
1.561 + ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
1.562 + ///Dijkstra dijkstra(g, length);
1.563 + ///dijkstra.run(s);
1.564 + ///\endcode
1.565 + ///Next, we consrtruct a map which filters the edge-set to the tight edges.
1.566 + ///\code
1.567 + ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
1.568 + /// TightEdgeFilter;
1.569 + ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
1.570 + ///
1.571 + ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
1.572 + ///SubGW gw(g, tight_edge_filter);
1.573 + ///\endcode
1.574 + ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
1.575 + ///with a max flow algorithm Preflow.
1.576 + ///\code
1.577 + ///ConstMap<Edge, int> const_1_map(1);
1.578 + ///Graph::EdgeMap<int> flow(g, 0);
1.579 + ///
1.580 + ///Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
1.581 + /// preflow(gw, s, t, const_1_map, flow);
1.582 + ///preflow.run();
1.583 + ///\endcode
1.584 + ///Last, the output is:
1.585 + ///\code
1.586 + ///cout << "maximum number of edge-disjoint shortest path: "
1.587 + /// << preflow.flowValue() << endl;
1.588 + ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
1.589 + /// << endl;
1.590 + ///for(EdgeIt e(g); e!=INVALID; ++e)
1.591 + /// if (flow[e])
1.592 + /// cout << " " << g.id(g.source(e)) << "--"
1.593 + /// << length[e] << "->" << g.id(g.target(e)) << endl;
1.594 + ///\endcode
1.595 + ///The program has the following (expected :-)) output:
1.596 + ///\code
1.597 + ///edges with lengths (of form id, source--length->target):
1.598 + /// 9, 5--4->6
1.599 + /// 8, 4--2->6
1.600 + /// 7, 3--1->5
1.601 + /// 6, 2--3->5
1.602 + /// 5, 2--5->6
1.603 + /// 4, 2--2->4
1.604 + /// 3, 1--3->4
1.605 + /// 2, 0--1->3
1.606 + /// 1, 0--2->2
1.607 + /// 0, 0--3->1
1.608 + ///s: 0 t: 6
1.609 + ///maximum number of edge-disjoint shortest path: 2
1.610 + ///edges of the maximum number of edge-disjoint shortest s-t paths:
1.611 + /// 9, 5--4->6
1.612 + /// 8, 4--2->6
1.613 + /// 7, 3--1->5
1.614 + /// 4, 2--2->4
1.615 + /// 2, 0--1->3
1.616 + /// 1, 0--2->2
1.617 + ///\endcode
1.618 + ///
1.619 + ///\author Marton Makai
1.620 template<typename Graph, typename EdgeFilterMap>
1.621 class EdgeSubGraphAdaptor :
1.622 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
1.623 @@ -769,13 +768,13 @@
1.624
1.625 };
1.626
1.627 - //x\brief An undirected graph is made from a directed graph by an adaptor
1.628 - //x\ingroup graph_adaptors
1.629 - //x
1.630 - //x Undocumented, untested!!!
1.631 - //x If somebody knows nice demo application, let's polulate it.
1.632 - //x
1.633 - //x \author Marton Makai
1.634 + ///\brief An undirected graph is made from a directed graph by an adaptor
1.635 + ///\ingroup graph_adaptors
1.636 + ///
1.637 + /// Undocumented, untested!!!
1.638 + /// If somebody knows nice demo application, let's polulate it.
1.639 + ///
1.640 + /// \author Marton Makai
1.641 template<typename _Graph>
1.642 class UGraphAdaptor :
1.643 public IterableUGraphExtender<
1.644 @@ -961,21 +960,21 @@
1.645 Node target(Edge e) const {
1.646 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
1.647
1.648 - //x Gives back the opposite edge.
1.649 + /// Gives back the opposite edge.
1.650
1.651 - //x\e
1.652 - //x
1.653 + ///\e
1.654 + ///
1.655 Edge opposite(const Edge& e) const {
1.656 Edge f=e;
1.657 f.backward=!f.backward;
1.658 return f;
1.659 }
1.660
1.661 - //x\e
1.662 + ///\e
1.663
1.664 - //x \warning This is a linear time operation and works only if
1.665 - //x \c Graph::EdgeIt is defined.
1.666 - //x \todo hmm
1.667 + /// \warning This is a linear time operation and works only if
1.668 + /// \c Graph::EdgeIt is defined.
1.669 + /// \todo hmm
1.670 int edgeNum() const {
1.671 int i=0;
1.672 Edge e;
1.673 @@ -986,11 +985,11 @@
1.674 bool forward(const Edge& e) const { return !e.backward; }
1.675 bool backward(const Edge& e) const { return e.backward; }
1.676
1.677 - //x\e
1.678 + ///\e
1.679
1.680 - //x \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
1.681 - //x _Graph::EdgeMap one for the forward edges and
1.682 - //x one for the backward edges.
1.683 + /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
1.684 + /// _Graph::EdgeMap one for the forward edges and
1.685 + /// one for the backward edges.
1.686 template <typename T>
1.687 class EdgeMap {
1.688 template <typename TT> friend class EdgeMap;
1.689 @@ -1039,46 +1038,46 @@
1.690 };
1.691
1.692
1.693 - //x\brief An adaptor for composing a subgraph of a
1.694 - //x bidirected graph made from a directed one.
1.695 - //x\ingroup graph_adaptors
1.696 - //x
1.697 - //x An adaptor for composing a subgraph of a
1.698 - //x bidirected graph made from a directed one.
1.699 - //x
1.700 - //x\warning Graph adaptors are in even more experimental state
1.701 - //xthan the other
1.702 - //xparts of the lib. Use them at you own risk.
1.703 - //x
1.704 - //x Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
1.705 - //x \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1.706 - //x reversing its orientation. We are given moreover two bool valued
1.707 - //x maps on the edge-set,
1.708 - //x \f$forward\_filter\f$, and \f$backward\_filter\f$.
1.709 - //x SubBidirGraphAdaptor implements the graph structure with node-set
1.710 - //x \f$V\f$ and edge-set
1.711 - //x \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
1.712 - //x The purpose of writing + instead of union is because parallel
1.713 - //x edges can arise. (Similarly, antiparallel edges also can arise).
1.714 - //x In other words, a subgraph of the bidirected graph obtained, which
1.715 - //x is given by orienting the edges of the original graph in both directions.
1.716 - //x As the oppositely directed edges are logically different,
1.717 - //x the maps are able to attach different values for them.
1.718 - //x
1.719 - //x An example for such a construction is \c RevGraphAdaptor where the
1.720 - //x forward_filter is everywhere false and the backward_filter is
1.721 - //x everywhere true. We note that for sake of efficiency,
1.722 - //x \c RevGraphAdaptor is implemented in a different way.
1.723 - //x But BidirGraphAdaptor is obtained from
1.724 - //x SubBidirGraphAdaptor by considering everywhere true
1.725 - //x valued maps both for forward_filter and backward_filter.
1.726 - //x
1.727 - //x The most important application of SubBidirGraphAdaptor
1.728 - //x is ResGraphAdaptor, which stands for the residual graph in directed
1.729 - //x flow and circulation problems.
1.730 - //x As adaptors usually, the SubBidirGraphAdaptor implements the
1.731 - //x above mentioned graph structure without its physical storage,
1.732 - //x that is the whole stuff is stored in constant memory.
1.733 + ///\brief An adaptor for composing a subgraph of a
1.734 + /// bidirected graph made from a directed one.
1.735 + ///\ingroup graph_adaptors
1.736 + ///
1.737 + /// An adaptor for composing a subgraph of a
1.738 + /// bidirected graph made from a directed one.
1.739 + ///
1.740 + ///\warning Graph adaptors are in even more experimental state
1.741 + ///than the other
1.742 + ///parts of the lib. Use them at you own risk.
1.743 + ///
1.744 + /// Let \f$ G=(V, A) \f$ be a directed graph and for each directed edge
1.745 + /// \f$ e\in A \f$ , let \f$ \bar e \f$ denote the edge obtained by
1.746 + /// reversing its orientation. We are given moreover two bool valued
1.747 + /// maps on the edge-set,
1.748 + /// \f$ forward\_filter \f$ , and \f$ backward\_filter \f$ .
1.749 + /// SubBidirGraphAdaptor implements the graph structure with node-set
1.750 + /// \f$ V \f$ and edge-set
1.751 + /// \f$ \{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\} \f$ .
1.752 + /// The purpose of writing + instead of union is because parallel
1.753 + /// edges can arise. (Similarly, antiparallel edges also can arise).
1.754 + /// In other words, a subgraph of the bidirected graph obtained, which
1.755 + /// is given by orienting the edges of the original graph in both directions.
1.756 + /// As the oppositely directed edges are logically different,
1.757 + /// the maps are able to attach different values for them.
1.758 + ///
1.759 + /// An example for such a construction is \c RevGraphAdaptor where the
1.760 + /// forward_filter is everywhere false and the backward_filter is
1.761 + /// everywhere true. We note that for sake of efficiency,
1.762 + /// \c RevGraphAdaptor is implemented in a different way.
1.763 + /// But BidirGraphAdaptor is obtained from
1.764 + /// SubBidirGraphAdaptor by considering everywhere true
1.765 + /// valued maps both for forward_filter and backward_filter.
1.766 + ///
1.767 + /// The most important application of SubBidirGraphAdaptor
1.768 + /// is ResGraphAdaptor, which stands for the residual graph in directed
1.769 + /// flow and circulation problems.
1.770 + /// As adaptors usually, the SubBidirGraphAdaptor implements the
1.771 + /// above mentioned graph structure without its physical storage,
1.772 + /// that is the whole stuff is stored in constant memory.
1.773 template<typename _Graph,
1.774 typename ForwardFilterMap, typename BackwardFilterMap>
1.775 class SubBidirGraphAdaptor :
1.776 @@ -1102,17 +1101,17 @@
1.777
1.778
1.779
1.780 - //x\brief An adaptor for composing bidirected graph from a directed one.
1.781 - //x\ingroup graph_adaptors
1.782 - //x
1.783 - //x\warning Graph adaptors are in even more experimental state
1.784 - //xthan the other
1.785 - //xparts of the lib. Use them at you own risk.
1.786 - //x
1.787 - //x An adaptor for composing bidirected graph from a directed one.
1.788 - //x A bidirected graph is composed over the directed one without physical
1.789 - //x storage. As the oppositely directed edges are logically different ones
1.790 - //x the maps are able to attach different values for them.
1.791 + ///\brief An adaptor for composing bidirected graph from a directed one.
1.792 + ///\ingroup graph_adaptors
1.793 + ///
1.794 + ///\warning Graph adaptors are in even more experimental state
1.795 + ///than the other
1.796 + ///parts of the lib. Use them at you own risk.
1.797 + ///
1.798 + /// An adaptor for composing bidirected graph from a directed one.
1.799 + /// A bidirected graph is composed over the directed one without physical
1.800 + /// storage. As the oppositely directed edges are logically different ones
1.801 + /// the maps are able to attach different values for them.
1.802 template<typename Graph>
1.803 class BidirGraphAdaptor :
1.804 public SubBidirGraphAdaptor<
1.805 @@ -1180,41 +1179,41 @@
1.806 };
1.807
1.808
1.809 - //x\brief An adaptor for composing the residual
1.810 - //xgraph for directed flow and circulation problems.
1.811 - //x\ingroup graph_adaptors
1.812 - //x
1.813 - //xAn adaptor for composing the residual graph for
1.814 - //xdirected flow and circulation problems.
1.815 - //xLet \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1.816 - //xnumber type. Let moreover
1.817 - //x\f$f,c:A\to F\f$, be functions on the edge-set.
1.818 - //xIn the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1.819 - //xand \f$c\f$ for a capacity function.
1.820 - //xSuppose that a graph instange \c g of type
1.821 - //x\c ListGraph implements \f$G\f$ .
1.822 - //x\code
1.823 - //x ListGraph g;
1.824 - //x\endcode
1.825 - //xThen RevGraphAdaptor implements the graph structure with node-set
1.826 - //x\f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1.827 - //x\f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1.828 - //x\f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1.829 - //xi.e. the so called residual graph.
1.830 - //xWhen we take the union \f$A_{forward}\cup A_{backward}\f$,
1.831 - //xmultilicities are counted, i.e. if an edge is in both
1.832 - //x\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1.833 - //xappears twice.
1.834 - //xThe following code shows how
1.835 - //xsuch an instance can be constructed.
1.836 - //x\code
1.837 - //xtypedef ListGraph Graph;
1.838 - //xGraph::EdgeMap<int> f(g);
1.839 - //xGraph::EdgeMap<int> c(g);
1.840 - //xResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1.841 - //x\endcode
1.842 - //x\author Marton Makai
1.843 - //x
1.844 + ///\brief An adaptor for composing the residual
1.845 + ///graph for directed flow and circulation problems.
1.846 + ///\ingroup graph_adaptors
1.847 + ///
1.848 + ///An adaptor for composing the residual graph for
1.849 + ///directed flow and circulation problems.
1.850 + ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a
1.851 + ///number type. Let moreover
1.852 + /// \f$ f,c:A\to F \f$ , be functions on the edge-set.
1.853 + ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a flow
1.854 + ///and \f$ c \f$ for a capacity function.
1.855 + ///Suppose that a graph instange \c g of type
1.856 + ///\c ListGraph implements \f$ G \f$ .
1.857 + ///\code
1.858 + /// ListGraph g;
1.859 + ///\endcode
1.860 + ///Then RevGraphAdaptor implements the graph structure with node-set
1.861 + /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$ , where
1.862 + /// \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1.863 + /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$ ,
1.864 + ///i.e. the so called residual graph.
1.865 + ///When we take the union \f$ A_{forward}\cup A_{backward} \f$ ,
1.866 + ///multilicities are counted, i.e. if an edge is in both
1.867 + /// \f$ A_{forward} \f$ and \f$ A_{backward} \f$ , then in the adaptor it
1.868 + ///appears twice.
1.869 + ///The following code shows how
1.870 + ///such an instance can be constructed.
1.871 + ///\code
1.872 + ///typedef ListGraph Graph;
1.873 + ///Graph::EdgeMap<int> f(g);
1.874 + ///Graph::EdgeMap<int> c(g);
1.875 + ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1.876 + ///\endcode
1.877 + ///\author Marton Makai
1.878 + ///
1.879 template<typename Graph, typename Number,
1.880 typename CapacityMap, typename FlowMap>
1.881 class ResGraphAdaptor :
1.882 @@ -1264,10 +1263,10 @@
1.883 flow->set(e, (*flow)[e]-a);
1.884 }
1.885
1.886 - //x \brief Residual capacity map.
1.887 - //x
1.888 - //x In generic residual graphs the residual capacity can be obtained
1.889 - //x as a map.
1.890 + /// \brief Residual capacity map.
1.891 + ///
1.892 + /// In generic residual graphs the residual capacity can be obtained
1.893 + /// as a map.
1.894 class ResCap {
1.895 protected:
1.896 const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1.897 @@ -1321,23 +1320,23 @@
1.898 };
1.899
1.900
1.901 - //x\brief For blocking flows.
1.902 - //x\ingroup graph_adaptors
1.903 - //x
1.904 - //x\warning Graph adaptors are in even more
1.905 - //xexperimental state than the other
1.906 - //xparts of the lib. Use them at you own risk.
1.907 - //x
1.908 - //xThis graph adaptor is used for on-the-fly
1.909 - //xDinits blocking flow computations.
1.910 - //xFor each node, an out-edge is stored which is used when the
1.911 - //x\code
1.912 - //xOutEdgeIt& first(OutEdgeIt&, const Node&)
1.913 - //x\endcode
1.914 - //xis called.
1.915 - //x
1.916 - //x\author Marton Makai
1.917 - //x
1.918 + ///\brief For blocking flows.
1.919 + ///\ingroup graph_adaptors
1.920 + ///
1.921 + ///\warning Graph adaptors are in even more
1.922 + ///experimental state than the other
1.923 + ///parts of the lib. Use them at you own risk.
1.924 + ///
1.925 + ///This graph adaptor is used for on-the-fly
1.926 + ///Dinits blocking flow computations.
1.927 + ///For each node, an out-edge is stored which is used when the
1.928 + ///\code
1.929 + ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1.930 + ///\endcode
1.931 + ///is called.
1.932 + ///
1.933 + ///\author Marton Makai
1.934 + ///
1.935 template <typename _Graph, typename FirstOutEdgesMap>
1.936 class ErasingFirstGraphAdaptor :
1.937 public IterableGraphExtender<
1.938 @@ -1394,7 +1393,7 @@
1.939 }
1.940 };
1.941
1.942 - //x \todo May we want VARIANT/union type
1.943 + /// \todo May we want VARIANT/union type
1.944 class Edge : public Parent::Edge {
1.945 friend class SplitGraphAdaptorBase;
1.946 template <typename T> friend class EdgeMap;