Index: lemon/graph_adaptor.h
===================================================================
 lemon/graph_adaptor.h (revision 1946)
+++ lemon/graph_adaptor.h (revision 1949)
@@ 39,27 +39,23 @@
namespace lemon {
 // Graph adaptors

 /*!
 \addtogroup graph_adaptors
 @{
 */

 /*!
 Base type for the Graph Adaptors

 \warning Graph adaptors are in even more experimental state than the other
 parts of the lib. Use them at you own risk.

 This is the base type for most of LEMON graph adaptors.
 This class implements a trivial graph adaptor i.e. it only wraps the
 functions and types of the graph. The purpose of this class is to
 make easier implementing graph adaptors. E.g. if an adaptor is
 considered which differs from the wrapped graph only in some of its
 functions or types, then it can be derived from GraphAdaptor, and only the
 differences should be implemented.

 \author Marton Makai
 */
+ //x\brief Base type for the Graph Adaptors
+ //x\ingroup graph_adaptors
+ //x
+ //xBase type for the Graph Adaptors
+ //x
+ //x\warning Graph adaptors are in even
+ //xmore experimental state than the other
+ //xparts of the lib. Use them at you own risk.
+ //x
+ //xThis is the base type for most of LEMON graph adaptors.
+ //xThis class implements a trivial graph adaptor i.e. it only wraps the
+ //xfunctions and types of the graph. The purpose of this class is to
+ //xmake easier implementing graph adaptors. E.g. if an adaptor is
+ //xconsidered which differs from the wrapped graph only in some of its
+ //xfunctions or types, then it can be derived from GraphAdaptor,
+ //xand only the
+ //xdifferences should be implemented.
+ //x
+ //xauthor Marton Makai
template
class GraphAdaptorBase {
@@ 181,27 +177,21 @@
 /// A graph adaptor which reverses the orientation of the edges.

 ///\warning Graph adaptors are in even more experimental state than the other
+ ///\brief A graph adaptor which reverses the orientation of the edges.
+ ///\ingroup graph_adaptors
+ ///
+ ///\warning Graph adaptors are in even more experimental
+ ///state than the other
///parts of the lib. Use them at you own risk.
///
 /// Let \f$G=(V, A)\f$ be a directed graph and
 /// suppose that a graph instange \c g of type
 /// \c ListGraph implements \f$G\f$.
+ /// If \c g is defined as
///\code
/// ListGraph g;
///\endcode
 /// For each directed edge
 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
 /// reversing its orientation.
 /// Then RevGraphAdaptor implements the graph structure with nodeset
 /// \f$V\f$ and edgeset
 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
 /// reversing the orientation of its edges. The following code shows how
 /// such an instance can be constructed.
+ /// then
///\code
/// RevGraphAdaptor gw(g);
///\endcode
 ///\author Marton Makai
+ ///implements the graph obtained from \c g by
+ /// reversing the orientation of its edges.
template
@@ 291,28 +281,42 @@
}
 /// This function hides \c n in the graph, i.e. the iteration
 /// jumps over it. This is done by simply setting the value of \c n
 /// to be false in the corresponding nodemap.
+ //x\e
+
+ //x This function hides \c n in the graph, i.e. the iteration
+ //x jumps over it. This is done by simply setting the value of \c n
+ //x to be false in the corresponding nodemap.
void hide(const Node& n) const { node_filter_map>set(n, false); }
 /// This function hides \c e in the graph, i.e. the iteration
 /// jumps over it. This is done by simply setting the value of \c e
 /// to be false in the corresponding edgemap.
+ //x\e
+
+ //x This function hides \c e in the graph, i.e. the iteration
+ //x jumps over it. This is done by simply setting the value of \c e
+ //x to be false in the corresponding edgemap.
void hide(const Edge& e) const { edge_filter_map>set(e, false); }
 /// The value of \c n is set to be true in the nodemap which stores
 /// hide information. If \c n was hidden previuosly, then it is shown
 /// again
+ //x\e
+
+ //x The value of \c n is set to be true in the nodemap which stores
+ //x hide information. If \c n was hidden previuosly, then it is shown
+ //x again
void unHide(const Node& n) const { node_filter_map>set(n, true); }
 /// The value of \c e is set to be true in the edgemap which stores
 /// hide information. If \c e was hidden previuosly, then it is shown
 /// again
+ //x\e
+
+ //x The value of \c e is set to be true in the edgemap which stores
+ //x hide information. If \c e was hidden previuosly, then it is shown
+ //x again
void unHide(const Edge& e) const { edge_filter_map>set(e, true); }
 /// Returns true if \c n is hidden.
+ //x Returns true if \c n is hidden.
+
+ //x\e
+ //x
bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
 /// Returns true if \c n is hidden.
+ //x Returns true if \c n is hidden.
+
+ //x\e
+ //x
bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
@@ 383,28 +387,42 @@
}
 /// This function hides \c n in the graph, i.e. the iteration
 /// jumps over it. This is done by simply setting the value of \c n
 /// to be false in the corresponding nodemap.
+ //x\e
+
+ //x This function hides \c n in the graph, i.e. the iteration
+ //x jumps over it. This is done by simply setting the value of \c n
+ //x to be false in the corresponding nodemap.
void hide(const Node& n) const { node_filter_map>set(n, false); }
 /// This function hides \c e in the graph, i.e. the iteration
 /// jumps over it. This is done by simply setting the value of \c e
 /// to be false in the corresponding edgemap.
+ //x\e
+
+ //x This function hides \c e in the graph, i.e. the iteration
+ //x jumps over it. This is done by simply setting the value of \c e
+ //x to be false in the corresponding edgemap.
void hide(const Edge& e) const { edge_filter_map>set(e, false); }
 /// The value of \c n is set to be true in the nodemap which stores
 /// hide information. If \c n was hidden previuosly, then it is shown
 /// again
+ //x\e
+
+ //x The value of \c n is set to be true in the nodemap which stores
+ //x hide information. If \c n was hidden previuosly, then it is shown
+ //x again
void unHide(const Node& n) const { node_filter_map>set(n, true); }
 /// The value of \c e is set to be true in the edgemap which stores
 /// hide information. If \c e was hidden previuosly, then it is shown
 /// again
+ //x\e
+
+ //x The value of \c e is set to be true in the edgemap which stores
+ //x hide information. If \c e was hidden previuosly, then it is shown
+ //x again
void unHide(const Edge& e) const { edge_filter_map>set(e, true); }
 /// Returns true if \c n is hidden.
+ //x Returns true if \c n is hidden.
+
+ //x\e
+ //x
bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
 /// Returns true if \c n is hidden.
+ //x Returns true if \c n is hidden.
+
+ //x\e
+ //x
bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
@@ 413,62 +431,66 @@
};
 /*! \brief A graph adaptor for hiding nodes and edges from a graph.

 \warning Graph adaptors are in even more experimental state than the other
 parts of the lib. Use them at you own risk.

 SubGraphAdaptor shows the graph with filtered nodeset and
 edgeset. If the \c checked parameter is true then it filters the edgeset
 to do not get invalid edges without source or target.
 Let \f$G=(V, A)\f$ be a directed graph
 and suppose that the graph instance \c g of type ListGraph implements
 \f$G\f$.
 Let moreover \f$b_V\f$ and
 \f$b_A\f$ be boolvalued functions resp. on the nodeset and edgeset.
 SubGraphAdaptor<...>::NodeIt iterates
 on the nodeset \f$\{v\in V : b_V(v)=true\}\f$ and
 SubGraphAdaptor<...>::EdgeIt iterates
 on the edgeset \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
 SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
 only on edges leaving and entering a specific node which have true value.

 If the \c checked template parameter is false then we have to note that
 the nodeiterator cares only the filter on the nodeset, and the
 edgeiterator cares only the filter on the edgeset. This way the edgemap
 should filter all edges which's source or target is filtered by the
 nodefilter.
 \code
 typedef ListGraph Graph;
 Graph g;
 typedef Graph::Node Node;
 typedef Graph::Edge Edge;
 Node u=g.addNode(); //node of id 0
 Node v=g.addNode(); //node of id 1
 Node e=g.addEdge(u, v); //edge of id 0
 Node f=g.addEdge(v, u); //edge of id 1
 Graph::NodeMap nm(g, true);
 nm.set(u, false);
 Graph::EdgeMap em(g, true);
 em.set(e, false);
 typedef SubGraphAdaptor, Graph::EdgeMap > SubGW;
 SubGW gw(g, nm, em);
 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
 std::cout << ":)" << std::endl;
 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
 \endcode
 The output of the above code is the following.
 \code
 1
 :)
 1
 \endcode
 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
 \c Graph::Node that is why \c g.id(n) can be applied.

 For other examples see also the documentation of NodeSubGraphAdaptor and
 EdgeSubGraphAdaptor.

 \author Marton Makai
 */
+ //x\brief A graph adaptor for hiding nodes and edges from a graph.
+ //x\ingroup graph_adaptors
+ //x
+ //x\warning Graph adaptors are in even more experimental
+ //xstate than the other
+ //xparts of the lib. Use them at you own risk.
+ //x
+ //xSubGraphAdaptor shows the graph with filtered nodeset and
+ //xedgeset. If the \c checked parameter is true then it filters the edgeset
+ //xto do not get invalid edges without source or target.
+ //xLet \f$G=(V, A)\f$ be a directed graph
+ //xand suppose that the graph instance \c g of type ListGraph implements
+ //x\f$G\f$.
+ //x/Let moreover \f$b_V\f$ and
+ //x\f$b_A\f$ be boolvalued functions resp. on the nodeset and edgeset.
+ //xSubGraphAdaptor<...>::NodeIt iterates
+ //xon the nodeset \f$\{v\in V : b_V(v)=true\}\f$ and
+ //xSubGraphAdaptor<...>::EdgeIt iterates
+ //xon the edgeset \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
+ //xSubGraphAdaptor<...>::OutEdgeIt and
+ //xSubGraphAdaptor<...>::InEdgeIt iterates
+ //xonly on edges leaving and entering a specific node which have true value.
+ //x
+ //xIf the \c checked template parameter is false then we have to note that
+ //xthe nodeiterator cares only the filter on the nodeset, and the
+ //xedgeiterator cares only the filter on the edgeset.
+ //xThis way the edgemap
+ //xshould filter all edges which's source or target is filtered by the
+ //xnodefilter.
+ //x\code
+ //xtypedef ListGraph Graph;
+ //xGraph g;
+ //xtypedef Graph::Node Node;
+ //xtypedef Graph::Edge Edge;
+ //xNode u=g.addNode(); //node of id 0
+ //xNode v=g.addNode(); //node of id 1
+ //xNode e=g.addEdge(u, v); //edge of id 0
+ //xNode f=g.addEdge(v, u); //edge of id 1
+ //xGraph::NodeMap nm(g, true);
+ //xnm.set(u, false);
+ //xGraph::EdgeMap em(g, true);
+ //xem.set(e, false);
+ //xtypedef SubGraphAdaptor, Graph::EdgeMap > SubGW;
+ //xSubGW gw(g, nm, em);
+ //xfor (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
+ //xstd::cout << ":)" << std::endl;
+ //xfor (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
+ //x\endcode
+ //xThe output of the above code is the following.
+ //x\code
+ //x1
+ //x:)
+ //x1
+ //x\endcode
+ //xNote that \c n is of type \c SubGW::NodeIt, but it can be converted to
+ //x\c Graph::Node that is why \c g.id(n) can be applied.
+ //x
+ //xFor other examples see also the documentation of NodeSubGraphAdaptor and
+ //xEdgeSubGraphAdaptor.
+ //x
+ //x\author Marton Makai
+
template
@@ 493,16 +515,18 @@
 /*! \brief An adaptor for hiding nodes from a graph.

 \warning Graph adaptors are in even more experimental state than the other
 parts of the lib. Use them at you own risk.

 An adaptor for hiding nodes from a graph.
 This adaptor specializes SubGraphAdaptor in the way that only the nodeset
 can be filtered. In usual case the checked parameter is true, we get the
 induced subgraph. But if the checked parameter is false then we can only
 filter only isolated nodes.
 \author Marton Makai
 */
+ //x\brief An adaptor for hiding nodes from a graph.
+ //x\ingroup graph_adaptors
+ //x
+ //x\warning Graph adaptors are in even more experimental state
+ //xthan the other
+ //xparts of the lib. Use them at you own risk.
+ //x
+ //xAn adaptor for hiding nodes from a graph.
+ //xThis adaptor specializes SubGraphAdaptor in the way that only
+ //xthe nodeset
+ //xcan be filtered. In usual case the checked parameter is true, we get the
+ //xinduced subgraph. But if the checked parameter is false then we can only
+ //xfilter only isolated nodes.
+ //x\author Marton Makai
template
class NodeSubGraphAdaptor :
@@ 524,135 +548,140 @@
 /*! \brief An adaptor for hiding edges from a graph.

 \warning Graph adaptors are in even more experimental state than the other
 parts of the lib. Use them at you own risk.

 An adaptor for hiding edges from a graph.
 This adaptor specializes SubGraphAdaptor in the way that only the edgeset
 can be filtered. The usefulness of this adaptor is demonstrated in the
 problem of searching a maximum number of edgedisjoint shortest paths
 between
 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
 nonnegative edgelengths. Note that
 the comprehension of the presented solution
 need's some elementary knowledge from combinatorial optimization.

 If a single shortest path is to be
 searched between \c s and \c t, then this can be done easily by
 applying the Dijkstra algorithm. What happens, if a maximum number of
 edgedisjoint shortest paths is to be computed. It can be proved that an
 edge can be in a shortest path if and only if it is tight with respect to
 the potential function computed by Dijkstra. Moreover, any path containing
 only such edges is a shortest one. Thus we have to compute a maximum number
 of edgedisjoint paths between \c s and \c t in the graph which has edgeset
 all the tight edges. The computation will be demonstrated on the following
 graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
 The full source code is available in \ref sub_graph_adaptor_demo.cc.
 If you are interested in more demo programs, you can use
 \ref dim_to_dot.cc to generate .dot files from dimacs files.
 The .dot file of the following figure was generated by
 the demo program \ref dim_to_dot.cc.

 \dot
 digraph lemon_dot_example {
 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
 n0 [ label="0 (s)" ];
 n1 [ label="1" ];
 n2 [ label="2" ];
 n3 [ label="3" ];
 n4 [ label="4" ];
 n5 [ label="5" ];
 n6 [ label="6 (t)" ];
 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
 n5 > n6 [ label="9, length:4" ];
 n4 > n6 [ label="8, length:2" ];
 n3 > n5 [ label="7, length:1" ];
 n2 > n5 [ label="6, length:3" ];
 n2 > n6 [ label="5, length:5" ];
 n2 > n4 [ label="4, length:2" ];
 n1 > n4 [ label="3, length:3" ];
 n0 > n3 [ label="2, length:1" ];
 n0 > n2 [ label="1, length:2" ];
 n0 > n1 [ label="0, length:3" ];
 }
 \enddot

 \code
 Graph g;
 Node s, t;
 LengthMap length(g);

 readDimacs(std::cin, g, length, s, t);

 cout << "edges with lengths (of form id, sourcelength>target): " << endl;
 for(EdgeIt e(g); e!=INVALID; ++e)
 cout << g.id(e) << ", " << g.id(g.source(e)) << ""
 << length[e] << ">" << g.id(g.target(e)) << endl;

 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
 \endcode
 Next, the potential function is computed with Dijkstra.
 \code
 typedef Dijkstra Dijkstra;
 Dijkstra dijkstra(g, length);
 dijkstra.run(s);
 \endcode
 Next, we consrtruct a map which filters the edgeset to the tight edges.
 \code
 typedef TightEdgeFilterMap
 TightEdgeFilter;
 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);

 typedef EdgeSubGraphAdaptor SubGW;
 SubGW gw(g, tight_edge_filter);
 \endcode
 Then, the maximum nimber of edgedisjoint \c s\c t paths are computed
 with a max flow algorithm Preflow.
 \code
 ConstMap const_1_map(1);
 Graph::EdgeMap flow(g, 0);

 Preflow, Graph::EdgeMap >
 preflow(gw, s, t, const_1_map, flow);
 preflow.run();
 \endcode
 Last, the output is:
 \code
 cout << "maximum number of edgedisjoint shortest path: "
 << preflow.flowValue() << endl;
 cout << "edges of the maximum number of edgedisjoint shortest st paths: "
 << endl;
 for(EdgeIt e(g); e!=INVALID; ++e)
 if (flow[e])
 cout << " " << g.id(g.source(e)) << ""
 << length[e] << ">" << g.id(g.target(e)) << endl;
 \endcode
 The program has the following (expected :)) output:
 \code
 edges with lengths (of form id, sourcelength>target):
 9, 54>6
 8, 42>6
 7, 31>5
 6, 23>5
 5, 25>6
 4, 22>4
 3, 13>4
 2, 01>3
 1, 02>2
 0, 03>1
 s: 0 t: 6
 maximum number of edgedisjoint shortest path: 2
 edges of the maximum number of edgedisjoint shortest st paths:
 9, 54>6
 8, 42>6
 7, 31>5
 4, 22>4
 2, 01>3
 1, 02>2
 \endcode

 \author Marton Makai
 */
+ //x\brief An adaptor for hiding edges from a graph.
+ //x
+ //x\warning Graph adaptors are in even more experimental state
+ //xthan the other parts of the lib. Use them at you own risk.
+ //x
+ //xAn adaptor for hiding edges from a graph.
+ //xThis adaptor specializes SubGraphAdaptor in the way that
+ //xonly the edgeset
+ //xcan be filtered. The usefulness of this adaptor is demonstrated in the
+ //xproblem of searching a maximum number of edgedisjoint shortest paths
+ //xbetween
+ //xtwo nodes \c s and \c t. Shortest here means being shortest w.r.t.
+ //xnonnegative edgelengths. Note that
+ //xthe comprehension of the presented solution
+ //xneed's some elementary knowledge from combinatorial optimization.
+ //x
+ //xIf a single shortest path is to be
+ //xsearched between \c s and \c t, then this can be done easily by
+ //xapplying the Dijkstra algorithm. What happens, if a maximum number of
+ //xedgedisjoint shortest paths is to be computed. It can be proved that an
+ //xedge can be in a shortest path if and only
+ //xif it is tight with respect to
+ //xthe potential function computed by Dijkstra.
+ //xMoreover, any path containing
+ //xonly such edges is a shortest one.
+ //xThus we have to compute a maximum number
+ //xof edgedisjoint paths between \c s and \c t in
+ //xthe graph which has edgeset
+ //xall the tight edges. The computation will be demonstrated
+ //xon the following
+ //xgraph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
+ //xThe full source code is available in \ref sub_graph_adaptor_demo.cc.
+ //xIf you are interested in more demo programs, you can use
+ //x\ref dim_to_dot.cc to generate .dot files from dimacs files.
+ //xThe .dot file of the following figure was generated by
+ //xthe demo program \ref dim_to_dot.cc.
+ //x
+ //x\dot
+ //xdigraph lemon_dot_example {
+ //xnode [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
+ //xn0 [ label="0 (s)" ];
+ //xn1 [ label="1" ];
+ //xn2 [ label="2" ];
+ //xn3 [ label="3" ];
+ //xn4 [ label="4" ];
+ //xn5 [ label="5" ];
+ //xn6 [ label="6 (t)" ];
+ //xedge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
+ //xn5 > n6 [ label="9, length:4" ];
+ //xn4 > n6 [ label="8, length:2" ];
+ //xn3 > n5 [ label="7, length:1" ];
+ //xn2 > n5 [ label="6, length:3" ];
+ //xn2 > n6 [ label="5, length:5" ];
+ //xn2 > n4 [ label="4, length:2" ];
+ //xn1 > n4 [ label="3, length:3" ];
+ //xn0 > n3 [ label="2, length:1" ];
+ //xn0 > n2 [ label="1, length:2" ];
+ //xn0 > n1 [ label="0, length:3" ];
+ //x}
+ //x\enddot
+ //x
+ //x\code
+ //xGraph g;
+ //xNode s, t;
+ //xLengthMap length(g);
+ //x
+ //xreadDimacs(std::cin, g, length, s, t);
+ //x
+ //xcout << "edges with lengths (of form id, sourcelength>target): " << endl;
+ //xfor(EdgeIt e(g); e!=INVALID; ++e)
+ //x cout << g.id(e) << ", " << g.id(g.source(e)) << ""
+ //x << length[e] << ">" << g.id(g.target(e)) << endl;
+ //x
+ //xcout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
+ //x\endcode
+ //xNext, the potential function is computed with Dijkstra.
+ //x\code
+ //xtypedef Dijkstra Dijkstra;
+ //xDijkstra dijkstra(g, length);
+ //xdijkstra.run(s);
+ //x\endcode
+ //xNext, we consrtruct a map which filters the edgeset to the tight edges.
+ //x\code
+ //xtypedef TightEdgeFilterMap
+ //x TightEdgeFilter;
+ //xTightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
+ //x
+ //xtypedef EdgeSubGraphAdaptor SubGW;
+ //xSubGW gw(g, tight_edge_filter);
+ //x\endcode
+ //xThen, the maximum nimber of edgedisjoint \c s\c t paths are computed
+ //xwith a max flow algorithm Preflow.
+ //x\code
+ //xConstMap const_1_map(1);
+ //xGraph::EdgeMap flow(g, 0);
+ //x
+ //xPreflow, Graph::EdgeMap >
+ //x preflow(gw, s, t, const_1_map, flow);
+ //xpreflow.run();
+ //x\endcode
+ //xLast, the output is:
+ //x\code
+ //xcout << "maximum number of edgedisjoint shortest path: "
+ //x << preflow.flowValue() << endl;
+ //xcout << "edges of the maximum number of edgedisjoint shortest st paths: "
+ //x << endl;
+ //xfor(EdgeIt e(g); e!=INVALID; ++e)
+ //x if (flow[e])
+ //x cout << " " << g.id(g.source(e)) << ""
+ //x << length[e] << ">" << g.id(g.target(e)) << endl;
+ //x\endcode
+ //xThe program has the following (expected :)) output:
+ //x\code
+ //xedges with lengths (of form id, sourcelength>target):
+ //x 9, 54>6
+ //x 8, 42>6
+ //x 7, 31>5
+ //x 6, 23>5
+ //x 5, 25>6
+ //x 4, 22>4
+ //x 3, 13>4
+ //x 2, 01>3
+ //x 1, 02>2
+ //x 0, 03>1
+ //xs: 0 t: 6
+ //xmaximum number of edgedisjoint shortest path: 2
+ //xedges of the maximum number of edgedisjoint shortest st paths:
+ //x 9, 54>6
+ //x 8, 42>6
+ //x 7, 31>5
+ //x 4, 22>4
+ //x 2, 01>3
+ //x 1, 02>2
+ //x\endcode
+ //x
+ //x\author Marton Makai
template
class EdgeSubGraphAdaptor :
@@ 741,10 +770,11 @@
};
 /// \brief An undirected graph is made from a directed graph by an adaptor
 ///
 /// Undocumented, untested!!!
 /// If somebody knows nice demo application, let's polulate it.
 ///
 /// \author Marton Makai
+ //x\brief An undirected graph is made from a directed graph by an adaptor
+ //x\ingroup graph_adaptors
+ //x
+ //x Undocumented, untested!!!
+ //x If somebody knows nice demo application, let's polulate it.
+ //x
+ //x \author Marton Makai
template
class UGraphAdaptor :
@@ 794,8 +824,8 @@
typedef typename _Graph::Edge GraphEdge;
template class EdgeMap;
 /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
 /// _Graph::Edge. It contains an extra bool flag which is true
 /// if and only if the
 /// edge is the backward version of the original edge.
+ // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
+ // _Graph::Edge. It contains an extra bool flag which is true
+ // if and only if the
+ // edge is the backward version of the original edge.
class Edge : public _Graph::Edge {
friend class SubBidirGraphAdaptorBase<
@@ 806,7 +836,7 @@
public:
Edge() { }
 /// \todo =false is needed, or causes problems?
 /// If \c _backward is false, then we get an edge corresponding to the
 /// original one, otherwise its oppositely directed pair is obtained.
+ // \todo =false is needed, or causes problems?
+ // If \c _backward is false, then we get an edge corresponding to the
+ // original one, otherwise its oppositely directed pair is obtained.
Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
_Graph::Edge(e), backward(_backward) { }
@@ 932,5 +962,8 @@
return ((!e.backward) ? this>graph>target(e) : this>graph>source(e)); }
 /// Gives back the opposite edge.
+ //x Gives back the opposite edge.
+
+ //x\e
+ //x
Edge opposite(const Edge& e) const {
Edge f=e;
@@ 939,7 +972,9 @@
}
 /// \warning This is a linear time operation and works only if
 /// \c Graph::EdgeIt is defined.
 /// \todo hmm
+ //x\e
+
+ //x \warning This is a linear time operation and works only if
+ //x \c Graph::EdgeIt is defined.
+ //x \todo hmm
int edgeNum() const {
int i=0;
@@ 952,8 +987,10 @@
bool backward(const Edge& e) const { return e.backward; }
+ //x\e
+
+ //x \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
+ //x _Graph::EdgeMap one for the forward edges and
+ //x one for the backward edges.
template
 /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
 /// _Graph::EdgeMap one for the forward edges and
 /// one for the backward edges.
class EdgeMap {
template friend class EdgeMap;
@@ 1003,42 +1040,44 @@
 ///\brief An adaptor for composing a subgraph of a
 /// bidirected graph made from a directed one.
 ///
 /// An adaptor for composing a subgraph of a
 /// bidirected graph made from a directed one.
 ///
 ///\warning Graph adaptors are in even more experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
 /// reversing its orientation. We are given moreover two bool valued
 /// maps on the edgeset,
 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
 /// SubBidirGraphAdaptor implements the graph structure with nodeset
 /// \f$V\f$ and edgeset
 /// \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$.
 /// The purpose of writing + instead of union is because parallel
 /// edges can arise. (Similarly, antiparallel edges also can arise).
 /// In other words, a subgraph of the bidirected graph obtained, which
 /// is given by orienting the edges of the original graph in both directions.
 /// As the oppositely directed edges are logically different,
 /// the maps are able to attach different values for them.
 ///
 /// An example for such a construction is \c RevGraphAdaptor where the
 /// forward_filter is everywhere false and the backward_filter is
 /// everywhere true. We note that for sake of efficiency,
 /// \c RevGraphAdaptor is implemented in a different way.
 /// But BidirGraphAdaptor is obtained from
 /// SubBidirGraphAdaptor by considering everywhere true
 /// valued maps both for forward_filter and backward_filter.
 ///
 /// The most important application of SubBidirGraphAdaptor
 /// is ResGraphAdaptor, which stands for the residual graph in directed
 /// flow and circulation problems.
 /// As adaptors usually, the SubBidirGraphAdaptor implements the
 /// above mentioned graph structure without its physical storage,
 /// that is the whole stuff is stored in constant memory.
+ //x\brief An adaptor for composing a subgraph of a
+ //x bidirected graph made from a directed one.
+ //x\ingroup graph_adaptors
+ //x
+ //x An adaptor for composing a subgraph of a
+ //x bidirected graph made from a directed one.
+ //x
+ //x\warning Graph adaptors are in even more experimental state
+ //xthan the other
+ //xparts of the lib. Use them at you own risk.
+ //x
+ //x Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
+ //x \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
+ //x reversing its orientation. We are given moreover two bool valued
+ //x maps on the edgeset,
+ //x \f$forward\_filter\f$, and \f$backward\_filter\f$.
+ //x SubBidirGraphAdaptor implements the graph structure with nodeset
+ //x \f$V\f$ and edgeset
+ //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$.
+ //x The purpose of writing + instead of union is because parallel
+ //x edges can arise. (Similarly, antiparallel edges also can arise).
+ //x In other words, a subgraph of the bidirected graph obtained, which
+ //x is given by orienting the edges of the original graph in both directions.
+ //x As the oppositely directed edges are logically different,
+ //x the maps are able to attach different values for them.
+ //x
+ //x An example for such a construction is \c RevGraphAdaptor where the
+ //x forward_filter is everywhere false and the backward_filter is
+ //x everywhere true. We note that for sake of efficiency,
+ //x \c RevGraphAdaptor is implemented in a different way.
+ //x But BidirGraphAdaptor is obtained from
+ //x SubBidirGraphAdaptor by considering everywhere true
+ //x valued maps both for forward_filter and backward_filter.
+ //x
+ //x The most important application of SubBidirGraphAdaptor
+ //x is ResGraphAdaptor, which stands for the residual graph in directed
+ //x flow and circulation problems.
+ //x As adaptors usually, the SubBidirGraphAdaptor implements the
+ //x above mentioned graph structure without its physical storage,
+ //x that is the whole stuff is stored in constant memory.
template
@@ 1064,13 +1103,15 @@
 ///\brief An adaptor for composing bidirected graph from a directed one.
 ///
 ///\warning Graph adaptors are in even more experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
 /// An adaptor for composing bidirected graph from a directed one.
 /// A bidirected graph is composed over the directed one without physical
 /// storage. As the oppositely directed edges are logically different ones
 /// the maps are able to attach different values for them.
+ //x\brief An adaptor for composing bidirected graph from a directed one.
+ //x\ingroup graph_adaptors
+ //x
+ //x\warning Graph adaptors are in even more experimental state
+ //xthan the other
+ //xparts of the lib. Use them at you own risk.
+ //x
+ //x An adaptor for composing bidirected graph from a directed one.
+ //x A bidirected graph is composed over the directed one without physical
+ //x storage. As the oppositely directed edges are logically different ones
+ //x the maps are able to attach different values for them.
template
class BidirGraphAdaptor :
@@ 1140,36 +1181,39 @@
 /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.

 An adaptor for composing the residual graph for directed flow and circulation problems.
 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
 number type. Let moreover
 \f$f,c:A\to F\f$, be functions on the edgeset.
 In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
 and \f$c\f$ for a capacity function.
 Suppose that a graph instange \c g of type
 \c ListGraph implements \f$G\f$.
 \code
 ListGraph g;
 \endcode
 Then RevGraphAdaptor implements the graph structure with nodeset
 \f$V\f$ and edgeset \f$A_{forward}\cup A_{backward}\f$, where
 \f$A_{forward}=\{uv : uv\in A, f(uv)0\}\f$,
 i.e. the so called residual graph.
 When we take the union \f$A_{forward}\cup A_{backward}\f$,
 multilicities are counted, i.e. if an edge is in both
 \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
 appears twice.
 The following code shows how
 such an instance can be constructed.
 \code
 typedef ListGraph Graph;
 Graph::EdgeMap f(g);
 Graph::EdgeMap c(g);
 ResGraphAdaptor, Graph::EdgeMap > gw(g);
 \endcode
 \author Marton Makai
 */
+ //x\brief An adaptor for composing the residual
+ //xgraph for directed flow and circulation problems.
+ //x\ingroup graph_adaptors
+ //x
+ //xAn adaptor for composing the residual graph for
+ //xdirected flow and circulation problems.
+ //xLet \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
+ //xnumber type. Let moreover
+ //x\f$f,c:A\to F\f$, be functions on the edgeset.
+ //xIn the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
+ //xand \f$c\f$ for a capacity function.
+ //xSuppose that a graph instange \c g of type
+ //x\c ListGraph implements \f$G\f$ .
+ //x\code
+ //x ListGraph g;
+ //x\endcode
+ //xThen RevGraphAdaptor implements the graph structure with nodeset
+ //x\f$V\f$ and edgeset \f$A_{forward}\cup A_{backward}\f$, where
+ //x\f$A_{forward}=\{uv : uv\in A, f(uv)0\}\f$,
+ //xi.e. the so called residual graph.
+ //xWhen we take the union \f$A_{forward}\cup A_{backward}\f$,
+ //xmultilicities are counted, i.e. if an edge is in both
+ //x\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
+ //xappears twice.
+ //xThe following code shows how
+ //xsuch an instance can be constructed.
+ //x\code
+ //xtypedef ListGraph Graph;
+ //xGraph::EdgeMap f(g);
+ //xGraph::EdgeMap c(g);
+ //xResGraphAdaptor, Graph::EdgeMap > gw(g);
+ //x\endcode
+ //x\author Marton Makai
+ //x
template
@@ 1221,8 +1265,8 @@
}
 /// \brief Residual capacity map.
 ///
 /// In generic residual graphs the residual capacity can be obtained
 /// as a map.
+ //x \brief Residual capacity map.
+ //x
+ //x In generic residual graphs the residual capacity can be obtained
+ //x as a map.
class ResCap {
protected:
@@ 1278,18 +1322,21 @@
 /// For blocking flows.

 ///\warning Graph adaptors are in even more
 ///experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
 ///This graph adaptor is used for onthefly
 ///Dinits blocking flow computations.
 ///For each node, an outedge is stored which is used when the
 ///\code OutEdgeIt& first(OutEdgeIt&, const Node&)\endcode
 ///is called.
 ///
 ///\author Marton Makai
 ///
+ //x\brief For blocking flows.
+ //x\ingroup graph_adaptors
+ //x
+ //x\warning Graph adaptors are in even more
+ //xexperimental state than the other
+ //xparts of the lib. Use them at you own risk.
+ //x
+ //xThis graph adaptor is used for onthefly
+ //xDinits blocking flow computations.
+ //xFor each node, an outedge is stored which is used when the
+ //x\code
+ //xOutEdgeIt& first(OutEdgeIt&, const Node&)
+ //x\endcode
+ //xis called.
+ //x
+ //x\author Marton Makai
+ //x
template
class ErasingFirstGraphAdaptor :
@@ 1348,5 +1395,5 @@
};
 /// \todo May we want VARIANT/union type
+ //x \todo May we want VARIANT/union type
class Edge : public Parent::Edge {
friend class SplitGraphAdaptorBase;
@@ 1675,6 +1722,4 @@
};
 ///@}

} //namespace lemon