diff -r 990ef198f64d -r d391ea416aa0 lemon/topology.h
--- a/lemon/topology.h	Wed Nov 16 09:08:36 2005 +0000
+++ b/lemon/topology.h	Wed Nov 16 09:10:24 2005 +0000
@@ -480,13 +480,13 @@
   namespace _topology_bits {
     
     template <typename Graph>
-    class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
       typedef typename Graph::Edge Edge;
       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) {}
 
@@ -538,13 +538,13 @@
     };
 
     template <typename Graph, typename EdgeMap>
-    class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
       typedef typename Graph::Edge Edge;
       typedef typename Graph::UndirEdge UndirEdge;
 
-      NodeBiconnectedComponentsVisitor(const Graph& graph, 
+      BiNodeConnectedComponentsVisitor(const Graph& graph, 
 				       EdgeMap& compMap, int &compNum) 
 	: _graph(graph), _compMap(compMap), _compNum(compNum), 
 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
@@ -618,13 +618,13 @@
 
 
     template <typename Graph, typename NodeMap>
-    class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
+    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
       typedef typename Graph::Edge Edge;
       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),
 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
@@ -696,7 +696,7 @@
   }
 
   template <typename UndirGraph>
-  int countNodeBiconnectedComponents(const UndirGraph& graph);
+  int countBiNodeConnectedComponents(const UndirGraph& graph);
 
   /// \ingroup topology
   ///
@@ -711,7 +711,7 @@
   /// \todo Make it faster.
   template <typename UndirGraph>
   bool biNodeConnected(const UndirGraph& graph) {
-    return countNodeBiconnectedComponents(graph) == 1;
+    return countBiNodeConnectedComponents(graph) == 1;
   }
 
   /// \ingroup topology
@@ -726,13 +726,13 @@
   /// \param graph The graph.
   /// \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;
 
     using namespace _topology_bits;
 
-    typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
+    typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor;
 
     int compNum = 0;
     Visitor visitor(graph, compNum);
@@ -778,7 +778,7 @@
 
     using namespace _topology_bits;
 
-    typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
+    typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
     
     int compNum = 0;
     Visitor visitor(graph, compMap, compNum);
@@ -818,7 +818,7 @@
 
     using namespace _topology_bits;
 
-    typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
+    typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
     
     int cutNum = 0;
     Visitor visitor(graph, cutMap, cutNum);
@@ -838,13 +838,13 @@
   namespace _topology_bits {
     
     template <typename Graph>
-    class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
       typedef typename Graph::Edge Edge;
       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) {}
 
@@ -894,13 +894,13 @@
     };
 
     template <typename Graph, typename NodeMap>
-    class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
       typedef typename Graph::Edge Edge;
       typedef typename Graph::UndirEdge UndirEdge;
 
-      EdgeBiconnectedComponentsVisitor(const Graph& graph, 
+      BiEdgeConnectedComponentsVisitor(const Graph& graph, 
 				       NodeMap& compMap, int &compNum) 
 	: _graph(graph), _compMap(compMap), _compNum(compNum), 
 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
@@ -961,13 +961,13 @@
 
 
     template <typename Graph, typename EdgeMap>
-    class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
+    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
       typedef typename Graph::Edge Edge;
       typedef typename Graph::UndirEdge UndirEdge;
 
-      EdgeBiconnectedCutEdgesVisitor(const Graph& graph, 
+      BiEdgeConnectedCutEdgesVisitor(const Graph& graph, 
 				     EdgeMap& cutMap, int &cutNum) 
 	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 
 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
@@ -1023,7 +1023,7 @@
   }
 
   template <typename UndirGraph>
-  int countEdgeBiconnectedComponents(const UndirGraph& graph);
+  int countbiEdgeConnectedComponents(const UndirGraph& graph);
 
   /// \ingroup topology
   ///
@@ -1038,7 +1038,7 @@
   /// \todo Make it faster.
   template <typename UndirGraph>
   bool biEdgeConnected(const UndirGraph& graph) { 
-    return countEdgeBiconnectedComponents(graph) == 1;
+    return countBiEdgeConnectedComponents(graph) == 1;
   }
 
   /// \ingroup topology
@@ -1053,13 +1053,13 @@
   /// \param graph The undirected graph.
   /// \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;
 
     using namespace _topology_bits;
 
-    typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
+    typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor;
     
     int compNum = 0;
     Visitor visitor(graph, compNum);
@@ -1104,7 +1104,7 @@
 
     using namespace _topology_bits;
 
-    typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
+    typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
     
     int compNum = 0;
     Visitor visitor(graph, compMap, compNum);
@@ -1145,7 +1145,7 @@
 
     using namespace _topology_bits;
 
-    typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
+    typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
     
     int cutNum = 0;
     Visitor visitor(graph, cutMap, cutNum);
@@ -1388,41 +1388,76 @@
 
   /// \ingroup topology
   ///
-  /// \brief Check that the given undirected graph is bipartite.
+  /// \brief Check if the given undirected graph is bipartite or not
   ///
-  /// Check that the given undirected 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.
   /// \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