RhodeCode

        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<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);

      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;

          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);

      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);

          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 {

    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;

      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;

        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;