Index: lemon/topology.h
===================================================================
--- lemon/topology.h	(revision 1793)
+++ lemon/topology.h	(revision 1800)
@@ -481,5 +481,5 @@
     
     template <typename Graph>
-    class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -487,5 +487,5 @@
       typedef typename Graph::UndirEdge UndirEdge;
 
-      CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 
+      CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum) 
 	: _graph(graph), _compNum(compNum), 
 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
@@ -539,5 +539,5 @@
 
     template <typename Graph, typename EdgeMap>
-    class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -545,5 +545,5 @@
       typedef typename Graph::UndirEdge UndirEdge;
 
-      NodeBiconnectedComponentsVisitor(const Graph& graph, 
+      BiNodeConnectedComponentsVisitor(const Graph& graph, 
 				       EdgeMap& compMap, int &compNum) 
 	: _graph(graph), _compMap(compMap), _compNum(compNum), 
@@ -619,5 +619,5 @@
 
     template <typename Graph, typename NodeMap>
-    class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
+    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -625,5 +625,5 @@
       typedef typename Graph::UndirEdge UndirEdge;
 
-      NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
+      BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
 				     int& cutNum) 
 	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
@@ -697,5 +697,5 @@
 
   template <typename UndirGraph>
-  int countNodeBiconnectedComponents(const UndirGraph& graph);
+  int countBiNodeConnectedComponents(const UndirGraph& graph);
 
   /// \ingroup topology
@@ -712,5 +712,5 @@
   template <typename UndirGraph>
   bool biNodeConnected(const UndirGraph& graph) {
-    return countNodeBiconnectedComponents(graph) == 1;
+    return countBiNodeConnectedComponents(graph) == 1;
   }
 
@@ -727,5 +727,5 @@
   /// \return The number of components.
   template <typename UndirGraph>
-  int countNodeBiconnectedComponents(const UndirGraph& graph) {
+  int countBiNodeConnectedComponents(const UndirGraph& graph) {
     checkConcept<concept::UndirGraph, UndirGraph>();
     typedef typename UndirGraph::NodeIt NodeIt;
@@ -733,5 +733,5 @@
     using namespace _topology_bits;
 
-    typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
+    typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor;
 
     int compNum = 0;
@@ -779,5 +779,5 @@
     using namespace _topology_bits;
 
-    typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
+    typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
     
     int compNum = 0;
@@ -819,5 +819,5 @@
     using namespace _topology_bits;
 
-    typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
+    typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
     
     int cutNum = 0;
@@ -839,5 +839,5 @@
     
     template <typename Graph>
-    class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -845,5 +845,5 @@
       typedef typename Graph::UndirEdge UndirEdge;
 
-      CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 
+      CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum) 
 	: _graph(graph), _compNum(compNum), 
 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
@@ -895,5 +895,5 @@
 
     template <typename Graph, typename NodeMap>
-    class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -901,5 +901,5 @@
       typedef typename Graph::UndirEdge UndirEdge;
 
-      EdgeBiconnectedComponentsVisitor(const Graph& graph, 
+      BiEdgeConnectedComponentsVisitor(const Graph& graph, 
 				       NodeMap& compMap, int &compNum) 
 	: _graph(graph), _compMap(compMap), _compNum(compNum), 
@@ -962,5 +962,5 @@
 
     template <typename Graph, typename EdgeMap>
-    class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
+    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -968,5 +968,5 @@
       typedef typename Graph::UndirEdge UndirEdge;
 
-      EdgeBiconnectedCutEdgesVisitor(const Graph& graph, 
+      BiEdgeConnectedCutEdgesVisitor(const Graph& graph, 
 				     EdgeMap& cutMap, int &cutNum) 
 	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 
@@ -1024,5 +1024,5 @@
 
   template <typename UndirGraph>
-  int countEdgeBiconnectedComponents(const UndirGraph& graph);
+  int countbiEdgeConnectedComponents(const UndirGraph& graph);
 
   /// \ingroup topology
@@ -1039,5 +1039,5 @@
   template <typename UndirGraph>
   bool biEdgeConnected(const UndirGraph& graph) { 
-    return countEdgeBiconnectedComponents(graph) == 1;
+    return countBiEdgeConnectedComponents(graph) == 1;
   }
 
@@ -1054,5 +1054,5 @@
   /// \return The number of components.
   template <typename UndirGraph>
-  int countEdgeBiconnectedComponents(const UndirGraph& graph) { 
+  int countBiEdgeConnectedComponents(const UndirGraph& graph) { 
     checkConcept<concept::UndirGraph, UndirGraph>();
     typedef typename UndirGraph::NodeIt NodeIt;
@@ -1060,5 +1060,5 @@
     using namespace _topology_bits;
 
-    typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
+    typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor;
     
     int compNum = 0;
@@ -1105,5 +1105,5 @@
     using namespace _topology_bits;
 
-    typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
+    typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
     
     int compNum = 0;
@@ -1146,5 +1146,5 @@
     using namespace _topology_bits;
 
-    typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
+    typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
     
     int cutNum = 0;
@@ -1389,39 +1389,74 @@
   /// \ingroup topology
   ///
-  /// \brief Check that the given undirected graph is bipartite.
-  ///
-  /// Check that the given undirected graph is bipartite.
+  /// \brief Check if the given undirected graph is bipartite or not
+  ///
+  /// The function checks if the given undirected \c graph graph is bipartite 
+  /// or not. The \ref Bfs algorithm is used to calculate the result.
   /// \param graph The undirected graph.
-  /// \return %True when the nodes can be separated into two sets that
-  /// there are not connected nodes in neither sets.
-  template <typename UndirGraph>
-  bool bipartite(const UndirGraph& graph) {
+  /// \return %True if \c graph is bipartite, %false otherwise.
+  /// \sa bipartitePartitions
+  ///
+  /// \author Balazs Attila Mihaly  
+  template<typename UndirGraph>
+  inline bool bipartite(const UndirGraph &graph){
     checkConcept<concept::UndirGraph, UndirGraph>();
+    
+    typedef typename UndirGraph::NodeIt NodeIt;
+    typedef typename UndirGraph::EdgeIt EdgeIt;
+    
+    Bfs<UndirGraph> bfs(graph);
+    bfs.init();
+    for(NodeIt i(graph);i!=INVALID;++i){
+      if(!bfs.reached(i)){
+	bfs.run(i);
+      }
+    }
+    for(EdgeIt i(graph);i!=INVALID;++i){
+      if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
+    }
+    return true;
+  };
+  
+  /// \ingroup topology
+  ///
+  /// \brief Check if the given undirected graph is bipartite or not
+  ///
+  /// The function checks if the given undirected graph is bipartite 
+  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result. 
+  /// During the execution, the \c partMap will be set as the two 
+  /// partitions of the graph.
+  /// \param graph The undirected graph.
+  /// \retval partMap A writeable bool map of nodes. It will be set as the
+  /// two partitions of the graph. 
+  /// \return %True if \c graph is bipartite, %false otherwise.
+  ///
+  /// \author Balazs Attila Mihaly  
+  ///
+  /// \image html bipartite_partitions.png
+  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
+  template<typename UndirGraph, typename NodeMap>
+  inline bool bipartitePartitions(const UndirGraph &graph, NodeMap &partMap){
+    checkConcept<concept::UndirGraph, UndirGraph>();
+    
     typedef typename UndirGraph::Node Node;
     typedef typename UndirGraph::NodeIt NodeIt;
-    typedef typename UndirGraph::Edge Edge;
-    if (NodeIt(graph) == INVALID) return false;
-    Dfs<UndirGraph> dfs(graph);
-    dfs.init();
-    typename UndirGraph::template NodeMap<bool> red(graph);
-    for (NodeIt it(graph); it != INVALID; ++it) {
-      if (!dfs.reached(it)) {
-	dfs.addSource(it);
-	red[it] = true;
-	while (!dfs.emptyQueue()) {
-	  Edge edge = dfs.nextEdge();
-	  Node source = graph.source(edge);
-	  Node target = graph.target(edge);
-	  if (dfs.reached(target) && red[source] == red[target]) {
-	    return false;
-	  } else {
-	    red[target] = !red[source];
-	  }
-	  dfs.processNextEdge();
-	}
-      }
+    typedef typename UndirGraph::EdgeIt EdgeIt;
+  
+    Bfs<UndirGraph> bfs(graph);
+    bfs.init();
+    for(NodeIt i(graph);i!=INVALID;++i){
+      if(!bfs.reached(i)){
+	bfs.addSource(i);
+	for(Node j=bfs.processNextNode();!bfs.emptyQueue();
+	    j=bfs.processNextNode()){
+	  partMap.set(j,bfs.dist(j)%2==0);
+	}
+      }
+    }
+    for(EdgeIt i(graph);i!=INVALID;++i){
+      if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
     }
     return true;
-  }
+  };
    
 } //namespace lemon
