RhodeCode

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

        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;

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

      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.

  ///

    ///

    /// 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];

    }

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;

}