Changeset 2499:c97596611d59 in lemon-0.x

Timestamp:

10/19/07 18:24:31 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Planar Grid Embedding

File:

• lemon/planarity.h (modified) (9 diffs)

lemon/planarity.h

@@ -19 +19 @@
 #define LEMON_PLANARITY_H
 
-/// \ingroup graph_prop
+/// \ingroup planar
 /// \file
 /// \brief Planarity checking, embedding
@@ -30 +30 @@
 #include <lemon/maps.h>
 #include <lemon/path.h>
+#include <lemon/iterable_maps.h>
+#include <lemon/edge_set.h>
 
 
@@ -135 +137 @@
   }
 
-  /// \ingroup  graph_prop
+  /// \ingroup planar
   ///
   /// \brief Planarity checking of an undirected simple graph
   ///
-  /// This class implements the Boyer-Myrvold algorithm for planar
+  /// This class implements the Boyer-Myrvold algorithm for planarity
   /// checking of an undirected graph. This class is a simplified
   /// version of the PlanarEmbedding algorithm class, and it does
@@ -147 +149 @@
   private:
     
-    UGRAPH_TYPEDEFS(typename UGraph)
+    UGRAPH_TYPEDEFS(typename UGraph);
       
     const UGraph& _ugraph;
@@ -523 +525 @@
   };
 
-  /// \ingroup graph_prop
+  /// \ingroup planar
   ///
   /// \brief Planar embedding of an undirected simple graph
@@ -542 +544 @@
   private:
     
-    UGRAPH_TYPEDEFS(typename UGraph)
+    UGRAPH_TYPEDEFS(typename UGraph);
       
     const UGraph& _ugraph;
@@ -586 +588 @@
 
   public:
+
+    /// \brief The map for store of embedding
+    typedef typename UGraph::template EdgeMap<Edge> EmbeddingMap;
 
     /// \brief Constructor
@@ -700 +705 @@
     Edge next(const Edge& edge) const {
       return _embedding[edge];
+    }
+
+    /// \brief Gives back the calculated embedding map
+    ///
+    /// The returned map contains the successor of each edge in the
+    /// graph.
+    const EmbeddingMap& embedding() const {
+      return _embedding;
     }
 
@@ -1807 +1820 @@
   };
 
+  namespace _planarity_bits {
+
+    template <typename UGraph, typename EmbeddingMap>
+    void makeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
+      DfsVisitor<UGraph> null_visitor;
+      DfsVisit<UGraph, DfsVisitor<UGraph> > dfs(ugraph, null_visitor);
+      dfs.init();
+
+      typename UGraph::Node u = INVALID;
+      for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
+        if (!dfs.reached(n)) {
+          dfs.addSource(n);
+          dfs.start();
+          if (u == INVALID) {
+            u = n;
+          } else {
+            typename UGraph::Node v = n;
+            
+            typename UGraph::Edge ue = typename UGraph::OutEdgeIt(ugraph, u);
+            typename UGraph::Edge ve = typename UGraph::OutEdgeIt(ugraph, v);
+
+            typename UGraph::Edge e = ugraph.direct(ugraph.addEdge(u, v), true);
+            
+            if (ue != INVALID) {
+              embedding[e] = embedding[ue];
+              embedding[ue] = e;
+            } else {
+              embedding[e] = e;
+            }
+
+            if (ve != INVALID) {
+              embedding[ugraph.oppositeEdge(e)] = embedding[ve];
+              embedding[ve] = ugraph.oppositeEdge(e);
+            } else {
+              embedding[ugraph.oppositeEdge(e)] = ugraph.oppositeEdge(e);
+            }
+          }
+        }
+      }
+    }
+
+    template <typename UGraph, typename EmbeddingMap>
+    void makeBiNodeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
+      typename UGraph::template EdgeMap<bool> processed(ugraph);
+
+      std::vector<typename UGraph::Edge> edges;
+      for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
+        edges.push_back(e);
+      }
+
+      IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
+      
+      for (int i = 0; i < int(edges.size()); ++i) {
+        typename UGraph::Edge pp = edges[i];
+        if (processed[pp]) continue;
+
+        typename UGraph::Edge e = embedding[ugraph.oppositeEdge(pp)];
+        processed[e] = true;
+        visited.set(ugraph.source(e), true);
+        
+        typename UGraph::Edge p = e, l = e;
+        e = embedding[ugraph.oppositeEdge(e)];
+        
+        while (e != l) {
+          processed[e] = true;
+
+          if (visited[ugraph.source(e)]) {
+            
+            typename UGraph::Edge n = 
+              ugraph.direct(ugraph.addEdge(ugraph.source(p), 
+                                           ugraph.target(e)), true);
+            embedding[n] = p;
+            embedding[ugraph.oppositeEdge(pp)] = n;
+
+            embedding[ugraph.oppositeEdge(n)] = 
+              embedding[ugraph.oppositeEdge(e)];
+            embedding[ugraph.oppositeEdge(e)] = 
+              ugraph.oppositeEdge(n);
+            
+            p = n;
+            e = embedding[ugraph.oppositeEdge(n)];
+          } else {
+            visited.set(ugraph.source(e), true);
+            pp = p;
+            p = e;
+            e = embedding[ugraph.oppositeEdge(e)];
+          }
+        }
+        visited.setAll(false);
+      }
+    }
+    
+    
+    template <typename UGraph, typename EmbeddingMap>
+    void makeMaxPlanar(UGraph& ugraph, EmbeddingMap& embedding) {
+      
+      typename UGraph::template NodeMap<int> degree(ugraph);
+
+      for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
+        degree[n] = countIncEdges(ugraph, n);
+      }
+
+      typename UGraph::template EdgeMap<bool> processed(ugraph);
+      IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
+
+      std::vector<typename UGraph::Edge> edges;
+      for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
+        edges.push_back(e);
+      }
+
+      for (int i = 0; i < int(edges.size()); ++i) {
+        typename UGraph::Edge e = edges[i];
+
+        if (processed[e]) continue;
+        processed[e] = true;
+
+        typename UGraph::Edge mine = e;
+        int mind = degree[ugraph.source(e)];
+
+        int face_size = 1;      
+
+        typename UGraph::Edge l = e;
+        e = embedding[ugraph.oppositeEdge(e)];
+        while (l != e) {
+          processed[e] = true;
+
+          ++face_size;
+
+          if (degree[ugraph.source(e)] < mind) {
+            mine = e;
+            mind = degree[ugraph.source(e)];
+          }
+          
+          e = embedding[ugraph.oppositeEdge(e)];          
+        }
+        
+        if (face_size < 4) {
+          continue;
+        }
+
+        typename UGraph::Node s = ugraph.source(mine);
+        for (typename UGraph::OutEdgeIt e(ugraph, s); e != INVALID; ++e) {
+          visited.set(ugraph.target(e), true); 
+        }
+
+        typename UGraph::Edge oppe = INVALID;
+
+        e = embedding[ugraph.oppositeEdge(mine)];
+        e = embedding[ugraph.oppositeEdge(e)];
+        while (ugraph.target(e) != s) {
+          if (visited[ugraph.source(e)]) {
+            oppe = e;
+            break;
+          }
+          e = embedding[ugraph.oppositeEdge(e)];
+        }
+        visited.setAll(false);
+        
+        if (oppe == INVALID) {
+
+          e = embedding[ugraph.oppositeEdge(mine)];
+          typename UGraph::Edge pn = mine, p = e;
+
+          e = embedding[ugraph.oppositeEdge(e)];
+          while (ugraph.target(e) != s) {
+            typename UGraph::Edge n = 
+              ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
+
+            embedding[n] = pn;
+            embedding[ugraph.oppositeEdge(n)] = e;
+            embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
+
+            pn = n;
+            
+            p = e;
+            e = embedding[ugraph.oppositeEdge(e)];
+          }
+
+          embedding[ugraph.oppositeEdge(e)] = pn;
+
+        } else {
+
+          mine = embedding[ugraph.oppositeEdge(mine)];
+          s = ugraph.source(mine);
+          oppe = embedding[ugraph.oppositeEdge(oppe)];
+          typename UGraph::Node t = ugraph.source(oppe);
+          
+          typename UGraph::Edge ce = ugraph.direct(ugraph.addEdge(s, t), true);
+          embedding[ce] = mine;
+          embedding[ugraph.oppositeEdge(ce)] = oppe;
+
+          typename UGraph::Edge pn = ce, p = oppe;        
+          e = embedding[ugraph.oppositeEdge(oppe)];
+          while (ugraph.target(e) != s) {
+            typename UGraph::Edge n = 
+              ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
+
+            embedding[n] = pn;
+            embedding[ugraph.oppositeEdge(n)] = e;
+            embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
+
+            pn = n;
+            
+            p = e;
+            e = embedding[ugraph.oppositeEdge(e)];
+            
+          }
+          embedding[ugraph.oppositeEdge(e)] = pn;
+
+          pn = ugraph.oppositeEdge(ce), p = mine;         
+          e = embedding[ugraph.oppositeEdge(mine)];
+          while (ugraph.target(e) != t) {
+            typename UGraph::Edge n = 
+              ugraph.direct(ugraph.addEdge(t, ugraph.source(e)), true);
+
+            embedding[n] = pn;
+            embedding[ugraph.oppositeEdge(n)] = e;
+            embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
+
+            pn = n;
+            
+            p = e;
+            e = embedding[ugraph.oppositeEdge(e)];
+            
+          }
+          embedding[ugraph.oppositeEdge(e)] = pn;
+        }
+      }
+    }
+
+  }
+
+  /// \brief Schnyder's planar drawing algorithms
+  ///
+  /// The planar drawing algorithm calculates location for each node
+  /// in the plane, which coordinates satisfies that if each edge is
+  /// represented with a straight line then the edges will not
+  /// intersect each other.
+  ///
+  /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
+  /// ie. each node will be located in the \c [0,n-2]x[0,n-2] square.
+  /// The time complexity of the algorithm is O(n).
+  template <typename UGraph>
+  class PlanarDrawing {
+  public:
+
+    UGRAPH_TYPEDEFS(typename UGraph);
+
+    /// \brief The point type for store coordinates
+    typedef dim2::Point<int> Point;
+    /// \brief The map type for store coordinates
+    typedef typename UGraph::template NodeMap<Point> PointMap;
+
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    /// \pre The ugraph should be simple, ie. loop and parallel edge free. 
+    PlanarDrawing(const UGraph& ugraph)
+      : _ugraph(ugraph), _point_map(ugraph) {}
+
+  private:
+
+    template <typename AuxUGraph, typename AuxEmbeddingMap>
+    void drawing(const AuxUGraph& ugraph, 
+                 const AuxEmbeddingMap& next, 
+                 PointMap& point_map) {
+      UGRAPH_TYPEDEFS(typename AuxUGraph);
+
+      typename AuxUGraph::template EdgeMap<Edge> prev(ugraph);
+
+      for (NodeIt n(ugraph); n != INVALID; ++n) {
+        Edge e = OutEdgeIt(ugraph, n);
+        
+        Edge p = e, l = e;
+        
+        e = next[e];
+        while (e != l) {
+          prev[e] = p;
+          p = e;
+          e = next[e];
+        }
+        prev[e] = p;
+      }
+
+      Node anode, bnode, cnode;
+
+      {
+        Edge e = EdgeIt(ugraph);
+        anode = ugraph.source(e);
+        bnode = ugraph.target(e);
+        cnode = ugraph.target(next[ugraph.oppositeEdge(e)]);
+      }
+      
+      IterableBoolMap<AuxUGraph, Node> proper(ugraph, false);
+      typename AuxUGraph::template NodeMap<int> conn(ugraph, -1);
+
+      conn[anode] = conn[bnode] = -2;      
+      {
+        for (OutEdgeIt e(ugraph, anode); e != INVALID; ++e) {
+          Node m = ugraph.target(e);
+          if (conn[m] == -1) {
+            conn[m] = 1;
+          }
+        }
+        conn[cnode] = 2;
+
+        for (OutEdgeIt e(ugraph, bnode); e != INVALID; ++e) {
+          Node m = ugraph.target(e);
+          if (conn[m] == -1) {
+            conn[m] = 1;
+          } else if (conn[m] != -2) {
+            conn[m] += 1;           
+            Edge pe = ugraph.oppositeEdge(e);
+            if (conn[ugraph.target(next[pe])] == -2) {
+              conn[m] -= 1;
+            }
+            if (conn[ugraph.target(prev[pe])] == -2) {
+              conn[m] -= 1;
+            }
+
+            proper.set(m, conn[m] == 1);
+          }
+        }
+      }
+      
+
+      typename AuxUGraph::template EdgeMap<int> angle(ugraph, -1);
+
+      while (proper.trueNum() != 0) {
+        Node n = typename IterableBoolMap<AuxUGraph, Node>::TrueIt(proper);
+        proper.set(n, false);
+        conn[n] = -2;
+
+        for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
+          Node m = ugraph.target(e);
+          if (conn[m] == -1) {
+            conn[m] = 1;
+          } else if (conn[m] != -2) {
+            conn[m] += 1;           
+            Edge pe = ugraph.oppositeEdge(e);
+            if (conn[ugraph.target(next[pe])] == -2) {
+              conn[m] -= 1;
+            }
+            if (conn[ugraph.target(prev[pe])] == -2) {
+              conn[m] -= 1;
+            }
+
+            proper.set(m, conn[m] == 1);
+          }
+        }
+
+        {
+          Edge e = OutEdgeIt(ugraph, n);
+          Edge p = e, l = e;
+          
+          e = next[e];
+          while (e != l) {
+            
+            if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
+              Edge f = e;
+              angle[f] = 0;
+              f = next[ugraph.oppositeEdge(f)];
+              angle[f] = 1;
+              f = next[ugraph.oppositeEdge(f)];
+              angle[f] = 2;
+            }
+            
+            p = e;
+            e = next[e];
+          }
+          
+          if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
+            Edge f = e;
+            angle[f] = 0;
+            f = next[ugraph.oppositeEdge(f)];
+            angle[f] = 1;
+            f = next[ugraph.oppositeEdge(f)];
+            angle[f] = 2;
+          }
+        }
+      }
+
+      typename AuxUGraph::template NodeMap<Node> apred(ugraph, INVALID);
+      typename AuxUGraph::template NodeMap<Node> bpred(ugraph, INVALID);
+      typename AuxUGraph::template NodeMap<Node> cpred(ugraph, INVALID);
+
+      typename AuxUGraph::template NodeMap<int> apredid(ugraph, -1);
+      typename AuxUGraph::template NodeMap<int> bpredid(ugraph, -1);
+      typename AuxUGraph::template NodeMap<int> cpredid(ugraph, -1);
+
+      for (EdgeIt e(ugraph); e != INVALID; ++e) {
+        if (angle[e] == angle[next[e]]) {
+          switch (angle[e]) {
+          case 2:
+            apred[ugraph.target(e)] = ugraph.source(e);
+            apredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
+            break;
+          case 1:
+            bpred[ugraph.target(e)] = ugraph.source(e);
+            bpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
+            break;
+          case 0:
+            cpred[ugraph.target(e)] = ugraph.source(e);
+            cpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
+            break;
+          }
+        }
+      }
+
+      cpred[anode] = INVALID;
+      cpred[bnode] = INVALID;
+
+      std::vector<Node> aorder, border, corder; 
+
+      {
+        typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
+        std::vector<Node> st;
+        for (NodeIt n(ugraph); n != INVALID; ++n) {
+          if (!processed[n] && n != bnode && n != cnode) {
+            st.push_back(n);
+            processed[n] = true;
+            Node m = apred[n];
+            while (m != INVALID && !processed[m]) {
+              st.push_back(m);
+              processed[m] = true;
+              m = apred[m];
+            }
+            while (!st.empty()) {
+              aorder.push_back(st.back());
+              st.pop_back();
+            }
+          }
+        }
+      }
+
+      {
+        typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
+        std::vector<Node> st;
+        for (NodeIt n(ugraph); n != INVALID; ++n) {
+          if (!processed[n] && n != cnode && n != anode) {
+            st.push_back(n);
+            processed[n] = true;
+            Node m = bpred[n];
+            while (m != INVALID && !processed[m]) {
+              st.push_back(m);
+              processed[m] = true;
+              m = bpred[m];
+            }
+            while (!st.empty()) {
+              border.push_back(st.back());
+              st.pop_back();
+            }
+          }
+        }
+      }
+
+      {
+        typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
+        std::vector<Node> st;
+        for (NodeIt n(ugraph); n != INVALID; ++n) {
+          if (!processed[n] && n != anode && n != bnode) {
+            st.push_back(n);
+            processed[n] = true;
+            Node m = cpred[n];
+            while (m != INVALID && !processed[m]) {
+              st.push_back(m);
+              processed[m] = true;
+              m = cpred[m];
+            }
+            while (!st.empty()) {
+              corder.push_back(st.back());
+              st.pop_back();
+            }
+          }
+        }
+      }
+
+      typename AuxUGraph::template NodeMap<int> atree(ugraph, 0);
+      for (int i = aorder.size() - 1; i >= 0; --i) {
+        Node n = aorder[i];
+        atree[n] = 1;
+        for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
+          if (apred[ugraph.target(e)] == n) {
+            atree[n] += atree[ugraph.target(e)];
+          }
+        } 
+      }
+
+      typename AuxUGraph::template NodeMap<int> btree(ugraph, 0);
+      for (int i = border.size() - 1; i >= 0; --i) {
+        Node n = border[i];
+        btree[n] = 1;
+        for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
+          if (bpred[ugraph.target(e)] == n) {
+            btree[n] += btree[ugraph.target(e)];
+          }
+        } 
+      }
+      
+      typename AuxUGraph::template NodeMap<int> apath(ugraph, 0);
+      apath[bnode] = apath[cnode] = 1;
+      typename AuxUGraph::template NodeMap<int> apath_btree(ugraph, 0);
+      apath_btree[bnode] = btree[bnode];
+      for (int i = 1; i < int(aorder.size()); ++i) {
+        Node n = aorder[i];
+        apath[n] = apath[apred[n]] + 1;
+        apath_btree[n] = btree[n] + apath_btree[apred[n]];
+      }
+
+      typename AuxUGraph::template NodeMap<int> bpath_atree(ugraph, 0);
+      bpath_atree[anode] = atree[anode];
+      for (int i = 1; i < int(border.size()); ++i) {
+        Node n = border[i];
+        bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];
+      }
+
+      typename AuxUGraph::template NodeMap<int> cpath(ugraph, 0);
+      cpath[anode] = cpath[bnode] = 1;
+      typename AuxUGraph::template NodeMap<int> cpath_atree(ugraph, 0);
+      cpath_atree[anode] = atree[anode];
+      typename AuxUGraph::template NodeMap<int> cpath_btree(ugraph, 0);
+      cpath_btree[bnode] = btree[bnode];
+      for (int i = 1; i < int(corder.size()); ++i) {
+        Node n = corder[i];
+        cpath[n] = cpath[cpred[n]] + 1;
+        cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];
+        cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];
+      }
+
+      typename AuxUGraph::template NodeMap<int> third(ugraph);
+      for (NodeIt n(ugraph); n != INVALID; ++n) {
+        point_map[n].x = 
+          bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;
+        point_map[n].y = 
+          cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;
+      }
+      
+    }
+
+  public:
+
+    /// \brief Calculates the node locations
+    ///
+    /// This function calculates the node locations.
+    bool run() {
+      PlanarEmbedding<UGraph> pe(_ugraph);
+      if (!pe.run()) return false;
+      
+      run(pe);
+      return true;
+    }
+
+    /// \brief Calculates the node locations according to a
+    /// combinatorical embedding
+    ///
+    /// This function calculates the node locations. The \c embedding
+    /// parameter should contain a valid combinatorical embedding, ie.
+    /// a valid cyclic order of the edges.
+    template <typename EmbeddingMap>
+    void run(const EmbeddingMap& embedding) {
+      typedef SmartUEdgeSet<UGraph> AuxUGraph; 
+
+      if (3 * countNodes(_ugraph) - 6 == countUEdges(_ugraph)) {
+        drawing(_ugraph, embedding, _point_map);
+        return;
+      }
+
+      AuxUGraph aux_ugraph(_ugraph);
+      typename AuxUGraph::template EdgeMap<typename AuxUGraph::Edge> 
+        aux_embedding(aux_ugraph);
+
+      {
+
+        typename UGraph::template UEdgeMap<typename AuxUGraph::UEdge> 
+          ref(_ugraph);
+        
+        for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
+          ref[e] = aux_ugraph.addEdge(_ugraph.source(e), _ugraph.target(e));
+        }
+
+        for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
+          Edge ee = embedding[_ugraph.direct(e, true)];
+          aux_embedding[aux_ugraph.direct(ref[e], true)] = 
+            aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
+          ee = embedding[_ugraph.direct(e, false)];
+          aux_embedding[aux_ugraph.direct(ref[e], false)] = 
+            aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
+        }
+      }
+      _planarity_bits::makeConnected(aux_ugraph, aux_embedding);
+      _planarity_bits::makeBiNodeConnected(aux_ugraph, aux_embedding);
+      _planarity_bits::makeMaxPlanar(aux_ugraph, aux_embedding);
+      drawing(aux_ugraph, aux_embedding, _point_map);
+    }
+
+    /// \brief The coordinate of the given node
+    ///
+    /// The coordinate of the given node.
+    Point operator[](const Node& node) {
+      return _point_map[node];
+    }
+
+    /// \brief Returns the grid embedding in a \e NodeMap.
+    ///
+    /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
+    const PointMap& coords() const {
+      return _point_map;
+    }
+
+  private:
+    
+    const UGraph& _ugraph;
+    PointMap _point_map;
+    
+  };
+
 }