RhodeCode

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

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

                       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,

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

      }

    }

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

      _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:

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

        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;