Changeset 2306:42cce226b87b in lemon-0.x for lemon/topology.h

Timestamp:

11/21/06 19:22:08 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3081

Message:

BfsVisitor?
Bipartite partitions based on visitors

topology_demo.cc => scaleToA4 works without extra parameters

File:

• lemon/topology.h (modified) (5 diffs)

lemon/topology.h

@@ -1390 +1390 @@
   }
 
+  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
   ///
@@ -1403 +1461 @@
   template<typename UGraph>
   inline bool bipartite(const UGraph &graph){
+    using namespace _topology_bits;
+
     checkConcept<concepts::UGraph, UGraph>();
     
@@ -1408 +1468 @@
     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(EdgeIt i(graph);i!=INVALID;++i){
-      if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
+    for(NodeIt it(graph); it != INVALID; ++it) {
+      if(!bfs.reached(it)){
+        bfs.addSource(it);
+        while (!bfs.emptyQueue()) {
+          bfs.processNextNode();
+          if (!bipartite) return false;
+        }
+      }
     }
     return true;
@@ -1440 +1506 @@
   template<typename UGraph, typename NodeMap>
   inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
+    using namespace _topology_bits;
+
     checkConcept<concepts::UGraph, UGraph>();
     
@@ -1445 +1513 @@
     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(EdgeIt i(graph);i!=INVALID;++i){
-      if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
+    for(NodeIt it(graph); it != INVALID; ++it) {
+      if(!bfs.reached(it)){
+        bfs.addSource(it);
+        while (!bfs.emptyQueue()) {
+          bfs.processNextNode();
+          if (!bipartite) 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;