diff -r 4a2236cc98a0 -r 42cce226b87b lemon/topology.h
--- a/lemon/topology.h	Tue Nov 21 17:28:08 2006 +0000
+++ b/lemon/topology.h	Tue Nov 21 18:22:08 2006 +0000
@@ -1389,6 +1389,64 @@
     return true;
   }
 
+  namespace _topology_bits {
+
+    template <typename Graph>
+    class BipartiteVisitor : public BfsVisitor<Graph> {
+    public:
+      typedef typename Graph::Edge Edge;
+      typedef typename Graph::Node Node;
+
+      BipartiteVisitor(const Graph& graph, bool& bipartite) 
+        : _graph(graph), _part(graph), _bipartite(bipartite) {}
+      
+      void start(const Node& node) {
+        _part[node] = true;
+      }
+      void discover(const Edge& edge) {
+        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
+      }
+      void examine(const Edge& edge) {
+        _bipartite = _bipartite && 
+          _part[_graph.target(edge)] != _part[_graph.source(edge)];
+      }
+
+    private:
+
+      const Graph& _graph;
+      typename Graph::template NodeMap<bool> _part;
+      bool& _bipartite;
+    };
+
+    template <typename Graph, typename PartMap>
+    class BipartitePartitionsVisitor : public BfsVisitor<Graph> {
+    public:
+      typedef typename Graph::Edge Edge;
+      typedef typename Graph::Node Node;
+
+      BipartitePartitionsVisitor(const Graph& graph, 
+                                 PartMap& part, bool& bipartite) 
+        : _graph(graph), _part(part), _bipartite(bipartite) {}
+      
+      void start(const Node& node) {
+        _part.set(node, true);
+      }
+      void discover(const Edge& edge) {
+        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
+      }
+      void examine(const Edge& edge) {
+        _bipartite = _bipartite && 
+          _part[_graph.target(edge)] != _part[_graph.source(edge)];
+      }
+
+    private:
+
+      const Graph& _graph;
+      PartMap& _part;
+      bool& _bipartite;
+    };
+  }
+
   /// \ingroup topology
   ///
   /// \brief Check if the given undirected graph is bipartite or not
@@ -1402,21 +1460,29 @@
   /// \author Balazs Attila Mihaly  
   template<typename UGraph>
   inline bool bipartite(const UGraph &graph){
+    using namespace _topology_bits;
+
     checkConcept<concepts::UGraph, UGraph>();
     
     typedef typename UGraph::NodeIt NodeIt;
     typedef typename UGraph::EdgeIt EdgeIt;
     
-    Bfs<UGraph> bfs(graph);
+    bool bipartite = true;
+
+    BipartiteVisitor<UGraph> 
+      visitor(graph, bipartite);
+    BfsVisit<UGraph, BipartiteVisitor<UGraph> > 
+      bfs(graph, visitor);
     bfs.init();
-    for(NodeIt i(graph);i!=INVALID;++i){
-      if(!bfs.reached(i)){
-	bfs.run(i);
+    for(NodeIt it(graph); it != INVALID; ++it) {
+      if(!bfs.reached(it)){
+	bfs.addSource(it);
+        while (!bfs.emptyQueue()) {
+          bfs.processNextNode();
+          if (!bipartite) return false;
+        }
       }
     }
-    for(EdgeIt i(graph);i!=INVALID;++i){
-      if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
-    }
     return true;
   }
   
@@ -1439,25 +1505,80 @@
   /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
   template<typename UGraph, typename NodeMap>
   inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
+    using namespace _topology_bits;
+
     checkConcept<concepts::UGraph, UGraph>();
     
     typedef typename UGraph::Node Node;
     typedef typename UGraph::NodeIt NodeIt;
     typedef typename UGraph::EdgeIt EdgeIt;
-  
-    Bfs<UGraph> bfs(graph);
+
+    bool bipartite = true;
+
+    BipartitePartitionsVisitor<UGraph, NodeMap> 
+      visitor(graph, partMap, bipartite);
+    BfsVisit<UGraph, BipartitePartitionsVisitor<UGraph, NodeMap> > 
+      bfs(graph, visitor);
     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(NodeIt it(graph); it != INVALID; ++it) {
+      if(!bfs.reached(it)){
+	bfs.addSource(it);
+        while (!bfs.emptyQueue()) {
+          bfs.processNextNode();
+          if (!bipartite) return false;
+        }
       }
     }
-    for(EdgeIt i(graph);i!=INVALID;++i){
-      if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
+    return true;
+  }
+
+  /// \brief Returns true when there is not loop edge in the graph.
+  ///
+  /// Returns true when there is not loop edge in the graph.
+  template <typename Graph>
+  bool loopFree(const Graph& graph) {
+    for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
+      if (graph.source(it) == graph.target(it)) return false;
+    }
+    return true;
+  }
+
+  /// \brief Returns true when there is not parallel edges in the graph.
+  ///
+  /// Returns true when there is not parallel edges in the graph.
+  template <typename Graph>
+  bool parallelFree(const Graph& graph) {
+    typename Graph::template NodeMap<bool> reached(graph, false);
+    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
+      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
+        if (reached[graph.target(e)]) return false;
+        reached.set(graph.target(e), true);
+      }
+      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
+        reached.set(graph.target(e), false);
+      }
+    }
+    return true;
+  }
+
+  /// \brief Returns true when there is not loop edge and parallel
+  /// edges in the graph.
+  ///
+  /// Returns true when there is not loop edge and parallel edges in
+  /// the graph.
+  template <typename Graph>
+  bool simpleGraph(const Graph& graph) {
+    typename Graph::template NodeMap<bool> reached(graph, false);
+    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
+      reached.set(n, true);
+      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
+        if (reached[graph.target(e)]) return false;
+        reached.set(graph.target(e), true);
+      }
+      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
+        reached.set(graph.target(e), false);
+      }
+      reached.set(n, false);
     }
     return true;
   }