RhodeCode

      int prev, next;

      int visited;

      typename Graph::Arc first;

      bool inverted;

    };

    template <typename Graph>

    struct NodeDataNode<Graph, false> {

      int prev, next;

      int visited;

    };

    template <typename Graph>

    struct ChildListNode {

      typedef typename Graph::Node Node;

      Node first;

      Node prev, next;

    };

    template <typename Graph>

    struct ArcListNode {

      typename Graph::Arc prev, next;

    };

  template <typename Graph>

  class PlanarityChecking {

  private:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

    const Graph& _graph;

  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<bool> EmbedArc;

  public:

    PlanarityChecking(const Graph& graph) : _graph(graph) {}

    bool run() {

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

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

        Node node = order_list[i];

        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, node_data, 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] = true;

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

                   order_map, order_list, node_data, merge_roots);

          }

        }

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

          int rn = *it;

          walkDown(rn, i, node_data, 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]) {

              return false;

            }

          }

        }

      }

      return true;

    }

  private:

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

                          const LowMap& low_map, ChildLists& child_lists) {

            // Embedding arc into external face

            if (rd) node_data[rn].next = n; else node_data[rn].prev = n;

            if (d) node_data[n].prev = rn; else node_data[n].next = rn;

            pn = rn;

            embed_arc[order_list[n]] = false;

          }

          if (!merge_roots[node].empty()) {

            bool d = pn == node_data[n].prev;

            merge_stack.push_back(std::make_pair(n, d));

            int rn = merge_roots[node].front();

            int xn = node_data[rn].next;

            Node xnode = order_list[xn];

            int yn = node_data[rn].prev;

            Node ynode = order_list[yn];

            bool rd;

              rd = true;

            } else if (!external(ynode, rorder, child_lists,

                                 ancestor_map, low_map)) {

              rd = false;

            } else if (pertinent(xnode, embed_arc, merge_roots)) {

              rd = true;

            } else {

              rd = false;

            }

            merge_stack.push_back(std::make_pair(rn, rd));

            pn = rn;

            n = rd ? xn : yn;

          } else if (!external(node, rorder, child_lists,

                               ancestor_map, low_map)) {

            int nn = (node_data[n].next != pn ?

                      node_data[n].next : node_data[n].prev);

            bool nd = n == node_data[nn].prev;

            if (nd) node_data[nn].prev = pn;

            else node_data[nn].next = pn;

    }

    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 Planar embedding of an undirected simple graph

  ///

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

  /// embedding of an undirected graph. The planar embedding is an

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

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

  /// such ordering then the graph contains a \f$ K_5 \f$ (full graph

  /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on

  /// 3 ANode and 3 BNode) subdivision.

  ///

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

  /// Kuratowski subdivision. The running time of the algorithm is 

  /// \f$ O(n) \f$.

  template <typename Graph>

  class PlanarEmbedding {

  private:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

    const Graph& _graph;

    typename Graph::template ArcMap<Arc> _embedding;

      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;

    }

    /// \brief Gives back the successor of an arc

    ///

    /// Gives back the successor of an arc. This function makes

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

    /// a node.

    Arc next(const Arc& arc) const {

      return _embedding[arc];

    }

    /// \brief Gives back the calculated embedding map

    ///

    /// The returned map contains the successor of each arc in the

    /// graph.

      return _embedding;

    }

    /// \brief Gives back true if the undirected arc is in the

    /// kuratowski subdivision

    ///

    /// Gives back true if the undirected arc is in the kuratowski

    /// subdivision

    /// \note The \c run() had to be called with true value.

    bool kuratowski(const Edge& edge) {

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

}

void checkColoring(const Graph& graph, PC& pc, int num) {

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

    check(pc.colorIndex(n) >= 0 && pc.colorIndex(n) < num,

          "Wrong coloring");

  }

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

    check(pc.colorIndex(graph.u(e)) != pc.colorIndex(graph.v(e)),

          "Wrong coloring");

  }

}

int main() {

  for (int i = 0; i < lgfn; ++i) {

    std::istringstream lgfs(lgf[i]);

    SmartGraph graph;

    graphReader(graph, lgfs).run();

    check(simpleGraph(graph), "Test graphs must be simple");

    PE pe(graph);

      checkEmbedding(graph, pe);

      PlanarDrawing<Graph> pd(graph);

      checkDrawing(graph, pd);

      PlanarColoring<Graph> pc(graph);

      checkColoring(graph, pc, 5);

    } else {

      checkKuratowski(graph, pe);

    }

  }

  return 0;

}