RhodeCode

          if (!merge_stack.empty() || n == rn) {

            break;

          }

        }

      }

      void initFace(const Node& node, NodeData& node_data,

                    const OrderMap& order_map, const OrderList& order_list) {

        int n = order_map[node];

        int rn = n + order_list.size();

        node_data[n].next = node_data[n].prev = rn;

        node_data[rn].next = node_data[rn].prev = n;

        node_data[n].visited = order_list.size();

        node_data[rn].visited = order_list.size();

      }

      bool external(const Node& node, int rorder,

                    ChildLists& child_lists, AncestorMap& ancestor_map,

                    LowMap& low_map) {

        Node child = child_lists[node].first;

        if (child != INVALID) {

          if (low_map[child] < rorder) return true;

        }

        if (ancestor_map[node] < rorder) return true;

        return false;

      }

      bool pertinent(const Node& node, const EmbedArc& embed_arc,

                     const MergeRoots& merge_roots) {

        return !merge_roots[node].empty() || embed_arc[node];

      }

    };

  }

  /// \ingroup planar

  ///

  /// \brief Planarity checking of an undirected simple graph

  ///

  /// This function implements the Boyer-Myrvold algorithm for

  /// version of the PlanarEmbedding algorithm class because neither

  template <typename GR>

  bool checkPlanarity(const GR& graph) {

    _planarity_bits::PlanarityChecking<GR> pc(graph);

    return pc.run();

  }

  /// \ingroup planar

  ///

  /// \brief Planar embedding of an undirected simple graph

  ///

  /// This class implements the Boyer-Myrvold algorithm for planar

  /// ordering of the outgoing edges of the nodes, which is a possible

  /// configuration to draw the graph in the plane. If there is not

  ///

  /// The current implementation calculates either an embedding or a

  template <typename Graph>

  class PlanarEmbedding {

  private:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

    const Graph& _graph;

    typename Graph::template ArcMap<Arc> _embedding;

    typename Graph::template EdgeMap<bool> _kuratowski;

  private:

    typedef typename Graph::template NodeMap<Arc> PredMap;

    typedef typename Graph::template EdgeMap<bool> TreeMap;

    typedef typename Graph::template NodeMap<int> OrderMap;

    typedef std::vector<Node> OrderList;

    typedef typename Graph::template NodeMap<int> LowMap;

    typedef typename Graph::template NodeMap<int> AncestorMap;

    typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;

    typedef std::vector<NodeDataNode> NodeData;

    typedef _planarity_bits::ChildListNode<Graph> ChildListNode;

    typedef typename Graph::template NodeMap<ChildListNode> ChildLists;

    typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;

    typedef typename Graph::template NodeMap<Arc> EmbedArc;

    typedef _planarity_bits::ArcListNode<Graph> ArcListNode;

    typedef typename Graph::template ArcMap<ArcListNode> ArcLists;

    typedef typename Graph::template NodeMap<bool> FlipMap;

    typedef typename Graph::template NodeMap<int> TypeMap;

    enum IsolatorNodeType {

      HIGHX = 6, LOWX = 7,

      HIGHY = 8, LOWY = 9,

      ROOT = 10, PERTINENT = 11,

      INTERNAL = 12

    };

  public:

    typedef typename Graph::template ArcMap<Arc> EmbeddingMap;

    /// \brief Constructor

    ///

    PlanarEmbedding(const Graph& graph)

      : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}

    ///

    /// algorithm does not compute a Kuratowski subdivision.

    bool run(bool kuratowski = true) {

      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;

      PredMap pred_map(_graph, INVALID);

      TreeMap tree_map(_graph, false);

      OrderMap order_map(_graph, -1);

      OrderList order_list;

      AncestorMap ancestor_map(_graph, -1);

      LowMap low_map(_graph, -1);

      Visitor visitor(_graph, pred_map, tree_map,

                      order_map, order_list, ancestor_map, low_map);

      DfsVisit<Graph, Visitor> visit(_graph, visitor);

      visit.run();

      ChildLists child_lists(_graph);

      createChildLists(tree_map, order_map, low_map, child_lists);

      NodeData node_data(2 * order_list.size());

      EmbedArc embed_arc(_graph, INVALID);

      MergeRoots merge_roots(_graph);

      ArcLists arc_lists(_graph);

      FlipMap flip_map(_graph, false);

      for (int i = order_list.size() - 1; i >= 0; --i) {

        Node node = order_list[i];

        node_data[i].first = INVALID;

        Node source = node;

        for (OutArcIt e(_graph, node); e != INVALID; ++e) {

          Node target = _graph.target(e);

          if (order_map[source] < order_map[target] && tree_map[e]) {

            initFace(target, arc_lists, node_data,

                     pred_map, order_map, order_list);

          }

        }

        for (OutArcIt e(_graph, node); e != INVALID; ++e) {

          Node target = _graph.target(e);

          if (order_map[source] < order_map[target] && !tree_map[e]) {

            embed_arc[target] = e;

            walkUp(target, source, i, pred_map, low_map,

                   order_map, order_list, node_data, merge_roots);

          }

        }

        for (typename MergeRoots::Value::iterator it =

               merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {

          int rn = *it;

          walkDown(rn, i, node_data, arc_lists, flip_map, order_list,

                   child_lists, ancestor_map, low_map, embed_arc, merge_roots);

        }

        merge_roots[node].clear();

        for (OutArcIt e(_graph, node); e != INVALID; ++e) {

          Node target = _graph.target(e);

          if (order_map[source] < order_map[target] && !tree_map[e]) {

            if (embed_arc[target] != INVALID) {

              if (kuratowski) {

                isolateKuratowski(e, node_data, arc_lists, flip_map,

                                  order_map, order_list, pred_map, child_lists,

                                  ancestor_map, low_map,

                                  embed_arc, merge_roots);

              }

              return false;

            }

          }

        }

      }

      for (int i = 0; i < int(order_list.size()); ++i) {

        mergeRemainingFaces(order_list[i], node_data, order_list, order_map,

                            child_lists, arc_lists);

        storeEmbedding(order_list[i], node_data, order_map, pred_map,

                       arc_lists, flip_map);

      }

      return true;

    }

    ///

    /// possible to query the cyclic order of the outgoing arcs from

    /// a node.

    Arc next(const Arc& arc) const {

      return _embedding[arc];

    }

    ///

    const EmbeddingMap& embeddingMap() const {

      return _embedding;

    }

    ///

      return _kuratowski[edge];

    }

  private:

    void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,

                          const LowMap& low_map, ChildLists& child_lists) {

      for (NodeIt n(_graph); n != INVALID; ++n) {

        Node source = n;

        std::vector<Node> targets;

        for (OutArcIt e(_graph, n); e != INVALID; ++e) {

          Node target = _graph.target(e);

          if (order_map[source] < order_map[target] && tree_map[e]) {

            targets.push_back(target);

          }

        }

        if (targets.size() == 0) {

          child_lists[source].first = INVALID;

        } else if (targets.size() == 1) {

          child_lists[source].first = targets[0];

          child_lists[targets[0]].prev = INVALID;

          child_lists[targets[0]].next = INVALID;

        } else {

          radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));

          for (int i = 1; i < int(targets.size()); ++i) {

            child_lists[targets[i]].prev = targets[i - 1];

            child_lists[targets[i - 1]].next = targets[i];

          }

          child_lists[targets.back()].next = INVALID;

          child_lists[targets.front()].prev = INVALID;

          child_lists[source].first = targets.front();

        }

      }

    }

    void walkUp(const Node& node, Node root, int rorder,

                const PredMap& pred_map, const LowMap& low_map,

                const OrderMap& order_map, const OrderList& order_list,

                NodeData& node_data, MergeRoots& merge_roots) {

      int na, nb;

      bool da, db;

      na = nb = order_map[node];

          embedding[graph.oppositeArc(ce)] = oppe;

          typename Graph::Arc pn = ce, p = oppe;

          e = embedding[graph.oppositeArc(oppe)];

          while (graph.target(e) != s) {

            typename Graph::Arc n =

              graph.direct(graph.addEdge(s, graph.source(e)), true);

            embedding[n] = pn;

            embedding[graph.oppositeArc(n)] = e;

            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);

            pn = n;

            p = e;

            e = embedding[graph.oppositeArc(e)];

          }

          embedding[graph.oppositeArc(e)] = pn;

          pn = graph.oppositeArc(ce), p = mine;

          e = embedding[graph.oppositeArc(mine)];

          while (graph.target(e) != t) {

            typename Graph::Arc n =

              graph.direct(graph.addEdge(t, graph.source(e)), true);

            embedding[n] = pn;

            embedding[graph.oppositeArc(n)] = e;

            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);

            pn = n;

            p = e;

            e = embedding[graph.oppositeArc(e)];

          }

          embedding[graph.oppositeArc(e)] = pn;

        }

      }

    }

  }

  /// \ingroup planar

  ///

  /// \brief Schnyder's planar drawing algorithm

  ///

  /// The planar drawing algorithm calculates positions for the nodes

  /// each other.

  ///

  /// The time complexity of the algorithm is O(n).

  template <typename Graph>

  class PlanarDrawing {

  public:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

    typedef dim2::Point<int> Point;

    typedef typename Graph::template NodeMap<Point> PointMap;

    /// \brief Constructor

    ///

    /// Constructor

    PlanarDrawing(const Graph& graph)

      : _graph(graph), _point_map(graph) {}

  private:

    template <typename AuxGraph, typename AuxEmbeddingMap>

    void drawing(const AuxGraph& graph,

                 const AuxEmbeddingMap& next,

                 PointMap& point_map) {

      TEMPLATE_GRAPH_TYPEDEFS(AuxGraph);

      typename AuxGraph::template ArcMap<Arc> prev(graph);

      for (NodeIt n(graph); n != INVALID; ++n) {

        Arc e = OutArcIt(graph, n);

        Arc p = e, l = e;

        e = next[e];

        while (e != l) {

          prev[e] = p;

          p = e;

          e = next[e];

        }

        prev[e] = p;

      }

      Node anode, bnode, cnode;

      {

        Arc e = ArcIt(graph);

        anode = graph.source(e);

        bnode = graph.target(e);

        cnode = graph.target(next[graph.oppositeArc(e)]);

      }

      IterableBoolMap<AuxGraph, Node> proper(graph, false);

      typename AuxGraph::template NodeMap<int> conn(graph, -1);

      conn[anode] = conn[bnode] = -2;

      {

        for (OutArcIt e(graph, anode); e != INVALID; ++e) {

          Node m = graph.target(e);

          if (conn[m] == -1) {

            conn[m] = 1;

          }

        }

        conn[cnode] = 2;

          if (bpred[graph.target(e)] == n) {

            btree[n] += btree[graph.target(e)];

          }

        }

      }

      typename AuxGraph::template NodeMap<int> apath(graph, 0);

      apath[bnode] = apath[cnode] = 1;

      typename AuxGraph::template NodeMap<int> apath_btree(graph, 0);

      apath_btree[bnode] = btree[bnode];

      for (int i = 1; i < int(aorder.size()); ++i) {

        Node n = aorder[i];

        apath[n] = apath[apred[n]] + 1;

        apath_btree[n] = btree[n] + apath_btree[apred[n]];

      }

      typename AuxGraph::template NodeMap<int> bpath_atree(graph, 0);

      bpath_atree[anode] = atree[anode];

      for (int i = 1; i < int(border.size()); ++i) {

        Node n = border[i];

        bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];

      }

      typename AuxGraph::template NodeMap<int> cpath(graph, 0);

      cpath[anode] = cpath[bnode] = 1;

      typename AuxGraph::template NodeMap<int> cpath_atree(graph, 0);

      cpath_atree[anode] = atree[anode];

      typename AuxGraph::template NodeMap<int> cpath_btree(graph, 0);

      cpath_btree[bnode] = btree[bnode];

      for (int i = 1; i < int(corder.size()); ++i) {

        Node n = corder[i];

        cpath[n] = cpath[cpred[n]] + 1;

        cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];

        cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];

      }

      typename AuxGraph::template NodeMap<int> third(graph);

      for (NodeIt n(graph); n != INVALID; ++n) {

        point_map[n].x =

          bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;

        point_map[n].y =

          cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;

      }

    }

  public:

    ///

    bool run() {

      PlanarEmbedding<Graph> pe(_graph);

      if (!pe.run()) return false;

      run(pe);

      return true;

    }

    /// combinatorical embedding

    ///

    template <typename EmbeddingMap>

    void run(const EmbeddingMap& embedding) {

      typedef SmartEdgeSet<Graph> AuxGraph;

      if (3 * countNodes(_graph) - 6 == countEdges(_graph)) {

        drawing(_graph, embedding, _point_map);

        return;

      }

      AuxGraph aux_graph(_graph);

      typename AuxGraph::template ArcMap<typename AuxGraph::Arc>

        aux_embedding(aux_graph);

      {

        typename Graph::template EdgeMap<typename AuxGraph::Edge>

          ref(_graph);

        for (EdgeIt e(_graph); e != INVALID; ++e) {

          ref[e] = aux_graph.addEdge(_graph.u(e), _graph.v(e));

        }

        for (EdgeIt e(_graph); e != INVALID; ++e) {

          Arc ee = embedding[_graph.direct(e, true)];

          aux_embedding[aux_graph.direct(ref[e], true)] =

            aux_graph.direct(ref[ee], _graph.direction(ee));

          ee = embedding[_graph.direct(e, false)];

          aux_embedding[aux_graph.direct(ref[e], false)] =

            aux_graph.direct(ref[ee], _graph.direction(ee));

        }

      }

      _planarity_bits::makeConnected(aux_graph, aux_embedding);

      _planarity_bits::makeBiNodeConnected(aux_graph, aux_embedding);

      _planarity_bits::makeMaxPlanar(aux_graph, aux_embedding);

      drawing(aux_graph, aux_embedding, _point_map);

    }

    /// \brief The coordinate of the given node

    ///

    Point operator[](const Node& node) const {

      return _point_map[node];

    }

    ///

    const PointMap& coords() const {

      return _point_map;

    }

  private:

    const Graph& _graph;

    PointMap _point_map;

  };

  namespace _planarity_bits {

    template <typename ColorMap>

    class KempeFilter {

    public:

      typedef typename ColorMap::Key Key;

      typedef bool Value;

      KempeFilter(const ColorMap& color_map,

                  const typename ColorMap::Value& first,

                  const typename ColorMap::Value& second)

        : _color_map(color_map), _first(first), _second(second) {}

      Value operator[](const Key& key) const {

        return _color_map[key] == _first || _color_map[key] == _second;

      }

    private:

      const ColorMap& _color_map;

      typename ColorMap::Value _first, _second;

    };

  }

  /// \ingroup planar

  ///

  /// \brief Coloring planar graphs

  ///

  /// The graph coloring problem is the coloring of the graph nodes

  /// time algorithm for four coloring, but it could not be used to

  /// quadratic worst case time complexity. The two coloring (if

  /// possible) is solvable with a graph search algorithm and it is

  /// implemented in \ref bipartitePartitions() function in LEMON. To

  ///

  /// This class contains member functions for calculate colorings

  /// with five and six colors. The six coloring algorithm is a simple

  /// greedy coloring on the backward minimum outgoing order of nodes.

  /// guarantees that when a node is chosen for coloring it has at

  /// most five already colored adjacents. The five coloring algorithm

  /// use the same method, but if the greedy approach fails to color

  /// with five colors, i.e. the node has five already different

  /// colored neighbours, it swaps the colors in one of the connected

  /// two colored sets with the Kempe recoloring method.

  template <typename Graph>

  class PlanarColoring {

  public:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

    typedef typename Graph::template NodeMap<int> IndexMap;

    typedef ComposeMap<Palette, IndexMap> ColorMap;

    /// \brief Constructor

    ///

    PlanarColoring(const Graph& graph)

      : _graph(graph), _color_map(graph), _palette(0) {

      _palette.add(Color(1,0,0));

      _palette.add(Color(0,1,0));

      _palette.add(Color(0,0,1));

      _palette.add(Color(1,1,0));

      _palette.add(Color(1,0,1));

      _palette.add(Color(0,1,1));

    }

    ///

    IndexMap colorIndexMap() const {

      return _color_map;

    }

    ///

    ColorMap colorMap() const {

      return composeMap(_palette, _color_map);

    }

    ///

    int colorIndex(const Node& node) const {

      return _color_map[node];

    }

    ///

    Color color(const Node& node) const {

      return _palette[_color_map[node]];

    }

    ///

    /// This function calculates a coloring with at most six colors. The time

    /// complexity of this variant is linear in the size of the graph.

    bool runSixColoring() {

      typename Graph::template NodeMap<int> heap_index(_graph, -1);

      BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);

      for (NodeIt n(_graph); n != INVALID; ++n) {

        _color_map[n] = -2;

        heap.push(n, countOutArcs(_graph, n));

      }

      std::vector<Node> order;

      while (!heap.empty()) {

        Node n = heap.top();

        heap.pop();

        _color_map[n] = -1;

        order.push_back(n);

        for (OutArcIt e(_graph, n); e != INVALID; ++e) {

          Node t = _graph.runningNode(e);

          if (_color_map[t] == -2) {

            heap.decrease(t, heap[t] - 1);

          }

        }

      }

      for (int i = order.size() - 1; i >= 0; --i) {

        std::vector<bool> forbidden(6, false);

        for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {

          Node t = _graph.runningNode(e);

          if (_color_map[t] != -1) {

            forbidden[_color_map[t]] = true;

          }

        }

               for (int k = 0; k < 6; ++k) {

          if (!forbidden[k]) {

            _color_map[order[i]] = k;

            break;

          }

        }

        if (_color_map[order[i]] == -1) {

          return false;

        }

      }

      return true;

    }

  private:

      typedef FilterNodes<const Graph, const KempeFilter> KempeGraph;

      KempeGraph kempe_graph(_graph, filter);

      std::vector<Node> comp;

      Bfs<KempeGraph> bfs(kempe_graph);

      bfs.init();

      bfs.addSource(u);

      while (!bfs.emptyQueue()) {

        Node n = bfs.nextNode();

        if (n == v) return false;

        comp.push_back(n);

        bfs.processNextNode();

      }

      int scolor = ucolor + vcolor;

      for (int i = 0; i < static_cast<int>(comp.size()); ++i) {

        _color_map[comp[i]] = scolor - _color_map[comp[i]];

      }

      return true;

    }

    template <typename EmbeddingMap>

    void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) {

      std::vector<Node> nodes;

      nodes.reserve(4);

      for (Arc e = OutArcIt(_graph, node); e != INVALID; e = embedding[e]) {

        Node t = _graph.target(e);

        if (_color_map[t] != -1) {

          nodes.push_back(t);

          if (nodes.size() == 4) break;

        }

      }

      int color = _color_map[nodes[0]];

      if (recolor(nodes[0], nodes[2])) {

        _color_map[node] = color;

      } else {

        color = _color_map[nodes[1]];

        recolor(nodes[1], nodes[3]);

        _color_map[node] = color;

      }

    }

  public:

    ///

    /// This function calculates a coloring with at most five

    /// colors. The worst case time complexity of this variant is

    /// quadratic in the size of the graph.

    template <typename EmbeddingMap>

    void runFiveColoring(const EmbeddingMap& embedding) {

      typename Graph::template NodeMap<int> heap_index(_graph, -1);

      BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);

      for (NodeIt n(_graph); n != INVALID; ++n) {

        _color_map[n] = -2;

        heap.push(n, countOutArcs(_graph, n));

      }

      std::vector<Node> order;

      while (!heap.empty()) {

        Node n = heap.top();

        heap.pop();

        _color_map[n] = -1;

        order.push_back(n);

        for (OutArcIt e(_graph, n); e != INVALID; ++e) {

          Node t = _graph.runningNode(e);

          if (_color_map[t] == -2) {

            heap.decrease(t, heap[t] - 1);

          }

        }

      }

      for (int i = order.size() - 1; i >= 0; --i) {

        std::vector<bool> forbidden(5, false);

        for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {

          Node t = _graph.runningNode(e);

          if (_color_map[t] != -1) {

            forbidden[_color_map[t]] = true;

          }

        }

        for (int k = 0; k < 5; ++k) {

          if (!forbidden[k]) {

            _color_map[order[i]] = k;

            break;

          }

        }

        if (_color_map[order[i]] == -1) {

          kempeRecoloring(order[i], embedding);

        }

      }

    }

    ///

    /// This function calculates a coloring with at most five

    /// colors. The worst case time complexity of this variant is

    /// quadratic in the size of the graph.

    bool runFiveColoring() {

      PlanarEmbedding<Graph> pe(_graph);

      if (!pe.run()) return false;

      runFiveColoring(pe.embeddingMap());

      return true;

    }

  private:

    const Graph& _graph;

    IndexMap _color_map;

    Palette _palette;

  };

}

#endif