/// \brief Check whether the given undirected graph is connected.

   /// \brief Check whether an undirected graph is connected.

   ///

   ///

   /// Check whether the given undirected graph is connected.

   /// This function checks whether the given undirected graph is connected,

   /// \param graph The undirected graph.

   /// i.e. there is a path between any two nodes in the graph.

   /// \return \c true when there is path between any two nodes in the graph.

   ///

   /// \return \c true if the graph is connected.

   /// Count the number of connected components of an undirected graph

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

   ///

   /// undirected graph.

   /// \param graph The graph. It must be undirected.

   ///

   /// \return The number of components

   /// The connected components are the classes of an equivalence relation

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

   /// if they are connected with a path.

   ///

   /// \return The number of connected components.

   /// Find the connected components of an undirected graph.

   /// This function finds the connected components of the given undirected

   /// graph.

   ///

   /// The connected components are the classes of an equivalence relation

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

   /// if they are connected with a path.

   /// \param graph The graph. It must be undirected.

   /// \param graph The undirected graph.

   /// the number of the connected components minus one. Each values of the map

   /// the number of the connected components minus one. Each value of the map

   /// will be set exactly once, the values of a certain component will be

   /// will be set exactly once, and the values of a certain component will be

   /// \return The number of components

   /// \return The number of connected components.

   /// \note By definition, the empty graph consists

   /// of zero connected components.

   ///

   /// \see connected(), countConnectedComponents()

   /// \brief Check whether the given directed graph is strongly connected.

   /// \brief Check whether a directed graph is strongly connected.

   ///

   ///

   /// Check whether the given directed graph is strongly connected. The

   /// This function checks whether the given directed graph is strongly

   /// graph is strongly connected when any two nodes of the graph are

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

   /// \return \c false when the graph is not strongly connected.

   ///

   /// \see connected

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

   ///

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

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

   /// 

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

   /// \see connected()

     typedef DfsVisitor<Digraph> RVisitor;

     typedef DfsVisitor<RDigraph> RVisitor;

   /// \brief Count the strongly connected components of a directed graph

   /// \brief Count the number of strongly connected components of a 

   ///

   /// directed graph

   /// Count the strongly connected components of a directed graph.

   ///

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

   /// the given directed graph.

   ///

   /// equivalence relation on the nodes of the graph. Two nodes are in

   /// equivalence relation on the nodes of a digraph. Two nodes are in

   /// \param digraph The graph.

   /// \return The number of strongly connected components.

   /// \return The number of components

   /// \note By definition, the empty digraph has zero

   /// \note By definition, the empty graph has zero

   /// Find the strongly connected components of a directed graph.  The

   /// This function finds the strongly connected components of the given

   /// strongly connected components are the classes of an equivalence

   /// directed graph. In addition, the numbering of the components will

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

   /// satisfy that there is no arc going from a higher numbered component

   /// relationship when there are directed paths between them in both

   /// to a lower one (i.e. it provides a topological order of the components).

   /// direction. In addition, the numbering of components will satisfy

   ///

   /// that there is no arc going from a higher numbered component to

   /// The strongly connected components are the classes of an

   /// a lower.

   /// equivalence relation on the nodes of a digraph. Two nodes are in

   /// the same class if they are connected with directed paths in both

   /// direction.

   /// of the map will be set exactly once, the values of a certain component

   /// of the map will be set exactly once, and the values of a certain

   /// will be set continuously.

   /// component will be set continuously.

   /// \return The number of components

   /// \return The number of strongly connected components.

   /// \note By definition, the empty digraph has zero

   /// strongly connected components.

   ///

   /// \see stronglyConnected(), countStronglyConnectedComponents()

   /// Find the cut arcs of the strongly connected components.

   /// This function finds the cut arcs of the strongly connected components

   /// The strongly connected components are the classes of an equivalence

   /// of the given digraph.

   /// relation on the nodes of the graph. Two nodes are in relationship

   ///

   /// when there are directed paths between them in both direction.

   /// The strongly connected components are the classes of an

   /// equivalence relation on the nodes of a digraph. Two nodes are in

   /// the same class if they are connected with directed paths in both

   /// direction.

   /// \param graph The graph.

   /// \param digraph The digraph.

   /// \retval cutMap A writable node map. The values will be set true when the

   /// \retval cutMap A writable arc map. The values will be set to \c true

   /// arc is a cut arc.

   /// for the cut arcs (exactly once for each cut arc), and will not be

   ///

   /// changed for other arcs.

   /// \return The number of cut arcs

   /// \return The number of cut arcs.

   ///

   /// \see stronglyConnected(), stronglyConnectedComponents()

   int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {

   int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {

     Container nodes(countNodes(graph));

     Container nodes(countNodes(digraph));

     DfsVisit<Digraph, Visitor> dfs(graph, visitor);

     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);

     for (NodeIt it(graph); it != INVALID; ++it) {

     for (NodeIt it(digraph); it != INVALID; ++it) {

     RDigraph rgraph(graph);

     RDigraph rdigraph(digraph);

     RVisitor rvisitor(rgraph, cutMap, cutNum);

     RVisitor rvisitor(rdigraph, cutMap, cutNum);

     DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);

     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);

   /// \brief Checks the graph is bi-node-connected.

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

   ///

   ///

   /// This function checks that the undirected graph is bi-node-connected

   /// This function checks whether the given undirected graph is 

   /// graph. The graph is bi-node-connected if any two undirected edge is

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

   /// on same circle.

   ///

   ///

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

   /// \param graph The graph.

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

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

   ///

   /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()

   /// \brief Count the biconnected components.

   /// \brief Count the number of bi-node-connected components of an 

   ///

   /// undirected graph.

   /// This function finds the bi-node-connected components in an undirected

   ///

   /// graph. The biconnected components are the classes of an equivalence

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

   /// relation on the undirected edges. Two undirected edge is in relationship

   /// the given undirected graph.

   /// when they are on same circle.

   ///

   ///

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

   /// \param graph The graph.

   /// relation on the edges of a undirected graph. Two edges are in the

   /// \return The number of components.

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

   ///

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

   ///

   /// \see biNodeConnected(), biNodeConnectedComponents()

   /// \brief Find the bi-node-connected components.

   /// \brief Find the bi-node-connected components of an undirected graph.

   ///

   ///

   /// This function finds the bi-node-connected components in an undirected

   /// This function finds the bi-node-connected components of the given

   /// graph. The bi-node-connected components are the classes of an equivalence

   /// undirected graph.

   /// relation on the undirected edges. Two undirected edge are in relationship

   ///

   /// when they are on same circle.

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

   /// relation on the edges of a undirected graph. Two edges are in the

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

   /// \param graph The graph.

   /// \param graph The undirected graph.

   /// \retval compMap A writable uedge 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 biconnected components minus one. Each values

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

   /// of the map will be set exactly once, the values of a certain component

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

   /// will be set continuously.

   /// certain component will be set continuously.

   /// \return The number of components.

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

   ///

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

   /// \brief Find the bi-node-connected cut nodes.

   /// \brief Find the bi-node-connected cut nodes in an undirected graph.

   ///

   ///

   /// This function finds the bi-node-connected cut nodes in an undirected

   /// This function finds the bi-node-connected cut nodes in the given

   /// graph. The bi-node-connected components are the classes of an equivalence

   /// undirected graph.

   /// relation on the undirected edges. Two undirected edges are in

   ///

   /// relationship when they are on same circle. The biconnected components

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

   /// are separted by nodes which are the cut nodes of the components.

   /// relation on the edges of a undirected graph. Two edges are in the

   ///

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

   /// \param graph The graph.

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

   /// \retval cutMap A writable edge map. The values will be set true when

   /// the components.

   /// the node separate two or more components.

   ///

   /// \param graph The undirected graph.

   /// \retval cutMap A writable node map. The values will be set to 

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

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

   /// other nodes.

   /// \brief Checks that the graph is bi-edge-connected.

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

   ///

   ///

   /// This function checks that the graph is bi-edge-connected. The undirected

   /// This function checks whether the given undirected graph is 

   /// graph is bi-edge-connected when any two nodes are connected with two

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

   /// edge-disjoint paths.

   /// two edge-disjoint paths.

   ///

   ///

   /// \param graph The undirected graph.

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

   /// \return The number of components.

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

   ///

   /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()

   /// \brief Count the bi-edge-connected components.

   /// \brief Count the number of bi-edge-connected components of an

   ///

   /// undirected graph.

   /// This function count the bi-edge-connected components in an undirected

   ///

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

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

   /// relation on the nodes. Two nodes are in relationship when they are

   /// the given undirected graph.

   /// connected with at least two edge-disjoint paths.

   ///

   ///

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

   /// \param graph The undirected graph.

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

   /// \return The number of components.

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

   /// paths.

   ///

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

   ///

   /// \see biEdgeConnected(), biEdgeConnectedComponents()

   /// \brief Find the bi-edge-connected components.

   /// \brief Find the bi-edge-connected components of an undirected graph.

   ///

   ///

   /// This function finds the bi-edge-connected components in an undirected

   /// This function finds the bi-edge-connected components of the given

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

   /// undirected graph.

   /// relation on the nodes. Two nodes are in relationship when they are

   ///

   /// connected at least two edge-disjoint paths.

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

   /// 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

   /// paths.

   /// \param graph The graph.

   /// \param graph The undirected graph.

   /// the number of the biconnected components minus one. Each values

   /// the number of the bi-edge-connected components minus one. Each value

   /// of the map will be set exactly once, the values of a certain component

   /// of the map will be set exactly once, and the values of a certain

   /// will be set continuously.

   /// component will be set continuously.

   /// \return The number of components.

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

   ///

   /// \see biEdgeConnected(), countBiEdgeConnectedComponents()

   /// \brief Find the bi-edge-connected cut edges.

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

   ///

   ///

   /// This function finds the bi-edge-connected components in an undirected

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

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

   /// undirected graph. 

   /// relation on the nodes. Two nodes are in relationship when they are

   ///

   /// connected with at least two edge-disjoint paths. The bi-edge-connected

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

   /// components are separted by edges which are the cut edges of the

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

   /// components.

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

   ///

   /// paths.

   /// \param graph The graph.

   /// The bi-edge-connected components are separted by the cut edges of

   /// \retval cutMap A writable node map. The values will be set true when the

   /// the components.

   /// edge is a cut edge.

   ///

   /// \param graph The undirected graph.

   /// \retval cutMap A writable edge map. The values will be set to \c true

   /// for the cut edges (exactly once for each cut edge), and will not be

   /// changed for other edges.

   /// \brief Sort the nodes of a DAG into topolgical order.

   /// \brief Check whether a digraph is DAG.

   ///

   ///

   /// Sort the nodes of a DAG into topolgical order.

   /// This function checks whether the given digraph is DAG, i.e.

   ///

   /// \e Directed \e Acyclic \e Graph.

   /// \param graph The graph. It must be directed and acyclic.

   /// \return \c true if there is no directed cycle in the digraph.

   /// \retval order A writable node map. The values will be set from 0 to

   /// \see acyclic()

   /// the number of the nodes in the graph minus one. Each values of the map

   template <typename Digraph>

   /// will be set exactly once, the values  will be set descending order.

   bool dag(const Digraph& digraph) {

   ///

   /// \see checkedTopologicalSort

   /// \see dag

   template <typename Digraph, typename NodeMap>

   void topologicalSort(const Digraph& graph, NodeMap& order) {

     using namespace _connectivity_bits;

       visitor(order, countNodes(graph));

       visitor(order, countNodes(digraph));

       dfs(graph, visitor);

       dfs(digraph, visitor);

     for (NodeIt it(graph); it != INVALID; ++it) {

     for (NodeIt it(digraph); it != INVALID; ++it) {

   /// Sort the nodes of a DAG into topolgical order. It also checks

   /// This function sorts the nodes of the given acyclic digraph (DAG)

   /// that the given graph is DAG.

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

   ///

   /// is DAG.

   /// \param digraph The graph. It must be directed and acyclic.

   ///

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

   /// \param digraph The digraph.

   /// from 0 to the number of the nodes in the graph minus one. Each values

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

   /// of the map will be set exactly once, the values will be set descending

   /// set from 0 to the number of the nodes in the digraph minus one. 

   /// order.

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

   /// \return \c false when the graph is not DAG.

   /// be set descending order.

   ///

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

   /// \see topologicalSort

   ///

   /// \see dag

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

   /// \brief Check that the given directed graph is a DAG.

   /// \brief Check whether an undirected graph is acyclic.

   ///

   ///

   /// Check that the given directed graph is a DAG. The DAG is

   /// This function checks whether the given undirected graph is acyclic.

   /// an Directed Acyclic Digraph.

   /// \return \c true if there is no cycle in the graph.

   /// \return \c false when the graph is not DAG.

   /// \see dag()

   /// \see acyclic

   template <typename Digraph>

   bool dag(const Digraph& digraph) {

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

     typedef typename Digraph::Node Node;

     typedef typename Digraph::NodeIt NodeIt;

     typedef typename Digraph::Arc Arc;

     typedef typename Digraph::template NodeMap<bool> ProcessedMap;

     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::

       Create dfs(digraph);

     ProcessedMap processed(digraph);

     dfs.processedMap(processed);

     dfs.init();

     for (NodeIt it(digraph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

         dfs.addSource(it);

         while (!dfs.emptyQueue()) {

           Arc edge = dfs.nextArc();

           Node target = digraph.target(edge);

           if (dfs.reached(target) && !processed[target]) {

             return false;

           }

           dfs.processNextArc();

         }

       }

     }

     return true;

   }

   /// \ingroup graph_properties

   ///

   /// \brief Check that the given undirected graph is acyclic.

   ///

   /// Check that the given undirected graph acyclic.

   /// \param graph The undirected graph.

   /// \return \c true when there is no circle in the graph.

   /// \see dag

           Arc edge = dfs.nextArc();

           Arc arc = dfs.nextArc();

           Node source = graph.source(edge);

           Node source = graph.source(arc);

           Node target = graph.target(edge);

           Node target = graph.target(arc);

               dfs.predArc(source) != graph.oppositeArc(edge)) {

               dfs.predArc(source) != graph.oppositeArc(arc)) {

   /// \brief Check that the given undirected graph is tree.

   /// \brief Check whether an undirected graph is tree.

   ///

   ///

   /// Check that the given undirected graph is tree.

   /// This function checks whether the given undirected graph is tree.

   /// \param graph The undirected graph.

   /// \return \c true if the graph is acyclic and connected.

   /// \return \c true when the graph is acyclic and connected.

   /// \see acyclic(), connected()

       Arc edge = dfs.nextArc();

       Arc arc = dfs.nextArc();

       Node source = graph.source(edge);

       Node source = graph.source(arc);

       Node target = graph.target(edge);

       Node target = graph.target(arc);

           dfs.predArc(source) != graph.oppositeArc(edge)) {

           dfs.predArc(source) != graph.oppositeArc(arc)) {

   /// \brief Check if the given undirected graph is bipartite or not

   /// \brief Check whether an undirected graph is bipartite.

   ///

   ///

   /// The function checks if the given undirected \c graph graph is bipartite

   /// The function checks whether the given undirected graph is bipartite.

   /// or not. The \ref Bfs algorithm is used to calculate the result.

   /// \return \c true if the graph is bipartite.

   /// \param graph The undirected graph.

   ///

   /// \return \c true if \c graph is bipartite, \c false otherwise.

   /// \see bipartitePartitions()

   /// \sa bipartitePartitions

   inline bool bipartite(const Graph &graph){

   bool bipartite(const Graph &graph){

   /// \brief Check if the given undirected graph is bipartite or not

   /// \brief Find the bipartite partitions of an undirected graph.

   ///

   ///

   /// The function checks if the given undirected graph is bipartite

   /// This function checks whether the given undirected graph is bipartite

   /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.

   /// and gives back the bipartite partitions.

   /// During the execution, the \c partMap will be set as the two

   /// partitions of the graph.

   /// \retval partMap A writable bool map of nodes. It will be set as the

   /// \retval partMap A writable node map of \c bool (or convertible) value

   /// two partitions of the graph.

   /// type. The values will be set to \c true for one component and

   /// \return \c true if \c graph is bipartite, \c false otherwise.

   /// \c false for the other one.

   /// \return \c true if the graph is bipartite, \c false otherwise.

   ///

   /// \see bipartite()

   inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){

   bool bipartitePartitions(const Graph &graph, NodeMap &partMap){

   /// \brief Returns true when there are not loop edges in the graph.

   /// \ingroup graph_properties

   ///

   ///

   /// Returns true when there are not loop edges in the graph.

   /// \brief Check whether the given graph contains no loop arcs/edges.

   template <typename Digraph>

   ///

   bool loopFree(const Digraph& digraph) {

   /// This function returns \c true if there are no loop arcs/edges in

     for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {

   /// the given graph. It works for both directed and undirected graphs.

       if (digraph.source(it) == digraph.target(it)) return false;

   template <typename Graph>

   bool loopFree(const Graph& graph) {

     for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {

       if (graph.source(it) == graph.target(it)) return false;

   /// \brief Returns true when there are not parallel edges in the graph.

   /// \ingroup graph_properties

   ///

   ///

   /// Returns true when there are not parallel edges in the graph.

   /// \brief Check whether the given graph contains no parallel arcs/edges.

   ///

   /// This function returns \c true if there are no parallel arcs/edges in

   /// the given graph. It works for both directed and undirected graphs.

   /// \brief Returns true when there are not loop edges and parallel

   /// \ingroup graph_properties

   /// edges in the graph.

   ///

   ///

   /// \brief Check whether the given graph is simple.

   /// Returns true when there are not loop edges and parallel edges in

   ///

   /// the graph.

   /// This function returns \c true if the given graph is simple, i.e.

   /// it contains no loop arcs/edges and no parallel arcs/edges.

   /// The function works for both directed and undirected graphs.

   /// \see loopFree(), parallelFree()