Changeset 2499:c97596611d59 in lemon0.x
 Timestamp:
 10/19/07 18:24:31 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3338
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/planarity.h
r2481 r2499 19 19 #define LEMON_PLANARITY_H 20 20 21 /// \ingroup graph_prop21 /// \ingroup planar 22 22 /// \file 23 23 /// \brief Planarity checking, embedding … … 30 30 #include <lemon/maps.h> 31 31 #include <lemon/path.h> 32 #include <lemon/iterable_maps.h> 33 #include <lemon/edge_set.h> 32 34 33 35 … … 135 137 } 136 138 137 /// \ingroup graph_prop139 /// \ingroup planar 138 140 /// 139 141 /// \brief Planarity checking of an undirected simple graph 140 142 /// 141 /// This class implements the BoyerMyrvold algorithm for planar 143 /// This class implements the BoyerMyrvold algorithm for planarity 142 144 /// checking of an undirected graph. This class is a simplified 143 145 /// version of the PlanarEmbedding algorithm class, and it does … … 147 149 private: 148 150 149 UGRAPH_TYPEDEFS(typename UGraph) 151 UGRAPH_TYPEDEFS(typename UGraph); 150 152 151 153 const UGraph& _ugraph; … … 523 525 }; 524 526 525 /// \ingroup graph_prop527 /// \ingroup planar 526 528 /// 527 529 /// \brief Planar embedding of an undirected simple graph … … 542 544 private: 543 545 544 UGRAPH_TYPEDEFS(typename UGraph) 546 UGRAPH_TYPEDEFS(typename UGraph); 545 547 546 548 const UGraph& _ugraph; … … 586 588 587 589 public: 590 591 /// \brief The map for store of embedding 592 typedef typename UGraph::template EdgeMap<Edge> EmbeddingMap; 588 593 589 594 /// \brief Constructor … … 700 705 Edge next(const Edge& edge) const { 701 706 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; 702 715 } 703 716 … … 1807 1820 }; 1808 1821 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 (n2,n2) size grid, 2062 /// ie. each node will be located in the \c [0,n2]x[0,n2] 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 1809 2439 } 1810 2440
Note: See TracChangeset
for help on using the changeset viewer.