Changeset 1800:d391ea416aa0 in lemon-0.x

Timestamp:

11/16/05 10:10:24 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

bipartite by szakall

File:

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

lemon/topology.h

@@ -481 +481 @@
     
     template <typename Graph>
-    class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -487 +487 @@
       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 +539 @@
 
     template <typename Graph, typename EdgeMap>
-    class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -545 +545 @@
       typedef typename Graph::UndirEdge UndirEdge;
 
-      NodeBiconnectedComponentsVisitor(const Graph& graph, 
+      BiNodeConnectedComponentsVisitor(const Graph& graph, 
                                        EdgeMap& compMap, int &compNum) 
         : _graph(graph), _compMap(compMap), _compNum(compNum), 
@@ -619 +619 @@
 
     template <typename Graph, typename NodeMap>
-    class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
+    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -625 +625 @@
       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 +697 @@
 
   template <typename UndirGraph>
-  int countNodeBiconnectedComponents(const UndirGraph& graph);
+  int countBiNodeConnectedComponents(const UndirGraph& graph);
 
   /// \ingroup topology
@@ -712 +712 @@
   template <typename UndirGraph>
   bool biNodeConnected(const UndirGraph& graph) {
-    return countNodeBiconnectedComponents(graph) == 1;
+    return countBiNodeConnectedComponents(graph) == 1;
   }
 
@@ -727 +727 @@
   /// \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 +733 @@
     using namespace _topology_bits;
 
-    typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
+    typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor;
 
     int compNum = 0;
@@ -779 +779 @@
     using namespace _topology_bits;
 
-    typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
+    typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
     
     int compNum = 0;
@@ -819 +819 @@
     using namespace _topology_bits;
 
-    typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
+    typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
     
     int cutNum = 0;
@@ -839 +839 @@
     
     template <typename Graph>
-    class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -845 +845 @@
       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 +895 @@
 
     template <typename Graph, typename NodeMap>
-    class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
+    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -901 +901 @@
       typedef typename Graph::UndirEdge UndirEdge;
 
-      EdgeBiconnectedComponentsVisitor(const Graph& graph, 
+      BiEdgeConnectedComponentsVisitor(const Graph& graph, 
                                        NodeMap& compMap, int &compNum) 
         : _graph(graph), _compMap(compMap), _compNum(compNum), 
@@ -962 +962 @@
 
     template <typename Graph, typename EdgeMap>
-    class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
+    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
     public:
       typedef typename Graph::Node Node;
@@ -968 +968 @@
       typedef typename Graph::UndirEdge UndirEdge;
 
-      EdgeBiconnectedCutEdgesVisitor(const Graph& graph, 
+      BiEdgeConnectedCutEdgesVisitor(const Graph& graph, 
                                      EdgeMap& cutMap, int &cutNum) 
         : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 
@@ -1024 +1024 @@
 
   template <typename UndirGraph>
-  int countEdgeBiconnectedComponents(const UndirGraph& graph);
+  int countbiEdgeConnectedComponents(const UndirGraph& graph);
 
   /// \ingroup topology
@@ -1039 +1039 @@
   template <typename UndirGraph>
   bool biEdgeConnected(const UndirGraph& graph) { 
-    return countEdgeBiconnectedComponents(graph) == 1;
+    return countBiEdgeConnectedComponents(graph) == 1;
   }
 
@@ -1054 +1054 @@
   /// \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 +1060 @@
     using namespace _topology_bits;
 
-    typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
+    typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor;
     
     int compNum = 0;
@@ -1105 +1105 @@
     using namespace _topology_bits;
 
-    typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
+    typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
     
     int compNum = 0;
@@ -1146 +1146 @@
     using namespace _topology_bits;
 
-    typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
+    typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
     
     int cutNum = 0;
@@ -1389 +1389 @@
   /// \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