# Changeset 2499:c97596611d59 in lemon-0.x

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

Planar Grid Embedding

File:
1 edited

Unmodified
Added
Removed
• ## lemon/planarity.h

 r2481 #define LEMON_PLANARITY_H /// \ingroup graph_prop /// \ingroup planar /// \file /// \brief Planarity checking, embedding #include #include #include #include } /// \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 private: UGRAPH_TYPEDEFS(typename UGraph) UGRAPH_TYPEDEFS(typename UGraph); const UGraph& _ugraph; }; /// \ingroup graph_prop /// \ingroup planar /// /// \brief Planar embedding of an undirected simple graph private: UGRAPH_TYPEDEFS(typename UGraph) UGRAPH_TYPEDEFS(typename UGraph); const UGraph& _ugraph; public: /// \brief The map for store of embedding typedef typename UGraph::template EdgeMap EmbeddingMap; /// \brief Constructor 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; } }; namespace _planarity_bits { template void makeConnected(UGraph& ugraph, EmbeddingMap& embedding) { DfsVisitor null_visitor; DfsVisit > 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 void makeBiNodeConnected(UGraph& ugraph, EmbeddingMap& embedding) { typename UGraph::template EdgeMap processed(ugraph); std::vector edges; for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) { edges.push_back(e); } IterableBoolMap 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 void makeMaxPlanar(UGraph& ugraph, EmbeddingMap& embedding) { typename UGraph::template NodeMap degree(ugraph); for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) { degree[n] = countIncEdges(ugraph, n); } typename UGraph::template EdgeMap processed(ugraph); IterableBoolMap visited(ugraph, false); std::vector 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 class PlanarDrawing { public: UGRAPH_TYPEDEFS(typename UGraph); /// \brief The point type for store coordinates typedef dim2::Point Point; /// \brief The map type for store coordinates typedef typename UGraph::template NodeMap 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 void drawing(const AuxUGraph& ugraph, const AuxEmbeddingMap& next, PointMap& point_map) { UGRAPH_TYPEDEFS(typename AuxUGraph); typename AuxUGraph::template EdgeMap 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 proper(ugraph, false); typename AuxUGraph::template NodeMap 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 angle(ugraph, -1); while (proper.trueNum() != 0) { Node n = typename IterableBoolMap::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 apred(ugraph, INVALID); typename AuxUGraph::template NodeMap bpred(ugraph, INVALID); typename AuxUGraph::template NodeMap cpred(ugraph, INVALID); typename AuxUGraph::template NodeMap apredid(ugraph, -1); typename AuxUGraph::template NodeMap bpredid(ugraph, -1); typename AuxUGraph::template NodeMap 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 aorder, border, corder; { typename AuxUGraph::template NodeMap processed(ugraph, false); std::vector 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 processed(ugraph, false); std::vector 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 processed(ugraph, false); std::vector 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 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 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 apath(ugraph, 0); apath[bnode] = apath[cnode] = 1; typename AuxUGraph::template NodeMap 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 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 cpath(ugraph, 0); cpath[anode] = cpath[bnode] = 1; typename AuxUGraph::template NodeMap cpath_atree(ugraph, 0); cpath_atree[anode] = atree[anode]; typename AuxUGraph::template NodeMap 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 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 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 void run(const EmbeddingMap& embedding) { typedef SmartUEdgeSet AuxUGraph; if (3 * countNodes(_ugraph) - 6 == countUEdges(_ugraph)) { drawing(_ugraph, embedding, _point_map); return; } AuxUGraph aux_ugraph(_ugraph); typename AuxUGraph::template EdgeMap aux_embedding(aux_ugraph); { typename UGraph::template UEdgeMap 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 . const PointMap& coords() const { return _point_map; } private: const UGraph& _ugraph; PointMap _point_map; }; }
Note: See TracChangeset for help on using the changeset viewer.