1804 |
1817 |
1805 } |
1818 } |
1806 |
1819 |
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 (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 |
1809 } |
2439 } |
1810 |
2440 |
1811 #endif |
2441 #endif |