lemon/connectivity.h
changeset 561 6e0525ec5355
parent 440 88ed40ad0d4f
child 586 7c12061bd271
equal deleted inserted replaced
3:bfed54e41820 4:11f76843d458
    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.
    49   /// \return %True when there is path between any two nodes in the graph.
    49   /// \return \c true when there is path between any two nodes in the graph.
    50   /// \note By definition, the empty graph is connected.
    50   /// \note By definition, the empty graph is connected.
    51   template <typename Graph>
    51   template <typename Graph>
    52   bool connected(const Graph& graph) {
    52   bool connected(const Graph& graph) {
    53     checkConcept<concepts::Graph, Graph>();
    53     checkConcept<concepts::Graph, Graph>();
    54     typedef typename Graph::NodeIt NodeIt;
    54     typedef typename Graph::NodeIt NodeIt;
   232   /// \brief Check whether the given directed graph is strongly connected.
   232   /// \brief Check whether the given directed graph is strongly connected.
   233   ///
   233   ///
   234   /// Check whether the given directed graph is strongly connected. The
   234   /// Check whether the given directed graph is strongly connected. The
   235   /// graph is strongly connected when any two nodes of the graph are
   235   /// graph is strongly connected when any two nodes of the graph are
   236   /// connected with directed paths in both direction.
   236   /// connected with directed paths in both direction.
   237   /// \return %False when the graph is not strongly connected.
   237   /// \return \c false when the graph is not strongly connected.
   238   /// \see connected
   238   /// \see connected
   239   ///
   239   ///
   240   /// \note By definition, the empty graph is strongly connected.
   240   /// \note By definition, the empty graph is strongly connected.
   241   template <typename Digraph>
   241   template <typename Digraph>
   242   bool stronglyConnected(const Digraph& digraph) {
   242   bool stronglyConnected(const Digraph& digraph) {
   707   /// This function checks that the undirected graph is bi-node-connected
   707   /// 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
   708   /// graph. The graph is bi-node-connected if any two undirected edge is
   709   /// on same circle.
   709   /// on same circle.
   710   ///
   710   ///
   711   /// \param graph The graph.
   711   /// \param graph The graph.
   712   /// \return %True when the graph bi-node-connected.
   712   /// \return \c true when the graph bi-node-connected.
   713   template <typename Graph>
   713   template <typename Graph>
   714   bool biNodeConnected(const Graph& graph) {
   714   bool biNodeConnected(const Graph& graph) {
   715     return countBiNodeConnectedComponents(graph) <= 1;
   715     return countBiNodeConnectedComponents(graph) <= 1;
   716   }
   716   }
   717 
   717 
  1228   /// \param digraph The graph. It must be directed and acyclic.
  1228   /// \param digraph The graph. It must be directed and acyclic.
  1229   /// \retval order A readable - writable node map. The values will be set
  1229   /// \retval order A readable - writable node map. The values will be set
  1230   /// from 0 to the number of the nodes in the graph minus one. Each values
  1230   /// from 0 to the number of the nodes in the graph minus one. Each values
  1231   /// of the map will be set exactly once, the values will be set descending
  1231   /// of the map will be set exactly once, the values will be set descending
  1232   /// order.
  1232   /// order.
  1233   /// \return %False when the graph is not DAG.
  1233   /// \return \c false when the graph is not DAG.
  1234   ///
  1234   ///
  1235   /// \see topologicalSort
  1235   /// \see topologicalSort
  1236   /// \see dag
  1236   /// \see dag
  1237   template <typename Digraph, typename NodeMap>
  1237   template <typename Digraph, typename NodeMap>
  1238   bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
  1238   bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
  1277   ///
  1277   ///
  1278   /// \brief Check that the given directed graph is a DAG.
  1278   /// \brief Check that the given directed graph is a DAG.
  1279   ///
  1279   ///
  1280   /// Check that the given directed graph is a DAG. The DAG is
  1280   /// Check that the given directed graph is a DAG. The DAG is
  1281   /// an Directed Acyclic Digraph.
  1281   /// an Directed Acyclic Digraph.
  1282   /// \return %False when the graph is not DAG.
  1282   /// \return \c false when the graph is not DAG.
  1283   /// \see acyclic
  1283   /// \see acyclic
  1284   template <typename Digraph>
  1284   template <typename Digraph>
  1285   bool dag(const Digraph& digraph) {
  1285   bool dag(const Digraph& digraph) {
  1286 
  1286 
  1287     checkConcept<concepts::Digraph, Digraph>();
  1287     checkConcept<concepts::Digraph, Digraph>();
  1319   ///
  1319   ///
  1320   /// \brief Check that the given undirected graph is acyclic.
  1320   /// \brief Check that the given undirected graph is acyclic.
  1321   ///
  1321   ///
  1322   /// Check that the given undirected graph acyclic.
  1322   /// Check that the given undirected graph acyclic.
  1323   /// \param graph The undirected graph.
  1323   /// \param graph The undirected graph.
  1324   /// \return %True when there is no circle in the graph.
  1324   /// \return \c true when there is no circle in the graph.
  1325   /// \see dag
  1325   /// \see dag
  1326   template <typename Graph>
  1326   template <typename Graph>
  1327   bool acyclic(const Graph& graph) {
  1327   bool acyclic(const Graph& graph) {
  1328     checkConcept<concepts::Graph, Graph>();
  1328     checkConcept<concepts::Graph, Graph>();
  1329     typedef typename Graph::Node Node;
  1329     typedef typename Graph::Node Node;
  1353   ///
  1353   ///
  1354   /// \brief Check that the given undirected graph is tree.
  1354   /// \brief Check that the given undirected graph is tree.
  1355   ///
  1355   ///
  1356   /// Check that the given undirected graph is tree.
  1356   /// Check that the given undirected graph is tree.
  1357   /// \param graph The undirected graph.
  1357   /// \param graph The undirected graph.
  1358   /// \return %True when the graph is acyclic and connected.
  1358   /// \return \c true when the graph is acyclic and connected.
  1359   template <typename Graph>
  1359   template <typename Graph>
  1360   bool tree(const Graph& graph) {
  1360   bool tree(const Graph& graph) {
  1361     checkConcept<concepts::Graph, Graph>();
  1361     checkConcept<concepts::Graph, Graph>();
  1362     typedef typename Graph::Node Node;
  1362     typedef typename Graph::Node Node;
  1363     typedef typename Graph::NodeIt NodeIt;
  1363     typedef typename Graph::NodeIt NodeIt;
  1446   /// \brief Check if the given undirected graph is bipartite or not
  1446   /// \brief Check if the given undirected graph is bipartite or not
  1447   ///
  1447   ///
  1448   /// The function checks if the given undirected \c graph graph is bipartite
  1448   /// 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.
  1449   /// or not. The \ref Bfs algorithm is used to calculate the result.
  1450   /// \param graph The undirected graph.
  1450   /// \param graph The undirected graph.
  1451   /// \return %True if \c graph is bipartite, %false otherwise.
  1451   /// \return \c true if \c graph is bipartite, \c false otherwise.
  1452   /// \sa bipartitePartitions
  1452   /// \sa bipartitePartitions
  1453   template<typename Graph>
  1453   template<typename Graph>
  1454   inline bool bipartite(const Graph &graph){
  1454   inline bool bipartite(const Graph &graph){
  1455     using namespace _connectivity_bits;
  1455     using namespace _connectivity_bits;
  1456 
  1456 
  1487   /// During the execution, the \c partMap will be set as the two
  1487   /// During the execution, the \c partMap will be set as the two
  1488   /// partitions of the graph.
  1488   /// partitions of the graph.
  1489   /// \param graph The undirected graph.
  1489   /// \param graph The undirected graph.
  1490   /// \retval partMap A writable bool map of nodes. It will be set as the
  1490   /// \retval partMap A writable bool map of nodes. It will be set as the
  1491   /// two partitions of the graph.
  1491   /// two partitions of the graph.
  1492   /// \return %True if \c graph is bipartite, %false otherwise.
  1492   /// \return \c true if \c graph is bipartite, \c false otherwise.
  1493   template<typename Graph, typename NodeMap>
  1493   template<typename Graph, typename NodeMap>
  1494   inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  1494   inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  1495     using namespace _connectivity_bits;
  1495     using namespace _connectivity_bits;
  1496 
  1496 
  1497     checkConcept<concepts::Graph, Graph>();
  1497     checkConcept<concepts::Graph, Graph>();