COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r687 r698  
    336336In most cases the \ref Preflow "Preflow" algorithm provides the
    337337fastest method for computing a maximum flow. All implementations
    338 provides functions to also query the minimum cut, which is the dual
    339 problem of the maximum flow.
     338also provide functions to query the minimum cut, which is the dual
     339problem of maximum flow.
     340
     341\ref Circulation is a preflow push-relabel algorithm implemented directly
     342for finding feasible circulations, which is a somewhat different problem,
     343but it is strongly related to maximum flow.
     344For more information, see \ref Circulation.
    340345*/
    341346
     
    542547@defgroup spantree Minimum Spanning Tree Algorithms
    543548@ingroup algs
    544 \brief Algorithms for finding a minimum cost spanning tree in a graph.
    545 
    546 This group contains the algorithms for finding a minimum cost spanning
    547 tree in a graph.
     549\brief Algorithms for finding minimum cost spanning trees and arborescences.
     550
     551This group contains the algorithms for finding minimum cost spanning
     552trees and arborescences.
    548553*/
    549554
  • doc/mainpage.dox

    r606 r698  
    4242\subsection howtoread How to read the documentation
    4343
    44 If you want to get a quick start and see the most important features then
    45 take a look at our \ref quicktour
    46 "Quick Tour to LEMON" which will guide you along.
    47 
    48 If you already feel like using our library, see the
     44If you would like to get to know the library, see
    4945<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    5046
    51 If you know what you are looking for then try to find it under the
     47If you know what you are looking for, then try to find it under the
    5248<a class="el" href="modules.html">Modules</a> section.
    5349
  • lemon/connectivity.h

    r633 r695  
    4343  /// \ingroup graph_properties
    4444  ///
    45   /// \brief Check whether the given undirected graph is connected.
    46   ///
    47   /// Check whether the given undirected graph is connected.
    48   /// \param graph The undirected graph.
    49   /// \return \c true when there is path between any two nodes in the graph.
     45  /// \brief Check whether an undirected graph is connected.
     46  ///
     47  /// This function checks whether the given undirected graph is connected,
     48  /// i.e. there is a path between any two nodes in the graph.
     49  ///
     50  /// \return \c true if the graph is connected.
    5051  /// \note By definition, the empty graph is connected.
     52  ///
     53  /// \see countConnectedComponents(), connectedComponents()
     54  /// \see stronglyConnected()
    5155  template <typename Graph>
    5256  bool connected(const Graph& graph) {
     
    6872  /// \brief Count the number of connected components of an undirected graph
    6973  ///
    70   /// Count the number of connected components of an undirected graph
    71   ///
    72   /// \param graph The graph. It must be undirected.
    73   /// \return The number of components
     74  /// This function counts the number of connected components of the given
     75  /// undirected graph.
     76  ///
     77  /// The connected components are the classes of an equivalence relation
     78  /// on the nodes of an undirected graph. Two nodes are in the same class
     79  /// if they are connected with a path.
     80  ///
     81  /// \return The number of connected components.
    7482  /// \note By definition, the empty graph consists
    7583  /// of zero connected components.
     84  ///
     85  /// \see connected(), connectedComponents()
    7686  template <typename Graph>
    7787  int countConnectedComponents(const Graph &graph) {
     
    110120  /// \brief Find the connected components of an undirected graph
    111121  ///
    112   /// Find the connected components of an undirected graph.
     122  /// This function finds the connected components of the given undirected
     123  /// graph.
     124  ///
     125  /// The connected components are the classes of an equivalence relation
     126  /// on the nodes of an undirected graph. Two nodes are in the same class
     127  /// if they are connected with a path.
    113128  ///
    114129  /// \image html connected_components.png
    115130  /// \image latex connected_components.eps "Connected components" width=\textwidth
    116131  ///
    117   /// \param graph The graph. It must be undirected.
     132  /// \param graph The undirected graph.
    118133  /// \retval compMap A writable node map. The values will be set from 0 to
    119   /// the number of the connected components minus one. Each values of the map
    120   /// will be set exactly once, the values of a certain component will be
     134  /// the number of the connected components minus one. Each value of the map
     135  /// will be set exactly once, and the values of a certain component will be
    121136  /// set continuously.
    122   /// \return The number of components
     137  /// \return The number of connected components.
     138  /// \note By definition, the empty graph consists
     139  /// of zero connected components.
     140  ///
     141  /// \see connected(), countConnectedComponents()
    123142  template <class Graph, class NodeMap>
    124143  int connectedComponents(const Graph &graph, NodeMap &compMap) {
     
    232251  /// \ingroup graph_properties
    233252  ///
    234   /// \brief Check whether the given directed graph is strongly connected.
    235   ///
    236   /// Check whether the given directed graph is strongly connected. The
    237   /// graph is strongly connected when any two nodes of the graph are
     253  /// \brief Check whether a directed graph is strongly connected.
     254  ///
     255  /// This function checks whether the given directed graph is strongly
     256  /// connected, i.e. any two nodes of the digraph are
    238257  /// connected with directed paths in both direction.
    239   /// \return \c false when the graph is not strongly connected.
    240   /// \see connected
    241   ///
    242   /// \note By definition, the empty graph is strongly connected.
     258  ///
     259  /// \return \c true if the digraph is strongly connected.
     260  /// \note By definition, the empty digraph is strongly connected.
     261  ///
     262  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
     263  /// \see connected()
    243264  template <typename Digraph>
    244265  bool stronglyConnected(const Digraph& digraph) {
     
    271292    RDigraph rdigraph(digraph);
    272293
    273     typedef DfsVisitor<Digraph> RVisitor;
     294    typedef DfsVisitor<RDigraph> RVisitor;
    274295    RVisitor rvisitor;
    275296
     
    290311  /// \ingroup graph_properties
    291312  ///
    292   /// \brief Count the strongly connected components of a directed graph
    293   ///
    294   /// Count the strongly connected components of a directed graph.
     313  /// \brief Count the number of strongly connected components of a
     314  /// directed graph
     315  ///
     316  /// This function counts the number of strongly connected components of
     317  /// the given directed graph.
     318  ///
    295319  /// The strongly connected components are the classes of an
    296   /// equivalence relation on the nodes of the graph. Two nodes are in
     320  /// equivalence relation on the nodes of a digraph. Two nodes are in
    297321  /// the same class if they are connected with directed paths in both
    298322  /// direction.
    299323  ///
    300   /// \param digraph The graph.
    301   /// \return The number of components
    302   /// \note By definition, the empty graph has zero
     324  /// \return The number of strongly connected components.
     325  /// \note By definition, the empty digraph has zero
    303326  /// strongly connected components.
     327  ///
     328  /// \see stronglyConnected(), stronglyConnectedComponents()
    304329  template <typename Digraph>
    305330  int countStronglyConnectedComponents(const Digraph& digraph) {
     
    356381  /// \brief Find the strongly connected components of a directed graph
    357382  ///
    358   /// Find the strongly connected components of a directed graph.  The
    359   /// strongly connected components are the classes of an equivalence
    360   /// relation on the nodes of the graph. Two nodes are in
    361   /// relationship when there are directed paths between them in both
    362   /// direction. In addition, the numbering of components will satisfy
    363   /// that there is no arc going from a higher numbered component to
    364   /// a lower.
     383  /// This function finds the strongly connected components of the given
     384  /// directed graph. In addition, the numbering of the components will
     385  /// satisfy that there is no arc going from a higher numbered component
     386  /// to a lower one (i.e. it provides a topological order of the components).
     387  ///
     388  /// The strongly connected components are the classes of an
     389  /// equivalence relation on the nodes of a digraph. Two nodes are in
     390  /// the same class if they are connected with directed paths in both
     391  /// direction.
    365392  ///
    366393  /// \image html strongly_connected_components.png
     
    370397  /// \retval compMap A writable node map. The values will be set from 0 to
    371398  /// the number of the strongly connected components minus one. Each value
    372   /// of the map will be set exactly once, the values of a certain component
    373   /// will be set continuously.
    374   /// \return The number of components
     399  /// of the map will be set exactly once, and the values of a certain
     400  /// component will be set continuously.
     401  /// \return The number of strongly connected components.
     402  /// \note By definition, the empty digraph has zero
     403  /// strongly connected components.
     404  ///
     405  /// \see stronglyConnected(), countStronglyConnectedComponents()
    375406  template <typename Digraph, typename NodeMap>
    376407  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
     
    425456  /// \brief Find the cut arcs of the strongly connected components.
    426457  ///
    427   /// Find the cut arcs of the strongly connected components.
    428   /// The strongly connected components are the classes of an equivalence
    429   /// relation on the nodes of the graph. Two nodes are in relationship
    430   /// when there are directed paths between them in both direction.
     458  /// This function finds the cut arcs of the strongly connected components
     459  /// of the given digraph.
     460  ///
     461  /// The strongly connected components are the classes of an
     462  /// equivalence relation on the nodes of a digraph. Two nodes are in
     463  /// the same class if they are connected with directed paths in both
     464  /// direction.
    431465  /// The strongly connected components are separated by the cut arcs.
    432466  ///
    433   /// \param graph The graph.
    434   /// \retval cutMap A writable node map. The values will be set true when the
    435   /// arc is a cut arc.
    436   ///
    437   /// \return The number of cut arcs
     467  /// \param digraph The digraph.
     468  /// \retval cutMap A writable arc map. The values will be set to \c true
     469  /// for the cut arcs (exactly once for each cut arc), and will not be
     470  /// changed for other arcs.
     471  /// \return The number of cut arcs.
     472  ///
     473  /// \see stronglyConnected(), stronglyConnectedComponents()
    438474  template <typename Digraph, typename ArcMap>
    439   int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
     475  int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
    440476    checkConcept<concepts::Digraph, Digraph>();
    441477    typedef typename Digraph::Node Node;
     
    449485    typedef typename Container::iterator Iterator;
    450486
    451     Container nodes(countNodes(graph));
     487    Container nodes(countNodes(digraph));
    452488    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
    453489    Visitor visitor(nodes.begin());
    454490
    455     DfsVisit<Digraph, Visitor> dfs(graph, visitor);
     491    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
    456492    dfs.init();
    457     for (NodeIt it(graph); it != INVALID; ++it) {
     493    for (NodeIt it(digraph); it != INVALID; ++it) {
    458494      if (!dfs.reached(it)) {
    459495        dfs.addSource(it);
     
    465501    typedef ReverseDigraph<const Digraph> RDigraph;
    466502
    467     RDigraph rgraph(graph);
     503    RDigraph rdigraph(digraph);
    468504
    469505    int cutNum = 0;
    470506
    471507    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
    472     RVisitor rvisitor(rgraph, cutMap, cutNum);
    473 
    474     DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
     508    RVisitor rvisitor(rdigraph, cutMap, cutNum);
     509
     510    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
    475511
    476512    rdfs.init();
     
    707743  /// \ingroup graph_properties
    708744  ///
    709   /// \brief Checks the graph is bi-node-connected.
    710   ///
    711   /// This function checks that the undirected graph is bi-node-connected
    712   /// graph. The graph is bi-node-connected if any two undirected edge is
    713   /// on same circle.
    714   ///
    715   /// \param graph The graph.
    716   /// \return \c true when the graph bi-node-connected.
     745  /// \brief Check whether an undirected graph is bi-node-connected.
     746  ///
     747  /// This function checks whether the given undirected graph is
     748  /// bi-node-connected, i.e. any two edges are on same circle.
     749  ///
     750  /// \return \c true if the graph bi-node-connected.
     751  /// \note By definition, the empty graph is bi-node-connected.
     752  ///
     753  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
    717754  template <typename Graph>
    718755  bool biNodeConnected(const Graph& graph) {
     
    722759  /// \ingroup graph_properties
    723760  ///
    724   /// \brief Count the biconnected components.
    725   ///
    726   /// This function finds the bi-node-connected components in an undirected
    727   /// graph. The biconnected components are the classes of an equivalence
    728   /// relation on the undirected edges. Two undirected edge is in relationship
    729   /// when they are on same circle.
    730   ///
    731   /// \param graph The graph.
    732   /// \return The number of components.
     761  /// \brief Count the number of bi-node-connected components of an
     762  /// undirected graph.
     763  ///
     764  /// This function counts the number of bi-node-connected components of
     765  /// the given undirected graph.
     766  ///
     767  /// The bi-node-connected components are the classes of an equivalence
     768  /// relation on the edges of a undirected graph. Two edges are in the
     769  /// same class if they are on same circle.
     770  ///
     771  /// \return The number of bi-node-connected components.
     772  ///
     773  /// \see biNodeConnected(), biNodeConnectedComponents()
    733774  template <typename Graph>
    734775  int countBiNodeConnectedComponents(const Graph& graph) {
     
    757798  /// \ingroup graph_properties
    758799  ///
    759   /// \brief Find the bi-node-connected components.
    760   ///
    761   /// This function finds the bi-node-connected components in an undirected
    762   /// graph. The bi-node-connected components are the classes of an equivalence
    763   /// relation on the undirected edges. Two undirected edge are in relationship
    764   /// when they are on same circle.
     800  /// \brief Find the bi-node-connected components of an undirected graph.
     801  ///
     802  /// This function finds the bi-node-connected components of the given
     803  /// undirected graph.
     804  ///
     805  /// The bi-node-connected components are the classes of an equivalence
     806  /// relation on the edges of a undirected graph. Two edges are in the
     807  /// same class if they are on same circle.
    765808  ///
    766809  /// \image html node_biconnected_components.png
    767810  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
    768811  ///
    769   /// \param graph The graph.
    770   /// \retval compMap A writable uedge map. The values will be set from 0
    771   /// to the number of the biconnected components minus one. Each values
    772   /// of the map will be set exactly once, the values of a certain component
    773   /// will be set continuously.
    774   /// \return The number of components.
     812  /// \param graph The undirected graph.
     813  /// \retval compMap A writable edge map. The values will be set from 0
     814  /// to the number of the bi-node-connected components minus one. Each
     815  /// value of the map will be set exactly once, and the values of a
     816  /// certain component will be set continuously.
     817  /// \return The number of bi-node-connected components.
     818  ///
     819  /// \see biNodeConnected(), countBiNodeConnectedComponents()
    775820  template <typename Graph, typename EdgeMap>
    776821  int biNodeConnectedComponents(const Graph& graph,
     
    802847  /// \ingroup graph_properties
    803848  ///
    804   /// \brief Find the bi-node-connected cut nodes.
    805   ///
    806   /// This function finds the bi-node-connected cut nodes in an undirected
    807   /// graph. The bi-node-connected components are the classes of an equivalence
    808   /// relation on the undirected edges. Two undirected edges are in
    809   /// relationship when they are on same circle. The biconnected components
    810   /// are separted by nodes which are the cut nodes of the components.
    811   ///
    812   /// \param graph The graph.
    813   /// \retval cutMap A writable edge map. The values will be set true when
    814   /// the node separate two or more components.
     849  /// \brief Find the bi-node-connected cut nodes in an undirected graph.
     850  ///
     851  /// This function finds the bi-node-connected cut nodes in the given
     852  /// undirected graph.
     853  ///
     854  /// The bi-node-connected components are the classes of an equivalence
     855  /// relation on the edges of a undirected graph. Two edges are in the
     856  /// same class if they are on same circle.
     857  /// The bi-node-connected components are separted by the cut nodes of
     858  /// the components.
     859  ///
     860  /// \param graph The undirected graph.
     861  /// \retval cutMap A writable node map. The values will be set to
     862  /// \c true for the nodes that separate two or more components
     863  /// (exactly once for each cut node), and will not be changed for
     864  /// other nodes.
    815865  /// \return The number of the cut nodes.
     866  ///
     867  /// \see biNodeConnected(), biNodeConnectedComponents()
    816868  template <typename Graph, typename NodeMap>
    817869  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
     
    10321084  /// \ingroup graph_properties
    10331085  ///
    1034   /// \brief Checks that the graph is bi-edge-connected.
    1035   ///
    1036   /// This function checks that the graph is bi-edge-connected. The undirected
    1037   /// graph is bi-edge-connected when any two nodes are connected with two
    1038   /// edge-disjoint paths.
    1039   ///
    1040   /// \param graph The undirected graph.
    1041   /// \return The number of components.
     1086  /// \brief Check whether an undirected graph is bi-edge-connected.
     1087  ///
     1088  /// This function checks whether the given undirected graph is
     1089  /// bi-edge-connected, i.e. any two nodes are connected with at least
     1090  /// two edge-disjoint paths.
     1091  ///
     1092  /// \return \c true if the graph is bi-edge-connected.
     1093  /// \note By definition, the empty graph is bi-edge-connected.
     1094  ///
     1095  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
    10421096  template <typename Graph>
    10431097  bool biEdgeConnected(const Graph& graph) {
     
    10471101  /// \ingroup graph_properties
    10481102  ///
    1049   /// \brief Count the bi-edge-connected components.
    1050   ///
    1051   /// This function count the bi-edge-connected components in an undirected
    1052   /// graph. The bi-edge-connected components are the classes of an equivalence
    1053   /// relation on the nodes. Two nodes are in relationship when they are
    1054   /// connected with at least two edge-disjoint paths.
    1055   ///
    1056   /// \param graph The undirected graph.
    1057   /// \return The number of components.
     1103  /// \brief Count the number of bi-edge-connected components of an
     1104  /// undirected graph.
     1105  ///
     1106  /// This function counts the number of bi-edge-connected components of
     1107  /// the given undirected graph.
     1108  ///
     1109  /// The bi-edge-connected components are the classes of an equivalence
     1110  /// relation on the nodes of an undirected graph. Two nodes are in the
     1111  /// same class if they are connected with at least two edge-disjoint
     1112  /// paths.
     1113  ///
     1114  /// \return The number of bi-edge-connected components.
     1115  ///
     1116  /// \see biEdgeConnected(), biEdgeConnectedComponents()
    10581117  template <typename Graph>
    10591118  int countBiEdgeConnectedComponents(const Graph& graph) {
     
    10821141  /// \ingroup graph_properties
    10831142  ///
    1084   /// \brief Find the bi-edge-connected components.
    1085   ///
    1086   /// This function finds the bi-edge-connected components in an undirected
    1087   /// graph. The bi-edge-connected components are the classes of an equivalence
    1088   /// relation on the nodes. Two nodes are in relationship when they are
    1089   /// connected at least two edge-disjoint paths.
     1143  /// \brief Find the bi-edge-connected components of an undirected graph.
     1144  ///
     1145  /// This function finds the bi-edge-connected components of the given
     1146  /// undirected graph.
     1147  ///
     1148  /// The bi-edge-connected components are the classes of an equivalence
     1149  /// relation on the nodes of an undirected graph. Two nodes are in the
     1150  /// same class if they are connected with at least two edge-disjoint
     1151  /// paths.
    10901152  ///
    10911153  /// \image html edge_biconnected_components.png
    10921154  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    10931155  ///
    1094   /// \param graph The graph.
     1156  /// \param graph The undirected graph.
    10951157  /// \retval compMap A writable node map. The values will be set from 0 to
    1096   /// the number of the biconnected components minus one. Each values
    1097   /// of the map will be set exactly once, the values of a certain component
    1098   /// will be set continuously.
    1099   /// \return The number of components.
     1158  /// the number of the bi-edge-connected components minus one. Each value
     1159  /// of the map will be set exactly once, and the values of a certain
     1160  /// component will be set continuously.
     1161  /// \return The number of bi-edge-connected components.
     1162  ///
     1163  /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
    11001164  template <typename Graph, typename NodeMap>
    11011165  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
     
    11261190  /// \ingroup graph_properties
    11271191  ///
    1128   /// \brief Find the bi-edge-connected cut edges.
    1129   ///
    1130   /// This function finds the bi-edge-connected components in an undirected
    1131   /// graph. The bi-edge-connected components are the classes of an equivalence
    1132   /// relation on the nodes. Two nodes are in relationship when they are
    1133   /// connected with at least two edge-disjoint paths. The bi-edge-connected
    1134   /// components are separted by edges which are the cut edges of the
    1135   /// components.
    1136   ///
    1137   /// \param graph The graph.
    1138   /// \retval cutMap A writable node map. The values will be set true when the
    1139   /// edge is a cut edge.
     1192  /// \brief Find the bi-edge-connected cut edges in an undirected graph.
     1193  ///
     1194  /// This function finds the bi-edge-connected cut edges in the given
     1195  /// undirected graph.
     1196  ///
     1197  /// The bi-edge-connected components are the classes of an equivalence
     1198  /// relation on the nodes of an undirected graph. Two nodes are in the
     1199  /// same class if they are connected with at least two edge-disjoint
     1200  /// paths.
     1201  /// The bi-edge-connected components are separted by the cut edges of
     1202  /// the components.
     1203  ///
     1204  /// \param graph The undirected graph.
     1205  /// \retval cutMap A writable edge map. The values will be set to \c true
     1206  /// for the cut edges (exactly once for each cut edge), and will not be
     1207  /// changed for other edges.
    11401208  /// \return The number of cut edges.
     1209  ///
     1210  /// \see biEdgeConnected(), biEdgeConnectedComponents()
    11411211  template <typename Graph, typename EdgeMap>
    11421212  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
     
    11901260  /// \ingroup graph_properties
    11911261  ///
    1192   /// \brief Sort the nodes of a DAG into topolgical order.
    1193   ///
    1194   /// Sort the nodes of a DAG into topolgical order.
    1195   ///
    1196   /// \param graph The graph. It must be directed and acyclic.
    1197   /// \retval order A writable node map. The values will be set from 0 to
    1198   /// the number of the nodes in the graph minus one. Each values of the map
    1199   /// will be set exactly once, the values  will be set descending order.
    1200   ///
    1201   /// \see checkedTopologicalSort
    1202   /// \see dag
    1203   template <typename Digraph, typename NodeMap>
    1204   void topologicalSort(const Digraph& graph, NodeMap& order) {
    1205     using namespace _connectivity_bits;
     1262  /// \brief Check whether a digraph is DAG.
     1263  ///
     1264  /// This function checks whether the given digraph is DAG, i.e.
     1265  /// \e Directed \e Acyclic \e Graph.
     1266  /// \return \c true if there is no directed cycle in the digraph.
     1267  /// \see acyclic()
     1268  template <typename Digraph>
     1269  bool dag(const Digraph& digraph) {
    12061270
    12071271    checkConcept<concepts::Digraph, Digraph>();
    1208     checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
    12091272
    12101273    typedef typename Digraph::Node Node;
     
    12121275    typedef typename Digraph::Arc Arc;
    12131276
     1277    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
     1278
     1279    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
     1280      Create dfs(digraph);
     1281
     1282    ProcessedMap processed(digraph);
     1283    dfs.processedMap(processed);
     1284
     1285    dfs.init();
     1286    for (NodeIt it(digraph); it != INVALID; ++it) {
     1287      if (!dfs.reached(it)) {
     1288        dfs.addSource(it);
     1289        while (!dfs.emptyQueue()) {
     1290          Arc arc = dfs.nextArc();
     1291          Node target = digraph.target(arc);
     1292          if (dfs.reached(target) && !processed[target]) {
     1293            return false;
     1294          }
     1295          dfs.processNextArc();
     1296        }
     1297      }
     1298    }
     1299    return true;
     1300  }
     1301
     1302  /// \ingroup graph_properties
     1303  ///
     1304  /// \brief Sort the nodes of a DAG into topolgical order.
     1305  ///
     1306  /// This function sorts the nodes of the given acyclic digraph (DAG)
     1307  /// into topolgical order.
     1308  ///
     1309  /// \param digraph The digraph, which must be DAG.
     1310  /// \retval order A writable node map. The values will be set from 0 to
     1311  /// the number of the nodes in the digraph minus one. Each value of the
     1312  /// map will be set exactly once, and the values will be set descending
     1313  /// order.
     1314  ///
     1315  /// \see dag(), checkedTopologicalSort()
     1316  template <typename Digraph, typename NodeMap>
     1317  void topologicalSort(const Digraph& digraph, NodeMap& order) {
     1318    using namespace _connectivity_bits;
     1319
     1320    checkConcept<concepts::Digraph, Digraph>();
     1321    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
     1322
     1323    typedef typename Digraph::Node Node;
     1324    typedef typename Digraph::NodeIt NodeIt;
     1325    typedef typename Digraph::Arc Arc;
     1326
    12141327    TopologicalSortVisitor<Digraph, NodeMap>
    1215       visitor(order, countNodes(graph));
     1328      visitor(order, countNodes(digraph));
    12161329
    12171330    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
    1218       dfs(graph, visitor);
     1331      dfs(digraph, visitor);
    12191332
    12201333    dfs.init();
    1221     for (NodeIt it(graph); it != INVALID; ++it) {
     1334    for (NodeIt it(digraph); it != INVALID; ++it) {
    12221335      if (!dfs.reached(it)) {
    12231336        dfs.addSource(it);
     
    12311344  /// \brief Sort the nodes of a DAG into topolgical order.
    12321345  ///
    1233   /// Sort the nodes of a DAG into topolgical order. It also checks
    1234   /// that the given graph is DAG.
    1235   ///
    1236   /// \param digraph The graph. It must be directed and acyclic.
    1237   /// \retval order A readable - writable node map. The values will be set
    1238   /// from 0 to the number of the nodes in the graph minus one. Each values
    1239   /// of the map will be set exactly once, the values will be set descending
    1240   /// order.
    1241   /// \return \c false when the graph is not DAG.
    1242   ///
    1243   /// \see topologicalSort
    1244   /// \see dag
     1346  /// This function sorts the nodes of the given acyclic digraph (DAG)
     1347  /// into topolgical order and also checks whether the given digraph
     1348  /// is DAG.
     1349  ///
     1350  /// \param digraph The digraph.
     1351  /// \retval order A readable and writable node map. The values will be
     1352  /// set from 0 to the number of the nodes in the digraph minus one.
     1353  /// Each value of the map will be set exactly once, and the values will
     1354  /// be set descending order.
     1355  /// \return \c false if the digraph is not DAG.
     1356  ///
     1357  /// \see dag(), topologicalSort()
    12451358  template <typename Digraph, typename NodeMap>
    12461359  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
     
    12841397  /// \ingroup graph_properties
    12851398  ///
    1286   /// \brief Check that the given directed graph is a DAG.
    1287   ///
    1288   /// Check that the given directed graph is a DAG. The DAG is
    1289   /// an Directed Acyclic Digraph.
    1290   /// \return \c false when the graph is not DAG.
    1291   /// \see acyclic
    1292   template <typename Digraph>
    1293   bool dag(const Digraph& digraph) {
    1294 
    1295     checkConcept<concepts::Digraph, Digraph>();
    1296 
    1297     typedef typename Digraph::Node Node;
    1298     typedef typename Digraph::NodeIt NodeIt;
    1299     typedef typename Digraph::Arc Arc;
    1300 
    1301     typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    1302 
    1303     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
    1304       Create dfs(digraph);
    1305 
    1306     ProcessedMap processed(digraph);
    1307     dfs.processedMap(processed);
    1308 
    1309     dfs.init();
    1310     for (NodeIt it(digraph); it != INVALID; ++it) {
    1311       if (!dfs.reached(it)) {
    1312         dfs.addSource(it);
    1313         while (!dfs.emptyQueue()) {
    1314           Arc edge = dfs.nextArc();
    1315           Node target = digraph.target(edge);
    1316           if (dfs.reached(target) && !processed[target]) {
    1317             return false;
    1318           }
    1319           dfs.processNextArc();
    1320         }
    1321       }
    1322     }
    1323     return true;
    1324   }
    1325 
    1326   /// \ingroup graph_properties
    1327   ///
    1328   /// \brief Check that the given undirected graph is acyclic.
    1329   ///
    1330   /// Check that the given undirected graph acyclic.
    1331   /// \param graph The undirected graph.
    1332   /// \return \c true when there is no circle in the graph.
    1333   /// \see dag
     1399  /// \brief Check whether an undirected graph is acyclic.
     1400  ///
     1401  /// This function checks whether the given undirected graph is acyclic.
     1402  /// \return \c true if there is no cycle in the graph.
     1403  /// \see dag()
    13341404  template <typename Graph>
    13351405  bool acyclic(const Graph& graph) {
     
    13441414        dfs.addSource(it);
    13451415        while (!dfs.emptyQueue()) {
    1346           Arc edge = dfs.nextArc();
    1347           Node source = graph.source(edge);
    1348           Node target = graph.target(edge);
     1416          Arc arc = dfs.nextArc();
     1417          Node source = graph.source(arc);
     1418          Node target = graph.target(arc);
    13491419          if (dfs.reached(target) &&
    1350               dfs.predArc(source) != graph.oppositeArc(edge)) {
     1420              dfs.predArc(source) != graph.oppositeArc(arc)) {
    13511421            return false;
    13521422          }
     
    13601430  /// \ingroup graph_properties
    13611431  ///
    1362   /// \brief Check that the given undirected graph is tree.
    1363   ///
    1364   /// Check that the given undirected graph is tree.
    1365   /// \param graph The undirected graph.
    1366   /// \return \c true when the graph is acyclic and connected.
     1432  /// \brief Check whether an undirected graph is tree.
     1433  ///
     1434  /// This function checks whether the given undirected graph is tree.
     1435  /// \return \c true if the graph is acyclic and connected.
     1436  /// \see acyclic(), connected()
    13671437  template <typename Graph>
    13681438  bool tree(const Graph& graph) {
     
    13711441    typedef typename Graph::NodeIt NodeIt;
    13721442    typedef typename Graph::Arc Arc;
     1443    if (NodeIt(graph) == INVALID) return true;
    13731444    Dfs<Graph> dfs(graph);
    13741445    dfs.init();
    13751446    dfs.addSource(NodeIt(graph));
    13761447    while (!dfs.emptyQueue()) {
    1377       Arc edge = dfs.nextArc();
    1378       Node source = graph.source(edge);
    1379       Node target = graph.target(edge);
     1448      Arc arc = dfs.nextArc();
     1449      Node source = graph.source(arc);
     1450      Node target = graph.target(arc);
    13801451      if (dfs.reached(target) &&
    1381           dfs.predArc(source) != graph.oppositeArc(edge)) {
     1452          dfs.predArc(source) != graph.oppositeArc(arc)) {
    13821453        return false;
    13831454      }
     
    14521523  /// \ingroup graph_properties
    14531524  ///
    1454   /// \brief Check if the given undirected graph is bipartite or not
    1455   ///
    1456   /// The function checks if the given undirected \c graph graph is bipartite
    1457   /// or not. The \ref Bfs algorithm is used to calculate the result.
    1458   /// \param graph The undirected graph.
    1459   /// \return \c true if \c graph is bipartite, \c false otherwise.
    1460   /// \sa bipartitePartitions
     1525  /// \brief Check whether an undirected graph is bipartite.
     1526  ///
     1527  /// The function checks whether the given undirected graph is bipartite.
     1528  /// \return \c true if the graph is bipartite.
     1529  ///
     1530  /// \see bipartitePartitions()
    14611531  template<typename Graph>
    1462   inline bool bipartite(const Graph &graph){
     1532  bool bipartite(const Graph &graph){
    14631533    using namespace _connectivity_bits;
    14641534
     
    14891559  /// \ingroup graph_properties
    14901560  ///
    1491   /// \brief Check if the given undirected graph is bipartite or not
    1492   ///
    1493   /// The function checks if the given undirected graph is bipartite
    1494   /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
    1495   /// During the execution, the \c partMap will be set as the two
    1496   /// partitions of the graph.
     1561  /// \brief Find the bipartite partitions of an undirected graph.
     1562  ///
     1563  /// This function checks whether the given undirected graph is bipartite
     1564  /// and gives back the bipartite partitions.
    14971565  ///
    14981566  /// \image html bipartite_partitions.png
     
    15001568  ///
    15011569  /// \param graph The undirected graph.
    1502   /// \retval partMap A writable bool map of nodes. It will be set as the
    1503   /// two partitions of the graph.
    1504   /// \return \c true if \c graph is bipartite, \c false otherwise.
     1570  /// \retval partMap A writable node map of \c bool (or convertible) value
     1571  /// type. The values will be set to \c true for one component and
     1572  /// \c false for the other one.
     1573  /// \return \c true if the graph is bipartite, \c false otherwise.
     1574  ///
     1575  /// \see bipartite()
    15051576  template<typename Graph, typename NodeMap>
    1506   inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
     1577  bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
    15071578    using namespace _connectivity_bits;
    15081579
    15091580    checkConcept<concepts::Graph, Graph>();
     1581    checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
    15101582
    15111583    typedef typename Graph::Node Node;
     
    15321604  }
    15331605
    1534   /// \brief Returns true when there are not loop edges in the graph.
    1535   ///
    1536   /// Returns true when there are not loop edges in the graph.
    1537   template <typename Digraph>
    1538   bool loopFree(const Digraph& digraph) {
    1539     for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
    1540       if (digraph.source(it) == digraph.target(it)) return false;
     1606  /// \ingroup graph_properties
     1607  ///
     1608  /// \brief Check whether the given graph contains no loop arcs/edges.
     1609  ///
     1610  /// This function returns \c true if there are no loop arcs/edges in
     1611  /// the given graph. It works for both directed and undirected graphs.
     1612  template <typename Graph>
     1613  bool loopFree(const Graph& graph) {
     1614    for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
     1615      if (graph.source(it) == graph.target(it)) return false;
    15411616    }
    15421617    return true;
    15431618  }
    15441619
    1545   /// \brief Returns true when there are not parallel edges in the graph.
    1546   ///
    1547   /// Returns true when there are not parallel edges in the graph.
    1548   template <typename Digraph>
    1549   bool parallelFree(const Digraph& digraph) {
    1550     typename Digraph::template NodeMap<bool> reached(digraph, false);
    1551     for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
    1552       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1553         if (reached[digraph.target(a)]) return false;
    1554         reached.set(digraph.target(a), true);
    1555       }
    1556       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1557         reached.set(digraph.target(a), false);
    1558       }
     1620  /// \ingroup graph_properties
     1621  ///
     1622  /// \brief Check whether the given graph contains no parallel arcs/edges.
     1623  ///
     1624  /// This function returns \c true if there are no parallel arcs/edges in
     1625  /// the given graph. It works for both directed and undirected graphs.
     1626  template <typename Graph>
     1627  bool parallelFree(const Graph& graph) {
     1628    typename Graph::template NodeMap<int> reached(graph, 0);
     1629    int cnt = 1;
     1630    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
     1631      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
     1632        if (reached[graph.target(a)] == cnt) return false;
     1633        reached[graph.target(a)] = cnt;
     1634      }
     1635      ++cnt;
    15591636    }
    15601637    return true;
    15611638  }
    15621639
    1563   /// \brief Returns true when there are not loop edges and parallel
    1564   /// edges in the graph.
    1565   ///
    1566   /// Returns true when there are not loop edges and parallel edges in
    1567   /// the graph.
    1568   template <typename Digraph>
    1569   bool simpleDigraph(const Digraph& digraph) {
    1570     typename Digraph::template NodeMap<bool> reached(digraph, false);
    1571     for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
    1572       reached.set(n, true);
    1573       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1574         if (reached[digraph.target(a)]) return false;
    1575         reached.set(digraph.target(a), true);
    1576       }
    1577       for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1578         reached.set(digraph.target(a), false);
    1579       }
    1580       reached.set(n, false);
     1640  /// \ingroup graph_properties
     1641  ///
     1642  /// \brief Check whether the given graph is simple.
     1643  ///
     1644  /// This function returns \c true if the given graph is simple, i.e.
     1645  /// it contains no loop arcs/edges and no parallel arcs/edges.
     1646  /// The function works for both directed and undirected graphs.
     1647  /// \see loopFree(), parallelFree()
     1648  template <typename Graph>
     1649  bool simpleGraph(const Graph& graph) {
     1650    typename Graph::template NodeMap<int> reached(graph, 0);
     1651    int cnt = 1;
     1652    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
     1653      reached[n] = cnt;
     1654      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
     1655        if (reached[graph.target(a)] == cnt) return false;
     1656        reached[graph.target(a)] = cnt;
     1657      }
     1658      ++cnt;
    15811659    }
    15821660    return true;
  • lemon/euler.h

    r639 r695  
    245245
    246246
    247   ///Check if the given graph is \e Eulerian
     247  ///Check if the given graph is Eulerian
    248248
    249249  /// \ingroup graph_properties
    250   ///This function checks if the given graph is \e Eulerian.
     250  ///This function checks if the given graph is Eulerian.
    251251  ///It works for both directed and undirected graphs.
    252252  ///
  • lemon/matching.h

    r641 r698  
    500500    /// This function runs the original Edmonds' algorithm.
    501501    ///
    502     /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
     502    /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
    503503    /// called before using this function.
    504504    void startSparse() {
     
    519519    /// shrinks, therefore resulting in a faster algorithm for dense graphs.
    520520    ///
    521     /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
     521    /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
    522522    /// called before using this function.
    523523    void startDense() {
  • test/CMakeLists.txt

    r674 r696  
    1010  bfs_test
    1111  circulation_test
     12  connectivity_test
    1213  counter_test
    1314  dfs_test
  • test/Makefile.am

    r658 r696  
    1010        test/bfs_test \
    1111        test/circulation_test \
     12        test/connectivity_test \
    1213        test/counter_test \
    1314        test/dfs_test \
     
    5556test_circulation_test_SOURCES = test/circulation_test.cc
    5657test_counter_test_SOURCES = test/counter_test.cc
     58test_connectivity_test_SOURCES = test/connectivity_test.cc
    5759test_dfs_test_SOURCES = test/dfs_test.cc
    5860test_digraph_test_SOURCES = test/digraph_test.cc
Note: See TracChangeset for help on using the changeset viewer.