COIN-OR::LEMON - Graph Library

Changeset 474:fbd6e04acf44 in lemon


Ignore:
Timestamp:
01/09/09 12:54:27 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Various doc improvements for graph adaptors (#67)

  • Add notes about modifying the adapted graphs through adaptors if it is possible.
  • Add notes about the possible conversions between the Node, Arc and Edge types of the adapted graphs and the adaptors.
  • Hide the default values for template parameters (describe them in the doc instead).
  • More precise docs for template parameters.
  • More precise docs for member functions.
  • Add docs for important public typedefs.
  • Unify the docs of the adaptors.
  • Add \relates commands for the creator functions.
  • Fixes and improvements the module documentation.
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r434 r474  
    6363
    6464/**
    65 @defgroup graph_adaptors Adaptor Classes for graphs
     65@defgroup graph_adaptors Adaptor Classes for Graphs
    6666@ingroup graphs
    67 \brief This group contains several adaptor classes for digraphs and graphs
     67\brief Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
    6870
    6971The main parts of LEMON are the different graph structures, generic
    70 graph algorithms, graph concepts which couple these, and graph
     72graph algorithms, graph concepts, which couple them, and graph
    7173adaptors. While the previous notions are more or less clear, the
    7274latter one needs further explanation. Graph adaptors are graph classes
     
    7476
    7577A short example makes this much clearer.  Suppose that we have an
    76 instance \c g of a directed graph type say ListDigraph and an algorithm
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
    7779\code
    7880template <typename Digraph>
     
    8284(in time or in memory usage) to copy \c g with the reversed
    8385arcs.  In this case, an adaptor class is used, which (according
    84 to LEMON digraph concepts) works as a digraph.  The adaptor uses the
    85 original digraph structure and digraph operations when methods of the
    86 reversed oriented graph are called.  This means that the adaptor have
    87 minor memory usage, and do not perform sophisticated algorithmic
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
    8890actions.  The purpose of it is to give a tool for the cases when a
    8991graph have to be used in a specific alteration.  If this alteration is
    90 obtained by a usual construction like filtering the arc-set or
     92obtained by a usual construction like filtering the node or the arc set or
    9193considering a new orientation, then an adaptor is worthwhile to use.
    9294To come back to the reverse oriented graph, in this situation
     
    9799\code
    98100ListDigraph g;
    99 ReverseDigraph<ListGraph> rg(g);
     101ReverseDigraph<ListDigraph> rg(g);
    100102int result = algorithm(rg);
    101103\endcode
    102 After running the algorithm, the original graph \c g is untouched.
    103 This techniques gives rise to an elegant code, and based on stable
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
    104106graph adaptors, complex algorithms can be implemented easily.
    105107
    106 In flow, circulation and bipartite matching problems, the residual
     108In flow, circulation and matching problems, the residual
    107109graph is of particular importance. Combining an adaptor implementing
    108 this, shortest path algorithms and minimum mean cycle algorithms,
     110this with shortest path algorithms or minimum mean cycle algorithms,
    109111a range of weighted and cardinality optimization algorithms can be
    110112obtained. For other examples, the interested user is referred to the
     
    113115The behavior of graph adaptors can be very different. Some of them keep
    114116capabilities of the original graph while in other cases this would be
    115 meaningless. This means that the concepts that they are models of depend
    116 on the graph adaptor, and the wrapped graph(s).
    117 If an arc of \c rg is deleted, this is carried out by deleting the
    118 corresponding arc of \c g, thus the adaptor modifies the original graph.
    119 
    120 But for a residual graph, this operation has no sense.
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
    121124Let us stand one more example here to simplify your work.
    122 RevGraphAdaptor has constructor
     125ReverseDigraph has constructor
    123126\code
    124127ReverseDigraph(Digraph& digraph);
    125128\endcode
    126 This means that in a situation, when a <tt>const ListDigraph&</tt>
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
    127130reference to a graph is given, then it have to be instantiated with
    128 <tt>Digraph=const ListDigraph</tt>.
     131<tt>Digraph=const %ListDigraph</tt>.
    129132\code
    130133int algorithm1(const ListDigraph& g) {
    131   RevGraphAdaptor<const ListDigraph> rg(g);
     134  ReverseDigraph<const ListDigraph> rg(g);
    132135  return algorithm2(rg);
    133136}
  • lemon/adaptors.h

    r473 r474  
    2222/// \ingroup graph_adaptors
    2323/// \file
    24 /// \brief Several graph adaptors
     24/// \brief Adaptor classes for digraphs and graphs
    2525///
    2626/// This file contains several useful adaptors for digraphs and graphs.
     
    347347  /// \ingroup graph_adaptors
    348348  ///
    349   /// \brief A digraph adaptor which reverses the orientation of the arcs.
    350   ///
    351   /// ReverseDigraph reverses the arcs in the adapted digraph. The
    352   /// SubDigraph is conform to the \ref concepts::Digraph
    353   /// "Digraph concept".
    354   ///
    355   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
    356   /// "Digraph concept". The type can be specified to be const.
     349  /// \brief Adaptor class for reversing the orientation of the arcs in
     350  /// a digraph.
     351  ///
     352  /// ReverseDigraph can be used for reversing the arcs in a digraph.
     353  /// It conforms to the \ref concepts::Digraph "Digraph" concept.
     354  ///
     355  /// The adapted digraph can also be modified through this adaptor
     356  /// by adding or removing nodes or arcs, unless the \c _Digraph template
     357  /// parameter is set to be \c const.
     358  ///
     359  /// \tparam _Digraph The type of the adapted digraph.
     360  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     361  /// It can also be specified to be \c const.
     362  ///
     363  /// \note The \c Node and \c Arc types of this adaptor and the adapted
     364  /// digraph are convertible to each other.
    357365  template<typename _Digraph>
    358366  class ReverseDigraph :
     
    368376    /// \brief Constructor
    369377    ///
    370     /// Creates a reverse digraph adaptor for the given digraph
     378    /// Creates a reverse digraph adaptor for the given digraph.
    371379    explicit ReverseDigraph(Digraph& digraph) {
    372380      Parent::setDigraph(digraph);
     
    374382  };
    375383
    376   /// \brief Just gives back a reverse digraph adaptor
    377   ///
    378   /// Just gives back a reverse digraph adaptor
     384  /// \brief Returns a read-only ReverseDigraph adaptor
     385  ///
     386  /// This function just returns a read-only \ref ReverseDigraph adaptor.
     387  /// \ingroup graph_adaptors
     388  /// \relates ReverseDigraph
    379389  template<typename Digraph>
    380390  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
    381391    return ReverseDigraph<const Digraph>(digraph);
    382392  }
     393
    383394
    384395  template <typename _Digraph, typename _NodeFilterMap,
     
    686697  /// \ingroup graph_adaptors
    687698  ///
    688   /// \brief An adaptor for hiding nodes and arcs in a digraph
    689   ///
    690   /// SubDigraph hides nodes and arcs in a digraph. A bool node map
    691   /// and a bool arc map must be specified, which define the filters
    692   /// for nodes and arcs. Just the nodes and arcs with true value are
    693   /// shown in the subdigraph. The SubDigraph is conform to the \ref
    694   /// concepts::Digraph "Digraph concept". If the \c _checked parameter
    695   /// is true, then the arcs incident to filtered nodes are also
     699  /// \brief Adaptor class for hiding nodes and arcs in a digraph
     700  ///
     701  /// SubDigraph can be used for hiding nodes and arcs in a digraph.
     702  /// A \c bool node map and a \c bool arc map must be specified, which
     703  /// define the filters for nodes and arcs.
     704  /// Only the nodes and arcs with \c true filter value are
     705  /// shown in the subdigraph. This adaptor conforms to the \ref
     706  /// concepts::Digraph "Digraph" concept. If the \c _checked parameter
     707  /// is \c true, then the arcs incident to hidden nodes are also
    696708  /// filtered out.
    697709  ///
    698   /// \tparam _Digraph It must be conform to the \ref
    699   /// concepts::Digraph "Digraph concept". The type can be specified
    700   /// to const.
    701   /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
    702   /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
    703   /// \tparam _checked If the parameter is false then the arc filtering
    704   /// is not checked with respect to node filter. Otherwise, each arc
    705   /// is automatically filtered, which is incident to a filtered node.
     710  /// The adapted digraph can also be modified through this adaptor
     711  /// by adding or removing nodes or arcs, unless the \c _Digraph template
     712  /// parameter is set to be \c const.
     713  ///
     714  /// \tparam _Digraph The type of the adapted digraph.
     715  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     716  /// It can also be specified to be \c const.
     717  /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the
     718  /// adapted digraph. The default map type is
     719  /// \ref concepts::Digraph::NodeMap "_Digraph::NodeMap<bool>".
     720  /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the
     721  /// adapted digraph. The default map type is
     722  /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>".
     723  /// \tparam _checked If this parameter is set to \c false, then the arc
     724  /// filtering is not checked with respect to the node filter.
     725  /// Otherwise, each arc that is incident to a hidden node is automatically
     726  /// filtered out. This is the default option.
     727  ///
     728  /// \note The \c Node and \c Arc types of this adaptor and the adapted
     729  /// digraph are convertible to each other.
    706730  ///
    707731  /// \see FilterNodes
    708732  /// \see FilterArcs
     733#ifdef DOXYGEN
     734  template<typename _Digraph,
     735           typename _NodeFilterMap,
     736           typename _ArcFilterMap,
     737           bool _checked>
     738#else
    709739  template<typename _Digraph,
    710740           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
    711741           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
    712742           bool _checked = true>
     743#endif
    713744  class SubDigraph
    714745    : public DigraphAdaptorExtender<
    715746      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
    716747  public:
     748    /// The type of the adapted digraph.
    717749    typedef _Digraph Digraph;
     750    /// The type of the node filter map.
    718751    typedef _NodeFilterMap NodeFilterMap;
     752    /// The type of the arc filter map.
    719753    typedef _ArcFilterMap ArcFilterMap;
    720754
    721755    typedef DigraphAdaptorExtender<
    722       SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
     756      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> >
    723757    Parent;
    724758
     
    732766    /// \brief Constructor
    733767    ///
    734     /// Creates a subdigraph for the given digraph with
    735     /// given node and arc map filters.
     768    /// Creates a subdigraph for the given digraph with the
     769    /// given node and arc filter maps.
    736770    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
    737771               ArcFilterMap& arc_filter) {
     
    741775    }
    742776
    743     /// \brief Hides the node of the graph
    744     ///
    745     /// This function hides \c n in the digraph, i.e. the iteration
    746     /// jumps over it. This is done by simply setting the value of \c n
    747     /// to be false in the corresponding node-map.
     777    /// \brief Hides the given node
     778    ///
     779    /// This function hides the given node in the subdigraph,
     780    /// i.e. the iteration jumps over it.
     781    /// It is done by simply setting the assigned value of \c n
     782    /// to be \c false in the node filter map.
    748783    void hide(const Node& n) const { Parent::hide(n); }
    749784
    750     /// \brief Hides the arc of the graph
    751     ///
    752     /// This function hides \c a in the digraph, i.e. the iteration
    753     /// jumps over it. This is done by simply setting the value of \c a
    754     /// to be false in the corresponding arc-map.
     785    /// \brief Hides the given arc
     786    ///
     787    /// This function hides the given arc in the subdigraph,
     788    /// i.e. the iteration jumps over it.
     789    /// It is done by simply setting the assigned value of \c a
     790    /// to be \c false in the arc filter map.
    755791    void hide(const Arc& a) const { Parent::hide(a); }
    756792
    757     /// \brief Unhides the node of the graph
    758     ///
    759     /// The value of \c n is set to be true in the node-map which stores
    760     /// hide information. If \c n was hidden previuosly, then it is shown
    761     /// again
     793    /// \brief Shows the given node
     794    ///
     795    /// This function shows the given node in the subdigraph.
     796    /// It is done by simply setting the assigned value of \c n
     797    /// to be \c true in the node filter map.
    762798    void unHide(const Node& n) const { Parent::unHide(n); }
    763799
    764     /// \brief Unhides the arc of the graph
    765     ///
    766     /// The value of \c a is set to be true in the arc-map which stores
    767     /// hide information. If \c a was hidden previuosly, then it is shown
    768     /// again
     800    /// \brief Shows the given arc
     801    ///
     802    /// This function shows the given arc in the subdigraph.
     803    /// It is done by simply setting the assigned value of \c a
     804    /// to be \c true in the arc filter map.
    769805    void unHide(const Arc& a) const { Parent::unHide(a); }
    770806
    771     /// \brief Returns true if \c n is hidden.
    772     ///
    773     /// Returns true if \c n is hidden.
    774     ///
     807    /// \brief Returns \c true if the given node is hidden.
     808    ///
     809    /// This function returns \c true if the given node is hidden.
    775810    bool hidden(const Node& n) const { return Parent::hidden(n); }
    776811
    777     /// \brief Returns true if \c a is hidden.
    778     ///
    779     /// Returns true if \c a is hidden.
    780     ///
     812    /// \brief Returns \c true if the given arc is hidden.
     813    ///
     814    /// This function returns \c true if the given arc is hidden.
    781815    bool hidden(const Arc& a) const { return Parent::hidden(a); }
    782816
    783817  };
    784818
    785   /// \brief Just gives back a subdigraph
    786   ///
    787   /// Just gives back a subdigraph
     819  /// \brief Returns a read-only SubDigraph adaptor
     820  ///
     821  /// This function just returns a read-only \ref SubDigraph adaptor.
     822  /// \ingroup graph_adaptors
     823  /// \relates SubDigraph
    788824  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    789825  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
     
    12501286  /// \ingroup graph_adaptors
    12511287  ///
    1252   /// \brief A graph adaptor for hiding nodes and edges in an
    1253   /// undirected graph.
    1254   ///
    1255   /// SubGraph hides nodes and edges in a graph. A bool node map and a
    1256   /// bool edge map must be specified, which define the filters for
    1257   /// nodes and edges. Just the nodes and edges with true value are
    1258   /// shown in the subgraph. The SubGraph is conform to the \ref
    1259   /// concepts::Graph "Graph concept". If the \c _checked parameter is
    1260   /// true, then the edges incident to filtered nodes are also
     1288  /// \brief Adaptor class for hiding nodes and edges in an undirected
     1289  /// graph.
     1290  ///
     1291  /// SubGraph can be used for hiding nodes and edges in a graph.
     1292  /// A \c bool node map and a \c bool edge map must be specified, which
     1293  /// define the filters for nodes and edges.
     1294  /// Only the nodes and edges with \c true filter value are
     1295  /// shown in the subgraph. This adaptor conforms to the \ref
     1296  /// concepts::Graph "Graph" concept. If the \c _checked parameter is
     1297  /// \c true, then the edges incident to hidden nodes are also
    12611298  /// filtered out.
    12621299  ///
    1263   /// \tparam _Graph It must be conform to the \ref
    1264   /// concepts::Graph "Graph concept". The type can be specified
    1265   /// to const.
    1266   /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
    1267   /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
    1268   /// \tparam _checked If the parameter is false then the edge filtering
    1269   /// is not checked with respect to node filter. Otherwise, each edge
    1270   /// is automatically filtered, which is incident to a filtered node.
     1300  /// The adapted graph can also be modified through this adaptor
     1301  /// by adding or removing nodes or edges, unless the \c _Graph template
     1302  /// parameter is set to be \c const.
     1303  ///
     1304  /// \tparam _Graph The type of the adapted graph.
     1305  /// It must conform to the \ref concepts::Graph "Graph" concept.
     1306  /// It can also be specified to be \c const.
     1307  /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the
     1308  /// adapted graph. The default map type is
     1309  /// \ref concepts::Graph::NodeMap "_Graph::NodeMap<bool>".
     1310  /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the
     1311  /// adapted graph. The default map type is
     1312  /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>".
     1313  /// \tparam _checked If this parameter is set to \c false, then the edge
     1314  /// filtering is not checked with respect to the node filter.
     1315  /// Otherwise, each edge that is incident to a hidden node is automatically
     1316  /// filtered out. This is the default option.
     1317  ///
     1318  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
     1319  /// adapted graph are convertible to each other.
    12711320  ///
    12721321  /// \see FilterNodes
    12731322  /// \see FilterEdges
    1274   template<typename _Graph, typename NodeFilterMap,
    1275            typename EdgeFilterMap, bool _checked = true>
     1323#ifdef DOXYGEN
     1324  template<typename _Graph,
     1325           typename _NodeFilterMap,
     1326           typename _EdgeFilterMap,
     1327           bool _checked>
     1328#else
     1329  template<typename _Graph,
     1330           typename _NodeFilterMap = typename _Graph::template NodeMap<bool>,
     1331           typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool>,
     1332           bool _checked = true>
     1333#endif
    12761334  class SubGraph
    12771335    : public GraphAdaptorExtender<
    1278       SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
    1279   public:
     1336      SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > {
     1337  public:
     1338    /// The type of the adapted graph.
    12801339    typedef _Graph Graph;
     1340    /// The type of the node filter map.
     1341    typedef _NodeFilterMap NodeFilterMap;
     1342    /// The type of the edge filter map.
     1343    typedef _EdgeFilterMap EdgeFilterMap;
     1344
    12811345    typedef GraphAdaptorExtender<
    1282       SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
     1346      SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > Parent;
    12831347
    12841348    typedef typename Parent::Node Node;
     
    12911355    /// \brief Constructor
    12921356    ///
    1293     /// Creates a subgraph for the given graph with given node and
    1294     /// edge map filters.
    1295     SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
     1357    /// Creates a subgraph for the given graph with the given node
     1358    /// and edge filter maps.
     1359    SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
    12961360             EdgeFilterMap& edge_filter_map) {
    1297       setGraph(_graph);
     1361      setGraph(graph);
    12981362      setNodeFilterMap(node_filter_map);
    12991363      setEdgeFilterMap(edge_filter_map);
    13001364    }
    13011365
    1302     /// \brief Hides the node of the graph
    1303     ///
    1304     /// This function hides \c n in the graph, i.e. the iteration
    1305     /// jumps over it. This is done by simply setting the value of \c n
    1306     /// to be false in the corresponding node-map.
     1366    /// \brief Hides the given node
     1367    ///
     1368    /// This function hides the given node in the subgraph,
     1369    /// i.e. the iteration jumps over it.
     1370    /// It is done by simply setting the assigned value of \c n
     1371    /// to be \c false in the node filter map.
    13071372    void hide(const Node& n) const { Parent::hide(n); }
    13081373
    1309     /// \brief Hides the edge of the graph
    1310     ///
    1311     /// This function hides \c e in the graph, i.e. the iteration
    1312     /// jumps over it. This is done by simply setting the value of \c e
    1313     /// to be false in the corresponding edge-map.
     1374    /// \brief Hides the given edge
     1375    ///
     1376    /// This function hides the given edge in the subgraph,
     1377    /// i.e. the iteration jumps over it.
     1378    /// It is done by simply setting the assigned value of \c e
     1379    /// to be \c false in the edge filter map.
    13141380    void hide(const Edge& e) const { Parent::hide(e); }
    13151381
    1316     /// \brief Unhides the node of the graph
    1317     ///
    1318     /// The value of \c n is set to be true in the node-map which stores
    1319     /// hide information. If \c n was hidden previuosly, then it is shown
    1320     /// again
     1382    /// \brief Shows the given node
     1383    ///
     1384    /// This function shows the given node in the subgraph.
     1385    /// It is done by simply setting the assigned value of \c n
     1386    /// to be \c true in the node filter map.
    13211387    void unHide(const Node& n) const { Parent::unHide(n); }
    13221388
    1323     /// \brief Unhides the edge of the graph
    1324     ///
    1325     /// The value of \c e is set to be true in the edge-map which stores
    1326     /// hide information. If \c e was hidden previuosly, then it is shown
    1327     /// again
     1389    /// \brief Shows the given edge
     1390    ///
     1391    /// This function shows the given edge in the subgraph.
     1392    /// It is done by simply setting the assigned value of \c e
     1393    /// to be \c true in the edge filter map.
    13281394    void unHide(const Edge& e) const { Parent::unHide(e); }
    13291395
    1330     /// \brief Returns true if \c n is hidden.
    1331     ///
    1332     /// Returns true if \c n is hidden.
    1333     ///
     1396    /// \brief Returns \c true if the given node is hidden.
     1397    ///
     1398    /// This function returns \c true if the given node is hidden.
    13341399    bool hidden(const Node& n) const { return Parent::hidden(n); }
    13351400
    1336     /// \brief Returns true if \c e is hidden.
    1337     ///
    1338     /// Returns true if \c e is hidden.
    1339     ///
     1401    /// \brief Returns \c true if the given edge is hidden.
     1402    ///
     1403    /// This function returns \c true if the given edge is hidden.
    13401404    bool hidden(const Edge& e) const { return Parent::hidden(e); }
    13411405  };
    13421406
    1343   /// \brief Just gives back a subgraph
    1344   ///
    1345   /// Just gives back a subgraph
     1407  /// \brief Returns a read-only SubGraph adaptor
     1408  ///
     1409  /// This function just returns a read-only \ref SubGraph adaptor.
     1410  /// \ingroup graph_adaptors
     1411  /// \relates SubGraph
    13461412  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
    13471413  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
     
    13741440  }
    13751441
     1442
    13761443  /// \ingroup graph_adaptors
    13771444  ///
    1378   /// \brief An adaptor for hiding nodes from a digraph or a graph.
    1379   ///
    1380   /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
    1381   /// node map must be specified, which defines the filters for
    1382   /// nodes. Just the unfiltered nodes and the arcs or edges incident
    1383   /// to unfiltered nodes are shown in the subdigraph or subgraph. The
    1384   /// FilterNodes is conform to the \ref concepts::Digraph
    1385   /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
    1386   /// on the \c _Digraph template parameter. If the \c _checked
    1387   /// parameter is true, then the arc or edges incident to filtered nodes
    1388   /// are also filtered out.
    1389   ///
    1390   /// \tparam _Digraph It must be conform to the \ref
    1391   /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
    1392   /// "Graph concept". The type can be specified to be const.
    1393   /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
    1394   /// \tparam _checked If the parameter is false then the arc or edge
    1395   /// filtering is not checked with respect to node filter. In this
    1396   /// case just isolated nodes can be filtered out from the
    1397   /// graph.
     1445  /// \brief Adaptor class for hiding nodes in a digraph or a graph.
     1446  ///
     1447  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
     1448  /// graph. A \c bool node map must be specified, which defines the filter
     1449  /// for the nodes. Only the nodes with \c true filter value and the
     1450  /// arcs/edges incident to nodes both with \c true filter value are shown
     1451  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
     1452  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
     1453  /// depending on the \c _Graph template parameter.
     1454  ///
     1455  /// The adapted (di)graph can also be modified through this adaptor
     1456  /// by adding or removing nodes or arcs/edges, unless the \c _Graph template
     1457  /// parameter is set to be \c const.
     1458  ///
     1459  /// \tparam _Graph The type of the adapted digraph or graph.
     1460  /// It must conform to the \ref concepts::Digraph "Digraph" concept
     1461  /// or the \ref concepts::Graph "Graph" concept.
     1462  /// It can also be specified to be \c const.
     1463  /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the
     1464  /// adapted (di)graph. The default map type is
     1465  /// \ref concepts::Graph::NodeMap "_Graph::NodeMap<bool>".
     1466  /// \tparam _checked If this parameter is set to \c false then the arc/edge
     1467  /// filtering is not checked with respect to the node filter. In this
     1468  /// case only isolated nodes can be filtered out from the graph.
     1469  /// Otherwise, each arc/edge that is incident to a hidden node is
     1470  /// automatically filtered out. This is the default option.
     1471  ///
     1472  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
     1473  /// adapted (di)graph are convertible to each other.
    13981474#ifdef DOXYGEN
    1399   template<typename _Digraph,
    1400            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
    1401            bool _checked = true>
     1475  template<typename _Graph,
     1476           typename _NodeFilterMap,
     1477           bool _checked>
    14021478#else
    14031479  template<typename _Digraph,
     
    14311507    /// \brief Constructor
    14321508    ///
    1433     /// Creates an adaptor for the given digraph or graph with
     1509    /// Creates a subgraph for the given digraph or graph with the
    14341510    /// given node filter map.
    1435     FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
     1511#ifdef DOXYGEN
     1512    FilterNodes(_Graph& graph, _NodeFilterMap& node_filter) :
     1513#else
     1514    FilterNodes(Digraph& graph, NodeFilterMap& node_filter) :
     1515#endif
    14361516      Parent(), const_true_map(true) {
    1437       Parent::setDigraph(_digraph);
     1517      Parent::setDigraph(graph);
    14381518      Parent::setNodeFilterMap(node_filter);
    14391519      Parent::setArcFilterMap(const_true_map);
    14401520    }
    14411521
    1442     /// \brief Hides the node of the graph
    1443     ///
    1444     /// This function hides \c n in the digraph or graph, i.e. the iteration
    1445     /// jumps over it. This is done by simply setting the value of \c n
    1446     /// to be false in the corresponding node map.
     1522    /// \brief Hides the given node
     1523    ///
     1524    /// This function hides the given node in the subgraph,
     1525    /// i.e. the iteration jumps over it.
     1526    /// It is done by simply setting the assigned value of \c n
     1527    /// to be \c false in the node filter map.
    14471528    void hide(const Node& n) const { Parent::hide(n); }
    14481529
    1449     /// \brief Unhides the node of the graph
    1450     ///
    1451     /// The value of \c n is set to be true in the node-map which stores
    1452     /// hide information. If \c n was hidden previuosly, then it is shown
    1453     /// again
     1530    /// \brief Shows the given node
     1531    ///
     1532    /// This function shows the given node in the subgraph.
     1533    /// It is done by simply setting the assigned value of \c n
     1534    /// to be \c true in the node filter map.
    14541535    void unHide(const Node& n) const { Parent::unHide(n); }
    14551536
    1456     /// \brief Returns true if \c n is hidden.
    1457     ///
    1458     /// Returns true if \c n is hidden.
    1459     ///
     1537    /// \brief Returns \c true if the given node is hidden.
     1538    ///
     1539    /// This function returns \c true if the given node is hidden.
    14601540    bool hidden(const Node& n) const { return Parent::hidden(n); }
    14611541
     
    14971577
    14981578
    1499   /// \brief Just gives back a FilterNodes adaptor
    1500   ///
    1501   /// Just gives back a FilterNodes adaptor
     1579  /// \brief Returns a read-only FilterNodes adaptor
     1580  ///
     1581  /// This function just returns a read-only \ref FilterNodes adaptor.
     1582  /// \ingroup graph_adaptors
     1583  /// \relates FilterNodes
    15021584  template<typename Digraph, typename NodeFilterMap>
    15031585  FilterNodes<const Digraph, NodeFilterMap>
     
    15141596  /// \ingroup graph_adaptors
    15151597  ///
    1516   /// \brief An adaptor for hiding arcs from a digraph.
    1517   ///
    1518   /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
    1519   /// be specified, which defines the filters for arcs. Just the
    1520   /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
    1521   /// conform to the \ref concepts::Digraph "Digraph concept".
    1522   ///
    1523   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
    1524   /// "Digraph concept". The type can be specified to be const.
    1525   /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
    1526   /// graph.
    1527   template<typename _Digraph, typename _ArcFilterMap>
     1598  /// \brief Adaptor class for hiding arcs in a digraph.
     1599  ///
     1600  /// FilterArcs adaptor can be used for hiding arcs in a digraph.
     1601  /// A \c bool arc map must be specified, which defines the filter for
     1602  /// the arcs. Only the arcs with \c true filter value are shown in the
     1603  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
     1604  /// "Digraph" concept.
     1605  ///
     1606  /// The adapted digraph can also be modified through this adaptor
     1607  /// by adding or removing nodes or arcs, unless the \c _Digraph template
     1608  /// parameter is set to be \c const.
     1609  ///
     1610  /// \tparam _Digraph The type of the adapted digraph.
     1611  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     1612  /// It can also be specified to be \c const.
     1613  /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the
     1614  /// adapted digraph. The default map type is
     1615  /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>".
     1616  ///
     1617  /// \note The \c Node and \c Arc types of this adaptor and the adapted
     1618  /// digraph are convertible to each other.
     1619#ifdef DOXYGEN
     1620  template<typename _Digraph,
     1621           typename _ArcFilterMap>
     1622#else
     1623  template<typename _Digraph,
     1624           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool> >
     1625#endif
    15281626  class FilterArcs :
    15291627    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
    15301628                      _ArcFilterMap, false> {
    15311629  public:
     1630
    15321631    typedef _Digraph Digraph;
    15331632    typedef _ArcFilterMap ArcFilterMap;
     
    15491648    /// \brief Constructor
    15501649    ///
    1551     /// Creates a FilterArcs adaptor for the given graph with
    1552     /// given arc map filter.
     1650    /// Creates a subdigraph for the given digraph with the given arc
     1651    /// filter map.
    15531652    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
    15541653      : Parent(), const_true_map(true) {
     
    15581657    }
    15591658
    1560     /// \brief Hides the arc of the graph
    1561     ///
    1562     /// This function hides \c a in the graph, i.e. the iteration
    1563     /// jumps over it. This is done by simply setting the value of \c a
    1564     /// to be false in the corresponding arc map.
     1659    /// \brief Hides the given arc
     1660    ///
     1661    /// This function hides the given arc in the subdigraph,
     1662    /// i.e. the iteration jumps over it.
     1663    /// It is done by simply setting the assigned value of \c a
     1664    /// to be \c false in the arc filter map.
    15651665    void hide(const Arc& a) const { Parent::hide(a); }
    15661666
    1567     /// \brief Unhides the arc of the graph
    1568     ///
    1569     /// The value of \c a is set to be true in the arc-map which stores
    1570     /// hide information. If \c a was hidden previuosly, then it is shown
    1571     /// again
     1667    /// \brief Shows the given arc
     1668    ///
     1669    /// This function shows the given arc in the subdigraph.
     1670    /// It is done by simply setting the assigned value of \c a
     1671    /// to be \c true in the arc filter map.
    15721672    void unHide(const Arc& a) const { Parent::unHide(a); }
    15731673
    1574     /// \brief Returns true if \c a is hidden.
    1575     ///
    1576     /// Returns true if \c a is hidden.
    1577     ///
     1674    /// \brief Returns \c true if the given arc is hidden.
     1675    ///
     1676    /// This function returns \c true if the given arc is hidden.
    15781677    bool hidden(const Arc& a) const { return Parent::hidden(a); }
    15791678
    15801679  };
    15811680
    1582   /// \brief Just gives back an FilterArcs adaptor
    1583   ///
    1584   /// Just gives back an FilterArcs adaptor
     1681  /// \brief Returns a read-only FilterArcs adaptor
     1682  ///
     1683  /// This function just returns a read-only \ref FilterArcs adaptor.
     1684  /// \ingroup graph_adaptors
     1685  /// \relates FilterArcs
    15851686  template<typename Digraph, typename ArcFilterMap>
    15861687  FilterArcs<const Digraph, ArcFilterMap>
     
    15971698  /// \ingroup graph_adaptors
    15981699  ///
    1599   /// \brief An adaptor for hiding edges from a graph.
    1600   ///
    1601   /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
    1602   /// be specified, which defines the filters for edges. Just the
    1603   /// unfiltered edges are shown in the subdigraph. The FilterEdges is
    1604   /// conform to the \ref concepts::Graph "Graph concept".
    1605   ///
    1606   /// \tparam _Graph It must be conform to the \ref concepts::Graph
    1607   /// "Graph concept". The type can be specified to be const.
    1608   /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
    1609   /// graph.
    1610   template<typename _Graph, typename _EdgeFilterMap>
     1700  /// \brief Adaptor class for hiding edges in a graph.
     1701  ///
     1702  /// FilterEdges adaptor can be used for hiding edges in a graph.
     1703  /// A \c bool edge map must be specified, which defines the filter for
     1704  /// the edges. Only the edges with \c true filter value are shown in the
     1705  /// subgraph. This adaptor conforms to the \ref concepts::Graph
     1706  /// "Graph" concept.
     1707  ///
     1708  /// The adapted graph can also be modified through this adaptor
     1709  /// by adding or removing nodes or edges, unless the \c _Graph template
     1710  /// parameter is set to be \c const.
     1711  ///
     1712  /// \tparam _Graph The type of the adapted graph.
     1713  /// It must conform to the \ref concepts::Graph "Graph" concept.
     1714  /// It can also be specified to be \c const.
     1715  /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the
     1716  /// adapted graph. The default map type is
     1717  /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>".
     1718  ///
     1719  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
     1720  /// adapted graph are convertible to each other.
     1721#ifdef DOXYGEN
     1722  template<typename _Graph,
     1723           typename _EdgeFilterMap>
     1724#else
     1725  template<typename _Graph,
     1726           typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool> >
     1727#endif
    16111728  class FilterEdges :
    16121729    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
     
    16291746    /// \brief Constructor
    16301747    ///
    1631     /// Creates a FilterEdges adaptor for the given graph with
    1632     /// given edge map filters.
    1633     FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
     1748    /// Creates a subgraph for the given graph with the given edge
     1749    /// filter map.
     1750    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
    16341751      Parent(), const_true_map(true) {
    1635       Parent::setGraph(_graph);
     1752      Parent::setGraph(graph);
    16361753      Parent::setNodeFilterMap(const_true_map);
    16371754      Parent::setEdgeFilterMap(edge_filter_map);
    16381755    }
    16391756
    1640     /// \brief Hides the edge of the graph
    1641     ///
    1642     /// This function hides \c e in the graph, i.e. the iteration
    1643     /// jumps over it. This is done by simply setting the value of \c e
    1644     /// to be false in the corresponding edge-map.
     1757    /// \brief Hides the given edge
     1758    ///
     1759    /// This function hides the given edge in the subgraph,
     1760    /// i.e. the iteration jumps over it.
     1761    /// It is done by simply setting the assigned value of \c e
     1762    /// to be \c false in the edge filter map.
    16451763    void hide(const Edge& e) const { Parent::hide(e); }
    16461764
    1647     /// \brief Unhides the edge of the graph
    1648     ///
    1649     /// The value of \c e is set to be true in the edge-map which stores
    1650     /// hide information. If \c e was hidden previuosly, then it is shown
    1651     /// again
     1765    /// \brief Shows the given edge
     1766    ///
     1767    /// This function shows the given edge in the subgraph.
     1768    /// It is done by simply setting the assigned value of \c e
     1769    /// to be \c true in the edge filter map.
    16521770    void unHide(const Edge& e) const { Parent::unHide(e); }
    16531771
    1654     /// \brief Returns true if \c e is hidden.
    1655     ///
    1656     /// Returns true if \c e is hidden.
    1657     ///
     1772    /// \brief Returns \c true if the given edge is hidden.
     1773    ///
     1774    /// This function returns \c true if the given edge is hidden.
    16581775    bool hidden(const Edge& e) const { return Parent::hidden(e); }
    16591776
    16601777  };
    16611778
    1662   /// \brief Just gives back a FilterEdges adaptor
    1663   ///
    1664   /// Just gives back a FilterEdges adaptor
     1779  /// \brief Returns a read-only FilterEdges adaptor
     1780  ///
     1781  /// This function just returns a read-only \ref FilterEdges adaptor.
     1782  /// \ingroup graph_adaptors
     1783  /// \relates FilterEdges
    16651784  template<typename Graph, typename EdgeFilterMap>
    16661785  FilterEdges<const Graph, EdgeFilterMap>
     
    16751794  }
    16761795
     1796
    16771797  template <typename _Digraph>
    16781798  class UndirectorBase {
     
    17131833      }
    17141834    };
    1715 
    1716 
    17171835
    17181836    void first(Node& n) const {
     
    20692187  /// \ingroup graph_adaptors
    20702188  ///
    2071   /// \brief Undirect the graph
    2072   ///
    2073   /// This adaptor makes an undirected graph from a directed
    2074   /// graph. All arcs of the underlying digraph will be showed in the
    2075   /// adaptor as an edge. The Orienter adaptor is conform to the \ref
    2076   /// concepts::Graph "Graph concept".
    2077   ///
    2078   /// \tparam _Digraph It must be conform to the \ref
    2079   /// concepts::Digraph "Digraph concept". The type can be specified
    2080   /// to const.
     2189  /// \brief Adaptor class for viewing a digraph as an undirected graph.
     2190  ///
     2191  /// Undirector adaptor can be used for viewing a digraph as an undirected
     2192  /// graph. All arcs of the underlying digraph are showed in the
     2193  /// adaptor as an edge (and also as a pair of arcs, of course).
     2194  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
     2195  ///
     2196  /// The adapted digraph can also be modified through this adaptor
     2197  /// by adding or removing nodes or edges, unless the \c _Digraph template
     2198  /// parameter is set to be \c const.
     2199  ///
     2200  /// \tparam _Digraph The type of the adapted digraph.
     2201  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     2202  /// It can also be specified to be \c const.
     2203  ///
     2204  /// \note The \c Node type of this adaptor and the adapted digraph are
     2205  /// convertible to each other, moreover the \c Edge type of the adaptor
     2206  /// and the \c Arc type of the adapted digraph are also convertible to
     2207  /// each other.
     2208  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
     2209  /// of the adapted digraph.)
    20812210  template<typename _Digraph>
    20822211  class Undirector
     
    20912220    /// \brief Constructor
    20922221    ///
    2093     /// Creates a undirected graph from the given digraph
     2222    /// Creates an undirected graph from the given digraph.
    20942223    Undirector(_Digraph& digraph) {
    20952224      setDigraph(digraph);
    20962225    }
    20972226
    2098     /// \brief ArcMap combined from two original ArcMap
    2099     ///
    2100     /// This class adapts two original digraph ArcMap to
    2101     /// get an arc map on the undirected graph.
     2227    /// \brief Arc map combined from two original arc maps
     2228    ///
     2229    /// This map adaptor class adapts two arc maps of the underlying
     2230    /// digraph to get an arc map of the undirected graph.
     2231    /// Its value type is inherited from the first arc map type
     2232    /// (\c %ForwardMap).
    21022233    template <typename _ForwardMap, typename _BackwardMap>
    21032234    class CombinedArcMap {
     
    21092240      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
    21102241
     2242      /// The key type of the map
     2243      typedef typename Parent::Arc Key;
     2244      /// The value type of the map
    21112245      typedef typename ForwardMap::Value Value;
    2112       typedef typename Parent::Arc Key;
    21132246
    21142247      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
     
    21172250      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
    21182251
    2119       /// \brief Constructor
    2120       ///
    21212252      /// Constructor
    21222253      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
    21232254        : _forward(&forward), _backward(&backward) {}
    21242255
    2125 
    2126       /// \brief Sets the value associated with a key.
    2127       ///
    2128       /// Sets the value associated with a key.
     2256      /// Sets the value associated with the given key.
    21292257      void set(const Key& e, const Value& a) {
    21302258        if (Parent::direction(e)) {
     
    21352263      }
    21362264
    2137       /// \brief Returns the value associated with a key.
    2138       ///
    2139       /// Returns the value associated with a key.
     2265      /// Returns the value associated with the given key.
    21402266      ConstReturnValue operator[](const Key& e) const {
    21412267        if (Parent::direction(e)) {
     
    21462272      }
    21472273
    2148       /// \brief Returns the value associated with a key.
    2149       ///
    2150       /// Returns the value associated with a key.
     2274      /// Returns a reference to the value associated with the given key.
    21512275      ReturnValue operator[](const Key& e) {
    21522276        if (Parent::direction(e)) {
     
    21642288    };
    21652289
    2166     /// \brief Just gives back a combined arc map
    2167     ///
    2168     /// Just gives back a combined arc map
     2290    /// \brief Returns a combined arc map
     2291    ///
     2292    /// This function just returns a combined arc map.
    21692293    template <typename ForwardMap, typename BackwardMap>
    21702294    static CombinedArcMap<ForwardMap, BackwardMap>
     
    21962320  };
    21972321
    2198   /// \brief Just gives back an undirected view of the given digraph
    2199   ///
    2200   /// Just gives back an undirected view of the given digraph
     2322  /// \brief Returns a read-only Undirector adaptor
     2323  ///
     2324  /// This function just returns a read-only \ref Undirector adaptor.
     2325  /// \ingroup graph_adaptors
     2326  /// \relates Undirector
    22012327  template<typename Digraph>
    22022328  Undirector<const Digraph>
     
    22042330    return Undirector<const Digraph>(digraph);
    22052331  }
     2332
    22062333
    22072334  template <typename _Graph, typename _DirectionMap>
     
    23652492  /// \ingroup graph_adaptors
    23662493  ///
    2367   /// \brief Orients the edges of the graph to get a digraph
    2368   ///
    2369   /// This adaptor orients each edge in the undirected graph. The
    2370   /// direction of the arcs stored in an edge node map.  The arcs can
    2371   /// be easily reverted by the \c reverseArc() member function in the
    2372   /// adaptor. The Orienter adaptor is conform to the \ref
    2373   /// concepts::Digraph "Digraph concept".
    2374   ///
    2375   /// \tparam _Graph It must be conform to the \ref concepts::Graph
    2376   /// "Graph concept". The type can be specified to be const.
    2377   /// \tparam _DirectionMap A bool valued edge map of the the adapted
    2378   /// graph.
    2379   ///
    2380   /// \sa orienter
     2494  /// \brief Adaptor class for orienting the edges of a graph to get a digraph
     2495  ///
     2496  /// Orienter adaptor can be used for orienting the edges of a graph to
     2497  /// get a digraph. A \c bool edge map of the underlying graph must be
     2498  /// specified, which define the direction of the arcs in the adaptor.
     2499  /// The arcs can be easily reversed by the \c reverseArc() member function
     2500  /// of the adaptor.
     2501  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
     2502  ///
     2503  /// The adapted graph can also be modified through this adaptor
     2504  /// by adding or removing nodes or arcs, unless the \c _Graph template
     2505  /// parameter is set to be \c const.
     2506  ///
     2507  /// \tparam _Graph The type of the adapted graph.
     2508  /// It must conform to the \ref concepts::Graph "Graph" concept.
     2509  /// It can also be specified to be \c const.
     2510  /// \tparam _DirectionMap A \c bool (or convertible) edge map of the
     2511  /// adapted graph. The default map type is
     2512  /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>".
     2513  ///
     2514  /// \note The \c Node type of this adaptor and the adapted graph are
     2515  /// convertible to each other, moreover the \c Arc type of the adaptor
     2516  /// and the \c Edge type of the adapted graph are also convertible to
     2517  /// each other.
     2518#ifdef DOXYGEN
    23812519  template<typename _Graph,
    2382            typename DirectionMap = typename _Graph::template EdgeMap<bool> >
     2520           typename _DirectionMap>
     2521#else
     2522  template<typename _Graph,
     2523           typename _DirectionMap = typename _Graph::template EdgeMap<bool> >
     2524#endif
    23832525  class Orienter :
    2384     public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
    2385   public:
     2526    public DigraphAdaptorExtender<OrienterBase<_Graph, _DirectionMap> > {
     2527  public:
     2528
     2529    /// The type of the adapted graph.
    23862530    typedef _Graph Graph;
     2531    /// The type of the direction edge map.
     2532    typedef _DirectionMap DirectionMap;
     2533
    23872534    typedef DigraphAdaptorExtender<
    2388       OrienterBase<_Graph, DirectionMap> > Parent;
     2535      OrienterBase<_Graph, _DirectionMap> > Parent;
    23892536    typedef typename Parent::Arc Arc;
    23902537  protected:
     
    23922539  public:
    23932540
    2394     /// \brief Constructor of the adaptor
    2395     ///
    2396     /// Constructor of the adaptor
     2541    /// \brief Constructor
     2542    ///
     2543    /// Constructor of the adaptor.
    23972544    Orienter(Graph& graph, DirectionMap& direction) {
    23982545      setGraph(graph);
     
    24002547    }
    24012548
    2402     /// \brief Reverse arc
    2403     ///
    2404     /// It reverse the given arc. It simply negate the direction in the map.
     2549    /// \brief Reverses the given arc
     2550    ///
     2551    /// This function reverses the given arc.
     2552    /// It is done by simply negate the assigned value of \c a
     2553    /// in the direction map.
    24052554    void reverseArc(const Arc& a) {
    24062555      Parent::reverseArc(a);
     
    24082557  };
    24092558
    2410   /// \brief Just gives back a Orienter
    2411   ///
    2412   /// Just gives back a Orienter
     2559  /// \brief Returns a read-only Orienter adaptor
     2560  ///
     2561  /// This function just returns a read-only \ref Orienter adaptor.
     2562  /// \ingroup graph_adaptors
     2563  /// \relates Orienter
    24132564  template<typename Graph, typename DirectionMap>
    24142565  Orienter<const Graph, DirectionMap>
     
    24922643  /// \ingroup graph_adaptors
    24932644  ///
    2494   /// \brief An adaptor for composing the residual graph for directed
     2645  /// \brief Adaptor class for composing the residual digraph for directed
    24952646  /// flow and circulation problems.
    24962647  ///
    2497   /// An adaptor for composing the residual graph for directed flow and
    2498   /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
    2499   /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
    2500   /// be functions on the arc-set.
    2501   ///
    2502   /// Then Residual implements the digraph structure with
    2503   /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
    2504   /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
    2505   /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
    2506   /// called residual graph.  When we take the union
    2507   /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
    2508   /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
    2509   /// \f$ A_{backward} \f$, then in the adaptor it appears in both
    2510   /// orientation.
    2511   ///
    2512   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
    2513   /// "Digraph concept". The type is implicitly const.
    2514   /// \tparam _CapacityMap An arc map of some numeric type, it defines
    2515   /// the capacities in the flow problem. The map is implicitly const.
    2516   /// \tparam _FlowMap An arc map of some numeric type, it defines
    2517   /// the capacities in the flow problem.
    2518   /// \tparam _Tolerance Handler for inexact computation.
     2648  /// Residual can be used for composing the \e residual digraph for directed
     2649  /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
     2650  /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
     2651  /// functions on the arcs.
     2652  /// This adaptor implements a digraph structure with node set \f$ V \f$
     2653  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
     2654  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
     2655  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
     2656  /// called residual digraph.
     2657  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
     2658  /// multiplicities are counted, i.e. the adaptor has exactly
     2659  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
     2660  /// arcs).
     2661  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
     2662  ///
     2663  /// \tparam _Digraph The type of the adapted digraph.
     2664  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     2665  /// It is implicitly \c const.
     2666  /// \tparam _CapacityMap An arc map of some numerical type, which defines
     2667  /// the capacities in the flow problem. It is implicitly \c const.
     2668  /// The default map type is
     2669  /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
     2670  /// \tparam _FlowMap An arc map of some numerical type, which defines
     2671  /// the flow values in the flow problem.
     2672  /// The default map type is \c _CapacityMap.
     2673  /// \tparam _Tolerance Tolerance type for handling inexact computation.
     2674  /// The default tolerance type depends on the value type of the
     2675  /// capacity map.
     2676  ///
     2677  /// \note This adaptor is implemented using Undirector and FilterArcs
     2678  /// adaptors.
     2679  ///
     2680  /// \note The \c Node type of this adaptor and the adapted digraph are
     2681  /// convertible to each other, moreover the \c Arc type of the adaptor
     2682  /// is convertible to the \c Arc type of the adapted digraph.
     2683#ifdef DOXYGEN
     2684  template<typename _Digraph,
     2685           typename _CapacityMap,
     2686           typename _FlowMap,
     2687           typename _Tolerance>
     2688  class Residual
     2689#else
    25192690  template<typename _Digraph,
    25202691           typename _CapacityMap = typename _Digraph::template ArcMap<int>,
     
    25292700      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
    25302701                                       _FlowMap, _Tolerance> > >
     2702#endif
    25312703  {
    25322704  public:
    25332705
     2706    /// The type of the underlying digraph.
    25342707    typedef _Digraph Digraph;
     2708    /// The type of the capacity map.
    25352709    typedef _CapacityMap CapacityMap;
     2710    /// The type of the flow map.
    25362711    typedef _FlowMap FlowMap;
    25372712    typedef _Tolerance Tolerance;
     
    25652740  public:
    25662741
    2567     /// \brief Constructor of the residual digraph.
    2568     ///
    2569     /// Constructor of the residual graph. The parameters are the digraph,
    2570     /// the flow map, the capacity map and a tolerance object.
     2742    /// \brief Constructor
     2743    ///
     2744    /// Constructor of the residual digraph adaptor. The parameters are the
     2745    /// digraph, the capacity map, the flow map, and a tolerance object.
    25712746    Residual(const Digraph& digraph, const CapacityMap& capacity,
    25722747             FlowMap& flow, const Tolerance& tolerance = Tolerance())
     
    25822757    typedef typename Parent::Arc Arc;
    25832758
    2584     /// \brief Gives back the residual capacity of the arc.
    2585     ///
    2586     /// Gives back the residual capacity of the arc.
     2759    /// \brief Returns the residual capacity of the given arc.
     2760    ///
     2761    /// Returns the residual capacity of the given arc.
    25872762    Value residualCapacity(const Arc& a) const {
    25882763      if (Undirected::direction(a)) {
     
    25932768    }
    25942769
    2595     /// \brief Augment on the given arc in the residual graph.
    2596     ///
    2597     /// Augment on the given arc in the residual graph. It increase
    2598     /// or decrease the flow on the original arc depend on the direction
    2599     /// of the residual arc.
     2770    /// \brief Augment on the given arc in the residual digraph.
     2771    ///
     2772    /// Augment on the given arc in the residual digraph. It increases
     2773    /// or decreases the flow value on the original arc according to the
     2774    /// direction of the residual arc.
    26002775    void augment(const Arc& a, const Value& v) const {
    26012776      if (Undirected::direction(a)) {
     
    26062781    }
    26072782
    2608     /// \brief Returns the direction of the arc.
    2609     ///
    2610     /// Returns true when the arc is same oriented as the original arc.
     2783    /// \brief Returns \c true if the given residual arc is a forward arc.
     2784    ///
     2785    /// Returns \c true if the given residual arc has the same orientation
     2786    /// as the original arc, i.e. it is a so called forward arc.
    26112787    static bool forward(const Arc& a) {
    26122788      return Undirected::direction(a);
    26132789    }
    26142790
    2615     /// \brief Returns the direction of the arc.
    2616     ///
    2617     /// Returns true when the arc is opposite oriented as the original arc.
     2791    /// \brief Returns \c true if the given residual arc is a backward arc.
     2792    ///
     2793    /// Returns \c true if the given residual arc has the opposite orientation
     2794    /// than the original arc, i.e. it is a so called backward arc.
    26182795    static bool backward(const Arc& a) {
    26192796      return !Undirected::direction(a);
    26202797    }
    26212798
    2622     /// \brief Gives back the forward oriented residual arc.
    2623     ///
    2624     /// Gives back the forward oriented residual arc.
     2799    /// \brief Returns the forward oriented residual arc.
     2800    ///
     2801    /// Returns the forward oriented residual arc related to the given
     2802    /// arc of the underlying digraph.
    26252803    static Arc forward(const typename Digraph::Arc& a) {
    26262804      return Undirected::direct(a, true);
    26272805    }
    26282806
    2629     /// \brief Gives back the backward oriented residual arc.
    2630     ///
    2631     /// Gives back the backward oriented residual arc.
     2807    /// \brief Returns the backward oriented residual arc.
     2808    ///
     2809    /// Returns the backward oriented residual arc related to the given
     2810    /// arc of the underlying digraph.
    26322811    static Arc backward(const typename Digraph::Arc& a) {
    26332812      return Undirected::direct(a, false);
     
    26362815    /// \brief Residual capacity map.
    26372816    ///
    2638     /// In generic residual graph the residual capacity can be obtained
    2639     /// as a map.
     2817    /// This map adaptor class can be used for obtaining the residual
     2818    /// capacities as an arc map of the residual digraph.
     2819    /// Its value type is inherited from the capacity map.
    26402820    class ResidualCapacity {
    26412821    protected:
    26422822      const Adaptor* _adaptor;
    26432823    public:
    2644       /// The Key type
     2824      /// The key type of the map
    26452825      typedef Arc Key;
    2646       /// The Value type
     2826      /// The value type of the map
    26472827      typedef typename _CapacityMap::Value Value;
    26482828
     
    26502830      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
    26512831
    2652       /// \e
     2832      /// Returns the value associated with the given residual arc
    26532833      Value operator[](const Arc& a) const {
    26542834        return _adaptor->residualCapacity(a);
     
    31093289  /// \ingroup graph_adaptors
    31103290  ///
    3111   /// \brief Split the nodes of a directed graph
    3112   ///
    3113   /// The SplitNodes adaptor splits each node into an in-node and an
    3114   /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
    3115   /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
    3116   /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
    3117   /// original digraph the new target of the arc will be \f$ u_{in} \f$
    3118   /// and similarly the source of the original \f$ (u, v) \f$ arc
    3119   /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
    3120   /// the original digraph an additional arc which connects
    3121   /// \f$ (u_{in}, u_{out}) \f$.
    3122   ///
    3123   /// The aim of this class is to run algorithm with node costs if the
    3124   /// algorithm can use directly just arc costs. In this case we should use
    3125   /// a \c SplitNodes and set the node cost of the graph to the
    3126   /// bind arc in the adapted graph.
    3127   ///
    3128   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
    3129   /// "Digraph concept". The type can be specified to be const.
     3291  /// \brief Adaptor class for splitting the nodes of a digraph.
     3292  ///
     3293  /// SplitNodes adaptor can be used for splitting each node into an
     3294  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
     3295  /// replaces each node \f$ u \f$ in the digraph with two nodes,
     3296  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
     3297  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
     3298  /// new target of the arc will be \f$ u_{in} \f$ and similarly the
     3299  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
     3300  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
     3301  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
     3302  ///
     3303  /// The aim of this class is running an algorithm with respect to node
     3304  /// costs or capacities if the algorithm considers only arc costs or
     3305  /// capacities directly.
     3306  /// In this case you can use \c SplitNodes adaptor, and set the node
     3307  /// costs/capacities of the original digraph to the \e bind \e arcs
     3308  /// in the adaptor.
     3309  ///
     3310  /// \tparam _Digraph The type of the adapted digraph.
     3311  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     3312  /// It is implicitly \c const.
     3313  ///
     3314  /// \note The \c Node type of this adaptor is converible to the \c Node
     3315  /// type of the adapted digraph.
    31303316  template <typename _Digraph>
    31313317  class SplitNodes
     
    31413327    typedef typename Parent::Arc Arc;
    31423328
    3143     /// \brief Constructor of the adaptor.
     3329    /// \brief Constructor
    31443330    ///
    31453331    /// Constructor of the adaptor.
     
    31483334    }
    31493335
    3150     /// \brief Returns true when the node is in-node.
    3151     ///
    3152     /// Returns true when the node is in-node.
     3336    /// \brief Returns \c true if the given node is an in-node.
     3337    ///
     3338    /// Returns \c true if the given node is an in-node.
    31533339    static bool inNode(const Node& n) {
    31543340      return Parent::inNode(n);
    31553341    }
    31563342
    3157     /// \brief Returns true when the node is out-node.
    3158     ///
    3159     /// Returns true when the node is out-node.
     3343    /// \brief Returns \c true if the given node is an out-node.
     3344    ///
     3345    /// Returns \c true if the given node is an out-node.
    31603346    static bool outNode(const Node& n) {
    31613347      return Parent::outNode(n);
    31623348    }
    31633349
    3164     /// \brief Returns true when the arc is arc in the original digraph.
    3165     ///
    3166     /// Returns true when the arc is arc in the original digraph.
     3350    /// \brief Returns \c true if the given arc is an original arc.
     3351    ///
     3352    /// Returns \c true if the given arc is one of the arcs in the
     3353    /// original digraph.
    31673354    static bool origArc(const Arc& a) {
    31683355      return Parent::origArc(a);
    31693356    }
    31703357
    3171     /// \brief Returns true when the arc binds an in-node and an out-node.
    3172     ///
    3173     /// Returns true when the arc binds an in-node and an out-node.
     3358    /// \brief Returns \c true if the given arc is a bind arc.
     3359    ///
     3360    /// Returns \c true if the given arc is a bind arc, i.e. it connects
     3361    /// an in-node and an out-node.
    31743362    static bool bindArc(const Arc& a) {
    31753363      return Parent::bindArc(a);
    31763364    }
    31773365
    3178     /// \brief Gives back the in-node created from the \c node.
    3179     ///
    3180     /// Gives back the in-node created from the \c node.
     3366    /// \brief Returns the in-node created from the given original node.
     3367    ///
     3368    /// Returns the in-node created from the given original node.
    31813369    static Node inNode(const DigraphNode& n) {
    31823370      return Parent::inNode(n);
    31833371    }
    31843372
    3185     /// \brief Gives back the out-node created from the \c node.
    3186     ///
    3187     /// Gives back the out-node created from the \c node.
     3373    /// \brief Returns the out-node created from the given original node.
     3374    ///
     3375    /// Returns the out-node created from the given original node.
    31883376    static Node outNode(const DigraphNode& n) {
    31893377      return Parent::outNode(n);
    31903378    }
    31913379
    3192     /// \brief Gives back the arc binds the two part of the node.
    3193     ///
    3194     /// Gives back the arc binds the two part of the node.
     3380    /// \brief Returns the bind arc that corresponds to the given
     3381    /// original node.
     3382    ///
     3383    /// Returns the bind arc in the adaptor that corresponds to the given
     3384    /// original node, i.e. the arc connecting the in-node and out-node
     3385    /// of \c n.
    31953386    static Arc arc(const DigraphNode& n) {
    31963387      return Parent::arc(n);
    31973388    }
    31983389
    3199     /// \brief Gives back the arc of the original arc.
    3200     ///
    3201     /// Gives back the arc of the original arc.
     3390    /// \brief Returns the arc that corresponds to the given original arc.
     3391    ///
     3392    /// Returns the arc in the adaptor that corresponds to the given
     3393    /// original arc.
    32023394    static Arc arc(const DigraphArc& a) {
    32033395      return Parent::arc(a);
    32043396    }
    32053397
    3206     /// \brief NodeMap combined from two original NodeMap
    3207     ///
    3208     /// This class adapt two of the original digraph NodeMap to
    3209     /// get a node map on the adapted digraph.
     3398    /// \brief Node map combined from two original node maps
     3399    ///
     3400    /// This map adaptor class adapts two node maps of the original digraph
     3401    /// to get a node map of the split digraph.
     3402    /// Its value type is inherited from the first node map type
     3403    /// (\c InNodeMap).
    32103404    template <typename InNodeMap, typename OutNodeMap>
    32113405    class CombinedNodeMap {
    32123406    public:
    32133407
     3408      /// The key type of the map
    32143409      typedef Node Key;
     3410      /// The value type of the map
    32153411      typedef typename InNodeMap::Value Value;
    32163412
     
    32213417      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
    32223418
    3223       /// \brief Constructor
    3224       ///
    3225       /// Constructor.
     3419      /// Constructor
    32263420      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
    32273421        : _in_map(in_map), _out_map(out_map) {}
    32283422
    3229       /// \brief The subscript operator.
    3230       ///
    3231       /// The subscript operator.
     3423      /// Returns the value associated with the given key.
     3424      Value operator[](const Key& key) const {
     3425        if (Parent::inNode(key)) {
     3426          return _in_map[key];
     3427        } else {
     3428          return _out_map[key];
     3429        }
     3430      }
     3431
     3432      /// Returns a reference to the value associated with the given key.
    32323433      Value& operator[](const Key& key) {
    32333434        if (Parent::inNode(key)) {
     
    32383439      }
    32393440
    3240       /// \brief The const subscript operator.
    3241       ///
    3242       /// The const subscript operator.
    3243       Value operator[](const Key& key) const {
    3244         if (Parent::inNode(key)) {
    3245           return _in_map[key];
    3246         } else {
    3247           return _out_map[key];
    3248         }
    3249       }
    3250 
    3251       /// \brief The setter function of the map.
    3252       ///
    3253       /// The setter function of the map.
     3441      /// Sets the value associated with the given key.
    32543442      void set(const Key& key, const Value& value) {
    32553443        if (Parent::inNode(key)) {
     
    32683456
    32693457
    3270     /// \brief Just gives back a combined node map
    3271     ///
    3272     /// Just gives back a combined node map
     3458    /// \brief Returns a combined node map
     3459    ///
     3460    /// This function just returns a combined node map.
    32733461    template <typename InNodeMap, typename OutNodeMap>
    32743462    static CombinedNodeMap<InNodeMap, OutNodeMap>
     
    32963484    }
    32973485
    3298     /// \brief ArcMap combined from an original ArcMap and a NodeMap
    3299     ///
    3300     /// This class adapt an original ArcMap and a NodeMap to get an
    3301     /// arc map on the adapted digraph
     3486    /// \brief Arc map combined from an arc map and a node map of the
     3487    /// original digraph.
     3488    ///
     3489    /// This map adaptor class adapts an arc map and a node map of the
     3490    /// original digraph to get an arc map of the split digraph.
     3491    /// Its value type is inherited from the original arc map type
     3492    /// (\c DigraphArcMap).
    33023493    template <typename DigraphArcMap, typename DigraphNodeMap>
    33033494    class CombinedArcMap {
    33043495    public:
    33053496
     3497      /// The key type of the map
    33063498      typedef Arc Key;
     3499      /// The value type of the map
    33073500      typedef typename DigraphArcMap::Value Value;
    33083501
     
    33183511        ConstReference;
    33193512
    3320       /// \brief Constructor
    3321       ///
    3322       /// Constructor.
     3513      /// Constructor
    33233514      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
    33243515        : _arc_map(arc_map), _node_map(node_map) {}
    33253516
    3326       /// \brief The subscript operator.
    3327       ///
    3328       /// The subscript operator.
     3517      /// Returns the value associated with the given key.
     3518      Value operator[](const Key& arc) const {
     3519        if (Parent::origArc(arc)) {
     3520          return _arc_map[arc];
     3521        } else {
     3522          return _node_map[arc];
     3523        }
     3524      }
     3525
     3526      /// Returns a reference to the value associated with the given key.
     3527      Value& operator[](const Key& arc) {
     3528        if (Parent::origArc(arc)) {
     3529          return _arc_map[arc];
     3530        } else {
     3531          return _node_map[arc];
     3532        }
     3533      }
     3534
     3535      /// Sets the value associated with the given key.
    33293536      void set(const Arc& arc, const Value& val) {
    33303537        if (Parent::origArc(arc)) {
     
    33353542      }
    33363543
    3337       /// \brief The const subscript operator.
    3338       ///
    3339       /// The const subscript operator.
    3340       Value operator[](const Key& arc) const {
    3341         if (Parent::origArc(arc)) {
    3342           return _arc_map[arc];
    3343         } else {
    3344           return _node_map[arc];
    3345         }
    3346       }
    3347 
    3348       /// \brief The const subscript operator.
    3349       ///
    3350       /// The const subscript operator.
    3351       Value& operator[](const Key& arc) {
    3352         if (Parent::origArc(arc)) {
    3353           return _arc_map[arc];
    3354         } else {
    3355           return _node_map[arc];
    3356         }
    3357       }
    3358 
    33593544    private:
    33603545      DigraphArcMap& _arc_map;
     
    33623547    };
    33633548
    3364     /// \brief Just gives back a combined arc map
    3365     ///
    3366     /// Just gives back a combined arc map
     3549    /// \brief Returns a combined arc map
     3550    ///
     3551    /// This function just returns a combined arc map.
    33673552    template <typename DigraphArcMap, typename DigraphNodeMap>
    33683553    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
     
    33953580  };
    33963581
    3397   /// \brief Just gives back a node splitter
    3398   ///
    3399   /// Just gives back a node splitter
     3582  /// \brief Returns a (read-only) SplitNodes adaptor
     3583  ///
     3584  /// This function just returns a (read-only) \ref SplitNodes adaptor.
     3585  /// \ingroup graph_adaptors
     3586  /// \relates SplitNodes
    34003587  template<typename Digraph>
    34013588  SplitNodes<Digraph>
Note: See TracChangeset for help on using the changeset viewer.