COIN-OR::LEMON - Graph Library

Changes in / [651:3adf5e2d1e62:652:e2f99a473998] in lemon-main


Ignore:
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/connectivity.h

    r586 r648  
    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

    r592 r648  
    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  ///
  • test/CMakeLists.txt

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

    r611 r649  
    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.