#include <lemon/bucket_heap.h>

 #include <lemon/bucket_heap.h>

 #include <stack>

 #include <stack>

 #include <functional>

 #include <functional>

 /// \file

 /// \file

 /// \brief Topology related algorithms

 /// \brief Topology related algorithms

 ///

 ///

 /// Topology related algorithms

 /// Topology related algorithms

 namespace lemon {

 namespace lemon {

   ///

   ///

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

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

   ///

   ///

   /// Check that the given undirected graph connected.

   /// Check that the given undirected graph connected.

   /// \param graph The undirected graph.

   /// \param graph The undirected graph.

       }

       }

     }

     }

     return true;

     return true;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

   ///

   ///

       }

       }

     }

     }

     return compNum;

     return compNum;

   }

   }

   ///

   ///

   /// \brief Find the connected components of an undirected graph

   /// \brief Find the connected components of an undirected graph

   ///

   ///

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

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

   ///

   ///

     };

     };

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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

     }

     }

     return true;

     return true;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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

       }

       }

     }

     }

     return compNum;

     return compNum;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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

       }

       }

     }

     }

     return compNum;

     return compNum;

   }

   }

   ///

   ///

   /// \brief Find the cut edges of the strongly connected components.

   /// \brief Find the cut edges of the strongly connected components.

   ///

   ///

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

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

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

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

   }

   }

   template <typename UGraph>

   template <typename UGraph>

   int countBiNodeConnectedComponents(const UGraph& graph);

   int countBiNodeConnectedComponents(const UGraph& graph);

   ///

   ///

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

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

   ///

   ///

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

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

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

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

   template <typename UGraph>

   template <typename UGraph>

   bool biNodeConnected(const UGraph& graph) {

   bool biNodeConnected(const UGraph& graph) {

     return countBiNodeConnectedComponents(graph) == 1;

     return countBiNodeConnectedComponents(graph) == 1;

   }

   }

   ///

   ///

   /// \brief Count the biconnected components.

   /// \brief Count the biconnected components.

   ///

   ///

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

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

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

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

       }

       }

     }

     }

     return compNum;

     return compNum;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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

       }

       }

     }

     }

     return compNum;

     return compNum;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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

   }

   }

   template <typename UGraph>

   template <typename UGraph>

   int countBiEdgeConnectedComponents(const UGraph& graph);

   int countBiEdgeConnectedComponents(const UGraph& graph);

   ///

   ///

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

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

   ///

   ///

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

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

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

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

   template <typename UGraph>

   template <typename UGraph>

   bool biEdgeConnected(const UGraph& graph) { 

   bool biEdgeConnected(const UGraph& graph) { 

     return countBiEdgeConnectedComponents(graph) == 1;

     return countBiEdgeConnectedComponents(graph) == 1;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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

       }

       }

     }

     }

     return compNum;

     return compNum;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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

       }

       }

     }

     }

     return compNum;

     return compNum;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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

       int _num;

       int _num;

     };

     };

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

   ///

   ///

 	dfs.start();

 	dfs.start();

       }

       }

     }    

     }    

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

   /// that the given graph is DAG.

   /// that the given graph is DAG.

       }

       }

     }

     }

     return true;

     return true;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

   /// an Directed Acyclic Graph.

   /// an Directed Acyclic Graph.

       }

       }

     }    

     }    

     return true;

     return true;

   }

   }

   ///

   ///

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

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

   ///

   ///

   /// Check that the given undirected graph acyclic.

   /// Check that the given undirected graph acyclic.

   /// \param graph The undirected graph.

   /// \param graph The undirected graph.

       }

       }

     }

     }

     return true;

     return true;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

   /// \param graph The undirected graph.

   /// \param graph The undirected graph.

       PartMap& _part;

       PartMap& _part;

       bool& _bipartite;

       bool& _bipartite;

     };

     };

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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

       }

       }

     }

     }

     return true;

     return true;

   }

   }

   ///

   ///

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

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

   ///

   ///

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

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

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

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