lemon/connectivity.h
changeset 619 ec817dfc2cb7
parent 559 c5fd2d996909
child 647 dcba640438c7
equal deleted inserted replaced
4:11f76843d458 5:f94ea23f5613
    30 #include <lemon/concept_check.h>
    30 #include <lemon/concept_check.h>
    31 
    31 
    32 #include <stack>
    32 #include <stack>
    33 #include <functional>
    33 #include <functional>
    34 
    34 
    35 /// \ingroup connectivity
    35 /// \ingroup graph_properties
    36 /// \file
    36 /// \file
    37 /// \brief Connectivity algorithms
    37 /// \brief Connectivity algorithms
    38 ///
    38 ///
    39 /// Connectivity algorithms
    39 /// Connectivity algorithms
    40 
    40 
    41 namespace lemon {
    41 namespace lemon {
    42 
    42 
    43   /// \ingroup connectivity
    43   /// \ingroup graph_properties
    44   ///
    44   ///
    45   /// \brief Check whether the given undirected graph is connected.
    45   /// \brief Check whether the given undirected graph is connected.
    46   ///
    46   ///
    47   /// Check whether the given undirected graph is connected.
    47   /// Check whether the given undirected graph is connected.
    48   /// \param graph The undirected graph.
    48   /// \param graph The undirected graph.
    61       }
    61       }
    62     }
    62     }
    63     return true;
    63     return true;
    64   }
    64   }
    65 
    65 
    66   /// \ingroup connectivity
    66   /// \ingroup graph_properties
    67   ///
    67   ///
    68   /// \brief Count the number of connected components of an undirected graph
    68   /// \brief Count the number of connected components of an undirected graph
    69   ///
    69   ///
    70   /// Count the number of connected components of an undirected graph
    70   /// Count the number of connected components of an undirected graph
    71   ///
    71   ///
   103       }
   103       }
   104     }
   104     }
   105     return compNum;
   105     return compNum;
   106   }
   106   }
   107 
   107 
   108   /// \ingroup connectivity
   108   /// \ingroup graph_properties
   109   ///
   109   ///
   110   /// \brief Find the connected components of an undirected graph
   110   /// \brief Find the connected components of an undirected graph
   111   ///
   111   ///
   112   /// Find the connected components of an undirected graph.
   112   /// Find the connected components of an undirected graph.
       
   113   ///
       
   114   /// \image html connected_components.png
       
   115   /// \image latex connected_components.eps "Connected components" width=\textwidth
   113   ///
   116   ///
   114   /// \param graph The graph. It must be undirected.
   117   /// \param graph The graph. It must be undirected.
   115   /// \retval compMap A writable node map. The values will be set from 0 to
   118   /// \retval compMap A writable node map. The values will be set from 0 to
   116   /// the number of the connected components minus one. Each values of the map
   119   /// the number of the connected components minus one. Each values of the map
   117   /// will be set exactly once, the values of a certain component will be
   120   /// will be set exactly once, the values of a certain component will be
   118   /// set continuously.
   121   /// set continuously.
   119   /// \return The number of components
   122   /// \return The number of components
   120   ///
       
   121   template <class Graph, class NodeMap>
   123   template <class Graph, class NodeMap>
   122   int connectedComponents(const Graph &graph, NodeMap &compMap) {
   124   int connectedComponents(const Graph &graph, NodeMap &compMap) {
   123     checkConcept<concepts::Graph, Graph>();
   125     checkConcept<concepts::Graph, Graph>();
   124     typedef typename Graph::Node Node;
   126     typedef typename Graph::Node Node;
   125     typedef typename Graph::Arc Arc;
   127     typedef typename Graph::Arc Arc;
   225     };
   227     };
   226 
   228 
   227   }
   229   }
   228 
   230 
   229 
   231 
   230   /// \ingroup connectivity
   232   /// \ingroup graph_properties
   231   ///
   233   ///
   232   /// \brief Check whether the given directed graph is strongly connected.
   234   /// \brief Check whether the given directed graph is strongly connected.
   233   ///
   235   ///
   234   /// Check whether the given directed graph is strongly connected. The
   236   /// Check whether the given directed graph is strongly connected. The
   235   /// graph is strongly connected when any two nodes of the graph are
   237   /// graph is strongly connected when any two nodes of the graph are
   283     }
   285     }
   284 
   286 
   285     return true;
   287     return true;
   286   }
   288   }
   287 
   289 
   288   /// \ingroup connectivity
   290   /// \ingroup graph_properties
   289   ///
   291   ///
   290   /// \brief Count the strongly connected components of a directed graph
   292   /// \brief Count the strongly connected components of a directed graph
   291   ///
   293   ///
   292   /// Count the strongly connected components of a directed graph.
   294   /// Count the strongly connected components of a directed graph.
   293   /// The strongly connected components are the classes of an
   295   /// The strongly connected components are the classes of an
   347       }
   349       }
   348     }
   350     }
   349     return compNum;
   351     return compNum;
   350   }
   352   }
   351 
   353 
   352   /// \ingroup connectivity
   354   /// \ingroup graph_properties
   353   ///
   355   ///
   354   /// \brief Find the strongly connected components of a directed graph
   356   /// \brief Find the strongly connected components of a directed graph
   355   ///
   357   ///
   356   /// Find the strongly connected components of a directed graph.  The
   358   /// Find the strongly connected components of a directed graph.  The
   357   /// strongly connected components are the classes of an equivalence
   359   /// strongly connected components are the classes of an equivalence
   359   /// relationship when there are directed paths between them in both
   361   /// relationship when there are directed paths between them in both
   360   /// direction. In addition, the numbering of components will satisfy
   362   /// direction. In addition, the numbering of components will satisfy
   361   /// that there is no arc going from a higher numbered component to
   363   /// that there is no arc going from a higher numbered component to
   362   /// a lower.
   364   /// a lower.
   363   ///
   365   ///
       
   366   /// \image html strongly_connected_components.png
       
   367   /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
       
   368   ///
   364   /// \param digraph The digraph.
   369   /// \param digraph The digraph.
   365   /// \retval compMap A writable node map. The values will be set from 0 to
   370   /// \retval compMap A writable node map. The values will be set from 0 to
   366   /// the number of the strongly connected components minus one. Each value
   371   /// the number of the strongly connected components minus one. Each value
   367   /// of the map will be set exactly once, the values of a certain component
   372   /// of the map will be set exactly once, the values of a certain component
   368   /// will be set continuously.
   373   /// will be set continuously.
   369   /// \return The number of components
   374   /// \return The number of components
   370   ///
       
   371   template <typename Digraph, typename NodeMap>
   375   template <typename Digraph, typename NodeMap>
   372   int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
   376   int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
   373     checkConcept<concepts::Digraph, Digraph>();
   377     checkConcept<concepts::Digraph, Digraph>();
   374     typedef typename Digraph::Node Node;
   378     typedef typename Digraph::Node Node;
   375     typedef typename Digraph::NodeIt NodeIt;
   379     typedef typename Digraph::NodeIt NodeIt;
   414       }
   418       }
   415     }
   419     }
   416     return compNum;
   420     return compNum;
   417   }
   421   }
   418 
   422 
   419   /// \ingroup connectivity
   423   /// \ingroup graph_properties
   420   ///
   424   ///
   421   /// \brief Find the cut arcs of the strongly connected components.
   425   /// \brief Find the cut arcs of the strongly connected components.
   422   ///
   426   ///
   423   /// Find the cut arcs of the strongly connected components.
   427   /// Find the cut arcs of the strongly connected components.
   424   /// The strongly connected components are the classes of an equivalence
   428   /// The strongly connected components are the classes of an equivalence
   698   }
   702   }
   699 
   703 
   700   template <typename Graph>
   704   template <typename Graph>
   701   int countBiNodeConnectedComponents(const Graph& graph);
   705   int countBiNodeConnectedComponents(const Graph& graph);
   702 
   706 
   703   /// \ingroup connectivity
   707   /// \ingroup graph_properties
   704   ///
   708   ///
   705   /// \brief Checks the graph is bi-node-connected.
   709   /// \brief Checks the graph is bi-node-connected.
   706   ///
   710   ///
   707   /// This function checks that the undirected graph is bi-node-connected
   711   /// This function checks that the undirected graph is bi-node-connected
   708   /// graph. The graph is bi-node-connected if any two undirected edge is
   712   /// graph. The graph is bi-node-connected if any two undirected edge is
   713   template <typename Graph>
   717   template <typename Graph>
   714   bool biNodeConnected(const Graph& graph) {
   718   bool biNodeConnected(const Graph& graph) {
   715     return countBiNodeConnectedComponents(graph) <= 1;
   719     return countBiNodeConnectedComponents(graph) <= 1;
   716   }
   720   }
   717 
   721 
   718   /// \ingroup connectivity
   722   /// \ingroup graph_properties
   719   ///
   723   ///
   720   /// \brief Count the biconnected components.
   724   /// \brief Count the biconnected components.
   721   ///
   725   ///
   722   /// This function finds the bi-node-connected components in an undirected
   726   /// This function finds the bi-node-connected components in an undirected
   723   /// graph. The biconnected components are the classes of an equivalence
   727   /// graph. The biconnected components are the classes of an equivalence
   748       }
   752       }
   749     }
   753     }
   750     return compNum;
   754     return compNum;
   751   }
   755   }
   752 
   756 
   753   /// \ingroup connectivity
   757   /// \ingroup graph_properties
   754   ///
   758   ///
   755   /// \brief Find the bi-node-connected components.
   759   /// \brief Find the bi-node-connected components.
   756   ///
   760   ///
   757   /// This function finds the bi-node-connected components in an undirected
   761   /// This function finds the bi-node-connected components in an undirected
   758   /// graph. The bi-node-connected components are the classes of an equivalence
   762   /// graph. The bi-node-connected components are the classes of an equivalence
   759   /// relation on the undirected edges. Two undirected edge are in relationship
   763   /// relation on the undirected edges. Two undirected edge are in relationship
   760   /// when they are on same circle.
   764   /// when they are on same circle.
       
   765   ///
       
   766   /// \image html node_biconnected_components.png
       
   767   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
   761   ///
   768   ///
   762   /// \param graph The graph.
   769   /// \param graph The graph.
   763   /// \retval compMap A writable uedge map. The values will be set from 0
   770   /// \retval compMap A writable uedge map. The values will be set from 0
   764   /// to the number of the biconnected components minus one. Each values
   771   /// to the number of the biconnected components minus one. Each values
   765   /// of the map will be set exactly once, the values of a certain component
   772   /// of the map will be set exactly once, the values of a certain component
   766   /// will be set continuously.
   773   /// will be set continuously.
   767   /// \return The number of components.
   774   /// \return The number of components.
   768   ///
       
   769   template <typename Graph, typename EdgeMap>
   775   template <typename Graph, typename EdgeMap>
   770   int biNodeConnectedComponents(const Graph& graph,
   776   int biNodeConnectedComponents(const Graph& graph,
   771                                 EdgeMap& compMap) {
   777                                 EdgeMap& compMap) {
   772     checkConcept<concepts::Graph, Graph>();
   778     checkConcept<concepts::Graph, Graph>();
   773     typedef typename Graph::NodeIt NodeIt;
   779     typedef typename Graph::NodeIt NodeIt;
   791       }
   797       }
   792     }
   798     }
   793     return compNum;
   799     return compNum;
   794   }
   800   }
   795 
   801 
   796   /// \ingroup connectivity
   802   /// \ingroup graph_properties
   797   ///
   803   ///
   798   /// \brief Find the bi-node-connected cut nodes.
   804   /// \brief Find the bi-node-connected cut nodes.
   799   ///
   805   ///
   800   /// This function finds the bi-node-connected cut nodes in an undirected
   806   /// This function finds the bi-node-connected cut nodes in an undirected
   801   /// graph. The bi-node-connected components are the classes of an equivalence
   807   /// graph. The bi-node-connected components are the classes of an equivalence
  1021   }
  1027   }
  1022 
  1028 
  1023   template <typename Graph>
  1029   template <typename Graph>
  1024   int countBiEdgeConnectedComponents(const Graph& graph);
  1030   int countBiEdgeConnectedComponents(const Graph& graph);
  1025 
  1031 
  1026   /// \ingroup connectivity
  1032   /// \ingroup graph_properties
  1027   ///
  1033   ///
  1028   /// \brief Checks that the graph is bi-edge-connected.
  1034   /// \brief Checks that the graph is bi-edge-connected.
  1029   ///
  1035   ///
  1030   /// This function checks that the graph is bi-edge-connected. The undirected
  1036   /// This function checks that the graph is bi-edge-connected. The undirected
  1031   /// graph is bi-edge-connected when any two nodes are connected with two
  1037   /// graph is bi-edge-connected when any two nodes are connected with two
  1036   template <typename Graph>
  1042   template <typename Graph>
  1037   bool biEdgeConnected(const Graph& graph) {
  1043   bool biEdgeConnected(const Graph& graph) {
  1038     return countBiEdgeConnectedComponents(graph) <= 1;
  1044     return countBiEdgeConnectedComponents(graph) <= 1;
  1039   }
  1045   }
  1040 
  1046 
  1041   /// \ingroup connectivity
  1047   /// \ingroup graph_properties
  1042   ///
  1048   ///
  1043   /// \brief Count the bi-edge-connected components.
  1049   /// \brief Count the bi-edge-connected components.
  1044   ///
  1050   ///
  1045   /// This function count the bi-edge-connected components in an undirected
  1051   /// This function count the bi-edge-connected components in an undirected
  1046   /// graph. The bi-edge-connected components are the classes of an equivalence
  1052   /// graph. The bi-edge-connected components are the classes of an equivalence
  1071       }
  1077       }
  1072     }
  1078     }
  1073     return compNum;
  1079     return compNum;
  1074   }
  1080   }
  1075 
  1081 
  1076   /// \ingroup connectivity
  1082   /// \ingroup graph_properties
  1077   ///
  1083   ///
  1078   /// \brief Find the bi-edge-connected components.
  1084   /// \brief Find the bi-edge-connected components.
  1079   ///
  1085   ///
  1080   /// This function finds the bi-edge-connected components in an undirected
  1086   /// This function finds the bi-edge-connected components in an undirected
  1081   /// graph. The bi-edge-connected components are the classes of an equivalence
  1087   /// graph. The bi-edge-connected components are the classes of an equivalence
  1082   /// relation on the nodes. Two nodes are in relationship when they are
  1088   /// relation on the nodes. Two nodes are in relationship when they are
  1083   /// connected at least two edge-disjoint paths.
  1089   /// connected at least two edge-disjoint paths.
       
  1090   ///
       
  1091   /// \image html edge_biconnected_components.png
       
  1092   /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
  1084   ///
  1093   ///
  1085   /// \param graph The graph.
  1094   /// \param graph The graph.
  1086   /// \retval compMap A writable node map. The values will be set from 0 to
  1095   /// \retval compMap A writable node map. The values will be set from 0 to
  1087   /// the number of the biconnected components minus one. Each values
  1096   /// the number of the biconnected components minus one. Each values
  1088   /// of the map will be set exactly once, the values of a certain component
  1097   /// of the map will be set exactly once, the values of a certain component
  1089   /// will be set continuously.
  1098   /// will be set continuously.
  1090   /// \return The number of components.
  1099   /// \return The number of components.
  1091   ///
       
  1092   template <typename Graph, typename NodeMap>
  1100   template <typename Graph, typename NodeMap>
  1093   int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
  1101   int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
  1094     checkConcept<concepts::Graph, Graph>();
  1102     checkConcept<concepts::Graph, Graph>();
  1095     typedef typename Graph::NodeIt NodeIt;
  1103     typedef typename Graph::NodeIt NodeIt;
  1096     typedef typename Graph::Node Node;
  1104     typedef typename Graph::Node Node;
  1113       }
  1121       }
  1114     }
  1122     }
  1115     return compNum;
  1123     return compNum;
  1116   }
  1124   }
  1117 
  1125 
  1118   /// \ingroup connectivity
  1126   /// \ingroup graph_properties
  1119   ///
  1127   ///
  1120   /// \brief Find the bi-edge-connected cut edges.
  1128   /// \brief Find the bi-edge-connected cut edges.
  1121   ///
  1129   ///
  1122   /// This function finds the bi-edge-connected components in an undirected
  1130   /// This function finds the bi-edge-connected components in an undirected
  1123   /// graph. The bi-edge-connected components are the classes of an equivalence
  1131   /// graph. The bi-edge-connected components are the classes of an equivalence
  1177       int _num;
  1185       int _num;
  1178     };
  1186     };
  1179 
  1187 
  1180   }
  1188   }
  1181 
  1189 
  1182   /// \ingroup connectivity
  1190   /// \ingroup graph_properties
  1183   ///
  1191   ///
  1184   /// \brief Sort the nodes of a DAG into topolgical order.
  1192   /// \brief Sort the nodes of a DAG into topolgical order.
  1185   ///
  1193   ///
  1186   /// Sort the nodes of a DAG into topolgical order.
  1194   /// Sort the nodes of a DAG into topolgical order.
  1187   ///
  1195   ///
  1216         dfs.start();
  1224         dfs.start();
  1217       }
  1225       }
  1218     }
  1226     }
  1219   }
  1227   }
  1220 
  1228 
  1221   /// \ingroup connectivity
  1229   /// \ingroup graph_properties
  1222   ///
  1230   ///
  1223   /// \brief Sort the nodes of a DAG into topolgical order.
  1231   /// \brief Sort the nodes of a DAG into topolgical order.
  1224   ///
  1232   ///
  1225   /// Sort the nodes of a DAG into topolgical order. It also checks
  1233   /// Sort the nodes of a DAG into topolgical order. It also checks
  1226   /// that the given graph is DAG.
  1234   /// that the given graph is DAG.
  1271       }
  1279       }
  1272     }
  1280     }
  1273     return true;
  1281     return true;
  1274   }
  1282   }
  1275 
  1283 
  1276   /// \ingroup connectivity
  1284   /// \ingroup graph_properties
  1277   ///
  1285   ///
  1278   /// \brief Check that the given directed graph is a DAG.
  1286   /// \brief Check that the given directed graph is a DAG.
  1279   ///
  1287   ///
  1280   /// Check that the given directed graph is a DAG. The DAG is
  1288   /// Check that the given directed graph is a DAG. The DAG is
  1281   /// an Directed Acyclic Digraph.
  1289   /// an Directed Acyclic Digraph.
  1313       }
  1321       }
  1314     }
  1322     }
  1315     return true;
  1323     return true;
  1316   }
  1324   }
  1317 
  1325 
  1318   /// \ingroup connectivity
  1326   /// \ingroup graph_properties
  1319   ///
  1327   ///
  1320   /// \brief Check that the given undirected graph is acyclic.
  1328   /// \brief Check that the given undirected graph is acyclic.
  1321   ///
  1329   ///
  1322   /// Check that the given undirected graph acyclic.
  1330   /// Check that the given undirected graph acyclic.
  1323   /// \param graph The undirected graph.
  1331   /// \param graph The undirected graph.
  1347       }
  1355       }
  1348     }
  1356     }
  1349     return true;
  1357     return true;
  1350   }
  1358   }
  1351 
  1359 
  1352   /// \ingroup connectivity
  1360   /// \ingroup graph_properties
  1353   ///
  1361   ///
  1354   /// \brief Check that the given undirected graph is tree.
  1362   /// \brief Check that the given undirected graph is tree.
  1355   ///
  1363   ///
  1356   /// Check that the given undirected graph is tree.
  1364   /// Check that the given undirected graph is tree.
  1357   /// \param graph The undirected graph.
  1365   /// \param graph The undirected graph.
  1439       PartMap& _part;
  1447       PartMap& _part;
  1440       bool& _bipartite;
  1448       bool& _bipartite;
  1441     };
  1449     };
  1442   }
  1450   }
  1443 
  1451 
  1444   /// \ingroup connectivity
  1452   /// \ingroup graph_properties
  1445   ///
  1453   ///
  1446   /// \brief Check if the given undirected graph is bipartite or not
  1454   /// \brief Check if the given undirected graph is bipartite or not
  1447   ///
  1455   ///
  1448   /// The function checks if the given undirected \c graph graph is bipartite
  1456   /// The function checks if the given undirected \c graph graph is bipartite
  1449   /// or not. The \ref Bfs algorithm is used to calculate the result.
  1457   /// or not. The \ref Bfs algorithm is used to calculate the result.
  1476       }
  1484       }
  1477     }
  1485     }
  1478     return true;
  1486     return true;
  1479   }
  1487   }
  1480 
  1488 
  1481   /// \ingroup connectivity
  1489   /// \ingroup graph_properties
  1482   ///
  1490   ///
  1483   /// \brief Check if the given undirected graph is bipartite or not
  1491   /// \brief Check if the given undirected graph is bipartite or not
  1484   ///
  1492   ///
  1485   /// The function checks if the given undirected graph is bipartite
  1493   /// The function checks if the given undirected graph is bipartite
  1486   /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
  1494   /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
  1487   /// During the execution, the \c partMap will be set as the two
  1495   /// During the execution, the \c partMap will be set as the two
  1488   /// partitions of the graph.
  1496   /// partitions of the graph.
       
  1497   ///
       
  1498   /// \image html bipartite_partitions.png
       
  1499   /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
       
  1500   ///
  1489   /// \param graph The undirected graph.
  1501   /// \param graph The undirected graph.
  1490   /// \retval partMap A writable bool map of nodes. It will be set as the
  1502   /// \retval partMap A writable bool map of nodes. It will be set as the
  1491   /// two partitions of the graph.
  1503   /// two partitions of the graph.
  1492   /// \return \c true if \c graph is bipartite, \c false otherwise.
  1504   /// \return \c true if \c graph is bipartite, \c false otherwise.
  1493   template<typename Graph, typename NodeMap>
  1505   template<typename Graph, typename NodeMap>