COIN-OR::LEMON - Graph Library

Changeset 2499:c97596611d59 in lemon-0.x


Ignore:
Timestamp:
10/19/07 18:24:31 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3338
Message:

Planar Grid Embedding

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/planarity.h

    r2481 r2499  
    1919#define LEMON_PLANARITY_H
    2020
    21 /// \ingroup graph_prop
     21/// \ingroup planar
    2222/// \file
    2323/// \brief Planarity checking, embedding
     
    3030#include <lemon/maps.h>
    3131#include <lemon/path.h>
     32#include <lemon/iterable_maps.h>
     33#include <lemon/edge_set.h>
    3234
    3335
     
    135137  }
    136138
    137   /// \ingroup  graph_prop
     139  /// \ingroup planar
    138140  ///
    139141  /// \brief Planarity checking of an undirected simple graph
    140142  ///
    141   /// This class implements the Boyer-Myrvold algorithm for planar
     143  /// This class implements the Boyer-Myrvold algorithm for planarity
    142144  /// checking of an undirected graph. This class is a simplified
    143145  /// version of the PlanarEmbedding algorithm class, and it does
     
    147149  private:
    148150   
    149     UGRAPH_TYPEDEFS(typename UGraph)
     151    UGRAPH_TYPEDEFS(typename UGraph);
    150152     
    151153    const UGraph& _ugraph;
     
    523525  };
    524526
    525   /// \ingroup graph_prop
     527  /// \ingroup planar
    526528  ///
    527529  /// \brief Planar embedding of an undirected simple graph
     
    542544  private:
    543545   
    544     UGRAPH_TYPEDEFS(typename UGraph)
     546    UGRAPH_TYPEDEFS(typename UGraph);
    545547     
    546548    const UGraph& _ugraph;
     
    586588
    587589  public:
     590
     591    /// \brief The map for store of embedding
     592    typedef typename UGraph::template EdgeMap<Edge> EmbeddingMap;
    588593
    589594    /// \brief Constructor
     
    700705    Edge next(const Edge& edge) const {
    701706      return _embedding[edge];
     707    }
     708
     709    /// \brief Gives back the calculated embedding map
     710    ///
     711    /// The returned map contains the successor of each edge in the
     712    /// graph.
     713    const EmbeddingMap& embedding() const {
     714      return _embedding;
    702715    }
    703716
     
    18071820  };
    18081821
     1822  namespace _planarity_bits {
     1823
     1824    template <typename UGraph, typename EmbeddingMap>
     1825    void makeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
     1826      DfsVisitor<UGraph> null_visitor;
     1827      DfsVisit<UGraph, DfsVisitor<UGraph> > dfs(ugraph, null_visitor);
     1828      dfs.init();
     1829
     1830      typename UGraph::Node u = INVALID;
     1831      for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
     1832        if (!dfs.reached(n)) {
     1833          dfs.addSource(n);
     1834          dfs.start();
     1835          if (u == INVALID) {
     1836            u = n;
     1837          } else {
     1838            typename UGraph::Node v = n;
     1839           
     1840            typename UGraph::Edge ue = typename UGraph::OutEdgeIt(ugraph, u);
     1841            typename UGraph::Edge ve = typename UGraph::OutEdgeIt(ugraph, v);
     1842
     1843            typename UGraph::Edge e = ugraph.direct(ugraph.addEdge(u, v), true);
     1844           
     1845            if (ue != INVALID) {
     1846              embedding[e] = embedding[ue];
     1847              embedding[ue] = e;
     1848            } else {
     1849              embedding[e] = e;
     1850            }
     1851
     1852            if (ve != INVALID) {
     1853              embedding[ugraph.oppositeEdge(e)] = embedding[ve];
     1854              embedding[ve] = ugraph.oppositeEdge(e);
     1855            } else {
     1856              embedding[ugraph.oppositeEdge(e)] = ugraph.oppositeEdge(e);
     1857            }
     1858          }
     1859        }
     1860      }
     1861    }
     1862
     1863    template <typename UGraph, typename EmbeddingMap>
     1864    void makeBiNodeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
     1865      typename UGraph::template EdgeMap<bool> processed(ugraph);
     1866
     1867      std::vector<typename UGraph::Edge> edges;
     1868      for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
     1869        edges.push_back(e);
     1870      }
     1871
     1872      IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
     1873     
     1874      for (int i = 0; i < int(edges.size()); ++i) {
     1875        typename UGraph::Edge pp = edges[i];
     1876        if (processed[pp]) continue;
     1877
     1878        typename UGraph::Edge e = embedding[ugraph.oppositeEdge(pp)];
     1879        processed[e] = true;
     1880        visited.set(ugraph.source(e), true);
     1881       
     1882        typename UGraph::Edge p = e, l = e;
     1883        e = embedding[ugraph.oppositeEdge(e)];
     1884       
     1885        while (e != l) {
     1886          processed[e] = true;
     1887
     1888          if (visited[ugraph.source(e)]) {
     1889           
     1890            typename UGraph::Edge n =
     1891              ugraph.direct(ugraph.addEdge(ugraph.source(p),
     1892                                           ugraph.target(e)), true);
     1893            embedding[n] = p;
     1894            embedding[ugraph.oppositeEdge(pp)] = n;
     1895
     1896            embedding[ugraph.oppositeEdge(n)] =
     1897              embedding[ugraph.oppositeEdge(e)];
     1898            embedding[ugraph.oppositeEdge(e)] =
     1899              ugraph.oppositeEdge(n);
     1900           
     1901            p = n;
     1902            e = embedding[ugraph.oppositeEdge(n)];
     1903          } else {
     1904            visited.set(ugraph.source(e), true);
     1905            pp = p;
     1906            p = e;
     1907            e = embedding[ugraph.oppositeEdge(e)];
     1908          }
     1909        }
     1910        visited.setAll(false);
     1911      }
     1912    }
     1913   
     1914   
     1915    template <typename UGraph, typename EmbeddingMap>
     1916    void makeMaxPlanar(UGraph& ugraph, EmbeddingMap& embedding) {
     1917     
     1918      typename UGraph::template NodeMap<int> degree(ugraph);
     1919
     1920      for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
     1921        degree[n] = countIncEdges(ugraph, n);
     1922      }
     1923
     1924      typename UGraph::template EdgeMap<bool> processed(ugraph);
     1925      IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
     1926
     1927      std::vector<typename UGraph::Edge> edges;
     1928      for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
     1929        edges.push_back(e);
     1930      }
     1931
     1932      for (int i = 0; i < int(edges.size()); ++i) {
     1933        typename UGraph::Edge e = edges[i];
     1934
     1935        if (processed[e]) continue;
     1936        processed[e] = true;
     1937
     1938        typename UGraph::Edge mine = e;
     1939        int mind = degree[ugraph.source(e)];
     1940
     1941        int face_size = 1;     
     1942
     1943        typename UGraph::Edge l = e;
     1944        e = embedding[ugraph.oppositeEdge(e)];
     1945        while (l != e) {
     1946          processed[e] = true;
     1947
     1948          ++face_size;
     1949
     1950          if (degree[ugraph.source(e)] < mind) {
     1951            mine = e;
     1952            mind = degree[ugraph.source(e)];
     1953          }
     1954         
     1955          e = embedding[ugraph.oppositeEdge(e)];         
     1956        }
     1957       
     1958        if (face_size < 4) {
     1959          continue;
     1960        }
     1961
     1962        typename UGraph::Node s = ugraph.source(mine);
     1963        for (typename UGraph::OutEdgeIt e(ugraph, s); e != INVALID; ++e) {
     1964          visited.set(ugraph.target(e), true);
     1965        }
     1966
     1967        typename UGraph::Edge oppe = INVALID;
     1968
     1969        e = embedding[ugraph.oppositeEdge(mine)];
     1970        e = embedding[ugraph.oppositeEdge(e)];
     1971        while (ugraph.target(e) != s) {
     1972          if (visited[ugraph.source(e)]) {
     1973            oppe = e;
     1974            break;
     1975          }
     1976          e = embedding[ugraph.oppositeEdge(e)];
     1977        }
     1978        visited.setAll(false);
     1979       
     1980        if (oppe == INVALID) {
     1981
     1982          e = embedding[ugraph.oppositeEdge(mine)];
     1983          typename UGraph::Edge pn = mine, p = e;
     1984
     1985          e = embedding[ugraph.oppositeEdge(e)];
     1986          while (ugraph.target(e) != s) {
     1987            typename UGraph::Edge n =
     1988              ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
     1989
     1990            embedding[n] = pn;
     1991            embedding[ugraph.oppositeEdge(n)] = e;
     1992            embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
     1993
     1994            pn = n;
     1995           
     1996            p = e;
     1997            e = embedding[ugraph.oppositeEdge(e)];
     1998          }
     1999
     2000          embedding[ugraph.oppositeEdge(e)] = pn;
     2001
     2002        } else {
     2003
     2004          mine = embedding[ugraph.oppositeEdge(mine)];
     2005          s = ugraph.source(mine);
     2006          oppe = embedding[ugraph.oppositeEdge(oppe)];
     2007          typename UGraph::Node t = ugraph.source(oppe);
     2008         
     2009          typename UGraph::Edge ce = ugraph.direct(ugraph.addEdge(s, t), true);
     2010          embedding[ce] = mine;
     2011          embedding[ugraph.oppositeEdge(ce)] = oppe;
     2012
     2013          typename UGraph::Edge pn = ce, p = oppe;       
     2014          e = embedding[ugraph.oppositeEdge(oppe)];
     2015          while (ugraph.target(e) != s) {
     2016            typename UGraph::Edge n =
     2017              ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
     2018
     2019            embedding[n] = pn;
     2020            embedding[ugraph.oppositeEdge(n)] = e;
     2021            embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
     2022
     2023            pn = n;
     2024           
     2025            p = e;
     2026            e = embedding[ugraph.oppositeEdge(e)];
     2027           
     2028          }
     2029          embedding[ugraph.oppositeEdge(e)] = pn;
     2030
     2031          pn = ugraph.oppositeEdge(ce), p = mine;         
     2032          e = embedding[ugraph.oppositeEdge(mine)];
     2033          while (ugraph.target(e) != t) {
     2034            typename UGraph::Edge n =
     2035              ugraph.direct(ugraph.addEdge(t, ugraph.source(e)), true);
     2036
     2037            embedding[n] = pn;
     2038            embedding[ugraph.oppositeEdge(n)] = e;
     2039            embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
     2040
     2041            pn = n;
     2042           
     2043            p = e;
     2044            e = embedding[ugraph.oppositeEdge(e)];
     2045           
     2046          }
     2047          embedding[ugraph.oppositeEdge(e)] = pn;
     2048        }
     2049      }
     2050    }
     2051
     2052  }
     2053
     2054  /// \brief Schnyder's planar drawing algorithms
     2055  ///
     2056  /// The planar drawing algorithm calculates location for each node
     2057  /// in the plane, which coordinates satisfies that if each edge is
     2058  /// represented with a straight line then the edges will not
     2059  /// intersect each other.
     2060  ///
     2061  /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
     2062  /// ie. each node will be located in the \c [0,n-2]x[0,n-2] square.
     2063  /// The time complexity of the algorithm is O(n).
     2064  template <typename UGraph>
     2065  class PlanarDrawing {
     2066  public:
     2067
     2068    UGRAPH_TYPEDEFS(typename UGraph);
     2069
     2070    /// \brief The point type for store coordinates
     2071    typedef dim2::Point<int> Point;
     2072    /// \brief The map type for store coordinates
     2073    typedef typename UGraph::template NodeMap<Point> PointMap;
     2074
     2075
     2076    /// \brief Constructor
     2077    ///
     2078    /// Constructor
     2079    /// \pre The ugraph should be simple, ie. loop and parallel edge free.
     2080    PlanarDrawing(const UGraph& ugraph)
     2081      : _ugraph(ugraph), _point_map(ugraph) {}
     2082
     2083  private:
     2084
     2085    template <typename AuxUGraph, typename AuxEmbeddingMap>
     2086    void drawing(const AuxUGraph& ugraph,
     2087                 const AuxEmbeddingMap& next,
     2088                 PointMap& point_map) {
     2089      UGRAPH_TYPEDEFS(typename AuxUGraph);
     2090
     2091      typename AuxUGraph::template EdgeMap<Edge> prev(ugraph);
     2092
     2093      for (NodeIt n(ugraph); n != INVALID; ++n) {
     2094        Edge e = OutEdgeIt(ugraph, n);
     2095       
     2096        Edge p = e, l = e;
     2097       
     2098        e = next[e];
     2099        while (e != l) {
     2100          prev[e] = p;
     2101          p = e;
     2102          e = next[e];
     2103        }
     2104        prev[e] = p;
     2105      }
     2106
     2107      Node anode, bnode, cnode;
     2108
     2109      {
     2110        Edge e = EdgeIt(ugraph);
     2111        anode = ugraph.source(e);
     2112        bnode = ugraph.target(e);
     2113        cnode = ugraph.target(next[ugraph.oppositeEdge(e)]);
     2114      }
     2115     
     2116      IterableBoolMap<AuxUGraph, Node> proper(ugraph, false);
     2117      typename AuxUGraph::template NodeMap<int> conn(ugraph, -1);
     2118
     2119      conn[anode] = conn[bnode] = -2;     
     2120      {
     2121        for (OutEdgeIt e(ugraph, anode); e != INVALID; ++e) {
     2122          Node m = ugraph.target(e);
     2123          if (conn[m] == -1) {
     2124            conn[m] = 1;
     2125          }
     2126        }
     2127        conn[cnode] = 2;
     2128
     2129        for (OutEdgeIt e(ugraph, bnode); e != INVALID; ++e) {
     2130          Node m = ugraph.target(e);
     2131          if (conn[m] == -1) {
     2132            conn[m] = 1;
     2133          } else if (conn[m] != -2) {
     2134            conn[m] += 1;           
     2135            Edge pe = ugraph.oppositeEdge(e);
     2136            if (conn[ugraph.target(next[pe])] == -2) {
     2137              conn[m] -= 1;
     2138            }
     2139            if (conn[ugraph.target(prev[pe])] == -2) {
     2140              conn[m] -= 1;
     2141            }
     2142
     2143            proper.set(m, conn[m] == 1);
     2144          }
     2145        }
     2146      }
     2147     
     2148
     2149      typename AuxUGraph::template EdgeMap<int> angle(ugraph, -1);
     2150
     2151      while (proper.trueNum() != 0) {
     2152        Node n = typename IterableBoolMap<AuxUGraph, Node>::TrueIt(proper);
     2153        proper.set(n, false);
     2154        conn[n] = -2;
     2155
     2156        for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
     2157          Node m = ugraph.target(e);
     2158          if (conn[m] == -1) {
     2159            conn[m] = 1;
     2160          } else if (conn[m] != -2) {
     2161            conn[m] += 1;           
     2162            Edge pe = ugraph.oppositeEdge(e);
     2163            if (conn[ugraph.target(next[pe])] == -2) {
     2164              conn[m] -= 1;
     2165            }
     2166            if (conn[ugraph.target(prev[pe])] == -2) {
     2167              conn[m] -= 1;
     2168            }
     2169
     2170            proper.set(m, conn[m] == 1);
     2171          }
     2172        }
     2173
     2174        {
     2175          Edge e = OutEdgeIt(ugraph, n);
     2176          Edge p = e, l = e;
     2177         
     2178          e = next[e];
     2179          while (e != l) {
     2180           
     2181            if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
     2182              Edge f = e;
     2183              angle[f] = 0;
     2184              f = next[ugraph.oppositeEdge(f)];
     2185              angle[f] = 1;
     2186              f = next[ugraph.oppositeEdge(f)];
     2187              angle[f] = 2;
     2188            }
     2189           
     2190            p = e;
     2191            e = next[e];
     2192          }
     2193         
     2194          if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
     2195            Edge f = e;
     2196            angle[f] = 0;
     2197            f = next[ugraph.oppositeEdge(f)];
     2198            angle[f] = 1;
     2199            f = next[ugraph.oppositeEdge(f)];
     2200            angle[f] = 2;
     2201          }
     2202        }
     2203      }
     2204
     2205      typename AuxUGraph::template NodeMap<Node> apred(ugraph, INVALID);
     2206      typename AuxUGraph::template NodeMap<Node> bpred(ugraph, INVALID);
     2207      typename AuxUGraph::template NodeMap<Node> cpred(ugraph, INVALID);
     2208
     2209      typename AuxUGraph::template NodeMap<int> apredid(ugraph, -1);
     2210      typename AuxUGraph::template NodeMap<int> bpredid(ugraph, -1);
     2211      typename AuxUGraph::template NodeMap<int> cpredid(ugraph, -1);
     2212
     2213      for (EdgeIt e(ugraph); e != INVALID; ++e) {
     2214        if (angle[e] == angle[next[e]]) {
     2215          switch (angle[e]) {
     2216          case 2:
     2217            apred[ugraph.target(e)] = ugraph.source(e);
     2218            apredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
     2219            break;
     2220          case 1:
     2221            bpred[ugraph.target(e)] = ugraph.source(e);
     2222            bpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
     2223            break;
     2224          case 0:
     2225            cpred[ugraph.target(e)] = ugraph.source(e);
     2226            cpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
     2227            break;
     2228          }
     2229        }
     2230      }
     2231
     2232      cpred[anode] = INVALID;
     2233      cpred[bnode] = INVALID;
     2234
     2235      std::vector<Node> aorder, border, corder;
     2236
     2237      {
     2238        typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
     2239        std::vector<Node> st;
     2240        for (NodeIt n(ugraph); n != INVALID; ++n) {
     2241          if (!processed[n] && n != bnode && n != cnode) {
     2242            st.push_back(n);
     2243            processed[n] = true;
     2244            Node m = apred[n];
     2245            while (m != INVALID && !processed[m]) {
     2246              st.push_back(m);
     2247              processed[m] = true;
     2248              m = apred[m];
     2249            }
     2250            while (!st.empty()) {
     2251              aorder.push_back(st.back());
     2252              st.pop_back();
     2253            }
     2254          }
     2255        }
     2256      }
     2257
     2258      {
     2259        typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
     2260        std::vector<Node> st;
     2261        for (NodeIt n(ugraph); n != INVALID; ++n) {
     2262          if (!processed[n] && n != cnode && n != anode) {
     2263            st.push_back(n);
     2264            processed[n] = true;
     2265            Node m = bpred[n];
     2266            while (m != INVALID && !processed[m]) {
     2267              st.push_back(m);
     2268              processed[m] = true;
     2269              m = bpred[m];
     2270            }
     2271            while (!st.empty()) {
     2272              border.push_back(st.back());
     2273              st.pop_back();
     2274            }
     2275          }
     2276        }
     2277      }
     2278
     2279      {
     2280        typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
     2281        std::vector<Node> st;
     2282        for (NodeIt n(ugraph); n != INVALID; ++n) {
     2283          if (!processed[n] && n != anode && n != bnode) {
     2284            st.push_back(n);
     2285            processed[n] = true;
     2286            Node m = cpred[n];
     2287            while (m != INVALID && !processed[m]) {
     2288              st.push_back(m);
     2289              processed[m] = true;
     2290              m = cpred[m];
     2291            }
     2292            while (!st.empty()) {
     2293              corder.push_back(st.back());
     2294              st.pop_back();
     2295            }
     2296          }
     2297        }
     2298      }
     2299
     2300      typename AuxUGraph::template NodeMap<int> atree(ugraph, 0);
     2301      for (int i = aorder.size() - 1; i >= 0; --i) {
     2302        Node n = aorder[i];
     2303        atree[n] = 1;
     2304        for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
     2305          if (apred[ugraph.target(e)] == n) {
     2306            atree[n] += atree[ugraph.target(e)];
     2307          }
     2308        }
     2309      }
     2310
     2311      typename AuxUGraph::template NodeMap<int> btree(ugraph, 0);
     2312      for (int i = border.size() - 1; i >= 0; --i) {
     2313        Node n = border[i];
     2314        btree[n] = 1;
     2315        for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
     2316          if (bpred[ugraph.target(e)] == n) {
     2317            btree[n] += btree[ugraph.target(e)];
     2318          }
     2319        }
     2320      }
     2321     
     2322      typename AuxUGraph::template NodeMap<int> apath(ugraph, 0);
     2323      apath[bnode] = apath[cnode] = 1;
     2324      typename AuxUGraph::template NodeMap<int> apath_btree(ugraph, 0);
     2325      apath_btree[bnode] = btree[bnode];
     2326      for (int i = 1; i < int(aorder.size()); ++i) {
     2327        Node n = aorder[i];
     2328        apath[n] = apath[apred[n]] + 1;
     2329        apath_btree[n] = btree[n] + apath_btree[apred[n]];
     2330      }
     2331
     2332      typename AuxUGraph::template NodeMap<int> bpath_atree(ugraph, 0);
     2333      bpath_atree[anode] = atree[anode];
     2334      for (int i = 1; i < int(border.size()); ++i) {
     2335        Node n = border[i];
     2336        bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];
     2337      }
     2338
     2339      typename AuxUGraph::template NodeMap<int> cpath(ugraph, 0);
     2340      cpath[anode] = cpath[bnode] = 1;
     2341      typename AuxUGraph::template NodeMap<int> cpath_atree(ugraph, 0);
     2342      cpath_atree[anode] = atree[anode];
     2343      typename AuxUGraph::template NodeMap<int> cpath_btree(ugraph, 0);
     2344      cpath_btree[bnode] = btree[bnode];
     2345      for (int i = 1; i < int(corder.size()); ++i) {
     2346        Node n = corder[i];
     2347        cpath[n] = cpath[cpred[n]] + 1;
     2348        cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];
     2349        cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];
     2350      }
     2351
     2352      typename AuxUGraph::template NodeMap<int> third(ugraph);
     2353      for (NodeIt n(ugraph); n != INVALID; ++n) {
     2354        point_map[n].x =
     2355          bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;
     2356        point_map[n].y =
     2357          cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;
     2358      }
     2359     
     2360    }
     2361
     2362  public:
     2363
     2364    /// \brief Calculates the node locations
     2365    ///
     2366    /// This function calculates the node locations.
     2367    bool run() {
     2368      PlanarEmbedding<UGraph> pe(_ugraph);
     2369      if (!pe.run()) return false;
     2370     
     2371      run(pe);
     2372      return true;
     2373    }
     2374
     2375    /// \brief Calculates the node locations according to a
     2376    /// combinatorical embedding
     2377    ///
     2378    /// This function calculates the node locations. The \c embedding
     2379    /// parameter should contain a valid combinatorical embedding, ie.
     2380    /// a valid cyclic order of the edges.
     2381    template <typename EmbeddingMap>
     2382    void run(const EmbeddingMap& embedding) {
     2383      typedef SmartUEdgeSet<UGraph> AuxUGraph;
     2384
     2385      if (3 * countNodes(_ugraph) - 6 == countUEdges(_ugraph)) {
     2386        drawing(_ugraph, embedding, _point_map);
     2387        return;
     2388      }
     2389
     2390      AuxUGraph aux_ugraph(_ugraph);
     2391      typename AuxUGraph::template EdgeMap<typename AuxUGraph::Edge>
     2392        aux_embedding(aux_ugraph);
     2393
     2394      {
     2395
     2396        typename UGraph::template UEdgeMap<typename AuxUGraph::UEdge>
     2397          ref(_ugraph);
     2398       
     2399        for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
     2400          ref[e] = aux_ugraph.addEdge(_ugraph.source(e), _ugraph.target(e));
     2401        }
     2402
     2403        for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
     2404          Edge ee = embedding[_ugraph.direct(e, true)];
     2405          aux_embedding[aux_ugraph.direct(ref[e], true)] =
     2406            aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
     2407          ee = embedding[_ugraph.direct(e, false)];
     2408          aux_embedding[aux_ugraph.direct(ref[e], false)] =
     2409            aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
     2410        }
     2411      }
     2412      _planarity_bits::makeConnected(aux_ugraph, aux_embedding);
     2413      _planarity_bits::makeBiNodeConnected(aux_ugraph, aux_embedding);
     2414      _planarity_bits::makeMaxPlanar(aux_ugraph, aux_embedding);
     2415      drawing(aux_ugraph, aux_embedding, _point_map);
     2416    }
     2417
     2418    /// \brief The coordinate of the given node
     2419    ///
     2420    /// The coordinate of the given node.
     2421    Point operator[](const Node& node) {
     2422      return _point_map[node];
     2423    }
     2424
     2425    /// \brief Returns the grid embedding in a \e NodeMap.
     2426    ///
     2427    /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
     2428    const PointMap& coords() const {
     2429      return _point_map;
     2430    }
     2431
     2432  private:
     2433   
     2434    const UGraph& _ugraph;
     2435    PointMap _point_map;
     2436   
     2437  };
     2438
    18092439}
    18102440
Note: See TracChangeset for help on using the changeset viewer.