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