RhodeCode

          }

        }

      }

      void backtrack(const Arc& arc) {

        Node source = _graph.source(arc);

        Node target = _graph.target(arc);

        if (_low_map[source] > _low_map[target]) {

          _low_map[source] = _low_map[target];

        }

      }

      const Graph& _graph;

      PredMap& _pred_map;

      TreeMap& _tree_map;

      OrderMap& _order_map;

      OrderList& _order_list;

      AncestorMap& _ancestor_map;

      LowMap& _low_map;

    };

    template <typename Graph, bool embedding = true>

    struct NodeDataNode {

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

      MergeRoots merge_roots(_graph);

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

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

              if (child_lists[child].next != INVALID) {

                child_lists[child_lists[child].next].prev =

                  child_lists[child].prev;

              }

              // Merging external faces

              {

                int en = cn;

                cn = cd ? node_data[cn].prev : node_data[cn].next;

                cd = node_data[cn].next == en;

              }

              if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;

              if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;

            }

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

            if (node_data[n].prev == node_data[n].next &&

                node_data[n].inverted) {

              d = !d;

            }

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

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

            else node_data[pn].next = nn;

            node_data[nn].inverted =

              (node_data[nn].prev == node_data[nn].next && nd != rd);

            n = nn;

          }

          else break;

        }

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

    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;

               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;

    }

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

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

        }

      }

    }

      check(pd[m] != pd[n], "Two nodes with identical coordinates");

    }

  }

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

    for (Graph::EdgeIt f(e); f != e; ++f) {

      Point<int> e1 = pd[graph.u(e)];

      Point<int> e2 = pd[graph.v(e)];

      Point<int> f1 = pd[graph.u(f)];

      Point<int> f2 = pd[graph.v(f)];

      if (graph.u(e) == graph.u(f)) {

        check(!collinear(e1, e2, f2), "Wrong drawing");

      } else if (graph.u(e) == graph.v(f)) {

        check(!collinear(e1, e2, f1), "Wrong drawing");

      } else if (graph.v(e) == graph.u(f)) {

        check(!collinear(e2, e1, f2), "Wrong drawing");

      } else if (graph.v(e) == graph.v(f)) {

        check(!collinear(e2, e1, f1), "Wrong drawing");

      } else {

        check(!intersect(e1, e2, f1, f2), "Wrong drawing");

      }

    }

  }

}

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;

}