Fight with Doxygen.
Victory hasn't been reached yet, but it's on the horizon.
1.1 --- a/doc/graph-adaptors.dox Fri Feb 03 09:03:05 2006 +0000
1.2 +++ b/doc/graph-adaptors.dox Fri Feb 03 09:18:17 2006 +0000
1.3 @@ -1,7 +1,7 @@
1.4 /**
1.5 @defgroup graph_adaptors Adaptor Classes for Graphs
1.6 + @ingroup graphs
1.7 \brief This group contains several adaptor classes for graphs
1.8 - @ingroup graphs
1.9
1.10 The main parts of LEMON are the different graph structures,
1.11 generic graph algorithms, graph concepts which couple these, and
2.1 --- a/lemon/graph_adaptor.h Fri Feb 03 09:03:05 2006 +0000
2.2 +++ b/lemon/graph_adaptor.h Fri Feb 03 09:18:17 2006 +0000
2.3 @@ -38,29 +38,25 @@
2.4
2.5 namespace lemon {
2.6
2.7 - // Graph adaptors
2.8 -
2.9 - /*!
2.10 - \addtogroup graph_adaptors
2.11 - @{
2.12 - */
2.13 -
2.14 - /*!
2.15 - Base type for the Graph Adaptors
2.16 -
2.17 - \warning Graph adaptors are in even more experimental state than the other
2.18 - parts of the lib. Use them at you own risk.
2.19 -
2.20 - This is the base type for most of LEMON graph adaptors.
2.21 - This class implements a trivial graph adaptor i.e. it only wraps the
2.22 - functions and types of the graph. The purpose of this class is to
2.23 - make easier implementing graph adaptors. E.g. if an adaptor is
2.24 - considered which differs from the wrapped graph only in some of its
2.25 - functions or types, then it can be derived from GraphAdaptor, and only the
2.26 - differences should be implemented.
2.27 -
2.28 - \author Marton Makai
2.29 - */
2.30 + //x\brief Base type for the Graph Adaptors
2.31 + //x\ingroup graph_adaptors
2.32 + //x
2.33 + //xBase type for the Graph Adaptors
2.34 + //x
2.35 + //x\warning Graph adaptors are in even
2.36 + //xmore experimental state than the other
2.37 + //xparts of the lib. Use them at you own risk.
2.38 + //x
2.39 + //xThis is the base type for most of LEMON graph adaptors.
2.40 + //xThis class implements a trivial graph adaptor i.e. it only wraps the
2.41 + //xfunctions and types of the graph. The purpose of this class is to
2.42 + //xmake easier implementing graph adaptors. E.g. if an adaptor is
2.43 + //xconsidered which differs from the wrapped graph only in some of its
2.44 + //xfunctions or types, then it can be derived from GraphAdaptor,
2.45 + //xand only the
2.46 + //xdifferences should be implemented.
2.47 + //x
2.48 + //xauthor Marton Makai
2.49 template<typename _Graph>
2.50 class GraphAdaptorBase {
2.51 public:
2.52 @@ -180,29 +176,23 @@
2.53 };
2.54
2.55
2.56 - /// A graph adaptor which reverses the orientation of the edges.
2.57 -
2.58 - ///\warning Graph adaptors are in even more experimental state than the other
2.59 + ///\brief A graph adaptor which reverses the orientation of the edges.
2.60 + ///\ingroup graph_adaptors
2.61 + ///
2.62 + ///\warning Graph adaptors are in even more experimental
2.63 + ///state than the other
2.64 ///parts of the lib. Use them at you own risk.
2.65 ///
2.66 - /// Let \f$G=(V, A)\f$ be a directed graph and
2.67 - /// suppose that a graph instange \c g of type
2.68 - /// \c ListGraph implements \f$G\f$.
2.69 + /// If \c g is defined as
2.70 ///\code
2.71 /// ListGraph g;
2.72 ///\endcode
2.73 - /// For each directed edge
2.74 - /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
2.75 - /// reversing its orientation.
2.76 - /// Then RevGraphAdaptor implements the graph structure with node-set
2.77 - /// \f$V\f$ and edge-set
2.78 - /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
2.79 - /// reversing the orientation of its edges. The following code shows how
2.80 - /// such an instance can be constructed.
2.81 + /// then
2.82 ///\code
2.83 /// RevGraphAdaptor<ListGraph> gw(g);
2.84 ///\endcode
2.85 - ///\author Marton Makai
2.86 + ///implements the graph obtained from \c g by
2.87 + /// reversing the orientation of its edges.
2.88
2.89 template<typename _Graph>
2.90 class RevGraphAdaptor :
2.91 @@ -290,30 +280,44 @@
2.92 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
2.93 }
2.94
2.95 - /// This function hides \c n in the graph, i.e. the iteration
2.96 - /// jumps over it. This is done by simply setting the value of \c n
2.97 - /// to be false in the corresponding node-map.
2.98 + //x\e
2.99 +
2.100 + //x This function hides \c n in the graph, i.e. the iteration
2.101 + //x jumps over it. This is done by simply setting the value of \c n
2.102 + //x to be false in the corresponding node-map.
2.103 void hide(const Node& n) const { node_filter_map->set(n, false); }
2.104
2.105 - /// This function hides \c e in the graph, i.e. the iteration
2.106 - /// jumps over it. This is done by simply setting the value of \c e
2.107 - /// to be false in the corresponding edge-map.
2.108 + //x\e
2.109 +
2.110 + //x This function hides \c e in the graph, i.e. the iteration
2.111 + //x jumps over it. This is done by simply setting the value of \c e
2.112 + //x to be false in the corresponding edge-map.
2.113 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
2.114
2.115 - /// The value of \c n is set to be true in the node-map which stores
2.116 - /// hide information. If \c n was hidden previuosly, then it is shown
2.117 - /// again
2.118 + //x\e
2.119 +
2.120 + //x The value of \c n is set to be true in the node-map which stores
2.121 + //x hide information. If \c n was hidden previuosly, then it is shown
2.122 + //x again
2.123 void unHide(const Node& n) const { node_filter_map->set(n, true); }
2.124
2.125 - /// The value of \c e is set to be true in the edge-map which stores
2.126 - /// hide information. If \c e was hidden previuosly, then it is shown
2.127 - /// again
2.128 + //x\e
2.129 +
2.130 + //x The value of \c e is set to be true in the edge-map which stores
2.131 + //x hide information. If \c e was hidden previuosly, then it is shown
2.132 + //x again
2.133 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
2.134
2.135 - /// Returns true if \c n is hidden.
2.136 + //x Returns true if \c n is hidden.
2.137 +
2.138 + //x\e
2.139 + //x
2.140 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
2.141
2.142 - /// Returns true if \c n is hidden.
2.143 + //x Returns true if \c n is hidden.
2.144 +
2.145 + //x\e
2.146 + //x
2.147 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
2.148
2.149 typedef False NodeNumTag;
2.150 @@ -382,94 +386,112 @@
2.151 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
2.152 }
2.153
2.154 - /// This function hides \c n in the graph, i.e. the iteration
2.155 - /// jumps over it. This is done by simply setting the value of \c n
2.156 - /// to be false in the corresponding node-map.
2.157 + //x\e
2.158 +
2.159 + //x This function hides \c n in the graph, i.e. the iteration
2.160 + //x jumps over it. This is done by simply setting the value of \c n
2.161 + //x to be false in the corresponding node-map.
2.162 void hide(const Node& n) const { node_filter_map->set(n, false); }
2.163
2.164 - /// This function hides \c e in the graph, i.e. the iteration
2.165 - /// jumps over it. This is done by simply setting the value of \c e
2.166 - /// to be false in the corresponding edge-map.
2.167 + //x\e
2.168 +
2.169 + //x This function hides \c e in the graph, i.e. the iteration
2.170 + //x jumps over it. This is done by simply setting the value of \c e
2.171 + //x to be false in the corresponding edge-map.
2.172 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
2.173
2.174 - /// The value of \c n is set to be true in the node-map which stores
2.175 - /// hide information. If \c n was hidden previuosly, then it is shown
2.176 - /// again
2.177 + //x\e
2.178 +
2.179 + //x The value of \c n is set to be true in the node-map which stores
2.180 + //x hide information. If \c n was hidden previuosly, then it is shown
2.181 + //x again
2.182 void unHide(const Node& n) const { node_filter_map->set(n, true); }
2.183
2.184 - /// The value of \c e is set to be true in the edge-map which stores
2.185 - /// hide information. If \c e was hidden previuosly, then it is shown
2.186 - /// again
2.187 + //x\e
2.188 +
2.189 + //x The value of \c e is set to be true in the edge-map which stores
2.190 + //x hide information. If \c e was hidden previuosly, then it is shown
2.191 + //x again
2.192 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
2.193
2.194 - /// Returns true if \c n is hidden.
2.195 + //x Returns true if \c n is hidden.
2.196 +
2.197 + //x\e
2.198 + //x
2.199 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
2.200
2.201 - /// Returns true if \c n is hidden.
2.202 + //x Returns true if \c n is hidden.
2.203 +
2.204 + //x\e
2.205 + //x
2.206 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
2.207
2.208 typedef False NodeNumTag;
2.209 typedef False EdgeNumTag;
2.210 };
2.211
2.212 - /*! \brief A graph adaptor for hiding nodes and edges from a graph.
2.213 -
2.214 - \warning Graph adaptors are in even more experimental state than the other
2.215 - parts of the lib. Use them at you own risk.
2.216 -
2.217 - SubGraphAdaptor shows the graph with filtered node-set and
2.218 - edge-set. If the \c checked parameter is true then it filters the edgeset
2.219 - to do not get invalid edges without source or target.
2.220 - Let \f$G=(V, A)\f$ be a directed graph
2.221 - and suppose that the graph instance \c g of type ListGraph implements
2.222 - \f$G\f$.
2.223 - Let moreover \f$b_V\f$ and
2.224 - \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
2.225 - SubGraphAdaptor<...>::NodeIt iterates
2.226 - on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
2.227 - SubGraphAdaptor<...>::EdgeIt iterates
2.228 - on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
2.229 - SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
2.230 - only on edges leaving and entering a specific node which have true value.
2.231 + //x\brief A graph adaptor for hiding nodes and edges from a graph.
2.232 + //x\ingroup graph_adaptors
2.233 + //x
2.234 + //x\warning Graph adaptors are in even more experimental
2.235 + //xstate than the other
2.236 + //xparts of the lib. Use them at you own risk.
2.237 + //x
2.238 + //xSubGraphAdaptor shows the graph with filtered node-set and
2.239 + //xedge-set. If the \c checked parameter is true then it filters the edgeset
2.240 + //xto do not get invalid edges without source or target.
2.241 + //xLet \f$G=(V, A)\f$ be a directed graph
2.242 + //xand suppose that the graph instance \c g of type ListGraph implements
2.243 + //x\f$G\f$.
2.244 + //x/Let moreover \f$b_V\f$ and
2.245 + //x\f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
2.246 + //xSubGraphAdaptor<...>::NodeIt iterates
2.247 + //xon the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
2.248 + //xSubGraphAdaptor<...>::EdgeIt iterates
2.249 + //xon the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
2.250 + //xSubGraphAdaptor<...>::OutEdgeIt and
2.251 + //xSubGraphAdaptor<...>::InEdgeIt iterates
2.252 + //xonly on edges leaving and entering a specific node which have true value.
2.253 + //x
2.254 + //xIf the \c checked template parameter is false then we have to note that
2.255 + //xthe node-iterator cares only the filter on the node-set, and the
2.256 + //xedge-iterator cares only the filter on the edge-set.
2.257 + //xThis way the edge-map
2.258 + //xshould filter all edges which's source or target is filtered by the
2.259 + //xnode-filter.
2.260 + //x\code
2.261 + //xtypedef ListGraph Graph;
2.262 + //xGraph g;
2.263 + //xtypedef Graph::Node Node;
2.264 + //xtypedef Graph::Edge Edge;
2.265 + //xNode u=g.addNode(); //node of id 0
2.266 + //xNode v=g.addNode(); //node of id 1
2.267 + //xNode e=g.addEdge(u, v); //edge of id 0
2.268 + //xNode f=g.addEdge(v, u); //edge of id 1
2.269 + //xGraph::NodeMap<bool> nm(g, true);
2.270 + //xnm.set(u, false);
2.271 + //xGraph::EdgeMap<bool> em(g, true);
2.272 + //xem.set(e, false);
2.273 + //xtypedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
2.274 + //xSubGW gw(g, nm, em);
2.275 + //xfor (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
2.276 + //xstd::cout << ":-)" << std::endl;
2.277 + //xfor (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
2.278 + //x\endcode
2.279 + //xThe output of the above code is the following.
2.280 + //x\code
2.281 + //x1
2.282 + //x:-)
2.283 + //x1
2.284 + //x\endcode
2.285 + //xNote that \c n is of type \c SubGW::NodeIt, but it can be converted to
2.286 + //x\c Graph::Node that is why \c g.id(n) can be applied.
2.287 + //x
2.288 + //xFor other examples see also the documentation of NodeSubGraphAdaptor and
2.289 + //xEdgeSubGraphAdaptor.
2.290 + //x
2.291 + //x\author Marton Makai
2.292
2.293 - If the \c checked template parameter is false then we have to note that
2.294 - the node-iterator cares only the filter on the node-set, and the
2.295 - edge-iterator cares only the filter on the edge-set. This way the edge-map
2.296 - should filter all edges which's source or target is filtered by the
2.297 - node-filter.
2.298 - \code
2.299 - typedef ListGraph Graph;
2.300 - Graph g;
2.301 - typedef Graph::Node Node;
2.302 - typedef Graph::Edge Edge;
2.303 - Node u=g.addNode(); //node of id 0
2.304 - Node v=g.addNode(); //node of id 1
2.305 - Node e=g.addEdge(u, v); //edge of id 0
2.306 - Node f=g.addEdge(v, u); //edge of id 1
2.307 - Graph::NodeMap<bool> nm(g, true);
2.308 - nm.set(u, false);
2.309 - Graph::EdgeMap<bool> em(g, true);
2.310 - em.set(e, false);
2.311 - typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
2.312 - SubGW gw(g, nm, em);
2.313 - for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
2.314 - std::cout << ":-)" << std::endl;
2.315 - for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
2.316 - \endcode
2.317 - The output of the above code is the following.
2.318 - \code
2.319 - 1
2.320 - :-)
2.321 - 1
2.322 - \endcode
2.323 - Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
2.324 - \c Graph::Node that is why \c g.id(n) can be applied.
2.325 -
2.326 - For other examples see also the documentation of NodeSubGraphAdaptor and
2.327 - EdgeSubGraphAdaptor.
2.328 -
2.329 - \author Marton Makai
2.330 - */
2.331 template<typename _Graph, typename NodeFilterMap,
2.332 typename EdgeFilterMap, bool checked = true>
2.333 class SubGraphAdaptor :
2.334 @@ -492,18 +514,20 @@
2.335
2.336
2.337
2.338 - /*! \brief An adaptor for hiding nodes from a graph.
2.339 -
2.340 - \warning Graph adaptors are in even more experimental state than the other
2.341 - parts of the lib. Use them at you own risk.
2.342 -
2.343 - An adaptor for hiding nodes from a graph.
2.344 - This adaptor specializes SubGraphAdaptor in the way that only the node-set
2.345 - can be filtered. In usual case the checked parameter is true, we get the
2.346 - induced subgraph. But if the checked parameter is false then we can only
2.347 - filter only isolated nodes.
2.348 - \author Marton Makai
2.349 - */
2.350 + //x\brief An adaptor for hiding nodes from a graph.
2.351 + //x\ingroup graph_adaptors
2.352 + //x
2.353 + //x\warning Graph adaptors are in even more experimental state
2.354 + //xthan the other
2.355 + //xparts of the lib. Use them at you own risk.
2.356 + //x
2.357 + //xAn adaptor for hiding nodes from a graph.
2.358 + //xThis adaptor specializes SubGraphAdaptor in the way that only
2.359 + //xthe node-set
2.360 + //xcan be filtered. In usual case the checked parameter is true, we get the
2.361 + //xinduced subgraph. But if the checked parameter is false then we can only
2.362 + //xfilter only isolated nodes.
2.363 + //x\author Marton Makai
2.364 template<typename Graph, typename NodeFilterMap, bool checked = true>
2.365 class NodeSubGraphAdaptor :
2.366 public SubGraphAdaptor<Graph, NodeFilterMap,
2.367 @@ -523,137 +547,142 @@
2.368 };
2.369
2.370
2.371 - /*! \brief An adaptor for hiding edges from a graph.
2.372 -
2.373 - \warning Graph adaptors are in even more experimental state than the other
2.374 - parts of the lib. Use them at you own risk.
2.375 -
2.376 - An adaptor for hiding edges from a graph.
2.377 - This adaptor specializes SubGraphAdaptor in the way that only the edge-set
2.378 - can be filtered. The usefulness of this adaptor is demonstrated in the
2.379 - problem of searching a maximum number of edge-disjoint shortest paths
2.380 - between
2.381 - two nodes \c s and \c t. Shortest here means being shortest w.r.t.
2.382 - non-negative edge-lengths. Note that
2.383 - the comprehension of the presented solution
2.384 - need's some elementary knowledge from combinatorial optimization.
2.385 -
2.386 - If a single shortest path is to be
2.387 - searched between \c s and \c t, then this can be done easily by
2.388 - applying the Dijkstra algorithm. What happens, if a maximum number of
2.389 - edge-disjoint shortest paths is to be computed. It can be proved that an
2.390 - edge can be in a shortest path if and only if it is tight with respect to
2.391 - the potential function computed by Dijkstra. Moreover, any path containing
2.392 - only such edges is a shortest one. Thus we have to compute a maximum number
2.393 - of edge-disjoint paths between \c s and \c t in the graph which has edge-set
2.394 - all the tight edges. The computation will be demonstrated on the following
2.395 - graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
2.396 - The full source code is available in \ref sub_graph_adaptor_demo.cc.
2.397 - If you are interested in more demo programs, you can use
2.398 - \ref dim_to_dot.cc to generate .dot files from dimacs files.
2.399 - The .dot file of the following figure was generated by
2.400 - the demo program \ref dim_to_dot.cc.
2.401 -
2.402 - \dot
2.403 - digraph lemon_dot_example {
2.404 - node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
2.405 - n0 [ label="0 (s)" ];
2.406 - n1 [ label="1" ];
2.407 - n2 [ label="2" ];
2.408 - n3 [ label="3" ];
2.409 - n4 [ label="4" ];
2.410 - n5 [ label="5" ];
2.411 - n6 [ label="6 (t)" ];
2.412 - edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
2.413 - n5 -> n6 [ label="9, length:4" ];
2.414 - n4 -> n6 [ label="8, length:2" ];
2.415 - n3 -> n5 [ label="7, length:1" ];
2.416 - n2 -> n5 [ label="6, length:3" ];
2.417 - n2 -> n6 [ label="5, length:5" ];
2.418 - n2 -> n4 [ label="4, length:2" ];
2.419 - n1 -> n4 [ label="3, length:3" ];
2.420 - n0 -> n3 [ label="2, length:1" ];
2.421 - n0 -> n2 [ label="1, length:2" ];
2.422 - n0 -> n1 [ label="0, length:3" ];
2.423 - }
2.424 - \enddot
2.425 -
2.426 - \code
2.427 - Graph g;
2.428 - Node s, t;
2.429 - LengthMap length(g);
2.430 -
2.431 - readDimacs(std::cin, g, length, s, t);
2.432 -
2.433 - cout << "edges with lengths (of form id, source--length->target): " << endl;
2.434 - for(EdgeIt e(g); e!=INVALID; ++e)
2.435 - cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
2.436 - << length[e] << "->" << g.id(g.target(e)) << endl;
2.437 -
2.438 - cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
2.439 - \endcode
2.440 - Next, the potential function is computed with Dijkstra.
2.441 - \code
2.442 - typedef Dijkstra<Graph, LengthMap> Dijkstra;
2.443 - Dijkstra dijkstra(g, length);
2.444 - dijkstra.run(s);
2.445 - \endcode
2.446 - Next, we consrtruct a map which filters the edge-set to the tight edges.
2.447 - \code
2.448 - typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
2.449 - TightEdgeFilter;
2.450 - TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
2.451 -
2.452 - typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
2.453 - SubGW gw(g, tight_edge_filter);
2.454 - \endcode
2.455 - Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
2.456 - with a max flow algorithm Preflow.
2.457 - \code
2.458 - ConstMap<Edge, int> const_1_map(1);
2.459 - Graph::EdgeMap<int> flow(g, 0);
2.460 -
2.461 - Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
2.462 - preflow(gw, s, t, const_1_map, flow);
2.463 - preflow.run();
2.464 - \endcode
2.465 - Last, the output is:
2.466 - \code
2.467 - cout << "maximum number of edge-disjoint shortest path: "
2.468 - << preflow.flowValue() << endl;
2.469 - cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
2.470 - << endl;
2.471 - for(EdgeIt e(g); e!=INVALID; ++e)
2.472 - if (flow[e])
2.473 - cout << " " << g.id(g.source(e)) << "--"
2.474 - << length[e] << "->" << g.id(g.target(e)) << endl;
2.475 - \endcode
2.476 - The program has the following (expected :-)) output:
2.477 - \code
2.478 - edges with lengths (of form id, source--length->target):
2.479 - 9, 5--4->6
2.480 - 8, 4--2->6
2.481 - 7, 3--1->5
2.482 - 6, 2--3->5
2.483 - 5, 2--5->6
2.484 - 4, 2--2->4
2.485 - 3, 1--3->4
2.486 - 2, 0--1->3
2.487 - 1, 0--2->2
2.488 - 0, 0--3->1
2.489 - s: 0 t: 6
2.490 - maximum number of edge-disjoint shortest path: 2
2.491 - edges of the maximum number of edge-disjoint shortest s-t paths:
2.492 - 9, 5--4->6
2.493 - 8, 4--2->6
2.494 - 7, 3--1->5
2.495 - 4, 2--2->4
2.496 - 2, 0--1->3
2.497 - 1, 0--2->2
2.498 - \endcode
2.499 -
2.500 - \author Marton Makai
2.501 - */
2.502 + //x\brief An adaptor for hiding edges from a graph.
2.503 + //x
2.504 + //x\warning Graph adaptors are in even more experimental state
2.505 + //xthan the other parts of the lib. Use them at you own risk.
2.506 + //x
2.507 + //xAn adaptor for hiding edges from a graph.
2.508 + //xThis adaptor specializes SubGraphAdaptor in the way that
2.509 + //xonly the edge-set
2.510 + //xcan be filtered. The usefulness of this adaptor is demonstrated in the
2.511 + //xproblem of searching a maximum number of edge-disjoint shortest paths
2.512 + //xbetween
2.513 + //xtwo nodes \c s and \c t. Shortest here means being shortest w.r.t.
2.514 + //xnon-negative edge-lengths. Note that
2.515 + //xthe comprehension of the presented solution
2.516 + //xneed's some elementary knowledge from combinatorial optimization.
2.517 + //x
2.518 + //xIf a single shortest path is to be
2.519 + //xsearched between \c s and \c t, then this can be done easily by
2.520 + //xapplying the Dijkstra algorithm. What happens, if a maximum number of
2.521 + //xedge-disjoint shortest paths is to be computed. It can be proved that an
2.522 + //xedge can be in a shortest path if and only
2.523 + //xif it is tight with respect to
2.524 + //xthe potential function computed by Dijkstra.
2.525 + //xMoreover, any path containing
2.526 + //xonly such edges is a shortest one.
2.527 + //xThus we have to compute a maximum number
2.528 + //xof edge-disjoint paths between \c s and \c t in
2.529 + //xthe graph which has edge-set
2.530 + //xall the tight edges. The computation will be demonstrated
2.531 + //xon the following
2.532 + //xgraph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
2.533 + //xThe full source code is available in \ref sub_graph_adaptor_demo.cc.
2.534 + //xIf you are interested in more demo programs, you can use
2.535 + //x\ref dim_to_dot.cc to generate .dot files from dimacs files.
2.536 + //xThe .dot file of the following figure was generated by
2.537 + //xthe demo program \ref dim_to_dot.cc.
2.538 + //x
2.539 + //x\dot
2.540 + //xdigraph lemon_dot_example {
2.541 + //xnode [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
2.542 + //xn0 [ label="0 (s)" ];
2.543 + //xn1 [ label="1" ];
2.544 + //xn2 [ label="2" ];
2.545 + //xn3 [ label="3" ];
2.546 + //xn4 [ label="4" ];
2.547 + //xn5 [ label="5" ];
2.548 + //xn6 [ label="6 (t)" ];
2.549 + //xedge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
2.550 + //xn5 -> n6 [ label="9, length:4" ];
2.551 + //xn4 -> n6 [ label="8, length:2" ];
2.552 + //xn3 -> n5 [ label="7, length:1" ];
2.553 + //xn2 -> n5 [ label="6, length:3" ];
2.554 + //xn2 -> n6 [ label="5, length:5" ];
2.555 + //xn2 -> n4 [ label="4, length:2" ];
2.556 + //xn1 -> n4 [ label="3, length:3" ];
2.557 + //xn0 -> n3 [ label="2, length:1" ];
2.558 + //xn0 -> n2 [ label="1, length:2" ];
2.559 + //xn0 -> n1 [ label="0, length:3" ];
2.560 + //x}
2.561 + //x\enddot
2.562 + //x
2.563 + //x\code
2.564 + //xGraph g;
2.565 + //xNode s, t;
2.566 + //xLengthMap length(g);
2.567 + //x
2.568 + //xreadDimacs(std::cin, g, length, s, t);
2.569 + //x
2.570 + //xcout << "edges with lengths (of form id, source--length->target): " << endl;
2.571 + //xfor(EdgeIt e(g); e!=INVALID; ++e)
2.572 + //x cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
2.573 + //x << length[e] << "->" << g.id(g.target(e)) << endl;
2.574 + //x
2.575 + //xcout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
2.576 + //x\endcode
2.577 + //xNext, the potential function is computed with Dijkstra.
2.578 + //x\code
2.579 + //xtypedef Dijkstra<Graph, LengthMap> Dijkstra;
2.580 + //xDijkstra dijkstra(g, length);
2.581 + //xdijkstra.run(s);
2.582 + //x\endcode
2.583 + //xNext, we consrtruct a map which filters the edge-set to the tight edges.
2.584 + //x\code
2.585 + //xtypedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
2.586 + //x TightEdgeFilter;
2.587 + //xTightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
2.588 + //x
2.589 + //xtypedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
2.590 + //xSubGW gw(g, tight_edge_filter);
2.591 + //x\endcode
2.592 + //xThen, the maximum nimber of edge-disjoint \c s-\c t paths are computed
2.593 + //xwith a max flow algorithm Preflow.
2.594 + //x\code
2.595 + //xConstMap<Edge, int> const_1_map(1);
2.596 + //xGraph::EdgeMap<int> flow(g, 0);
2.597 + //x
2.598 + //xPreflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
2.599 + //x preflow(gw, s, t, const_1_map, flow);
2.600 + //xpreflow.run();
2.601 + //x\endcode
2.602 + //xLast, the output is:
2.603 + //x\code
2.604 + //xcout << "maximum number of edge-disjoint shortest path: "
2.605 + //x << preflow.flowValue() << endl;
2.606 + //xcout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
2.607 + //x << endl;
2.608 + //xfor(EdgeIt e(g); e!=INVALID; ++e)
2.609 + //x if (flow[e])
2.610 + //x cout << " " << g.id(g.source(e)) << "--"
2.611 + //x << length[e] << "->" << g.id(g.target(e)) << endl;
2.612 + //x\endcode
2.613 + //xThe program has the following (expected :-)) output:
2.614 + //x\code
2.615 + //xedges with lengths (of form id, source--length->target):
2.616 + //x 9, 5--4->6
2.617 + //x 8, 4--2->6
2.618 + //x 7, 3--1->5
2.619 + //x 6, 2--3->5
2.620 + //x 5, 2--5->6
2.621 + //x 4, 2--2->4
2.622 + //x 3, 1--3->4
2.623 + //x 2, 0--1->3
2.624 + //x 1, 0--2->2
2.625 + //x 0, 0--3->1
2.626 + //xs: 0 t: 6
2.627 + //xmaximum number of edge-disjoint shortest path: 2
2.628 + //xedges of the maximum number of edge-disjoint shortest s-t paths:
2.629 + //x 9, 5--4->6
2.630 + //x 8, 4--2->6
2.631 + //x 7, 3--1->5
2.632 + //x 4, 2--2->4
2.633 + //x 2, 0--1->3
2.634 + //x 1, 0--2->2
2.635 + //x\endcode
2.636 + //x
2.637 + //x\author Marton Makai
2.638 template<typename Graph, typename EdgeFilterMap>
2.639 class EdgeSubGraphAdaptor :
2.640 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
2.641 @@ -740,12 +769,13 @@
2.642
2.643 };
2.644
2.645 - /// \brief An undirected graph is made from a directed graph by an adaptor
2.646 - ///
2.647 - /// Undocumented, untested!!!
2.648 - /// If somebody knows nice demo application, let's polulate it.
2.649 - ///
2.650 - /// \author Marton Makai
2.651 + //x\brief An undirected graph is made from a directed graph by an adaptor
2.652 + //x\ingroup graph_adaptors
2.653 + //x
2.654 + //x Undocumented, untested!!!
2.655 + //x If somebody knows nice demo application, let's polulate it.
2.656 + //x
2.657 + //x \author Marton Makai
2.658 template<typename _Graph>
2.659 class UGraphAdaptor :
2.660 public IterableUGraphExtender<
2.661 @@ -793,10 +823,10 @@
2.662 typedef typename Parent::Node Node;
2.663 typedef typename _Graph::Edge GraphEdge;
2.664 template <typename T> class EdgeMap;
2.665 - /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
2.666 - /// _Graph::Edge. It contains an extra bool flag which is true
2.667 - /// if and only if the
2.668 - /// edge is the backward version of the original edge.
2.669 + // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
2.670 + // _Graph::Edge. It contains an extra bool flag which is true
2.671 + // if and only if the
2.672 + // edge is the backward version of the original edge.
2.673 class Edge : public _Graph::Edge {
2.674 friend class SubBidirGraphAdaptorBase<
2.675 Graph, ForwardFilterMap, BackwardFilterMap>;
2.676 @@ -805,9 +835,9 @@
2.677 bool backward; //true, iff backward
2.678 public:
2.679 Edge() { }
2.680 - /// \todo =false is needed, or causes problems?
2.681 - /// If \c _backward is false, then we get an edge corresponding to the
2.682 - /// original one, otherwise its oppositely directed pair is obtained.
2.683 + // \todo =false is needed, or causes problems?
2.684 + // If \c _backward is false, then we get an edge corresponding to the
2.685 + // original one, otherwise its oppositely directed pair is obtained.
2.686 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
2.687 _Graph::Edge(e), backward(_backward) { }
2.688 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
2.689 @@ -931,16 +961,21 @@
2.690 Node target(Edge e) const {
2.691 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
2.692
2.693 - /// Gives back the opposite edge.
2.694 + //x Gives back the opposite edge.
2.695 +
2.696 + //x\e
2.697 + //x
2.698 Edge opposite(const Edge& e) const {
2.699 Edge f=e;
2.700 f.backward=!f.backward;
2.701 return f;
2.702 }
2.703
2.704 - /// \warning This is a linear time operation and works only if
2.705 - /// \c Graph::EdgeIt is defined.
2.706 - /// \todo hmm
2.707 + //x\e
2.708 +
2.709 + //x \warning This is a linear time operation and works only if
2.710 + //x \c Graph::EdgeIt is defined.
2.711 + //x \todo hmm
2.712 int edgeNum() const {
2.713 int i=0;
2.714 Edge e;
2.715 @@ -951,10 +986,12 @@
2.716 bool forward(const Edge& e) const { return !e.backward; }
2.717 bool backward(const Edge& e) const { return e.backward; }
2.718
2.719 + //x\e
2.720 +
2.721 + //x \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
2.722 + //x _Graph::EdgeMap one for the forward edges and
2.723 + //x one for the backward edges.
2.724 template <typename T>
2.725 - /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
2.726 - /// _Graph::EdgeMap one for the forward edges and
2.727 - /// one for the backward edges.
2.728 class EdgeMap {
2.729 template <typename TT> friend class EdgeMap;
2.730 typename _Graph::template EdgeMap<T> forward_map, backward_map;
2.731 @@ -1002,44 +1039,46 @@
2.732 };
2.733
2.734
2.735 - ///\brief An adaptor for composing a subgraph of a
2.736 - /// bidirected graph made from a directed one.
2.737 - ///
2.738 - /// An adaptor for composing a subgraph of a
2.739 - /// bidirected graph made from a directed one.
2.740 - ///
2.741 - ///\warning Graph adaptors are in even more experimental state than the other
2.742 - ///parts of the lib. Use them at you own risk.
2.743 - ///
2.744 - /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
2.745 - /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
2.746 - /// reversing its orientation. We are given moreover two bool valued
2.747 - /// maps on the edge-set,
2.748 - /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
2.749 - /// SubBidirGraphAdaptor implements the graph structure with node-set
2.750 - /// \f$V\f$ and edge-set
2.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$.
2.752 - /// The purpose of writing + instead of union is because parallel
2.753 - /// edges can arise. (Similarly, antiparallel edges also can arise).
2.754 - /// In other words, a subgraph of the bidirected graph obtained, which
2.755 - /// is given by orienting the edges of the original graph in both directions.
2.756 - /// As the oppositely directed edges are logically different,
2.757 - /// the maps are able to attach different values for them.
2.758 - ///
2.759 - /// An example for such a construction is \c RevGraphAdaptor where the
2.760 - /// forward_filter is everywhere false and the backward_filter is
2.761 - /// everywhere true. We note that for sake of efficiency,
2.762 - /// \c RevGraphAdaptor is implemented in a different way.
2.763 - /// But BidirGraphAdaptor is obtained from
2.764 - /// SubBidirGraphAdaptor by considering everywhere true
2.765 - /// valued maps both for forward_filter and backward_filter.
2.766 - ///
2.767 - /// The most important application of SubBidirGraphAdaptor
2.768 - /// is ResGraphAdaptor, which stands for the residual graph in directed
2.769 - /// flow and circulation problems.
2.770 - /// As adaptors usually, the SubBidirGraphAdaptor implements the
2.771 - /// above mentioned graph structure without its physical storage,
2.772 - /// that is the whole stuff is stored in constant memory.
2.773 + //x\brief An adaptor for composing a subgraph of a
2.774 + //x bidirected graph made from a directed one.
2.775 + //x\ingroup graph_adaptors
2.776 + //x
2.777 + //x An adaptor for composing a subgraph of a
2.778 + //x bidirected graph made from a directed one.
2.779 + //x
2.780 + //x\warning Graph adaptors are in even more experimental state
2.781 + //xthan the other
2.782 + //xparts of the lib. Use them at you own risk.
2.783 + //x
2.784 + //x Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
2.785 + //x \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
2.786 + //x reversing its orientation. We are given moreover two bool valued
2.787 + //x maps on the edge-set,
2.788 + //x \f$forward\_filter\f$, and \f$backward\_filter\f$.
2.789 + //x SubBidirGraphAdaptor implements the graph structure with node-set
2.790 + //x \f$V\f$ and edge-set
2.791 + //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$.
2.792 + //x The purpose of writing + instead of union is because parallel
2.793 + //x edges can arise. (Similarly, antiparallel edges also can arise).
2.794 + //x In other words, a subgraph of the bidirected graph obtained, which
2.795 + //x is given by orienting the edges of the original graph in both directions.
2.796 + //x As the oppositely directed edges are logically different,
2.797 + //x the maps are able to attach different values for them.
2.798 + //x
2.799 + //x An example for such a construction is \c RevGraphAdaptor where the
2.800 + //x forward_filter is everywhere false and the backward_filter is
2.801 + //x everywhere true. We note that for sake of efficiency,
2.802 + //x \c RevGraphAdaptor is implemented in a different way.
2.803 + //x But BidirGraphAdaptor is obtained from
2.804 + //x SubBidirGraphAdaptor by considering everywhere true
2.805 + //x valued maps both for forward_filter and backward_filter.
2.806 + //x
2.807 + //x The most important application of SubBidirGraphAdaptor
2.808 + //x is ResGraphAdaptor, which stands for the residual graph in directed
2.809 + //x flow and circulation problems.
2.810 + //x As adaptors usually, the SubBidirGraphAdaptor implements the
2.811 + //x above mentioned graph structure without its physical storage,
2.812 + //x that is the whole stuff is stored in constant memory.
2.813 template<typename _Graph,
2.814 typename ForwardFilterMap, typename BackwardFilterMap>
2.815 class SubBidirGraphAdaptor :
2.816 @@ -1063,15 +1102,17 @@
2.817
2.818
2.819
2.820 - ///\brief An adaptor for composing bidirected graph from a directed one.
2.821 - ///
2.822 - ///\warning Graph adaptors are in even more experimental state than the other
2.823 - ///parts of the lib. Use them at you own risk.
2.824 - ///
2.825 - /// An adaptor for composing bidirected graph from a directed one.
2.826 - /// A bidirected graph is composed over the directed one without physical
2.827 - /// storage. As the oppositely directed edges are logically different ones
2.828 - /// the maps are able to attach different values for them.
2.829 + //x\brief An adaptor for composing bidirected graph from a directed one.
2.830 + //x\ingroup graph_adaptors
2.831 + //x
2.832 + //x\warning Graph adaptors are in even more experimental state
2.833 + //xthan the other
2.834 + //xparts of the lib. Use them at you own risk.
2.835 + //x
2.836 + //x An adaptor for composing bidirected graph from a directed one.
2.837 + //x A bidirected graph is composed over the directed one without physical
2.838 + //x storage. As the oppositely directed edges are logically different ones
2.839 + //x the maps are able to attach different values for them.
2.840 template<typename Graph>
2.841 class BidirGraphAdaptor :
2.842 public SubBidirGraphAdaptor<
2.843 @@ -1139,38 +1180,41 @@
2.844 };
2.845
2.846
2.847 - /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
2.848 -
2.849 - An adaptor for composing the residual graph for directed flow and circulation problems.
2.850 - Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
2.851 - number type. Let moreover
2.852 - \f$f,c:A\to F\f$, be functions on the edge-set.
2.853 - In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
2.854 - and \f$c\f$ for a capacity function.
2.855 - Suppose that a graph instange \c g of type
2.856 - \c ListGraph implements \f$G\f$.
2.857 - \code
2.858 - ListGraph g;
2.859 - \endcode
2.860 - Then RevGraphAdaptor implements the graph structure with node-set
2.861 - \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
2.862 - \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
2.863 - \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
2.864 - i.e. the so called residual graph.
2.865 - When we take the union \f$A_{forward}\cup A_{backward}\f$,
2.866 - multilicities are counted, i.e. if an edge is in both
2.867 - \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
2.868 - appears twice.
2.869 - The following code shows how
2.870 - such an instance can be constructed.
2.871 - \code
2.872 - typedef ListGraph Graph;
2.873 - Graph::EdgeMap<int> f(g);
2.874 - Graph::EdgeMap<int> c(g);
2.875 - ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
2.876 - \endcode
2.877 - \author Marton Makai
2.878 - */
2.879 + //x\brief An adaptor for composing the residual
2.880 + //xgraph for directed flow and circulation problems.
2.881 + //x\ingroup graph_adaptors
2.882 + //x
2.883 + //xAn adaptor for composing the residual graph for
2.884 + //xdirected flow and circulation problems.
2.885 + //xLet \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
2.886 + //xnumber type. Let moreover
2.887 + //x\f$f,c:A\to F\f$, be functions on the edge-set.
2.888 + //xIn the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
2.889 + //xand \f$c\f$ for a capacity function.
2.890 + //xSuppose that a graph instange \c g of type
2.891 + //x\c ListGraph implements \f$G\f$ .
2.892 + //x\code
2.893 + //x ListGraph g;
2.894 + //x\endcode
2.895 + //xThen RevGraphAdaptor implements the graph structure with node-set
2.896 + //x\f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
2.897 + //x\f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
2.898 + //x\f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
2.899 + //xi.e. the so called residual graph.
2.900 + //xWhen we take the union \f$A_{forward}\cup A_{backward}\f$,
2.901 + //xmultilicities are counted, i.e. if an edge is in both
2.902 + //x\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
2.903 + //xappears twice.
2.904 + //xThe following code shows how
2.905 + //xsuch an instance can be constructed.
2.906 + //x\code
2.907 + //xtypedef ListGraph Graph;
2.908 + //xGraph::EdgeMap<int> f(g);
2.909 + //xGraph::EdgeMap<int> c(g);
2.910 + //xResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
2.911 + //x\endcode
2.912 + //x\author Marton Makai
2.913 + //x
2.914 template<typename Graph, typename Number,
2.915 typename CapacityMap, typename FlowMap>
2.916 class ResGraphAdaptor :
2.917 @@ -1220,10 +1264,10 @@
2.918 flow->set(e, (*flow)[e]-a);
2.919 }
2.920
2.921 - /// \brief Residual capacity map.
2.922 - ///
2.923 - /// In generic residual graphs the residual capacity can be obtained
2.924 - /// as a map.
2.925 + //x \brief Residual capacity map.
2.926 + //x
2.927 + //x In generic residual graphs the residual capacity can be obtained
2.928 + //x as a map.
2.929 class ResCap {
2.930 protected:
2.931 const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
2.932 @@ -1277,20 +1321,23 @@
2.933 };
2.934
2.935
2.936 - /// For blocking flows.
2.937 -
2.938 - ///\warning Graph adaptors are in even more
2.939 - ///experimental state than the other
2.940 - ///parts of the lib. Use them at you own risk.
2.941 - ///
2.942 - ///This graph adaptor is used for on-the-fly
2.943 - ///Dinits blocking flow computations.
2.944 - ///For each node, an out-edge is stored which is used when the
2.945 - ///\code OutEdgeIt& first(OutEdgeIt&, const Node&)\endcode
2.946 - ///is called.
2.947 - ///
2.948 - ///\author Marton Makai
2.949 - ///
2.950 + //x\brief For blocking flows.
2.951 + //x\ingroup graph_adaptors
2.952 + //x
2.953 + //x\warning Graph adaptors are in even more
2.954 + //xexperimental state than the other
2.955 + //xparts of the lib. Use them at you own risk.
2.956 + //x
2.957 + //xThis graph adaptor is used for on-the-fly
2.958 + //xDinits blocking flow computations.
2.959 + //xFor each node, an out-edge is stored which is used when the
2.960 + //x\code
2.961 + //xOutEdgeIt& first(OutEdgeIt&, const Node&)
2.962 + //x\endcode
2.963 + //xis called.
2.964 + //x
2.965 + //x\author Marton Makai
2.966 + //x
2.967 template <typename _Graph, typename FirstOutEdgesMap>
2.968 class ErasingFirstGraphAdaptor :
2.969 public IterableGraphExtender<
2.970 @@ -1347,7 +1394,7 @@
2.971 }
2.972 };
2.973
2.974 - /// \todo May we want VARIANT/union type
2.975 + //x \todo May we want VARIANT/union type
2.976 class Edge : public Parent::Edge {
2.977 friend class SplitGraphAdaptorBase;
2.978 template <typename T> friend class EdgeMap;
2.979 @@ -1674,8 +1721,6 @@
2.980
2.981 };
2.982
2.983 - ///@}
2.984 -
2.985 } //namespace lemon
2.986
2.987 #endif //LEMON_GRAPH_ADAPTOR_H