lemon/connectivity.h
changeset 1064 fc3854d936f7
parent 648 4ff8041e9c2e
child 1091 9eac00ea588f
equal deleted inserted replaced
7:ae39c487374b 8:988877faa263
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
   256   /// connected, i.e. any two nodes of the digraph are
   256   /// connected, i.e. any two nodes of the digraph are
   257   /// connected with directed paths in both direction.
   257   /// connected with directed paths in both direction.
   258   ///
   258   ///
   259   /// \return \c true if the digraph is strongly connected.
   259   /// \return \c true if the digraph is strongly connected.
   260   /// \note By definition, the empty digraph is strongly connected.
   260   /// \note By definition, the empty digraph is strongly connected.
   261   /// 
   261   ///
   262   /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
   262   /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
   263   /// \see connected()
   263   /// \see connected()
   264   template <typename Digraph>
   264   template <typename Digraph>
   265   bool stronglyConnected(const Digraph& digraph) {
   265   bool stronglyConnected(const Digraph& digraph) {
   266     checkConcept<concepts::Digraph, Digraph>();
   266     checkConcept<concepts::Digraph, Digraph>();
   308     return true;
   308     return true;
   309   }
   309   }
   310 
   310 
   311   /// \ingroup graph_properties
   311   /// \ingroup graph_properties
   312   ///
   312   ///
   313   /// \brief Count the number of strongly connected components of a 
   313   /// \brief Count the number of strongly connected components of a
   314   /// directed graph
   314   /// directed graph
   315   ///
   315   ///
   316   /// This function counts the number of strongly connected components of
   316   /// This function counts the number of strongly connected components of
   317   /// the given directed graph.
   317   /// the given directed graph.
   318   ///
   318   ///
   742 
   742 
   743   /// \ingroup graph_properties
   743   /// \ingroup graph_properties
   744   ///
   744   ///
   745   /// \brief Check whether an undirected graph is bi-node-connected.
   745   /// \brief Check whether an undirected graph is bi-node-connected.
   746   ///
   746   ///
   747   /// This function checks whether the given undirected graph is 
   747   /// This function checks whether the given undirected graph is
   748   /// bi-node-connected, i.e. any two edges are on same circle.
   748   /// bi-node-connected, i.e. any two edges are on same circle.
   749   ///
   749   ///
   750   /// \return \c true if the graph bi-node-connected.
   750   /// \return \c true if the graph bi-node-connected.
   751   /// \note By definition, the empty graph is bi-node-connected.
   751   /// \note By definition, the empty graph is bi-node-connected.
   752   ///
   752   ///
   756     return countBiNodeConnectedComponents(graph) <= 1;
   756     return countBiNodeConnectedComponents(graph) <= 1;
   757   }
   757   }
   758 
   758 
   759   /// \ingroup graph_properties
   759   /// \ingroup graph_properties
   760   ///
   760   ///
   761   /// \brief Count the number of bi-node-connected components of an 
   761   /// \brief Count the number of bi-node-connected components of an
   762   /// undirected graph.
   762   /// undirected graph.
   763   ///
   763   ///
   764   /// This function counts the number of bi-node-connected components of
   764   /// This function counts the number of bi-node-connected components of
   765   /// the given undirected graph.
   765   /// the given undirected graph.
   766   ///
   766   ///
   810   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
   810   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
   811   ///
   811   ///
   812   /// \param graph The undirected graph.
   812   /// \param graph The undirected graph.
   813   /// \retval compMap A writable edge map. The values will be set from 0
   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
   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 
   815   /// value of the map will be set exactly once, and the values of a
   816   /// certain component will be set continuously.
   816   /// certain component will be set continuously.
   817   /// \return The number of bi-node-connected components.
   817   /// \return The number of bi-node-connected components.
   818   ///
   818   ///
   819   /// \see biNodeConnected(), countBiNodeConnectedComponents()
   819   /// \see biNodeConnected(), countBiNodeConnectedComponents()
   820   template <typename Graph, typename EdgeMap>
   820   template <typename Graph, typename EdgeMap>
   856   /// same class if they are on same circle.
   856   /// same class if they are on same circle.
   857   /// The bi-node-connected components are separted by the cut nodes of
   857   /// The bi-node-connected components are separted by the cut nodes of
   858   /// the components.
   858   /// the components.
   859   ///
   859   ///
   860   /// \param graph The undirected graph.
   860   /// \param graph The undirected graph.
   861   /// \retval cutMap A writable node map. The values will be set to 
   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
   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
   863   /// (exactly once for each cut node), and will not be changed for
   864   /// other nodes.
   864   /// other nodes.
   865   /// \return The number of the cut nodes.
   865   /// \return The number of the cut nodes.
   866   ///
   866   ///
  1083 
  1083 
  1084   /// \ingroup graph_properties
  1084   /// \ingroup graph_properties
  1085   ///
  1085   ///
  1086   /// \brief Check whether an undirected graph is bi-edge-connected.
  1086   /// \brief Check whether an undirected graph is bi-edge-connected.
  1087   ///
  1087   ///
  1088   /// This function checks whether the given undirected graph is 
  1088   /// This function checks whether the given undirected graph is
  1089   /// bi-edge-connected, i.e. any two nodes are connected with at least
  1089   /// bi-edge-connected, i.e. any two nodes are connected with at least
  1090   /// two edge-disjoint paths.
  1090   /// two edge-disjoint paths.
  1091   ///
  1091   ///
  1092   /// \return \c true if the graph is bi-edge-connected.
  1092   /// \return \c true if the graph is bi-edge-connected.
  1093   /// \note By definition, the empty graph is bi-edge-connected.
  1093   /// \note By definition, the empty graph is bi-edge-connected.
  1190   /// \ingroup graph_properties
  1190   /// \ingroup graph_properties
  1191   ///
  1191   ///
  1192   /// \brief Find the bi-edge-connected cut edges in an undirected graph.
  1192   /// \brief Find the bi-edge-connected cut edges in an undirected graph.
  1193   ///
  1193   ///
  1194   /// This function finds the bi-edge-connected cut edges in the given
  1194   /// This function finds the bi-edge-connected cut edges in the given
  1195   /// undirected graph. 
  1195   /// undirected graph.
  1196   ///
  1196   ///
  1197   /// The bi-edge-connected components are the classes of an equivalence
  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
  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
  1199   /// same class if they are connected with at least two edge-disjoint
  1200   /// paths.
  1200   /// paths.
  1347   /// into topolgical order and also checks whether the given digraph
  1347   /// into topolgical order and also checks whether the given digraph
  1348   /// is DAG.
  1348   /// is DAG.
  1349   ///
  1349   ///
  1350   /// \param digraph The digraph.
  1350   /// \param digraph The digraph.
  1351   /// \retval order A readable and writable node map. The values will be
  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. 
  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
  1353   /// Each value of the map will be set exactly once, and the values will
  1354   /// be set descending order.
  1354   /// be set descending order.
  1355   /// \return \c false if the digraph is not DAG.
  1355   /// \return \c false if the digraph is not DAG.
  1356   ///
  1356   ///
  1357   /// \see dag(), topologicalSort()
  1357   /// \see dag(), topologicalSort()