RhodeCode

    template <typename Graph>

    struct ArcListNode {

      typename Graph::Arc prev, next;

    };

  template <typename Graph>

  class PlanarityChecking {

  private:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

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

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

            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;

                   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

    }

    /// \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

    ///

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

    }

  }