Context Navigation

← Previous Changeset
Next Changeset →

Changeset 1951:cb7a6e0573bc in lemon-0.x

Timestamp:

02/03/06 15:07:52 (18 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2526

Message:

graph_adaptor.h: probably a doxygen bug: in tex formulas there should be

whitespace after the opening and before the closing \f$

File:

: 1 edited

lemon/graph_adaptor.h (modified) (16 diffs)

Legend:

: Unmodified
: Added
: Removed

lemon/graph_adaptor.h

-                      r1949
+                      r1951
 namespace lemon {
   //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
+  ///\brief Base type for the Graph Adaptors
+  ///\ingroup 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
   template<typename _Graph>
   class GraphAdaptorBase {
 …
+    }
     //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 node-map.
+    ///\e
+    /// 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 node-map.
     void hide(const Node& n) const { node_filter_map->set(n, false); }
     //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 edge-map.
+    ///\e
+    /// 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 edge-map.
     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
     //x\e
     //x The value of \c n is set to be true in the node-map which stores
     //x hide information. If \c n was hidden previuosly, then it is shown
     //x again
+    ///\e
+    /// The value of \c n is set to be true in the node-map which stores
+    /// hide information. If \c n was hidden previuosly, then it is shown
+    /// again
      void unHide(const Node& n) const { node_filter_map->set(n, true); }
     //x\e
     //x The value of \c e is set to be true in the edge-map which stores
     //x hide information. If \c e was hidden previuosly, then it is shown
     //x again
+    ///\e
+    /// The value of \c e is set to be true in the edge-map which stores
+    /// hide information. If \c e was hidden previuosly, then it is shown
+    /// again
     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
     //x Returns true if \c n is hidden.
+    /// Returns true if \c n is hidden.
     //x\e
     //x
+    ///\e
+    ///
     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
     //x Returns true if \c n is hidden.
+    /// Returns true if \c n is hidden.
     //x\e
     //x
+    ///\e
+    ///
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
 …
+    }
     //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 node-map.
+    ///\e
+    /// 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 node-map.
     void hide(const Node& n) const { node_filter_map->set(n, false); }
     //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 edge-map.
+    ///\e
+    /// 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 edge-map.
     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
     //x\e
     //x The value of \c n is set to be true in the node-map which stores
     //x hide information. If \c n was hidden previuosly, then it is shown
     //x again
+    ///\e
+    /// The value of \c n is set to be true in the node-map which stores
+    /// hide information. If \c n was hidden previuosly, then it is shown
+    /// again
      void unHide(const Node& n) const { node_filter_map->set(n, true); }
     //x\e
     //x The value of \c e is set to be true in the edge-map which stores
     //x hide information. If \c e was hidden previuosly, then it is shown
     //x again
+    ///\e
+    /// The value of \c e is set to be true in the edge-map which stores
+    /// hide information. If \c e was hidden previuosly, then it is shown
+    /// again
     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
     //x Returns true if \c n is hidden.
+    /// Returns true if \c n is hidden.
     //x\e
     //x
+    ///\e
+    ///
     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
     //x Returns true if \c n is hidden.
+    /// Returns true if \c n is hidden.
     //x\e
     //x
+    ///\e
+    ///
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
 …
   };
+  //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 node-set and
+  //xedge-set. 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 bool-valued functions resp. on the node-set and edge-set.
+  //xSubGraphAdaptor<...>::NodeIt iterates
+  //xon the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
+  //xSubGraphAdaptor<...>::EdgeIt iterates
+  //xon the edge-set \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 node-iterator cares only the filter on the node-set, and the
+  //xedge-iterator cares only the filter on the edge-set.
+  //xThis way the edge-map
+  //xshould filter all edges which's source or target is filtered by the
+  //xnode-filter.
+  //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<bool> nm(g, true);
+  //xnm.set(u, false);
+  //xGraph::EdgeMap<bool> em(g, true);
+  //xem.set(e, false);
+  //xtypedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > 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
+  /// \brief A graph adaptor for hiding nodes and edges from a graph.
+  /// \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.
+  ///
+  /// SubGraphAdaptor shows the graph with filtered node-set and
+  /// edge-set. 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 bool-valued functions resp.
+  /// on the node-set and edge-set.
+  /// SubGraphAdaptor<...>::NodeIt iterates
+  /// on the node-set  \f$ \{v\in V : b_V(v)=true\} \f$  and
+  /// SubGraphAdaptor<...>::EdgeIt iterates
+  /// on the edge-set  \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 node-iterator cares only the filter on the node-set, and the
+  /// edge-iterator cares only the filter on the edge-set.
+  /// This way the edge-map
+  /// should filter all edges which's source or target is filtered by the
+  /// node-filter.
+  /// \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<bool> nm(g, true);
+  /// nm.set(u, false);
+  /// Graph::EdgeMap<bool> em(g, true);
+  /// em.set(e, false);
+  /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > 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
   template<typename _Graph, typename NodeFilterMap,
 …
   //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 node-set
   //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
+  ///\brief An adaptor for hiding nodes from a graph.
+  ///\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.
+  ///
+  ///An adaptor for hiding nodes from a graph.
+  ///This adaptor specializes SubGraphAdaptor in the way that only
+  ///the node-set
+  ///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
   template<typename Graph, typename NodeFilterMap, bool checked = true>
   class NodeSubGraphAdaptor :
 …
   //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 edge-set
   //xcan be filtered. The usefulness of this adaptor is demonstrated in the
   //xproblem of searching a maximum number of edge-disjoint shortest paths
   //xbetween
   //xtwo nodes \c s and \c t. Shortest here means being shortest w.r.t.
   //xnon-negative edge-lengths. 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
   //xedge-disjoint 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 edge-disjoint paths between \c s and \c t in
   //xthe graph which has edge-set
   //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, source--length->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<Graph, LengthMap> Dijkstra;
   //xDijkstra dijkstra(g, length);
   //xdijkstra.run(s);
   //x\endcode
   //xNext, we consrtruct a map which filters the edge-set to the tight edges.
   //x\code
   //xtypedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
   //x  TightEdgeFilter;
   //xTightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
   //x
   //xtypedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
   //xSubGW gw(g, tight_edge_filter);
   //x\endcode
   //xThen, the maximum nimber of edge-disjoint \c s-\c t paths are computed
   //xwith a max flow algorithm Preflow.
   //x\code
   //xConstMap<Edge, int> const_1_map(1);
   //xGraph::EdgeMap<int> flow(g, 0);
   //x
   //xPreflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
   //x  preflow(gw, s, t, const_1_map, flow);
   //xpreflow.run();
   //x\endcode
   //xLast, the output is:
   //x\code
   //xcout << "maximum number of edge-disjoint shortest path: "
   //x     << preflow.flowValue() << endl;
   //xcout << "edges of the maximum number of edge-disjoint shortest s-t 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, source--length->target):
   //x 9, 5--4->6
   //x 8, 4--2->6
   //x 7, 3--1->5
   //x 6, 2--3->5
   //x 5, 2--5->6
   //x 4, 2--2->4
   //x 3, 1--3->4
   //x 2, 0--1->3
   //x 1, 0--2->2
   //x 0, 0--3->1
   //xs: 0 t: 6
   //xmaximum number of edge-disjoint shortest path: 2
   //xedges of the maximum number of edge-disjoint shortest s-t paths:
   //x 9, 5--4->6
   //x 8, 4--2->6
   //x 7, 3--1->5
   //x 4, 2--2->4
   //x 2, 0--1->3
   //x 1, 0--2->2
   //x\endcode
   //x
   //x\author Marton Makai
+  ///\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 edge-set
+  ///can be filtered. The usefulness of this adaptor is demonstrated in the
+  ///problem of searching a maximum number of edge-disjoint shortest paths
+  ///between
+  ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
+  ///non-negative edge-lengths. 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
+  ///edge-disjoint 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 edge-disjoint paths between \c s and \c t in
+  ///the graph which has edge-set
+  ///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, source--length->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<Graph, LengthMap> Dijkstra;
+  ///Dijkstra dijkstra(g, length);
+  ///dijkstra.run(s);
+  ///\endcode
+  ///Next, we consrtruct a map which filters the edge-set to the tight edges.
+  ///\code
+  ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
+  ///  TightEdgeFilter;
+  ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
+  ///
+  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
+  ///SubGW gw(g, tight_edge_filter);
+  ///\endcode
+  ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
+  ///with a max flow algorithm Preflow.
+  ///\code
+  ///ConstMap<Edge, int> const_1_map(1);
+  ///Graph::EdgeMap<int> flow(g, 0);
+  ///
+  ///Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
+  ///  preflow(gw, s, t, const_1_map, flow);
+  ///preflow.run();
+  ///\endcode
+  ///Last, the output is:
+  ///\code
+  ///cout << "maximum number of edge-disjoint shortest path: "
+  ///     << preflow.flowValue() << endl;
+  ///cout << "edges of the maximum number of edge-disjoint shortest s-t 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, source--length->target):
+  /// 9, 5--4->6
+  /// 8, 4--2->6
+  /// 7, 3--1->5
+  /// 6, 2--3->5
+  /// 5, 2--5->6
+  /// 4, 2--2->4
+  /// 3, 1--3->4
+  /// 2, 0--1->3
+  /// 1, 0--2->2
+  /// 0, 0--3->1
+  ///s: 0 t: 6
+  ///maximum number of edge-disjoint shortest path: 2
+  ///edges of the maximum number of edge-disjoint shortest s-t paths:
+  /// 9, 5--4->6
+  /// 8, 4--2->6
+  /// 7, 3--1->5
+  /// 4, 2--2->4
+  /// 2, 0--1->3
+  /// 1, 0--2->2
+  ///\endcode
+  ///
+  ///\author Marton Makai
   template<typename Graph, typename EdgeFilterMap>
   class EdgeSubGraphAdaptor :
 …
   };
   //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
+  ///\brief An undirected graph is made from a directed graph by an adaptor
+  ///\ingroup graph_adaptors
+  ///
+  /// Undocumented, untested!!!
+  /// If somebody knows nice demo application, let's polulate it.
+  ///
+  /// \author Marton Makai
   template<typename _Graph>
   class UGraphAdaptor :
 …
       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
     //x Gives back the opposite edge.
     //x\e
     //x
+    /// Gives back the opposite edge.
+    ///\e
+    ///
     Edge opposite(const Edge& e) const {
       Edge f=e;
 …
+    }
     //x\e
     //x \warning This is a linear time operation and works only if
     //x \c Graph::EdgeIt is defined.
     //x \todo hmm
+    ///\e
+    /// \warning This is a linear time operation and works only if
+    /// \c Graph::EdgeIt is defined.
+    /// \todo hmm
     int edgeNum() const {
       int i=0;
 …
     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.
+    ///\e
+    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
+    /// _Graph::EdgeMap one for the forward edges and
+    /// one for the backward edges.
     template <typename T>
     class EdgeMap {
 …
   //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 edge-set,
   //x \f$forward\_filter\f$, and \f$backward\_filter\f$.
   //x SubBidirGraphAdaptor implements the graph structure with node-set
   //x \f$V\f$ and edge-set
   //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.
+  ///\brief An adaptor for composing a subgraph of a
+  /// bidirected graph made from a directed one.
+  ///\ingroup graph_adaptors
+  ///
+  /// 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 edge-set,
+  ///  \f$  forward\_filter  \f$ , and  \f$  backward\_filter  \f$ .
+  /// SubBidirGraphAdaptor implements the graph structure with node-set
+  ///  \f$  V  \f$  and edge-set
+  ///  \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.
   template<typename _Graph,
            typename ForwardFilterMap, typename BackwardFilterMap>
 …
   //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.
+  ///\brief An adaptor for composing bidirected graph from a directed one.
+  ///\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.
+  ///
+  /// 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.
   template<typename Graph>
   class BidirGraphAdaptor :
 …
   //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 edge-set.
   //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 node-set
   //x\f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
   //x\f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
   //x\f$A_{backward}=\{vu : 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<int> f(g);
   //xGraph::EdgeMap<int> c(g);
   //xResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
   //x\endcode
   //x\author Marton Makai
   //x
+  ///\brief An adaptor for composing the residual
+  ///graph for directed flow and circulation problems.
+  ///\ingroup graph_adaptors
+  ///
+  ///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 edge-set.
+  ///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 node-set
+  /// \f$ V \f$  and edge-set  \f$ A_{forward}\cup A_{backward} \f$ , where
+  /// \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$  and
+  /// \f$ A_{backward}=\{vu : 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<int> f(g);
+  ///Graph::EdgeMap<int> c(g);
+  ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
+  ///\endcode
+  ///\author Marton Makai
+  ///
   template<typename Graph, typename Number,
            typename CapacityMap, typename FlowMap>
 …
+    }
     //x \brief Residual capacity map.
     //x
     //x In generic residual graphs the residual capacity can be obtained
     //x as a map.
+    /// \brief Residual capacity map.
+    ///
+    /// In generic residual graphs the residual capacity can be obtained
+    /// as a map.
     class ResCap {
     protected:
 …
   //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 on-the-fly
   //xDinits blocking flow computations.
   //xFor each node, an out-edge is stored which is used when the
   //x\code
   //xOutEdgeIt& first(OutEdgeIt&, const Node&)
   //x\endcode
   //xis called.
   //x
   //x\author Marton Makai
   //x
+  ///\brief For blocking flows.
+  ///\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.
+  ///
+  ///This graph adaptor is used for on-the-fly
+  ///Dinits blocking flow computations.
+  ///For each node, an out-edge is stored which is used when the
+  ///\code
+  ///OutEdgeIt& first(OutEdgeIt&, const Node&)
+  ///\endcode
+  ///is called.
+  ///
+  ///\author Marton Makai
+  ///
   template <typename _Graph, typename FirstOutEdgesMap>
   class ErasingFirstGraphAdaptor :
 …
     };
     //x \todo May we want VARIANT/union type
+    /// \todo May we want VARIANT/union type
     class Edge : public Parent::Edge {
       friend class SplitGraphAdaptorBase;

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 1951:cb7a6e0573bc in lemon-0.x

Legend:

lemon/graph_adaptor.h

Download in other formats: