deba@2480: /* -*- C++ -*- deba@2480: * deba@2480: * This file is a part of LEMON, a generic C++ optimization library deba@2480: * deba@2480: * Copyright (C) 2003-2007 deba@2480: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2480: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2480: * deba@2480: * Permission to use, modify and distribute this software is granted deba@2480: * provided that this copyright notice appears in all copies. For deba@2480: * precise terms see the accompanying LICENSE file. deba@2480: * deba@2480: * This software is provided "AS IS" with no warranty of any kind, deba@2480: * express or implied, and with no claim as to its suitability for any deba@2480: * purpose. deba@2480: * deba@2480: */ deba@2480: #ifndef LEMON_PLANARITY_H deba@2480: #define LEMON_PLANARITY_H deba@2480: deba@2499: /// \ingroup planar deba@2480: /// \file deba@2508: /// \brief Planarity checking, embedding, drawing and coloring deba@2480: deba@2480: #include deba@2480: #include deba@2480: deba@2480: #include deba@2508: #include deba@2480: #include deba@2480: #include deba@2480: #include deba@2499: #include deba@2499: #include deba@2508: #include deba@2508: #include deba@2508: #include deba@2480: deba@2480: deba@2480: namespace lemon { deba@2480: deba@2480: namespace _planarity_bits { deba@2480: deba@2480: template deba@2480: struct PlanarityVisitor : DfsVisitor { deba@2480: deba@2480: typedef typename UGraph::Node Node; deba@2480: typedef typename UGraph::Edge Edge; deba@2480: deba@2480: typedef typename UGraph::template NodeMap PredMap; deba@2480: deba@2480: typedef typename UGraph::template UEdgeMap TreeMap; deba@2480: deba@2480: typedef typename UGraph::template NodeMap OrderMap; deba@2480: typedef std::vector OrderList; deba@2480: deba@2480: typedef typename UGraph::template NodeMap LowMap; deba@2480: typedef typename UGraph::template NodeMap AncestorMap; deba@2480: deba@2480: PlanarityVisitor(const UGraph& ugraph, deba@2480: PredMap& pred_map, TreeMap& tree_map, deba@2480: OrderMap& order_map, OrderList& order_list, deba@2480: AncestorMap& ancestor_map, LowMap& low_map) deba@2480: : _ugraph(ugraph), _pred_map(pred_map), _tree_map(tree_map), deba@2480: _order_map(order_map), _order_list(order_list), deba@2480: _ancestor_map(ancestor_map), _low_map(low_map) {} deba@2480: deba@2480: void reach(const Node& node) { deba@2480: _order_map[node] = _order_list.size(); deba@2480: _low_map[node] = _order_list.size(); deba@2480: _ancestor_map[node] = _order_list.size(); deba@2480: _order_list.push_back(node); deba@2480: } deba@2480: deba@2480: void discover(const Edge& edge) { deba@2480: Node source = _ugraph.source(edge); deba@2480: Node target = _ugraph.target(edge); deba@2480: deba@2480: _tree_map[edge] = true; deba@2480: _pred_map[target] = edge; deba@2480: } deba@2480: deba@2480: void examine(const Edge& edge) { deba@2480: Node source = _ugraph.source(edge); deba@2480: Node target = _ugraph.target(edge); deba@2480: deba@2480: if (_order_map[target] < _order_map[source] && !_tree_map[edge]) { deba@2480: if (_low_map[source] > _order_map[target]) { deba@2480: _low_map[source] = _order_map[target]; deba@2480: } deba@2480: if (_ancestor_map[source] > _order_map[target]) { deba@2480: _ancestor_map[source] = _order_map[target]; deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: void backtrack(const Edge& edge) { deba@2480: Node source = _ugraph.source(edge); deba@2480: Node target = _ugraph.target(edge); deba@2480: deba@2480: if (_low_map[source] > _low_map[target]) { deba@2480: _low_map[source] = _low_map[target]; deba@2480: } deba@2480: } deba@2480: deba@2480: const UGraph& _ugraph; deba@2480: PredMap& _pred_map; deba@2480: TreeMap& _tree_map; deba@2480: OrderMap& _order_map; deba@2480: OrderList& _order_list; deba@2480: AncestorMap& _ancestor_map; deba@2480: LowMap& _low_map; deba@2480: }; deba@2480: deba@2480: template deba@2480: struct NodeDataNode { deba@2480: int prev, next; deba@2480: int visited; deba@2480: typename UGraph::Edge first; deba@2480: bool inverted; deba@2480: }; deba@2480: deba@2480: template deba@2480: struct NodeDataNode { deba@2480: int prev, next; deba@2480: int visited; deba@2480: }; deba@2480: deba@2480: template deba@2480: struct ChildListNode { deba@2480: typedef typename UGraph::Node Node; deba@2480: Node first; deba@2480: Node prev, next; deba@2480: }; deba@2480: deba@2480: template deba@2480: struct EdgeListNode { deba@2480: typename UGraph::Edge prev, next; deba@2480: }; deba@2480: deba@2480: } deba@2480: deba@2499: /// \ingroup planar deba@2480: /// deba@2480: /// \brief Planarity checking of an undirected simple graph deba@2480: /// deba@2499: /// This class implements the Boyer-Myrvold algorithm for planarity deba@2480: /// checking of an undirected graph. This class is a simplified deba@2480: /// version of the PlanarEmbedding algorithm class, and it does deba@2480: /// provide neither embedding nor kuratowski subdivisons. deba@2480: template deba@2480: class PlanarityChecking { deba@2480: private: deba@2480: deba@2499: UGRAPH_TYPEDEFS(typename UGraph); deba@2480: deba@2480: const UGraph& _ugraph; deba@2480: deba@2480: private: deba@2480: deba@2480: typedef typename UGraph::template NodeMap PredMap; deba@2480: deba@2480: typedef typename UGraph::template UEdgeMap TreeMap; deba@2480: deba@2480: typedef typename UGraph::template NodeMap OrderMap; deba@2480: typedef std::vector OrderList; deba@2480: deba@2480: typedef typename UGraph::template NodeMap LowMap; deba@2480: typedef typename UGraph::template NodeMap AncestorMap; deba@2480: deba@2480: typedef _planarity_bits::NodeDataNode NodeDataNode; deba@2480: typedef std::vector NodeData; deba@2480: deba@2480: typedef _planarity_bits::ChildListNode ChildListNode; deba@2480: typedef typename UGraph::template NodeMap ChildLists; deba@2480: deba@2480: typedef typename UGraph::template NodeMap > MergeRoots; deba@2480: deba@2480: typedef typename UGraph::template NodeMap EmbedEdge; deba@2480: deba@2480: public: deba@2480: deba@2480: /// \brief Constructor deba@2480: /// deba@2480: /// \warining The graph should be simple, i.e. parallel and loop edge deba@2480: /// free. deba@2480: PlanarityChecking(const UGraph& ugraph) : _ugraph(ugraph) {} deba@2480: deba@2480: /// \brief Runs the algorithm. deba@2480: /// deba@2480: /// Runs the algorithm. deba@2480: /// \return %True when the graph is planar. deba@2481: bool run() { deba@2480: typedef _planarity_bits::PlanarityVisitor Visitor; deba@2480: deba@2480: PredMap pred_map(_ugraph, INVALID); deba@2480: TreeMap tree_map(_ugraph, false); deba@2480: deba@2480: OrderMap order_map(_ugraph, -1); deba@2480: OrderList order_list; deba@2480: deba@2480: AncestorMap ancestor_map(_ugraph, -1); deba@2480: LowMap low_map(_ugraph, -1); deba@2480: deba@2480: Visitor visitor(_ugraph, pred_map, tree_map, deba@2480: order_map, order_list, ancestor_map, low_map); deba@2480: DfsVisit visit(_ugraph, visitor); deba@2480: visit.run(); deba@2480: deba@2480: ChildLists child_lists(_ugraph); deba@2480: createChildLists(tree_map, order_map, low_map, child_lists); deba@2480: deba@2480: NodeData node_data(2 * order_list.size()); deba@2480: deba@2480: EmbedEdge embed_edge(_ugraph, false); deba@2480: deba@2480: MergeRoots merge_roots(_ugraph); deba@2480: deba@2480: for (int i = order_list.size() - 1; i >= 0; --i) { deba@2480: deba@2480: Node node = order_list[i]; deba@2480: deba@2480: Node source = node; deba@2480: for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { deba@2480: Node target = _ugraph.target(e); deba@2480: deba@2480: if (order_map[source] < order_map[target] && tree_map[e]) { deba@2481: initFace(target, node_data, order_map, order_list); deba@2480: } deba@2480: } deba@2480: deba@2480: for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { deba@2480: Node target = _ugraph.target(e); deba@2480: deba@2480: if (order_map[source] < order_map[target] && !tree_map[e]) { deba@2480: embed_edge[target] = true; deba@2480: walkUp(target, source, i, pred_map, low_map, deba@2480: order_map, order_list, node_data, merge_roots); deba@2480: } deba@2480: } deba@2480: deba@2480: for (typename MergeRoots::Value::iterator it = deba@2480: merge_roots[node].begin(); it != merge_roots[node].end(); ++it) { deba@2480: int rn = *it; deba@2480: walkDown(rn, i, node_data, order_list, child_lists, deba@2480: ancestor_map, low_map, embed_edge, merge_roots); deba@2480: } deba@2480: merge_roots[node].clear(); deba@2480: deba@2480: for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { deba@2480: Node target = _ugraph.target(e); deba@2480: deba@2480: if (order_map[source] < order_map[target] && !tree_map[e]) { deba@2480: if (embed_edge[target]) { deba@2480: return false; deba@2480: } deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: return true; deba@2480: } deba@2480: deba@2480: private: deba@2480: deba@2480: void createChildLists(const TreeMap& tree_map, const OrderMap& order_map, deba@2480: const LowMap& low_map, ChildLists& child_lists) { deba@2480: deba@2480: for (NodeIt n(_ugraph); n != INVALID; ++n) { deba@2480: Node source = n; deba@2480: deba@2480: std::vector targets; deba@2480: for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) { deba@2480: Node target = _ugraph.target(e); deba@2480: deba@2480: if (order_map[source] < order_map[target] && tree_map[e]) { deba@2480: targets.push_back(target); deba@2480: } deba@2480: } deba@2480: deba@2480: if (targets.size() == 0) { deba@2480: child_lists[source].first = INVALID; deba@2480: } else if (targets.size() == 1) { deba@2480: child_lists[source].first = targets[0]; deba@2480: child_lists[targets[0]].prev = INVALID; deba@2480: child_lists[targets[0]].next = INVALID; deba@2480: } else { deba@2480: radixSort(targets.begin(), targets.end(), mapFunctor(low_map)); deba@2480: for (int i = 1; i < int(targets.size()); ++i) { deba@2480: child_lists[targets[i]].prev = targets[i - 1]; deba@2480: child_lists[targets[i - 1]].next = targets[i]; deba@2480: } deba@2480: child_lists[targets.back()].next = INVALID; deba@2480: child_lists[targets.front()].prev = INVALID; deba@2480: child_lists[source].first = targets.front(); deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: void walkUp(const Node& node, Node root, int rorder, deba@2480: const PredMap& pred_map, const LowMap& low_map, deba@2480: const OrderMap& order_map, const OrderList& order_list, deba@2480: NodeData& node_data, MergeRoots& merge_roots) { deba@2480: deba@2480: int na, nb; deba@2480: bool da, db; deba@2480: deba@2480: na = nb = order_map[node]; deba@2480: da = true; db = false; deba@2480: deba@2480: while (true) { deba@2480: deba@2480: if (node_data[na].visited == rorder) break; deba@2480: if (node_data[nb].visited == rorder) break; deba@2480: deba@2480: node_data[na].visited = rorder; deba@2480: node_data[nb].visited = rorder; deba@2480: deba@2480: int rn = -1; deba@2480: deba@2480: if (na >= int(order_list.size())) { deba@2480: rn = na; deba@2480: } else if (nb >= int(order_list.size())) { deba@2480: rn = nb; deba@2480: } deba@2480: deba@2480: if (rn == -1) { deba@2480: int nn; deba@2480: deba@2480: nn = da ? node_data[na].prev : node_data[na].next; deba@2480: da = node_data[nn].prev != na; deba@2480: na = nn; deba@2480: deba@2480: nn = db ? node_data[nb].prev : node_data[nb].next; deba@2480: db = node_data[nn].prev != nb; deba@2480: nb = nn; deba@2480: deba@2480: } else { deba@2480: deba@2480: Node rep = order_list[rn - order_list.size()]; deba@2480: Node parent = _ugraph.source(pred_map[rep]); deba@2480: deba@2480: if (low_map[rep] < rorder) { deba@2480: merge_roots[parent].push_back(rn); deba@2480: } else { deba@2480: merge_roots[parent].push_front(rn); deba@2480: } deba@2480: deba@2480: if (parent != root) { deba@2480: na = nb = order_map[parent]; deba@2480: da = true; db = false; deba@2480: } else { deba@2480: break; deba@2480: } deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: void walkDown(int rn, int rorder, NodeData& node_data, deba@2480: OrderList& order_list, ChildLists& child_lists, deba@2480: AncestorMap& ancestor_map, LowMap& low_map, deba@2480: EmbedEdge& embed_edge, MergeRoots& merge_roots) { deba@2480: deba@2480: std::vector > merge_stack; deba@2480: deba@2480: for (int di = 0; di < 2; ++di) { deba@2480: bool rd = di == 0; deba@2480: int pn = rn; deba@2480: int n = rd ? node_data[rn].next : node_data[rn].prev; deba@2480: deba@2480: while (n != rn) { deba@2480: deba@2480: Node node = order_list[n]; deba@2480: deba@2480: if (embed_edge[node]) { deba@2480: deba@2480: // Merging components on the critical path deba@2480: while (!merge_stack.empty()) { deba@2480: deba@2480: // Component root deba@2480: int cn = merge_stack.back().first; deba@2480: bool cd = merge_stack.back().second; deba@2480: merge_stack.pop_back(); deba@2480: deba@2480: // Parent of component deba@2480: int dn = merge_stack.back().first; deba@2480: bool dd = merge_stack.back().second; deba@2480: merge_stack.pop_back(); deba@2480: deba@2480: Node parent = order_list[dn]; deba@2480: deba@2480: // Erasing from merge_roots deba@2480: merge_roots[parent].pop_front(); deba@2480: deba@2480: Node child = order_list[cn - order_list.size()]; deba@2480: deba@2480: // Erasing from child_lists deba@2480: if (child_lists[child].prev != INVALID) { deba@2480: child_lists[child_lists[child].prev].next = deba@2480: child_lists[child].next; deba@2480: } else { deba@2480: child_lists[parent].first = child_lists[child].next; deba@2480: } deba@2480: deba@2480: if (child_lists[child].next != INVALID) { deba@2480: child_lists[child_lists[child].next].prev = deba@2480: child_lists[child].prev; deba@2480: } deba@2480: deba@2480: // Merging external faces deba@2480: { deba@2480: int en = cn; deba@2480: cn = cd ? node_data[cn].prev : node_data[cn].next; deba@2480: cd = node_data[cn].next == en; deba@2480: deba@2480: } deba@2480: deba@2480: if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn; deba@2480: if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn; deba@2480: deba@2480: } deba@2480: deba@2480: bool d = pn == node_data[n].prev; deba@2480: deba@2480: if (node_data[n].prev == node_data[n].next && deba@2480: node_data[n].inverted) { deba@2480: d = !d; deba@2480: } deba@2480: deba@2480: // Embedding edge into external face deba@2480: if (rd) node_data[rn].next = n; else node_data[rn].prev = n; deba@2480: if (d) node_data[n].prev = rn; else node_data[n].next = rn; deba@2480: pn = rn; deba@2480: deba@2480: embed_edge[order_list[n]] = false; deba@2480: } deba@2480: deba@2480: if (!merge_roots[node].empty()) { deba@2480: deba@2480: bool d = pn == node_data[n].prev; deba@2480: deba@2480: merge_stack.push_back(std::make_pair(n, d)); deba@2480: deba@2480: int rn = merge_roots[node].front(); deba@2480: deba@2480: int xn = node_data[rn].next; deba@2480: Node xnode = order_list[xn]; deba@2480: deba@2480: int yn = node_data[rn].prev; deba@2480: Node ynode = order_list[yn]; deba@2480: deba@2480: bool rd; deba@2480: if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) { deba@2480: rd = true; deba@2480: } else if (!external(ynode, rorder, child_lists, deba@2480: ancestor_map, low_map)) { deba@2480: rd = false; deba@2480: } else if (pertinent(xnode, embed_edge, merge_roots)) { deba@2480: rd = true; deba@2480: } else { deba@2480: rd = false; deba@2480: } deba@2480: deba@2480: merge_stack.push_back(std::make_pair(rn, rd)); deba@2480: deba@2480: pn = rn; deba@2480: n = rd ? xn : yn; deba@2480: deba@2480: } else if (!external(node, rorder, child_lists, deba@2480: ancestor_map, low_map)) { deba@2480: int nn = (node_data[n].next != pn ? deba@2480: node_data[n].next : node_data[n].prev); deba@2480: deba@2480: bool nd = n == node_data[nn].prev; deba@2480: deba@2480: if (nd) node_data[nn].prev = pn; deba@2480: else node_data[nn].next = pn; deba@2480: deba@2480: if (n == node_data[pn].prev) node_data[pn].prev = nn; deba@2480: else node_data[pn].next = nn; deba@2480: deba@2480: node_data[nn].inverted = deba@2480: (node_data[nn].prev == node_data[nn].next && nd != rd); deba@2480: deba@2480: n = nn; deba@2480: } deba@2480: else break; deba@2480: deba@2480: } deba@2480: deba@2480: if (!merge_stack.empty() || n == rn) { deba@2480: break; deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: void initFace(const Node& node, NodeData& node_data, deba@2481: const OrderMap& order_map, const OrderList& order_list) { deba@2480: int n = order_map[node]; deba@2480: int rn = n + order_list.size(); deba@2480: deba@2480: node_data[n].next = node_data[n].prev = rn; deba@2480: node_data[rn].next = node_data[rn].prev = n; deba@2480: deba@2480: node_data[n].visited = order_list.size(); deba@2480: node_data[rn].visited = order_list.size(); deba@2480: deba@2480: } deba@2480: deba@2480: bool external(const Node& node, int rorder, deba@2480: ChildLists& child_lists, AncestorMap& ancestor_map, deba@2480: LowMap& low_map) { deba@2480: Node child = child_lists[node].first; deba@2480: deba@2480: if (child != INVALID) { deba@2480: if (low_map[child] < rorder) return true; deba@2480: } deba@2480: deba@2480: if (ancestor_map[node] < rorder) return true; deba@2480: deba@2480: return false; deba@2480: } deba@2480: deba@2480: bool pertinent(const Node& node, const EmbedEdge& embed_edge, deba@2480: const MergeRoots& merge_roots) { deba@2480: return !merge_roots[node].empty() || embed_edge[node]; deba@2480: } deba@2480: deba@2480: }; deba@2480: deba@2499: /// \ingroup planar deba@2480: /// deba@2480: /// \brief Planar embedding of an undirected simple graph deba@2480: /// deba@2480: /// This class implements the Boyer-Myrvold algorithm for planar deba@2480: /// embedding of an undirected graph. The planar embeding is an deba@2480: /// ordering of the outgoing edges in each node, which is a possible deba@2480: /// configuration to draw the graph in the plane. If there is not deba@2480: /// such ordering then the graph contains a \f$ K_5 \f$ (full graph deba@2480: /// with 5 nodes) or an \f$ K_{3,3} \f$ (complete bipartite graph on deba@2480: /// 3 ANode and 3 BNode) subdivision. deba@2480: /// deba@2480: /// The current implementation calculates an embedding or an deba@2480: /// Kuratowski subdivision if the graph is not planar. The running deba@2480: /// time of the algorithm is \f$ O(n) \f$. deba@2480: template deba@2480: class PlanarEmbedding { deba@2480: private: deba@2480: deba@2499: UGRAPH_TYPEDEFS(typename UGraph); deba@2480: deba@2480: const UGraph& _ugraph; deba@2480: typename UGraph::template EdgeMap _embedding; deba@2480: deba@2480: typename UGraph::template UEdgeMap _kuratowski; deba@2480: deba@2480: private: deba@2480: deba@2480: typedef typename UGraph::template NodeMap PredMap; deba@2480: deba@2480: typedef typename UGraph::template UEdgeMap TreeMap; deba@2480: deba@2480: typedef typename UGraph::template NodeMap OrderMap; deba@2480: typedef std::vector OrderList; deba@2480: deba@2480: typedef typename UGraph::template NodeMap LowMap; deba@2480: typedef typename UGraph::template NodeMap AncestorMap; deba@2480: deba@2480: typedef _planarity_bits::NodeDataNode NodeDataNode; deba@2480: typedef std::vector NodeData; deba@2480: deba@2480: typedef _planarity_bits::ChildListNode ChildListNode; deba@2480: typedef typename UGraph::template NodeMap ChildLists; deba@2480: deba@2480: typedef typename UGraph::template NodeMap > MergeRoots; deba@2480: deba@2480: typedef typename UGraph::template NodeMap EmbedEdge; deba@2480: deba@2480: typedef _planarity_bits::EdgeListNode EdgeListNode; deba@2480: typedef typename UGraph::template EdgeMap EdgeLists; deba@2480: deba@2480: typedef typename UGraph::template NodeMap FlipMap; deba@2480: deba@2480: typedef typename UGraph::template NodeMap TypeMap; deba@2480: deba@2480: enum IsolatorNodeType { deba@2480: HIGHX = 6, LOWX = 7, deba@2480: HIGHY = 8, LOWY = 9, deba@2480: ROOT = 10, PERTINENT = 11, deba@2480: INTERNAL = 12 deba@2480: }; deba@2480: deba@2480: public: deba@2480: deba@2499: /// \brief The map for store of embedding deba@2499: typedef typename UGraph::template EdgeMap EmbeddingMap; deba@2499: deba@2480: /// \brief Constructor deba@2480: /// deba@2480: /// \warining The graph should be simple, i.e. parallel and loop edge deba@2480: /// free. deba@2480: PlanarEmbedding(const UGraph& ugraph) deba@2480: : _ugraph(ugraph), _embedding(_ugraph), _kuratowski(ugraph, false) {} deba@2480: deba@2480: /// \brief Runs the algorithm. deba@2480: /// deba@2480: /// Runs the algorithm. deba@2480: /// \param kuratowski If the parameter is false, then the deba@2480: /// algorithm does not calculate the isolate Kuratowski deba@2480: /// subdivisions. deba@2480: ///\return %True when the graph is planar. deba@2480: bool run(bool kuratowski = true) { deba@2480: typedef _planarity_bits::PlanarityVisitor Visitor; deba@2480: deba@2480: PredMap pred_map(_ugraph, INVALID); deba@2480: TreeMap tree_map(_ugraph, false); deba@2480: deba@2480: OrderMap order_map(_ugraph, -1); deba@2480: OrderList order_list; deba@2480: deba@2480: AncestorMap ancestor_map(_ugraph, -1); deba@2480: LowMap low_map(_ugraph, -1); deba@2480: deba@2480: Visitor visitor(_ugraph, pred_map, tree_map, deba@2480: order_map, order_list, ancestor_map, low_map); deba@2480: DfsVisit visit(_ugraph, visitor); deba@2480: visit.run(); deba@2480: deba@2480: ChildLists child_lists(_ugraph); deba@2480: createChildLists(tree_map, order_map, low_map, child_lists); deba@2480: deba@2480: NodeData node_data(2 * order_list.size()); deba@2480: deba@2480: EmbedEdge embed_edge(_ugraph, INVALID); deba@2480: deba@2480: MergeRoots merge_roots(_ugraph); deba@2480: deba@2480: EdgeLists edge_lists(_ugraph); deba@2480: deba@2480: FlipMap flip_map(_ugraph, false); deba@2480: deba@2480: for (int i = order_list.size() - 1; i >= 0; --i) { deba@2480: deba@2480: Node node = order_list[i]; deba@2480: deba@2480: node_data[i].first = INVALID; deba@2480: deba@2480: Node source = node; deba@2480: for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { deba@2480: Node target = _ugraph.target(e); deba@2480: deba@2480: if (order_map[source] < order_map[target] && tree_map[e]) { deba@2480: initFace(target, edge_lists, node_data, deba@2480: pred_map, order_map, order_list); deba@2480: } deba@2480: } deba@2480: deba@2480: for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { deba@2480: Node target = _ugraph.target(e); deba@2480: deba@2480: if (order_map[source] < order_map[target] && !tree_map[e]) { deba@2480: embed_edge[target] = e; deba@2480: walkUp(target, source, i, pred_map, low_map, deba@2480: order_map, order_list, node_data, merge_roots); deba@2480: } deba@2480: } deba@2480: deba@2480: for (typename MergeRoots::Value::iterator it = deba@2480: merge_roots[node].begin(); it != merge_roots[node].end(); ++it) { deba@2480: int rn = *it; deba@2480: walkDown(rn, i, node_data, edge_lists, flip_map, order_list, deba@2480: child_lists, ancestor_map, low_map, embed_edge, merge_roots); deba@2480: } deba@2480: merge_roots[node].clear(); deba@2480: deba@2480: for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { deba@2480: Node target = _ugraph.target(e); deba@2480: deba@2480: if (order_map[source] < order_map[target] && !tree_map[e]) { deba@2480: if (embed_edge[target] != INVALID) { deba@2480: if (kuratowski) { deba@2480: isolateKuratowski(e, node_data, edge_lists, flip_map, deba@2480: order_map, order_list, pred_map, child_lists, deba@2480: ancestor_map, low_map, deba@2480: embed_edge, merge_roots); deba@2480: } deba@2480: return false; deba@2480: } deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: for (int i = 0; i < int(order_list.size()); ++i) { deba@2480: deba@2480: mergeRemainingFaces(order_list[i], node_data, order_list, order_map, deba@2480: child_lists, edge_lists); deba@2480: storeEmbedding(order_list[i], node_data, order_map, pred_map, deba@2480: edge_lists, flip_map); deba@2480: } deba@2480: deba@2480: return true; deba@2480: } deba@2480: deba@2480: /// \brief Gives back the successor of an edge deba@2480: /// deba@2480: /// Gives back the successor of an edge. This function makes deba@2480: /// possible to query the cyclic order of the outgoing edges from deba@2480: /// a node. deba@2480: Edge next(const Edge& edge) const { deba@2480: return _embedding[edge]; deba@2480: } deba@2480: deba@2499: /// \brief Gives back the calculated embedding map deba@2499: /// deba@2499: /// The returned map contains the successor of each edge in the deba@2499: /// graph. deba@2499: const EmbeddingMap& embedding() const { deba@2499: return _embedding; deba@2499: } deba@2499: deba@2480: /// \brief Gives back true when the undirected edge is in the deba@2480: /// kuratowski subdivision deba@2480: /// deba@2480: /// Gives back true when the undirected edge is in the kuratowski deba@2480: /// subdivision deba@2480: bool kuratowski(const UEdge& uedge) { deba@2480: return _kuratowski[uedge]; deba@2480: } deba@2480: deba@2480: private: deba@2480: deba@2480: void createChildLists(const TreeMap& tree_map, const OrderMap& order_map, deba@2480: const LowMap& low_map, ChildLists& child_lists) { deba@2480: deba@2480: for (NodeIt n(_ugraph); n != INVALID; ++n) { deba@2480: Node source = n; deba@2480: deba@2480: std::vector targets; deba@2480: for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) { deba@2480: Node target = _ugraph.target(e); deba@2480: deba@2480: if (order_map[source] < order_map[target] && tree_map[e]) { deba@2480: targets.push_back(target); deba@2480: } deba@2480: } deba@2480: deba@2480: if (targets.size() == 0) { deba@2480: child_lists[source].first = INVALID; deba@2480: } else if (targets.size() == 1) { deba@2480: child_lists[source].first = targets[0]; deba@2480: child_lists[targets[0]].prev = INVALID; deba@2480: child_lists[targets[0]].next = INVALID; deba@2480: } else { deba@2480: radixSort(targets.begin(), targets.end(), mapFunctor(low_map)); deba@2480: for (int i = 1; i < int(targets.size()); ++i) { deba@2480: child_lists[targets[i]].prev = targets[i - 1]; deba@2480: child_lists[targets[i - 1]].next = targets[i]; deba@2480: } deba@2480: child_lists[targets.back()].next = INVALID; deba@2480: child_lists[targets.front()].prev = INVALID; deba@2480: child_lists[source].first = targets.front(); deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: void walkUp(const Node& node, Node root, int rorder, deba@2480: const PredMap& pred_map, const LowMap& low_map, deba@2480: const OrderMap& order_map, const OrderList& order_list, deba@2480: NodeData& node_data, MergeRoots& merge_roots) { deba@2480: deba@2480: int na, nb; deba@2480: bool da, db; deba@2480: deba@2480: na = nb = order_map[node]; deba@2480: da = true; db = false; deba@2480: deba@2480: while (true) { deba@2480: deba@2480: if (node_data[na].visited == rorder) break; deba@2480: if (node_data[nb].visited == rorder) break; deba@2480: deba@2480: node_data[na].visited = rorder; deba@2480: node_data[nb].visited = rorder; deba@2480: deba@2480: int rn = -1; deba@2480: deba@2480: if (na >= int(order_list.size())) { deba@2480: rn = na; deba@2480: } else if (nb >= int(order_list.size())) { deba@2480: rn = nb; deba@2480: } deba@2480: deba@2480: if (rn == -1) { deba@2480: int nn; deba@2480: deba@2480: nn = da ? node_data[na].prev : node_data[na].next; deba@2480: da = node_data[nn].prev != na; deba@2480: na = nn; deba@2480: deba@2480: nn = db ? node_data[nb].prev : node_data[nb].next; deba@2480: db = node_data[nn].prev != nb; deba@2480: nb = nn; deba@2480: deba@2480: } else { deba@2480: deba@2480: Node rep = order_list[rn - order_list.size()]; deba@2480: Node parent = _ugraph.source(pred_map[rep]); deba@2480: deba@2480: if (low_map[rep] < rorder) { deba@2480: merge_roots[parent].push_back(rn); deba@2480: } else { deba@2480: merge_roots[parent].push_front(rn); deba@2480: } deba@2480: deba@2480: if (parent != root) { deba@2480: na = nb = order_map[parent]; deba@2480: da = true; db = false; deba@2480: } else { deba@2480: break; deba@2480: } deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: void walkDown(int rn, int rorder, NodeData& node_data, deba@2480: EdgeLists& edge_lists, FlipMap& flip_map, deba@2480: OrderList& order_list, ChildLists& child_lists, deba@2480: AncestorMap& ancestor_map, LowMap& low_map, deba@2480: EmbedEdge& embed_edge, MergeRoots& merge_roots) { deba@2480: deba@2480: std::vector > merge_stack; deba@2480: deba@2480: for (int di = 0; di < 2; ++di) { deba@2480: bool rd = di == 0; deba@2480: int pn = rn; deba@2480: int n = rd ? node_data[rn].next : node_data[rn].prev; deba@2480: deba@2480: while (n != rn) { deba@2480: deba@2480: Node node = order_list[n]; deba@2480: deba@2480: if (embed_edge[node] != INVALID) { deba@2480: deba@2480: // Merging components on the critical path deba@2480: while (!merge_stack.empty()) { deba@2480: deba@2480: // Component root deba@2480: int cn = merge_stack.back().first; deba@2480: bool cd = merge_stack.back().second; deba@2480: merge_stack.pop_back(); deba@2480: deba@2480: // Parent of component deba@2480: int dn = merge_stack.back().first; deba@2480: bool dd = merge_stack.back().second; deba@2480: merge_stack.pop_back(); deba@2480: deba@2480: Node parent = order_list[dn]; deba@2480: deba@2480: // Erasing from merge_roots deba@2480: merge_roots[parent].pop_front(); deba@2480: deba@2480: Node child = order_list[cn - order_list.size()]; deba@2480: deba@2480: // Erasing from child_lists deba@2480: if (child_lists[child].prev != INVALID) { deba@2480: child_lists[child_lists[child].prev].next = deba@2480: child_lists[child].next; deba@2480: } else { deba@2480: child_lists[parent].first = child_lists[child].next; deba@2480: } deba@2480: deba@2480: if (child_lists[child].next != INVALID) { deba@2480: child_lists[child_lists[child].next].prev = deba@2480: child_lists[child].prev; deba@2480: } deba@2480: deba@2480: // Merging edges + flipping deba@2480: Edge de = node_data[dn].first; deba@2480: Edge ce = node_data[cn].first; deba@2480: deba@2480: flip_map[order_list[cn - order_list.size()]] = cd != dd; deba@2480: if (cd != dd) { deba@2480: std::swap(edge_lists[ce].prev, edge_lists[ce].next); deba@2480: ce = edge_lists[ce].prev; deba@2480: std::swap(edge_lists[ce].prev, edge_lists[ce].next); deba@2480: } deba@2480: deba@2480: { deba@2480: Edge dne = edge_lists[de].next; deba@2480: Edge cne = edge_lists[ce].next; deba@2480: deba@2480: edge_lists[de].next = cne; deba@2480: edge_lists[ce].next = dne; deba@2480: deba@2480: edge_lists[dne].prev = ce; deba@2480: edge_lists[cne].prev = de; deba@2480: } deba@2480: deba@2480: if (dd) { deba@2480: node_data[dn].first = ce; deba@2480: } deba@2480: deba@2480: // Merging external faces deba@2480: { deba@2480: int en = cn; deba@2480: cn = cd ? node_data[cn].prev : node_data[cn].next; deba@2480: cd = node_data[cn].next == en; deba@2480: deba@2480: if (node_data[cn].prev == node_data[cn].next && deba@2480: node_data[cn].inverted) { deba@2480: cd = !cd; deba@2480: } deba@2480: } deba@2480: deba@2480: if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn; deba@2480: if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn; deba@2480: deba@2480: } deba@2480: deba@2480: bool d = pn == node_data[n].prev; deba@2480: deba@2480: if (node_data[n].prev == node_data[n].next && deba@2480: node_data[n].inverted) { deba@2480: d = !d; deba@2480: } deba@2480: deba@2480: // Add new edge deba@2480: { deba@2480: Edge edge = embed_edge[node]; deba@2480: Edge re = node_data[rn].first; deba@2480: deba@2480: edge_lists[edge_lists[re].next].prev = edge; deba@2480: edge_lists[edge].next = edge_lists[re].next; deba@2480: edge_lists[edge].prev = re; deba@2480: edge_lists[re].next = edge; deba@2480: deba@2480: if (!rd) { deba@2480: node_data[rn].first = edge; deba@2480: } deba@2480: deba@2480: Edge rev = _ugraph.oppositeEdge(edge); deba@2480: Edge e = node_data[n].first; deba@2480: deba@2480: edge_lists[edge_lists[e].next].prev = rev; deba@2480: edge_lists[rev].next = edge_lists[e].next; deba@2480: edge_lists[rev].prev = e; deba@2480: edge_lists[e].next = rev; deba@2480: deba@2480: if (d) { deba@2480: node_data[n].first = rev; deba@2480: } deba@2480: deba@2480: } deba@2480: deba@2480: // Embedding edge into external face deba@2480: if (rd) node_data[rn].next = n; else node_data[rn].prev = n; deba@2480: if (d) node_data[n].prev = rn; else node_data[n].next = rn; deba@2480: pn = rn; deba@2480: deba@2480: embed_edge[order_list[n]] = INVALID; deba@2480: } deba@2480: deba@2480: if (!merge_roots[node].empty()) { deba@2480: deba@2480: bool d = pn == node_data[n].prev; deba@2480: if (node_data[n].prev == node_data[n].next && deba@2480: node_data[n].inverted) { deba@2480: d = !d; deba@2480: } deba@2480: deba@2480: merge_stack.push_back(std::make_pair(n, d)); deba@2480: deba@2480: int rn = merge_roots[node].front(); deba@2480: deba@2480: int xn = node_data[rn].next; deba@2480: Node xnode = order_list[xn]; deba@2480: deba@2480: int yn = node_data[rn].prev; deba@2480: Node ynode = order_list[yn]; deba@2480: deba@2480: bool rd; deba@2480: if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) { deba@2480: rd = true; deba@2480: } else if (!external(ynode, rorder, child_lists, deba@2480: ancestor_map, low_map)) { deba@2480: rd = false; deba@2480: } else if (pertinent(xnode, embed_edge, merge_roots)) { deba@2480: rd = true; deba@2480: } else { deba@2480: rd = false; deba@2480: } deba@2480: deba@2480: merge_stack.push_back(std::make_pair(rn, rd)); deba@2480: deba@2480: pn = rn; deba@2480: n = rd ? xn : yn; deba@2480: deba@2480: } else if (!external(node, rorder, child_lists, deba@2480: ancestor_map, low_map)) { deba@2480: int nn = (node_data[n].next != pn ? deba@2480: node_data[n].next : node_data[n].prev); deba@2480: deba@2480: bool nd = n == node_data[nn].prev; deba@2480: deba@2480: if (nd) node_data[nn].prev = pn; deba@2480: else node_data[nn].next = pn; deba@2480: deba@2480: if (n == node_data[pn].prev) node_data[pn].prev = nn; deba@2480: else node_data[pn].next = nn; deba@2480: deba@2480: node_data[nn].inverted = deba@2480: (node_data[nn].prev == node_data[nn].next && nd != rd); deba@2480: deba@2480: n = nn; deba@2480: } deba@2480: else break; deba@2480: deba@2480: } deba@2480: deba@2480: if (!merge_stack.empty() || n == rn) { deba@2480: break; deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: void initFace(const Node& node, EdgeLists& edge_lists, deba@2480: NodeData& node_data, const PredMap& pred_map, deba@2480: const OrderMap& order_map, const OrderList& order_list) { deba@2480: int n = order_map[node]; deba@2480: int rn = n + order_list.size(); deba@2480: deba@2480: node_data[n].next = node_data[n].prev = rn; deba@2480: node_data[rn].next = node_data[rn].prev = n; deba@2480: deba@2480: node_data[n].visited = order_list.size(); deba@2480: node_data[rn].visited = order_list.size(); deba@2480: deba@2480: node_data[n].inverted = false; deba@2480: node_data[rn].inverted = false; deba@2480: deba@2480: Edge edge = pred_map[node]; deba@2480: Edge rev = _ugraph.oppositeEdge(edge); deba@2480: deba@2480: node_data[rn].first = edge; deba@2480: node_data[n].first = rev; deba@2480: deba@2480: edge_lists[edge].prev = edge; deba@2480: edge_lists[edge].next = edge; deba@2480: deba@2480: edge_lists[rev].prev = rev; deba@2480: edge_lists[rev].next = rev; deba@2480: deba@2480: } deba@2480: deba@2480: void mergeRemainingFaces(const Node& node, NodeData& node_data, deba@2480: OrderList& order_list, OrderMap& order_map, deba@2480: ChildLists& child_lists, EdgeLists& edge_lists) { deba@2480: while (child_lists[node].first != INVALID) { deba@2480: int dd = order_map[node]; deba@2480: Node child = child_lists[node].first; deba@2480: int cd = order_map[child] + order_list.size(); deba@2480: child_lists[node].first = child_lists[child].next; deba@2480: deba@2480: Edge de = node_data[dd].first; deba@2480: Edge ce = node_data[cd].first; deba@2480: deba@2480: if (de != INVALID) { deba@2480: Edge dne = edge_lists[de].next; deba@2480: Edge cne = edge_lists[ce].next; deba@2480: deba@2480: edge_lists[de].next = cne; deba@2480: edge_lists[ce].next = dne; deba@2480: deba@2480: edge_lists[dne].prev = ce; deba@2480: edge_lists[cne].prev = de; deba@2480: } deba@2480: deba@2480: node_data[dd].first = ce; deba@2480: deba@2480: } deba@2480: } deba@2480: deba@2480: void storeEmbedding(const Node& node, NodeData& node_data, deba@2480: OrderMap& order_map, PredMap& pred_map, deba@2480: EdgeLists& edge_lists, FlipMap& flip_map) { deba@2480: deba@2480: if (node_data[order_map[node]].first == INVALID) return; deba@2480: deba@2480: if (pred_map[node] != INVALID) { deba@2480: Node source = _ugraph.source(pred_map[node]); deba@2480: flip_map[node] = flip_map[node] != flip_map[source]; deba@2480: } deba@2480: deba@2480: Edge first = node_data[order_map[node]].first; deba@2480: Edge prev = first; deba@2480: deba@2480: Edge edge = flip_map[node] ? deba@2480: edge_lists[prev].prev : edge_lists[prev].next; deba@2480: deba@2480: _embedding[prev] = edge; deba@2480: deba@2480: while (edge != first) { deba@2480: Edge next = edge_lists[edge].prev == prev ? deba@2480: edge_lists[edge].next : edge_lists[edge].prev; deba@2480: prev = edge; edge = next; deba@2480: _embedding[prev] = edge; deba@2480: } deba@2480: } deba@2480: deba@2480: deba@2480: bool external(const Node& node, int rorder, deba@2480: ChildLists& child_lists, AncestorMap& ancestor_map, deba@2480: LowMap& low_map) { deba@2480: Node child = child_lists[node].first; deba@2480: deba@2480: if (child != INVALID) { deba@2480: if (low_map[child] < rorder) return true; deba@2480: } deba@2480: deba@2480: if (ancestor_map[node] < rorder) return true; deba@2480: deba@2480: return false; deba@2480: } deba@2480: deba@2480: bool pertinent(const Node& node, const EmbedEdge& embed_edge, deba@2480: const MergeRoots& merge_roots) { deba@2480: return !merge_roots[node].empty() || embed_edge[node] != INVALID; deba@2480: } deba@2480: deba@2480: int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists, deba@2480: AncestorMap& ancestor_map, LowMap& low_map) { deba@2480: int low_point; deba@2480: deba@2480: Node child = child_lists[node].first; deba@2480: deba@2480: if (child != INVALID) { deba@2480: low_point = low_map[child]; deba@2480: } else { deba@2480: low_point = order_map[node]; deba@2480: } deba@2480: deba@2480: if (low_point > ancestor_map[node]) { deba@2480: low_point = ancestor_map[node]; deba@2480: } deba@2480: deba@2480: return low_point; deba@2480: } deba@2480: deba@2480: int findComponentRoot(Node root, Node node, ChildLists& child_lists, deba@2480: OrderMap& order_map, OrderList& order_list) { deba@2480: deba@2480: int order = order_map[root]; deba@2480: int norder = order_map[node]; deba@2480: deba@2480: Node child = child_lists[root].first; deba@2480: while (child != INVALID) { deba@2480: int corder = order_map[child]; deba@2480: if (corder > order && corder < norder) { deba@2480: order = corder; deba@2480: } deba@2480: child = child_lists[child].next; deba@2480: } deba@2480: return order + order_list.size(); deba@2480: } deba@2480: deba@2480: Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data, deba@2480: EmbedEdge& embed_edge, MergeRoots& merge_roots) { deba@2480: Node wnode =_ugraph.target(node_data[order_map[node]].first); deba@2480: while (!pertinent(wnode, embed_edge, merge_roots)) { deba@2480: wnode = _ugraph.target(node_data[order_map[wnode]].first); deba@2480: } deba@2480: return wnode; deba@2480: } deba@2480: deba@2480: deba@2480: Node findExternal(Node node, int rorder, OrderMap& order_map, deba@2480: ChildLists& child_lists, AncestorMap& ancestor_map, deba@2480: LowMap& low_map, NodeData& node_data) { deba@2480: Node wnode =_ugraph.target(node_data[order_map[node]].first); deba@2480: while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) { deba@2480: wnode = _ugraph.target(node_data[order_map[wnode]].first); deba@2480: } deba@2480: return wnode; deba@2480: } deba@2480: deba@2480: void markCommonPath(Node node, int rorder, Node& wnode, Node& znode, deba@2480: OrderList& order_list, OrderMap& order_map, deba@2480: NodeData& node_data, EdgeLists& edge_lists, deba@2480: EmbedEdge& embed_edge, MergeRoots& merge_roots, deba@2480: ChildLists& child_lists, AncestorMap& ancestor_map, deba@2480: LowMap& low_map) { deba@2480: deba@2480: Node cnode = node; deba@2480: Node pred = INVALID; deba@2480: deba@2480: while (true) { deba@2480: deba@2480: bool pert = pertinent(cnode, embed_edge, merge_roots); deba@2480: bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map); deba@2480: deba@2480: if (pert && ext) { deba@2480: if (!merge_roots[cnode].empty()) { deba@2480: int cn = merge_roots[cnode].back(); deba@2480: deba@2480: if (low_map[order_list[cn - order_list.size()]] < rorder) { deba@2480: Edge edge = node_data[cn].first; deba@2480: _kuratowski.set(edge, true); deba@2480: deba@2480: pred = cnode; deba@2480: cnode = _ugraph.target(edge); deba@2480: deba@2480: continue; deba@2480: } deba@2480: } deba@2480: wnode = znode = cnode; deba@2480: return; deba@2480: deba@2480: } else if (pert) { deba@2480: wnode = cnode; deba@2480: deba@2480: while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) { deba@2480: Edge edge = node_data[order_map[cnode]].first; deba@2480: deba@2480: if (_ugraph.target(edge) == pred) { deba@2480: edge = edge_lists[edge].next; deba@2480: } deba@2480: _kuratowski.set(edge, true); deba@2480: deba@2480: Node next = _ugraph.target(edge); deba@2480: pred = cnode; cnode = next; deba@2480: } deba@2480: deba@2480: znode = cnode; deba@2480: return; deba@2480: deba@2480: } else if (ext) { deba@2480: znode = cnode; deba@2480: deba@2480: while (!pertinent(cnode, embed_edge, merge_roots)) { deba@2480: Edge edge = node_data[order_map[cnode]].first; deba@2480: deba@2480: if (_ugraph.target(edge) == pred) { deba@2480: edge = edge_lists[edge].next; deba@2480: } deba@2480: _kuratowski.set(edge, true); deba@2480: deba@2480: Node next = _ugraph.target(edge); deba@2480: pred = cnode; cnode = next; deba@2480: } deba@2480: deba@2480: wnode = cnode; deba@2480: return; deba@2480: deba@2480: } else { deba@2480: Edge edge = node_data[order_map[cnode]].first; deba@2480: deba@2480: if (_ugraph.target(edge) == pred) { deba@2480: edge = edge_lists[edge].next; deba@2480: } deba@2480: _kuratowski.set(edge, true); deba@2480: deba@2480: Node next = _ugraph.target(edge); deba@2480: pred = cnode; cnode = next; deba@2480: } deba@2480: deba@2480: } deba@2480: deba@2480: } deba@2480: deba@2480: void orientComponent(Node root, int rn, OrderMap& order_map, deba@2480: PredMap& pred_map, NodeData& node_data, deba@2480: EdgeLists& edge_lists, FlipMap& flip_map, deba@2480: TypeMap& type_map) { deba@2480: node_data[order_map[root]].first = node_data[rn].first; deba@2480: type_map[root] = 1; deba@2480: deba@2480: std::vector st, qu; deba@2480: deba@2480: st.push_back(root); deba@2480: while (!st.empty()) { deba@2480: Node node = st.back(); deba@2480: st.pop_back(); deba@2480: qu.push_back(node); deba@2480: deba@2480: Edge edge = node_data[order_map[node]].first; deba@2480: deba@2480: if (type_map[_ugraph.target(edge)] == 0) { deba@2480: st.push_back(_ugraph.target(edge)); deba@2480: type_map[_ugraph.target(edge)] = 1; deba@2480: } deba@2480: deba@2480: Edge last = edge, pred = edge; deba@2480: edge = edge_lists[edge].next; deba@2480: while (edge != last) { deba@2480: deba@2480: if (type_map[_ugraph.target(edge)] == 0) { deba@2480: st.push_back(_ugraph.target(edge)); deba@2480: type_map[_ugraph.target(edge)] = 1; deba@2480: } deba@2480: deba@2480: Edge next = edge_lists[edge].next != pred ? deba@2480: edge_lists[edge].next : edge_lists[edge].prev; deba@2480: pred = edge; edge = next; deba@2480: } deba@2480: deba@2480: } deba@2480: deba@2480: type_map[root] = 2; deba@2480: flip_map[root] = false; deba@2480: deba@2480: for (int i = 1; i < int(qu.size()); ++i) { deba@2480: deba@2480: Node node = qu[i]; deba@2480: deba@2480: while (type_map[node] != 2) { deba@2480: st.push_back(node); deba@2480: type_map[node] = 2; deba@2480: node = _ugraph.source(pred_map[node]); deba@2480: } deba@2480: deba@2480: bool flip = flip_map[node]; deba@2480: deba@2480: while (!st.empty()) { deba@2480: node = st.back(); deba@2480: st.pop_back(); deba@2480: deba@2480: flip_map[node] = flip != flip_map[node]; deba@2480: flip = flip_map[node]; deba@2480: deba@2480: if (flip) { deba@2480: Edge edge = node_data[order_map[node]].first; deba@2480: std::swap(edge_lists[edge].prev, edge_lists[edge].next); deba@2480: edge = edge_lists[edge].prev; deba@2480: std::swap(edge_lists[edge].prev, edge_lists[edge].next); deba@2480: node_data[order_map[node]].first = edge; deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: for (int i = 0; i < int(qu.size()); ++i) { deba@2480: deba@2480: Edge edge = node_data[order_map[qu[i]]].first; deba@2480: Edge last = edge, pred = edge; deba@2480: deba@2480: edge = edge_lists[edge].next; deba@2480: while (edge != last) { deba@2480: deba@2480: if (edge_lists[edge].next == pred) { deba@2480: std::swap(edge_lists[edge].next, edge_lists[edge].prev); deba@2480: } deba@2480: pred = edge; edge = edge_lists[edge].next; deba@2480: } deba@2480: deba@2480: } deba@2480: } deba@2480: deba@2480: void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode, deba@2480: OrderMap& order_map, NodeData& node_data, deba@2480: TypeMap& type_map) { deba@2480: Node node = _ugraph.target(node_data[order_map[root]].first); deba@2480: deba@2480: while (node != ynode) { deba@2480: type_map[node] = HIGHY; deba@2480: node = _ugraph.target(node_data[order_map[node]].first); deba@2480: } deba@2480: deba@2480: while (node != wnode) { deba@2480: type_map[node] = LOWY; deba@2480: node = _ugraph.target(node_data[order_map[node]].first); deba@2480: } deba@2480: deba@2480: node = _ugraph.target(node_data[order_map[wnode]].first); deba@2480: deba@2480: while (node != xnode) { deba@2480: type_map[node] = LOWX; deba@2480: node = _ugraph.target(node_data[order_map[node]].first); deba@2480: } deba@2480: type_map[node] = LOWX; deba@2480: deba@2480: node = _ugraph.target(node_data[order_map[xnode]].first); deba@2480: while (node != root) { deba@2480: type_map[node] = HIGHX; deba@2480: node = _ugraph.target(node_data[order_map[node]].first); deba@2480: } deba@2480: deba@2480: type_map[wnode] = PERTINENT; deba@2480: type_map[root] = ROOT; deba@2480: } deba@2480: deba@2480: void findInternalPath(std::vector& ipath, deba@2480: Node wnode, Node root, TypeMap& type_map, deba@2480: OrderMap& order_map, NodeData& node_data, deba@2480: EdgeLists& edge_lists) { deba@2480: std::vector st; deba@2480: deba@2480: Node node = wnode; deba@2480: deba@2480: while (node != root) { deba@2480: Edge edge = edge_lists[node_data[order_map[node]].first].next; deba@2480: st.push_back(edge); deba@2480: node = _ugraph.target(edge); deba@2480: } deba@2480: deba@2480: while (true) { deba@2480: Edge edge = st.back(); deba@2480: if (type_map[_ugraph.target(edge)] == LOWX || deba@2480: type_map[_ugraph.target(edge)] == HIGHX) { deba@2480: break; deba@2480: } deba@2480: if (type_map[_ugraph.target(edge)] == 2) { deba@2480: type_map[_ugraph.target(edge)] = 3; deba@2480: deba@2480: edge = edge_lists[_ugraph.oppositeEdge(edge)].next; deba@2480: st.push_back(edge); deba@2480: } else { deba@2480: st.pop_back(); deba@2480: edge = edge_lists[edge].next; deba@2480: deba@2480: while (_ugraph.oppositeEdge(edge) == st.back()) { deba@2480: edge = st.back(); deba@2480: st.pop_back(); deba@2480: edge = edge_lists[edge].next; deba@2480: } deba@2480: st.push_back(edge); deba@2480: } deba@2480: } deba@2480: deba@2480: for (int i = 0; i < int(st.size()); ++i) { deba@2480: if (type_map[_ugraph.target(st[i])] != LOWY && deba@2480: type_map[_ugraph.target(st[i])] != HIGHY) { deba@2480: for (; i < int(st.size()); ++i) { deba@2480: ipath.push_back(st[i]); deba@2480: } deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: void setInternalFlags(std::vector& ipath, TypeMap& type_map) { deba@2480: for (int i = 1; i < int(ipath.size()); ++i) { deba@2480: type_map[_ugraph.source(ipath[i])] = INTERNAL; deba@2480: } deba@2480: } deba@2480: deba@2480: void findPilePath(std::vector& ppath, deba@2480: Node root, TypeMap& type_map, OrderMap& order_map, deba@2480: NodeData& node_data, EdgeLists& edge_lists) { deba@2480: std::vector st; deba@2480: deba@2480: st.push_back(_ugraph.oppositeEdge(node_data[order_map[root]].first)); deba@2480: st.push_back(node_data[order_map[root]].first); deba@2480: deba@2480: while (st.size() > 1) { deba@2480: Edge edge = st.back(); deba@2480: if (type_map[_ugraph.target(edge)] == INTERNAL) { deba@2480: break; deba@2480: } deba@2480: if (type_map[_ugraph.target(edge)] == 3) { deba@2480: type_map[_ugraph.target(edge)] = 4; deba@2480: deba@2480: edge = edge_lists[_ugraph.oppositeEdge(edge)].next; deba@2480: st.push_back(edge); deba@2480: } else { deba@2480: st.pop_back(); deba@2480: edge = edge_lists[edge].next; deba@2480: deba@2480: while (!st.empty() && _ugraph.oppositeEdge(edge) == st.back()) { deba@2480: edge = st.back(); deba@2480: st.pop_back(); deba@2480: edge = edge_lists[edge].next; deba@2480: } deba@2480: st.push_back(edge); deba@2480: } deba@2480: } deba@2480: deba@2480: for (int i = 1; i < int(st.size()); ++i) { deba@2480: ppath.push_back(st[i]); deba@2480: } deba@2480: } deba@2480: deba@2480: deba@2480: int markExternalPath(Node node, OrderMap& order_map, deba@2480: ChildLists& child_lists, PredMap& pred_map, deba@2480: AncestorMap& ancestor_map, LowMap& low_map) { deba@2480: int lp = lowPoint(node, order_map, child_lists, deba@2480: ancestor_map, low_map); deba@2480: deba@2480: if (ancestor_map[node] != lp) { deba@2480: node = child_lists[node].first; deba@2480: _kuratowski[pred_map[node]] = true; deba@2480: deba@2480: while (ancestor_map[node] != lp) { deba@2480: for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { deba@2480: Node tnode = _ugraph.target(e); deba@2480: if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) { deba@2480: node = tnode; deba@2480: _kuratowski[e] = true; deba@2480: break; deba@2480: } deba@2480: } deba@2480: } deba@2480: } deba@2480: deba@2480: for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { deba@2480: if (order_map[_ugraph.target(e)] == lp) { deba@2480: _kuratowski[e] = true; deba@2480: break; deba@2480: } deba@2480: } deba@2480: deba@2480: return lp; deba@2480: } deba@2480: deba@2480: void markPertinentPath(Node node, OrderMap& order_map, deba@2480: NodeData& node_data, EdgeLists& edge_lists, deba@2480: EmbedEdge& embed_edge, MergeRoots& merge_roots) { deba@2480: while (embed_edge[node] == INVALID) { deba@2480: int n = merge_roots[node].front(); deba@2480: Edge edge = node_data[n].first; deba@2480: deba@2480: _kuratowski.set(edge, true); deba@2480: deba@2480: Node pred = node; deba@2480: node = _ugraph.target(edge); deba@2480: while (!pertinent(node, embed_edge, merge_roots)) { deba@2480: edge = node_data[order_map[node]].first; deba@2480: if (_ugraph.target(edge) == pred) { deba@2480: edge = edge_lists[edge].next; deba@2480: } deba@2480: _kuratowski.set(edge, true); deba@2480: pred = node; deba@2480: node = _ugraph.target(edge); deba@2480: } deba@2480: } deba@2480: _kuratowski.set(embed_edge[node], true); deba@2480: } deba@2480: deba@2480: void markPredPath(Node node, Node snode, PredMap& pred_map) { deba@2480: while (node != snode) { deba@2480: _kuratowski.set(pred_map[node], true); deba@2480: node = _ugraph.source(pred_map[node]); deba@2480: } deba@2480: } deba@2480: deba@2480: void markFacePath(Node ynode, Node xnode, deba@2480: OrderMap& order_map, NodeData& node_data) { deba@2480: Edge edge = node_data[order_map[ynode]].first; deba@2480: Node node = _ugraph.target(edge); deba@2480: _kuratowski.set(edge, true); deba@2480: deba@2480: while (node != xnode) { deba@2480: edge = node_data[order_map[node]].first; deba@2480: _kuratowski.set(edge, true); deba@2480: node = _ugraph.target(edge); deba@2480: } deba@2480: } deba@2480: deba@2480: void markInternalPath(std::vector& path) { deba@2480: for (int i = 0; i < int(path.size()); ++i) { deba@2480: _kuratowski.set(path[i], true); deba@2480: } deba@2480: } deba@2480: deba@2480: void markPilePath(std::vector& path) { deba@2480: for (int i = 0; i < int(path.size()); ++i) { deba@2480: _kuratowski.set(path[i], true); deba@2480: } deba@2480: } deba@2480: deba@2480: void isolateKuratowski(Edge edge, NodeData& node_data, deba@2480: EdgeLists& edge_lists, FlipMap& flip_map, deba@2480: OrderMap& order_map, OrderList& order_list, deba@2480: PredMap& pred_map, ChildLists& child_lists, deba@2480: AncestorMap& ancestor_map, LowMap& low_map, deba@2480: EmbedEdge& embed_edge, MergeRoots& merge_roots) { deba@2480: deba@2480: Node root = _ugraph.source(edge); deba@2480: Node enode = _ugraph.target(edge); deba@2480: deba@2480: int rorder = order_map[root]; deba@2480: deba@2480: TypeMap type_map(_ugraph, 0); deba@2480: deba@2480: int rn = findComponentRoot(root, enode, child_lists, deba@2480: order_map, order_list); deba@2480: deba@2480: Node xnode = order_list[node_data[rn].next]; deba@2480: Node ynode = order_list[node_data[rn].prev]; deba@2480: deba@2480: // Minor-A deba@2480: { deba@2480: while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) { deba@2480: deba@2480: if (!merge_roots[xnode].empty()) { deba@2480: root = xnode; deba@2480: rn = merge_roots[xnode].front(); deba@2480: } else { deba@2480: root = ynode; deba@2480: rn = merge_roots[ynode].front(); deba@2480: } deba@2480: deba@2480: xnode = order_list[node_data[rn].next]; deba@2480: ynode = order_list[node_data[rn].prev]; deba@2480: } deba@2480: deba@2480: if (root != _ugraph.source(edge)) { deba@2480: orientComponent(root, rn, order_map, pred_map, deba@2480: node_data, edge_lists, flip_map, type_map); deba@2480: markFacePath(root, root, order_map, node_data); deba@2480: int xlp = markExternalPath(xnode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: int ylp = markExternalPath(ynode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); deba@2480: Node lwnode = findPertinent(ynode, order_map, node_data, deba@2480: embed_edge, merge_roots); deba@2480: deba@2480: markPertinentPath(lwnode, order_map, node_data, edge_lists, deba@2480: embed_edge, merge_roots); deba@2480: deba@2480: return; deba@2480: } deba@2480: } deba@2480: deba@2480: orientComponent(root, rn, order_map, pred_map, deba@2480: node_data, edge_lists, flip_map, type_map); deba@2480: deba@2480: Node wnode = findPertinent(ynode, order_map, node_data, deba@2480: embed_edge, merge_roots); deba@2480: setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map); deba@2480: deba@2480: deba@2480: //Minor-B deba@2480: if (!merge_roots[wnode].empty()) { deba@2480: int cn = merge_roots[wnode].back(); deba@2480: Node rep = order_list[cn - order_list.size()]; deba@2480: if (low_map[rep] < rorder) { deba@2480: markFacePath(root, root, order_map, node_data); deba@2480: int xlp = markExternalPath(xnode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: int ylp = markExternalPath(ynode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: deba@2480: Node lwnode, lznode; deba@2480: markCommonPath(wnode, rorder, lwnode, lznode, order_list, deba@2480: order_map, node_data, edge_lists, embed_edge, deba@2480: merge_roots, child_lists, ancestor_map, low_map); deba@2480: deba@2480: markPertinentPath(lwnode, order_map, node_data, edge_lists, deba@2480: embed_edge, merge_roots); deba@2480: int zlp = markExternalPath(lznode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: deba@2480: int minlp = xlp < ylp ? xlp : ylp; deba@2480: if (zlp < minlp) minlp = zlp; deba@2480: deba@2480: int maxlp = xlp > ylp ? xlp : ylp; deba@2480: if (zlp > maxlp) maxlp = zlp; deba@2480: deba@2480: markPredPath(order_list[maxlp], order_list[minlp], pred_map); deba@2480: deba@2480: return; deba@2480: } deba@2480: } deba@2480: deba@2480: Node pxnode, pynode; deba@2480: std::vector ipath; deba@2480: findInternalPath(ipath, wnode, root, type_map, order_map, deba@2480: node_data, edge_lists); deba@2480: setInternalFlags(ipath, type_map); deba@2480: pynode = _ugraph.source(ipath.front()); deba@2480: pxnode = _ugraph.target(ipath.back()); deba@2480: deba@2480: wnode = findPertinent(pynode, order_map, node_data, deba@2480: embed_edge, merge_roots); deba@2480: deba@2480: // Minor-C deba@2480: { deba@2480: if (type_map[_ugraph.source(ipath.front())] == HIGHY) { deba@2480: if (type_map[_ugraph.target(ipath.back())] == HIGHX) { deba@2480: markFacePath(xnode, pxnode, order_map, node_data); deba@2480: } deba@2480: markFacePath(root, xnode, order_map, node_data); deba@2480: markPertinentPath(wnode, order_map, node_data, edge_lists, deba@2480: embed_edge, merge_roots); deba@2480: markInternalPath(ipath); deba@2480: int xlp = markExternalPath(xnode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: int ylp = markExternalPath(ynode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); deba@2480: return; deba@2480: } deba@2480: deba@2480: if (type_map[_ugraph.target(ipath.back())] == HIGHX) { deba@2480: markFacePath(ynode, root, order_map, node_data); deba@2480: markPertinentPath(wnode, order_map, node_data, edge_lists, deba@2480: embed_edge, merge_roots); deba@2480: markInternalPath(ipath); deba@2480: int xlp = markExternalPath(xnode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: int ylp = markExternalPath(ynode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); deba@2480: return; deba@2480: } deba@2480: } deba@2480: deba@2480: std::vector ppath; deba@2480: findPilePath(ppath, root, type_map, order_map, node_data, edge_lists); deba@2480: deba@2480: // Minor-D deba@2480: if (!ppath.empty()) { deba@2480: markFacePath(ynode, xnode, order_map, node_data); deba@2480: markPertinentPath(wnode, order_map, node_data, edge_lists, deba@2480: embed_edge, merge_roots); deba@2480: markPilePath(ppath); deba@2480: markInternalPath(ipath); deba@2480: int xlp = markExternalPath(xnode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: int ylp = markExternalPath(ynode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); deba@2480: return; deba@2480: } deba@2480: deba@2480: // Minor-E* deba@2480: { deba@2480: deba@2480: if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) { deba@2480: Node znode = findExternal(pynode, rorder, order_map, deba@2480: child_lists, ancestor_map, deba@2480: low_map, node_data); deba@2480: deba@2480: if (type_map[znode] == LOWY) { deba@2480: markFacePath(root, xnode, order_map, node_data); deba@2480: markPertinentPath(wnode, order_map, node_data, edge_lists, deba@2480: embed_edge, merge_roots); deba@2480: markInternalPath(ipath); deba@2480: int xlp = markExternalPath(xnode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: int zlp = markExternalPath(znode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map); deba@2480: } else { deba@2480: markFacePath(ynode, root, order_map, node_data); deba@2480: markPertinentPath(wnode, order_map, node_data, edge_lists, deba@2480: embed_edge, merge_roots); deba@2480: markInternalPath(ipath); deba@2480: int ylp = markExternalPath(ynode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: int zlp = markExternalPath(znode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map); deba@2480: } deba@2480: return; deba@2480: } deba@2480: deba@2480: int xlp = markExternalPath(xnode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: int ylp = markExternalPath(ynode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: int wlp = markExternalPath(wnode, order_map, child_lists, deba@2480: pred_map, ancestor_map, low_map); deba@2480: deba@2480: if (wlp > xlp && wlp > ylp) { deba@2480: markFacePath(root, root, order_map, node_data); deba@2480: markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); deba@2480: return; deba@2480: } deba@2480: deba@2480: markInternalPath(ipath); deba@2480: markPertinentPath(wnode, order_map, node_data, edge_lists, deba@2480: embed_edge, merge_roots); deba@2480: deba@2480: if (xlp > ylp && xlp > wlp) { deba@2480: markFacePath(root, pynode, order_map, node_data); deba@2480: markFacePath(wnode, xnode, order_map, node_data); deba@2480: markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map); deba@2480: return; deba@2480: } deba@2480: deba@2480: if (ylp > xlp && ylp > wlp) { deba@2480: markFacePath(pxnode, root, order_map, node_data); deba@2480: markFacePath(ynode, wnode, order_map, node_data); deba@2480: markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map); deba@2480: return; deba@2480: } deba@2480: deba@2480: if (pynode != ynode) { deba@2480: markFacePath(pxnode, wnode, order_map, node_data); deba@2480: deba@2480: int minlp = xlp < ylp ? xlp : ylp; deba@2480: if (wlp < minlp) minlp = wlp; deba@2480: deba@2480: int maxlp = xlp > ylp ? xlp : ylp; deba@2480: if (wlp > maxlp) maxlp = wlp; deba@2480: deba@2480: markPredPath(order_list[maxlp], order_list[minlp], pred_map); deba@2480: return; deba@2480: } deba@2480: deba@2480: if (pxnode != xnode) { deba@2480: markFacePath(wnode, pynode, order_map, node_data); deba@2480: deba@2480: int minlp = xlp < ylp ? xlp : ylp; deba@2480: if (wlp < minlp) minlp = wlp; deba@2480: deba@2480: int maxlp = xlp > ylp ? xlp : ylp; deba@2480: if (wlp > maxlp) maxlp = wlp; deba@2480: deba@2480: markPredPath(order_list[maxlp], order_list[minlp], pred_map); deba@2480: return; deba@2480: } deba@2480: deba@2480: markFacePath(root, root, order_map, node_data); deba@2480: int minlp = xlp < ylp ? xlp : ylp; deba@2480: if (wlp < minlp) minlp = wlp; deba@2480: markPredPath(root, order_list[minlp], pred_map); deba@2480: return; deba@2480: } deba@2480: deba@2480: } deba@2480: deba@2480: }; deba@2480: deba@2499: namespace _planarity_bits { deba@2499: deba@2499: template deba@2499: void makeConnected(UGraph& ugraph, EmbeddingMap& embedding) { deba@2499: DfsVisitor null_visitor; deba@2499: DfsVisit > dfs(ugraph, null_visitor); deba@2499: dfs.init(); deba@2499: deba@2499: typename UGraph::Node u = INVALID; deba@2499: for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) { deba@2499: if (!dfs.reached(n)) { deba@2499: dfs.addSource(n); deba@2499: dfs.start(); deba@2499: if (u == INVALID) { deba@2499: u = n; deba@2499: } else { deba@2499: typename UGraph::Node v = n; deba@2499: deba@2499: typename UGraph::Edge ue = typename UGraph::OutEdgeIt(ugraph, u); deba@2499: typename UGraph::Edge ve = typename UGraph::OutEdgeIt(ugraph, v); deba@2499: deba@2499: typename UGraph::Edge e = ugraph.direct(ugraph.addEdge(u, v), true); deba@2499: deba@2499: if (ue != INVALID) { deba@2499: embedding[e] = embedding[ue]; deba@2499: embedding[ue] = e; deba@2499: } else { deba@2499: embedding[e] = e; deba@2499: } deba@2499: deba@2499: if (ve != INVALID) { deba@2499: embedding[ugraph.oppositeEdge(e)] = embedding[ve]; deba@2499: embedding[ve] = ugraph.oppositeEdge(e); deba@2499: } else { deba@2499: embedding[ugraph.oppositeEdge(e)] = ugraph.oppositeEdge(e); deba@2499: } deba@2499: } deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: template deba@2499: void makeBiNodeConnected(UGraph& ugraph, EmbeddingMap& embedding) { deba@2499: typename UGraph::template EdgeMap processed(ugraph); deba@2499: deba@2499: std::vector edges; deba@2499: for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) { deba@2499: edges.push_back(e); deba@2499: } deba@2499: deba@2499: IterableBoolMap visited(ugraph, false); deba@2499: deba@2499: for (int i = 0; i < int(edges.size()); ++i) { deba@2499: typename UGraph::Edge pp = edges[i]; deba@2499: if (processed[pp]) continue; deba@2499: deba@2499: typename UGraph::Edge e = embedding[ugraph.oppositeEdge(pp)]; deba@2499: processed[e] = true; deba@2499: visited.set(ugraph.source(e), true); deba@2499: deba@2499: typename UGraph::Edge p = e, l = e; deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: deba@2499: while (e != l) { deba@2499: processed[e] = true; deba@2499: deba@2499: if (visited[ugraph.source(e)]) { deba@2499: deba@2499: typename UGraph::Edge n = deba@2499: ugraph.direct(ugraph.addEdge(ugraph.source(p), deba@2499: ugraph.target(e)), true); deba@2499: embedding[n] = p; deba@2499: embedding[ugraph.oppositeEdge(pp)] = n; deba@2499: deba@2499: embedding[ugraph.oppositeEdge(n)] = deba@2499: embedding[ugraph.oppositeEdge(e)]; deba@2499: embedding[ugraph.oppositeEdge(e)] = deba@2499: ugraph.oppositeEdge(n); deba@2499: deba@2499: p = n; deba@2499: e = embedding[ugraph.oppositeEdge(n)]; deba@2499: } else { deba@2499: visited.set(ugraph.source(e), true); deba@2499: pp = p; deba@2499: p = e; deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: } deba@2499: } deba@2499: visited.setAll(false); deba@2499: } deba@2499: } deba@2499: deba@2499: deba@2499: template deba@2499: void makeMaxPlanar(UGraph& ugraph, EmbeddingMap& embedding) { deba@2499: deba@2499: typename UGraph::template NodeMap degree(ugraph); deba@2499: deba@2499: for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) { deba@2499: degree[n] = countIncEdges(ugraph, n); deba@2499: } deba@2499: deba@2499: typename UGraph::template EdgeMap processed(ugraph); deba@2499: IterableBoolMap visited(ugraph, false); deba@2499: deba@2499: std::vector edges; deba@2499: for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) { deba@2499: edges.push_back(e); deba@2499: } deba@2499: deba@2499: for (int i = 0; i < int(edges.size()); ++i) { deba@2499: typename UGraph::Edge e = edges[i]; deba@2499: deba@2499: if (processed[e]) continue; deba@2499: processed[e] = true; deba@2499: deba@2499: typename UGraph::Edge mine = e; deba@2499: int mind = degree[ugraph.source(e)]; deba@2499: deba@2499: int face_size = 1; deba@2499: deba@2499: typename UGraph::Edge l = e; deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: while (l != e) { deba@2499: processed[e] = true; deba@2499: deba@2499: ++face_size; deba@2499: deba@2499: if (degree[ugraph.source(e)] < mind) { deba@2499: mine = e; deba@2499: mind = degree[ugraph.source(e)]; deba@2499: } deba@2499: deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: } deba@2499: deba@2499: if (face_size < 4) { deba@2499: continue; deba@2499: } deba@2499: deba@2499: typename UGraph::Node s = ugraph.source(mine); deba@2499: for (typename UGraph::OutEdgeIt e(ugraph, s); e != INVALID; ++e) { deba@2499: visited.set(ugraph.target(e), true); deba@2499: } deba@2499: deba@2499: typename UGraph::Edge oppe = INVALID; deba@2499: deba@2499: e = embedding[ugraph.oppositeEdge(mine)]; deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: while (ugraph.target(e) != s) { deba@2499: if (visited[ugraph.source(e)]) { deba@2499: oppe = e; deba@2499: break; deba@2499: } deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: } deba@2499: visited.setAll(false); deba@2499: deba@2499: if (oppe == INVALID) { deba@2499: deba@2499: e = embedding[ugraph.oppositeEdge(mine)]; deba@2499: typename UGraph::Edge pn = mine, p = e; deba@2499: deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: while (ugraph.target(e) != s) { deba@2499: typename UGraph::Edge n = deba@2499: ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true); deba@2499: deba@2499: embedding[n] = pn; deba@2499: embedding[ugraph.oppositeEdge(n)] = e; deba@2499: embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n); deba@2499: deba@2499: pn = n; deba@2499: deba@2499: p = e; deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: } deba@2499: deba@2499: embedding[ugraph.oppositeEdge(e)] = pn; deba@2499: deba@2499: } else { deba@2499: deba@2499: mine = embedding[ugraph.oppositeEdge(mine)]; deba@2499: s = ugraph.source(mine); deba@2499: oppe = embedding[ugraph.oppositeEdge(oppe)]; deba@2499: typename UGraph::Node t = ugraph.source(oppe); deba@2499: deba@2499: typename UGraph::Edge ce = ugraph.direct(ugraph.addEdge(s, t), true); deba@2499: embedding[ce] = mine; deba@2499: embedding[ugraph.oppositeEdge(ce)] = oppe; deba@2499: deba@2499: typename UGraph::Edge pn = ce, p = oppe; deba@2499: e = embedding[ugraph.oppositeEdge(oppe)]; deba@2499: while (ugraph.target(e) != s) { deba@2499: typename UGraph::Edge n = deba@2499: ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true); deba@2499: deba@2499: embedding[n] = pn; deba@2499: embedding[ugraph.oppositeEdge(n)] = e; deba@2499: embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n); deba@2499: deba@2499: pn = n; deba@2499: deba@2499: p = e; deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: deba@2499: } deba@2499: embedding[ugraph.oppositeEdge(e)] = pn; deba@2499: deba@2499: pn = ugraph.oppositeEdge(ce), p = mine; deba@2499: e = embedding[ugraph.oppositeEdge(mine)]; deba@2499: while (ugraph.target(e) != t) { deba@2499: typename UGraph::Edge n = deba@2499: ugraph.direct(ugraph.addEdge(t, ugraph.source(e)), true); deba@2499: deba@2499: embedding[n] = pn; deba@2499: embedding[ugraph.oppositeEdge(n)] = e; deba@2499: embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n); deba@2499: deba@2499: pn = n; deba@2499: deba@2499: p = e; deba@2499: e = embedding[ugraph.oppositeEdge(e)]; deba@2499: deba@2499: } deba@2499: embedding[ugraph.oppositeEdge(e)] = pn; deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: } deba@2499: deba@2500: /// \ingroup planar deba@2500: /// deba@2499: /// \brief Schnyder's planar drawing algorithms deba@2499: /// deba@2499: /// The planar drawing algorithm calculates location for each node deba@2499: /// in the plane, which coordinates satisfies that if each edge is deba@2499: /// represented with a straight line then the edges will not deba@2499: /// intersect each other. deba@2499: /// deba@2499: /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid, deba@2499: /// ie. each node will be located in the \c [0,n-2]x[0,n-2] square. deba@2499: /// The time complexity of the algorithm is O(n). deba@2499: template deba@2499: class PlanarDrawing { deba@2499: public: deba@2499: deba@2499: UGRAPH_TYPEDEFS(typename UGraph); deba@2499: deba@2499: /// \brief The point type for store coordinates deba@2499: typedef dim2::Point Point; deba@2499: /// \brief The map type for store coordinates deba@2499: typedef typename UGraph::template NodeMap PointMap; deba@2499: deba@2499: deba@2499: /// \brief Constructor deba@2499: /// deba@2499: /// Constructor deba@2499: /// \pre The ugraph should be simple, ie. loop and parallel edge free. deba@2499: PlanarDrawing(const UGraph& ugraph) deba@2499: : _ugraph(ugraph), _point_map(ugraph) {} deba@2499: deba@2499: private: deba@2499: deba@2499: template deba@2499: void drawing(const AuxUGraph& ugraph, deba@2499: const AuxEmbeddingMap& next, deba@2499: PointMap& point_map) { deba@2499: UGRAPH_TYPEDEFS(typename AuxUGraph); deba@2499: deba@2499: typename AuxUGraph::template EdgeMap prev(ugraph); deba@2499: deba@2499: for (NodeIt n(ugraph); n != INVALID; ++n) { deba@2499: Edge e = OutEdgeIt(ugraph, n); deba@2499: deba@2499: Edge p = e, l = e; deba@2499: deba@2499: e = next[e]; deba@2499: while (e != l) { deba@2499: prev[e] = p; deba@2499: p = e; deba@2499: e = next[e]; deba@2499: } deba@2499: prev[e] = p; deba@2499: } deba@2499: deba@2499: Node anode, bnode, cnode; deba@2499: deba@2499: { deba@2499: Edge e = EdgeIt(ugraph); deba@2499: anode = ugraph.source(e); deba@2499: bnode = ugraph.target(e); deba@2499: cnode = ugraph.target(next[ugraph.oppositeEdge(e)]); deba@2499: } deba@2499: deba@2499: IterableBoolMap proper(ugraph, false); deba@2499: typename AuxUGraph::template NodeMap conn(ugraph, -1); deba@2499: deba@2499: conn[anode] = conn[bnode] = -2; deba@2499: { deba@2499: for (OutEdgeIt e(ugraph, anode); e != INVALID; ++e) { deba@2499: Node m = ugraph.target(e); deba@2499: if (conn[m] == -1) { deba@2499: conn[m] = 1; deba@2499: } deba@2499: } deba@2499: conn[cnode] = 2; deba@2499: deba@2499: for (OutEdgeIt e(ugraph, bnode); e != INVALID; ++e) { deba@2499: Node m = ugraph.target(e); deba@2499: if (conn[m] == -1) { deba@2499: conn[m] = 1; deba@2499: } else if (conn[m] != -2) { deba@2499: conn[m] += 1; deba@2499: Edge pe = ugraph.oppositeEdge(e); deba@2499: if (conn[ugraph.target(next[pe])] == -2) { deba@2499: conn[m] -= 1; deba@2499: } deba@2499: if (conn[ugraph.target(prev[pe])] == -2) { deba@2499: conn[m] -= 1; deba@2499: } deba@2499: deba@2499: proper.set(m, conn[m] == 1); deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: deba@2499: typename AuxUGraph::template EdgeMap angle(ugraph, -1); deba@2499: deba@2499: while (proper.trueNum() != 0) { deba@2499: Node n = typename IterableBoolMap::TrueIt(proper); deba@2499: proper.set(n, false); deba@2499: conn[n] = -2; deba@2499: deba@2499: for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) { deba@2499: Node m = ugraph.target(e); deba@2499: if (conn[m] == -1) { deba@2499: conn[m] = 1; deba@2499: } else if (conn[m] != -2) { deba@2499: conn[m] += 1; deba@2499: Edge pe = ugraph.oppositeEdge(e); deba@2499: if (conn[ugraph.target(next[pe])] == -2) { deba@2499: conn[m] -= 1; deba@2499: } deba@2499: if (conn[ugraph.target(prev[pe])] == -2) { deba@2499: conn[m] -= 1; deba@2499: } deba@2499: deba@2499: proper.set(m, conn[m] == 1); deba@2499: } deba@2499: } deba@2499: deba@2499: { deba@2499: Edge e = OutEdgeIt(ugraph, n); deba@2499: Edge p = e, l = e; deba@2499: deba@2499: e = next[e]; deba@2499: while (e != l) { deba@2499: deba@2499: if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) { deba@2499: Edge f = e; deba@2499: angle[f] = 0; deba@2499: f = next[ugraph.oppositeEdge(f)]; deba@2499: angle[f] = 1; deba@2499: f = next[ugraph.oppositeEdge(f)]; deba@2499: angle[f] = 2; deba@2499: } deba@2499: deba@2499: p = e; deba@2499: e = next[e]; deba@2499: } deba@2499: deba@2499: if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) { deba@2499: Edge f = e; deba@2499: angle[f] = 0; deba@2499: f = next[ugraph.oppositeEdge(f)]; deba@2499: angle[f] = 1; deba@2499: f = next[ugraph.oppositeEdge(f)]; deba@2499: angle[f] = 2; deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: typename AuxUGraph::template NodeMap apred(ugraph, INVALID); deba@2499: typename AuxUGraph::template NodeMap bpred(ugraph, INVALID); deba@2499: typename AuxUGraph::template NodeMap cpred(ugraph, INVALID); deba@2499: deba@2499: typename AuxUGraph::template NodeMap apredid(ugraph, -1); deba@2499: typename AuxUGraph::template NodeMap bpredid(ugraph, -1); deba@2499: typename AuxUGraph::template NodeMap cpredid(ugraph, -1); deba@2499: deba@2499: for (EdgeIt e(ugraph); e != INVALID; ++e) { deba@2499: if (angle[e] == angle[next[e]]) { deba@2499: switch (angle[e]) { deba@2499: case 2: deba@2499: apred[ugraph.target(e)] = ugraph.source(e); deba@2499: apredid[ugraph.target(e)] = ugraph.id(ugraph.source(e)); deba@2499: break; deba@2499: case 1: deba@2499: bpred[ugraph.target(e)] = ugraph.source(e); deba@2499: bpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e)); deba@2499: break; deba@2499: case 0: deba@2499: cpred[ugraph.target(e)] = ugraph.source(e); deba@2499: cpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e)); deba@2499: break; deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: cpred[anode] = INVALID; deba@2499: cpred[bnode] = INVALID; deba@2499: deba@2499: std::vector aorder, border, corder; deba@2499: deba@2499: { deba@2499: typename AuxUGraph::template NodeMap processed(ugraph, false); deba@2499: std::vector st; deba@2499: for (NodeIt n(ugraph); n != INVALID; ++n) { deba@2499: if (!processed[n] && n != bnode && n != cnode) { deba@2499: st.push_back(n); deba@2499: processed[n] = true; deba@2499: Node m = apred[n]; deba@2499: while (m != INVALID && !processed[m]) { deba@2499: st.push_back(m); deba@2499: processed[m] = true; deba@2499: m = apred[m]; deba@2499: } deba@2499: while (!st.empty()) { deba@2499: aorder.push_back(st.back()); deba@2499: st.pop_back(); deba@2499: } deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: { deba@2499: typename AuxUGraph::template NodeMap processed(ugraph, false); deba@2499: std::vector st; deba@2499: for (NodeIt n(ugraph); n != INVALID; ++n) { deba@2499: if (!processed[n] && n != cnode && n != anode) { deba@2499: st.push_back(n); deba@2499: processed[n] = true; deba@2499: Node m = bpred[n]; deba@2499: while (m != INVALID && !processed[m]) { deba@2499: st.push_back(m); deba@2499: processed[m] = true; deba@2499: m = bpred[m]; deba@2499: } deba@2499: while (!st.empty()) { deba@2499: border.push_back(st.back()); deba@2499: st.pop_back(); deba@2499: } deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: { deba@2499: typename AuxUGraph::template NodeMap processed(ugraph, false); deba@2499: std::vector st; deba@2499: for (NodeIt n(ugraph); n != INVALID; ++n) { deba@2499: if (!processed[n] && n != anode && n != bnode) { deba@2499: st.push_back(n); deba@2499: processed[n] = true; deba@2499: Node m = cpred[n]; deba@2499: while (m != INVALID && !processed[m]) { deba@2499: st.push_back(m); deba@2499: processed[m] = true; deba@2499: m = cpred[m]; deba@2499: } deba@2499: while (!st.empty()) { deba@2499: corder.push_back(st.back()); deba@2499: st.pop_back(); deba@2499: } deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: typename AuxUGraph::template NodeMap atree(ugraph, 0); deba@2499: for (int i = aorder.size() - 1; i >= 0; --i) { deba@2499: Node n = aorder[i]; deba@2499: atree[n] = 1; deba@2499: for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) { deba@2499: if (apred[ugraph.target(e)] == n) { deba@2499: atree[n] += atree[ugraph.target(e)]; deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: typename AuxUGraph::template NodeMap btree(ugraph, 0); deba@2499: for (int i = border.size() - 1; i >= 0; --i) { deba@2499: Node n = border[i]; deba@2499: btree[n] = 1; deba@2499: for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) { deba@2499: if (bpred[ugraph.target(e)] == n) { deba@2499: btree[n] += btree[ugraph.target(e)]; deba@2499: } deba@2499: } deba@2499: } deba@2499: deba@2499: typename AuxUGraph::template NodeMap apath(ugraph, 0); deba@2499: apath[bnode] = apath[cnode] = 1; deba@2499: typename AuxUGraph::template NodeMap apath_btree(ugraph, 0); deba@2499: apath_btree[bnode] = btree[bnode]; deba@2499: for (int i = 1; i < int(aorder.size()); ++i) { deba@2499: Node n = aorder[i]; deba@2499: apath[n] = apath[apred[n]] + 1; deba@2499: apath_btree[n] = btree[n] + apath_btree[apred[n]]; deba@2499: } deba@2499: deba@2499: typename AuxUGraph::template NodeMap bpath_atree(ugraph, 0); deba@2499: bpath_atree[anode] = atree[anode]; deba@2499: for (int i = 1; i < int(border.size()); ++i) { deba@2499: Node n = border[i]; deba@2499: bpath_atree[n] = atree[n] + bpath_atree[bpred[n]]; deba@2499: } deba@2499: deba@2499: typename AuxUGraph::template NodeMap cpath(ugraph, 0); deba@2499: cpath[anode] = cpath[bnode] = 1; deba@2499: typename AuxUGraph::template NodeMap cpath_atree(ugraph, 0); deba@2499: cpath_atree[anode] = atree[anode]; deba@2499: typename AuxUGraph::template NodeMap cpath_btree(ugraph, 0); deba@2499: cpath_btree[bnode] = btree[bnode]; deba@2499: for (int i = 1; i < int(corder.size()); ++i) { deba@2499: Node n = corder[i]; deba@2499: cpath[n] = cpath[cpred[n]] + 1; deba@2499: cpath_atree[n] = atree[n] + cpath_atree[cpred[n]]; deba@2499: cpath_btree[n] = btree[n] + cpath_btree[cpred[n]]; deba@2499: } deba@2499: deba@2499: typename AuxUGraph::template NodeMap third(ugraph); deba@2499: for (NodeIt n(ugraph); n != INVALID; ++n) { deba@2499: point_map[n].x = deba@2499: bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1; deba@2499: point_map[n].y = deba@2499: cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1; deba@2499: } deba@2499: deba@2499: } deba@2499: deba@2499: public: deba@2499: deba@2499: /// \brief Calculates the node locations deba@2499: /// deba@2499: /// This function calculates the node locations. deba@2499: bool run() { deba@2499: PlanarEmbedding pe(_ugraph); deba@2499: if (!pe.run()) return false; deba@2499: deba@2499: run(pe); deba@2499: return true; deba@2499: } deba@2499: deba@2499: /// \brief Calculates the node locations according to a deba@2499: /// combinatorical embedding deba@2499: /// deba@2499: /// This function calculates the node locations. The \c embedding deba@2499: /// parameter should contain a valid combinatorical embedding, ie. deba@2499: /// a valid cyclic order of the edges. deba@2499: template deba@2499: void run(const EmbeddingMap& embedding) { deba@2499: typedef SmartUEdgeSet AuxUGraph; deba@2499: deba@2499: if (3 * countNodes(_ugraph) - 6 == countUEdges(_ugraph)) { deba@2499: drawing(_ugraph, embedding, _point_map); deba@2499: return; deba@2499: } deba@2499: deba@2499: AuxUGraph aux_ugraph(_ugraph); deba@2499: typename AuxUGraph::template EdgeMap deba@2499: aux_embedding(aux_ugraph); deba@2499: deba@2499: { deba@2499: deba@2499: typename UGraph::template UEdgeMap deba@2499: ref(_ugraph); deba@2499: deba@2499: for (UEdgeIt e(_ugraph); e != INVALID; ++e) { deba@2499: ref[e] = aux_ugraph.addEdge(_ugraph.source(e), _ugraph.target(e)); deba@2499: } deba@2499: deba@2499: for (UEdgeIt e(_ugraph); e != INVALID; ++e) { deba@2499: Edge ee = embedding[_ugraph.direct(e, true)]; deba@2499: aux_embedding[aux_ugraph.direct(ref[e], true)] = deba@2499: aux_ugraph.direct(ref[ee], _ugraph.direction(ee)); deba@2499: ee = embedding[_ugraph.direct(e, false)]; deba@2499: aux_embedding[aux_ugraph.direct(ref[e], false)] = deba@2499: aux_ugraph.direct(ref[ee], _ugraph.direction(ee)); deba@2499: } deba@2499: } deba@2499: _planarity_bits::makeConnected(aux_ugraph, aux_embedding); deba@2499: _planarity_bits::makeBiNodeConnected(aux_ugraph, aux_embedding); deba@2499: _planarity_bits::makeMaxPlanar(aux_ugraph, aux_embedding); deba@2499: drawing(aux_ugraph, aux_embedding, _point_map); deba@2499: } deba@2499: deba@2499: /// \brief The coordinate of the given node deba@2499: /// deba@2499: /// The coordinate of the given node. deba@2499: Point operator[](const Node& node) { deba@2499: return _point_map[node]; deba@2499: } deba@2499: deba@2499: /// \brief Returns the grid embedding in a \e NodeMap. deba@2499: /// deba@2499: /// Returns the grid embedding in a \e NodeMap of \c dim2::Point . deba@2499: const PointMap& coords() const { deba@2499: return _point_map; deba@2499: } deba@2499: deba@2499: private: deba@2499: deba@2499: const UGraph& _ugraph; deba@2499: PointMap _point_map; deba@2499: deba@2499: }; deba@2499: deba@2508: namespace _planarity_bits { deba@2508: deba@2508: template deba@2508: class KempeFilter { deba@2508: public: deba@2508: typedef typename ColorMap::Key Key; deba@2508: typedef bool Value; deba@2508: deba@2508: KempeFilter(const ColorMap& color_map, deba@2508: const typename ColorMap::Value& first, deba@2508: const typename ColorMap::Value& second) deba@2508: : _color_map(color_map), _first(first), _second(second) {} deba@2508: deba@2508: Value operator[](const Key& key) const { deba@2508: return _color_map[key] == _first || _color_map[key] == _second; deba@2508: } deba@2508: deba@2508: private: deba@2508: const ColorMap& _color_map; deba@2508: typename ColorMap::Value _first, _second; deba@2508: }; deba@2508: } deba@2508: deba@2508: /// \ingroup planar deba@2508: /// deba@2508: /// \brief Coloring planar graphs deba@2508: /// deba@2508: /// The graph coloring problem is the coloring of the graph nodes deba@2508: /// such way that there are not adjacent nodes with the same deba@2508: /// color. The planar graphs can be always colored with four colors, deba@2508: /// it is proved by Appel and Haken and their proofs provide a deba@2508: /// quadratic time algorithm for four coloring, but it could not be deba@2508: /// used to implement efficient algorithm. The five and six coloring deba@2508: /// can be made in linear time, but in this class the five coloring deba@2508: /// has quadratic worst case time complexity. The two coloring (if deba@2508: /// possible) is solvable with a graph search algorithm and it is deba@2508: /// implemented in \ref bipartitePartitions() function in Lemon. To deba@2508: /// decide whether the planar graph is three colorable is deba@2508: /// NP-complete. deba@2508: /// deba@2508: /// This class contains member functions for calculate colorings deba@2508: /// with five and six colors. The six coloring algorithm is a simple deba@2508: /// greedy coloring on the backward minimum outgoing order of nodes. deba@2508: /// This order can be computed such way, that in each phase the node deba@2508: /// with least outgoing edges to unprocessed nodes is choosen. This deba@2508: /// order guarantees that at the time of coloring of a node it has deba@2508: /// at most five already colored adjacents. The five coloring deba@2508: /// algorithm works in the same way, but if the greedy approach deba@2508: /// fails to color with five color, ie. the node has five already deba@2508: /// different colored neighbours, it swaps the colors in one deba@2508: /// connected two colored set with the Kempe recoloring method. deba@2508: template deba@2508: class PlanarColoring { deba@2508: public: deba@2508: deba@2508: UGRAPH_TYPEDEFS(typename UGraph); deba@2508: deba@2508: /// \brief The map type for store color indexes deba@2508: typedef typename UGraph::template NodeMap IndexMap; deba@2508: /// \brief The map type for store colors deba@2508: typedef ComposeMap ColorMap; deba@2508: deba@2508: /// \brief Constructor deba@2508: /// deba@2508: /// Constructor deba@2508: /// \pre The ugraph should be simple, ie. loop and parallel edge free. deba@2508: PlanarColoring(const UGraph& ugraph) deba@2508: : _ugraph(ugraph), _color_map(ugraph), _palette(0) { deba@2508: _palette.add(Color(1,0,0)); deba@2508: _palette.add(Color(0,1,0)); deba@2508: _palette.add(Color(0,0,1)); deba@2508: _palette.add(Color(1,1,0)); deba@2508: _palette.add(Color(1,0,1)); deba@2508: _palette.add(Color(0,1,1)); deba@2508: } deba@2508: deba@2508: /// \brief Returns the \e NodeMap of color indexes deba@2508: /// deba@2508: /// Returns the \e NodeMap of color indexes. The values are in the deba@2508: /// range \c [0..4] or \c [0..5] according to the five coloring or deba@2508: /// six coloring. deba@2508: IndexMap colorIndexMap() const { deba@2508: return _color_map; deba@2508: } deba@2508: deba@2508: /// \brief Returns the \e NodeMap of colors deba@2508: /// deba@2508: /// Returns the \e NodeMap of colors. The values are five or six deba@2508: /// distinct \ref lemon::Color "colors". deba@2508: ColorMap colorMap() const { deba@2508: return composeMap(_palette, _color_map); deba@2508: } deba@2508: deba@2508: /// \brief Returns the color index of the node deba@2508: /// deba@2508: /// Returns the color index of the node. The values are in the deba@2508: /// range \c [0..4] or \c [0..5] according to the five coloring or deba@2508: /// six coloring. deba@2508: int colorIndex(const Node& node) const { deba@2508: return _color_map[node]; deba@2508: } deba@2508: deba@2508: /// \brief Returns the color of the node deba@2508: /// deba@2508: /// Returns the color of the node. The values are five or six deba@2508: /// distinct \ref lemon::Color "colors". deba@2508: int color(const Node& node) const { deba@2508: return _palette[_color_map[node]]; deba@2508: } deba@2508: deba@2508: deba@2508: /// \brief Calculates a coloring with at most six colors deba@2508: /// deba@2508: /// This function calculates a coloring with at most six colors. The time deba@2508: /// complexity of this variant is linear in the size of the graph. deba@2508: /// \return %True when the algorithm could color the graph with six color. deba@2508: /// If the algorithm fails, then the graph could not be planar. deba@2508: bool runSixColoring() { deba@2508: deba@2508: typename UGraph::template NodeMap heap_index(_ugraph, -1); deba@2508: BucketHeap > heap(heap_index); deba@2508: deba@2508: for (NodeIt n(_ugraph); n != INVALID; ++n) { deba@2508: _color_map[n] = -2; deba@2508: heap.push(n, countOutEdges(_ugraph, n)); deba@2508: } deba@2508: deba@2508: std::vector order; deba@2508: deba@2508: while (!heap.empty()) { deba@2508: Node n = heap.top(); deba@2508: heap.pop(); deba@2508: _color_map[n] = -1; deba@2508: order.push_back(n); deba@2508: for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) { deba@2508: Node t = _ugraph.runningNode(e); deba@2508: if (_color_map[t] == -2) { deba@2508: heap.decrease(t, heap[t] - 1); deba@2508: } deba@2508: } deba@2508: } deba@2508: deba@2508: for (int i = order.size() - 1; i >= 0; --i) { deba@2508: std::vector forbidden(6, false); deba@2508: for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) { deba@2508: Node t = _ugraph.runningNode(e); deba@2508: if (_color_map[t] != -1) { deba@2508: forbidden[_color_map[t]] = true; deba@2508: } deba@2508: } deba@2508: for (int k = 0; k < 6; ++k) { deba@2508: if (!forbidden[k]) { deba@2508: _color_map[order[i]] = k; deba@2508: break; deba@2508: } deba@2508: } deba@2508: if (_color_map[order[i]] == -1) { deba@2508: return false; deba@2508: } deba@2508: } deba@2508: return true; deba@2508: } deba@2508: deba@2508: private: deba@2508: deba@2508: bool recolor(const Node& u, const Node& v) { deba@2508: int ucolor = _color_map[u]; deba@2508: int vcolor = _color_map[v]; deba@2508: typedef _planarity_bits::KempeFilter KempeFilter; deba@2508: KempeFilter filter(_color_map, ucolor, vcolor); deba@2508: deba@2508: typedef NodeSubUGraphAdaptor KempeUGraph; deba@2508: KempeUGraph kempe_ugraph(_ugraph, filter); deba@2508: deba@2508: std::vector comp; deba@2508: Bfs bfs(kempe_ugraph); deba@2508: bfs.init(); deba@2508: bfs.addSource(u); deba@2508: while (!bfs.emptyQueue()) { deba@2508: Node n = bfs.nextNode(); deba@2508: if (n == v) return false; deba@2508: comp.push_back(n); deba@2508: bfs.processNextNode(); deba@2508: } deba@2508: deba@2508: int scolor = ucolor + vcolor; deba@2508: for (int i = 0; i < static_cast(comp.size()); ++i) { deba@2508: _color_map[comp[i]] = scolor - _color_map[comp[i]]; deba@2508: } deba@2508: deba@2508: return true; deba@2508: } deba@2508: deba@2508: template deba@2508: void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) { deba@2508: std::vector nodes; deba@2508: nodes.reserve(4); deba@2508: deba@2508: for (Edge e = OutEdgeIt(_ugraph, node); e != INVALID; e = embedding[e]) { deba@2508: Node t = _ugraph.target(e); deba@2508: if (_color_map[t] != -1) { deba@2508: nodes.push_back(t); deba@2508: if (nodes.size() == 4) break; deba@2508: } deba@2508: } deba@2508: deba@2508: int color = _color_map[nodes[0]]; deba@2508: if (recolor(nodes[0], nodes[2])) { deba@2508: _color_map[node] = color; deba@2508: } else { deba@2508: color = _color_map[nodes[1]]; deba@2508: recolor(nodes[1], nodes[3]); deba@2508: _color_map[node] = color; deba@2508: } deba@2508: } deba@2508: deba@2508: public: deba@2508: deba@2508: /// \brief Calculates a coloring with at most five colors deba@2508: /// deba@2508: /// This function calculates a coloring with at most five deba@2508: /// colors. The wirst case time complexity of this variant is deba@2508: /// quadratic in the size of the graph. deba@2508: template deba@2508: void runFiveColoring(const EmbeddingMap& embedding) { deba@2508: deba@2508: typename UGraph::template NodeMap heap_index(_ugraph, -1); deba@2508: BucketHeap > heap(heap_index); deba@2508: deba@2508: for (NodeIt n(_ugraph); n != INVALID; ++n) { deba@2508: _color_map[n] = -2; deba@2508: heap.push(n, countOutEdges(_ugraph, n)); deba@2508: } deba@2508: deba@2508: std::vector order; deba@2508: deba@2508: while (!heap.empty()) { deba@2508: Node n = heap.top(); deba@2508: heap.pop(); deba@2508: _color_map[n] = -1; deba@2508: order.push_back(n); deba@2508: for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) { deba@2508: Node t = _ugraph.runningNode(e); deba@2508: if (_color_map[t] == -2) { deba@2508: heap.decrease(t, heap[t] - 1); deba@2508: } deba@2508: } deba@2508: } deba@2508: deba@2508: for (int i = order.size() - 1; i >= 0; --i) { deba@2508: std::vector forbidden(5, false); deba@2508: for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) { deba@2508: Node t = _ugraph.runningNode(e); deba@2508: if (_color_map[t] != -1) { deba@2508: forbidden[_color_map[t]] = true; deba@2508: } deba@2508: } deba@2508: for (int k = 0; k < 5; ++k) { deba@2508: if (!forbidden[k]) { deba@2508: _color_map[order[i]] = k; deba@2508: break; deba@2508: } deba@2508: } deba@2508: if (_color_map[order[i]] == -1) { deba@2508: kempeRecoloring(order[i], embedding); deba@2508: } deba@2508: } deba@2508: } deba@2508: deba@2508: /// \brief Calculates a coloring with at most five colors deba@2508: /// deba@2508: /// This function calculates a coloring with at most five deba@2508: /// colors. The worst case time complexity of this variant is deba@2508: /// quadratic in the size of the graph, but it most cases it does deba@2508: /// not have to use Kempe recoloring method, in this case it is deba@2508: /// equivalent with the runSixColoring() algorithm. deba@2508: /// \return %True when the graph is planar. deba@2508: bool runFiveColoring() { deba@2508: PlanarEmbedding pe(_ugraph); deba@2508: if (!pe.run()) return false; deba@2508: deba@2508: runFiveColoring(pe.embeddingMap()); deba@2508: return true; deba@2508: } deba@2508: deba@2508: private: deba@2508: deba@2508: const UGraph& _ugraph; deba@2508: IndexMap _color_map; deba@2508: Palette _palette; deba@2508: }; deba@2508: deba@2480: } deba@2480: deba@2480: #endif