/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

   /// connected, i.e. any two nodes of the digraph are

   /// connected, i.e. any two nodes of the digraph are

   /// connected with directed paths in both direction.

   /// connected with directed paths in both direction.

   ///

   ///

   /// \return \c true if the digraph is strongly connected.

   /// \return \c true if the digraph is strongly connected.

   /// \note By definition, the empty digraph is strongly connected.

   /// \note By definition, the empty digraph is strongly connected.

   /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()

   /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()

   /// \see connected()

   /// \see connected()

   template <typename Digraph>

   template <typename Digraph>

   bool stronglyConnected(const Digraph& digraph) {

   bool stronglyConnected(const Digraph& digraph) {

     checkConcept<concepts::Digraph, Digraph>();

     checkConcept<concepts::Digraph, Digraph>();

     return true;

     return true;

   }

   }

   /// \ingroup graph_properties

   /// \ingroup graph_properties

   ///

   ///

   /// directed graph

   /// directed graph

   ///

   ///

   /// This function counts the number of strongly connected components of

   /// This function counts the number of strongly connected components of

   /// the given directed graph.

   /// the given directed graph.

   ///

   ///

   /// \ingroup graph_properties

   /// \ingroup graph_properties

   ///

   ///

   /// \brief Check whether an undirected graph is bi-node-connected.

   /// \brief Check whether an undirected graph is bi-node-connected.

   ///

   ///

   /// bi-node-connected, i.e. any two edges are on same circle.

   /// bi-node-connected, i.e. any two edges are on same circle.

   ///

   ///

   /// \return \c true if the graph bi-node-connected.

   /// \return \c true if the graph bi-node-connected.

   /// \note By definition, the empty graph is bi-node-connected.

   /// \note By definition, the empty graph is bi-node-connected.

   ///

   ///

     return countBiNodeConnectedComponents(graph) <= 1;

     return countBiNodeConnectedComponents(graph) <= 1;

   }

   }

   /// \ingroup graph_properties

   /// \ingroup graph_properties

   ///

   ///

   /// undirected graph.

   /// undirected graph.

   ///

   ///

   /// This function counts the number of bi-node-connected components of

   /// This function counts the number of bi-node-connected components of

   /// the given undirected graph.

   /// the given undirected graph.

   ///

   ///

   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth

   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth

   ///

   ///

   /// \param graph The undirected graph.

   /// \param graph The undirected graph.

   /// \retval compMap A writable edge map. The values will be set from 0

   /// \retval compMap A writable edge map. The values will be set from 0

   /// to the number of the bi-node-connected components minus one. Each

   /// to the number of the bi-node-connected components minus one. Each

   /// certain component will be set continuously.

   /// certain component will be set continuously.

   /// \return The number of bi-node-connected components.

   /// \return The number of bi-node-connected components.

   ///

   ///

   /// \see biNodeConnected(), countBiNodeConnectedComponents()

   /// \see biNodeConnected(), countBiNodeConnectedComponents()

   template <typename Graph, typename EdgeMap>

   template <typename Graph, typename EdgeMap>

   /// same class if they are on same circle.

   /// same class if they are on same circle.

   /// The bi-node-connected components are separted by the cut nodes of

   /// The bi-node-connected components are separted by the cut nodes of

   /// the components.

   /// the components.

   ///

   ///

   /// \param graph The undirected graph.

   /// \param graph The undirected graph.

   /// \c true for the nodes that separate two or more components

   /// \c true for the nodes that separate two or more components

   /// (exactly once for each cut node), and will not be changed for

   /// (exactly once for each cut node), and will not be changed for

   /// other nodes.

   /// other nodes.

   /// \return The number of the cut nodes.

   /// \return The number of the cut nodes.

   ///

   ///

   /// \ingroup graph_properties

   /// \ingroup graph_properties

   ///

   ///

   /// \brief Check whether an undirected graph is bi-edge-connected.

   /// \brief Check whether an undirected graph is bi-edge-connected.

   ///

   ///

   /// bi-edge-connected, i.e. any two nodes are connected with at least

   /// bi-edge-connected, i.e. any two nodes are connected with at least

   /// two edge-disjoint paths.

   /// two edge-disjoint paths.

   ///

   ///

   /// \return \c true if the graph is bi-edge-connected.

   /// \return \c true if the graph is bi-edge-connected.

   /// \note By definition, the empty graph is bi-edge-connected.

   /// \note By definition, the empty graph is bi-edge-connected.

   /// \ingroup graph_properties

   /// \ingroup graph_properties

   ///

   ///

   /// \brief Find the bi-edge-connected cut edges in an undirected graph.

   /// \brief Find the bi-edge-connected cut edges in an undirected graph.

   ///

   ///

   /// This function finds the bi-edge-connected cut edges in the given

   /// This function finds the bi-edge-connected cut edges in the given

   ///

   ///

   /// The bi-edge-connected components are the classes of an equivalence

   /// The bi-edge-connected components are the classes of an equivalence

   /// relation on the nodes of an undirected graph. Two nodes are in the

   /// relation on the nodes of an undirected graph. Two nodes are in the

   /// same class if they are connected with at least two edge-disjoint

   /// same class if they are connected with at least two edge-disjoint

   /// paths.

   /// paths.

   /// into topolgical order and also checks whether the given digraph

   /// into topolgical order and also checks whether the given digraph

   /// is DAG.

   /// is DAG.

   ///

   ///

   /// \param digraph The digraph.

   /// \param digraph The digraph.

   /// \retval order A readable and writable node map. The values will be

   /// \retval order A readable and writable node map. The values will be

   /// Each value of the map will be set exactly once, and the values will

   /// Each value of the map will be set exactly once, and the values will

   /// be set descending order.

   /// be set descending order.

   /// \return \c false if the digraph is not DAG.

   /// \return \c false if the digraph is not DAG.

   ///

   ///

   /// \see dag(), topologicalSort()

   /// \see dag(), topologicalSort()