RhodeCode

  /// planarity checking of an undirected simple graph. It is a simplified

  /// the embedding nor the Kuratowski subdivisons are computed.

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

  /// such ordering then the graph contains a K<sub>5</sub> (full graph

  /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on

  /// 3 Red and 3 Blue nodes) subdivision.

  /// Kuratowski subdivision. The running time of the algorithm is O(n).

  ///

  /// \see PlanarDrawing, checkPlanarity()

    /// \brief The map type for storing the embedding

    ///

    /// The map type for storing the embedding.

    /// \see embeddingMap()

    /// Constructor.

    /// \pre The graph must be simple, i.e. it should not

    /// contain parallel or loop arcs.

    /// \brief Run the algorithm.

    /// This function runs the algorithm.

    /// \param kuratowski If this parameter is set to \c false, then the

    /// \return \c true if the graph is planar.

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

    /// This function gives back the successor of an arc. It makes

    /// \brief Give back the calculated embedding map

    /// This function gives back the calculated embedding map, which

    /// contains the successor of each arc in the cyclic order of the

    /// outgoing arcs of its source node.

    /// \brief Give back \c true if the given edge is in the Kuratowski

    /// subdivision

    /// This function gives back \c true if the given edge is in the found

    /// Kuratowski subdivision.

    /// \pre The \c run() function must be called with \c true parameter

    /// before using this function.

    bool kuratowski(const Edge& edge) const {

  /// in the plane. These coordinates satisfy that if the edges are

  /// represented with straight lines, then they will not intersect

  /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,

  /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.

  ///

  /// \see PlanarEmbedding

    /// \brief The point type for storing coordinates

    /// \brief The map type for storing the coordinates of the nodes

    /// \pre The graph must be simple, i.e. it should not

    /// contain parallel or loop arcs.

    /// \brief Calculate the node positions

    /// This function calculates the node positions on the plane.

    /// \return \c true if the graph is planar.

    /// \brief Calculate the node positions according to a

    /// This function calculates the node positions on the plane.

    /// The given \c embedding map should contain a valid combinatorical

    /// embedding, i.e. a valid cyclic order of the arcs.

    /// It can be computed using PlanarEmbedding.

    /// This function returns the coordinate of the given node.

    /// \brief Return the grid embedding in a node map

    /// This function returns the grid embedding in a node map of

    /// \c dim2::Point<int> coordinates.

  /// so that there are no adjacent nodes with the same color. The

  /// planar graphs can always be colored with four colors, which is

  /// proved by Appel and Haken. Their proofs provide a quadratic

  /// implement an efficient algorithm. The five and six coloring can be

  /// made in linear time, but in this class, the five coloring has

  /// decide whether a planar graph is three colorable is NP-complete.

  /// This order can be computed by selecting the node with least

  /// outgoing arcs to unprocessed nodes in each phase. This order

    /// \brief The map type for storing color indices

    /// \brief The map type for storing colors

    ///

    /// The map type for storing colors.

    /// \see Palette, Color

    /// Constructor.

    /// \pre The graph must be simple, i.e. it should not

    /// contain parallel or loop arcs.

    /// \brief Return the node map of color indices

    /// This function returns the node map of color indices. The values are

    /// in the range \c [0..4] or \c [0..5] according to the coloring method.

    /// \brief Return the node map of colors

    /// This function returns the node map of colors. The values are among

    /// five or six distinct \ref lemon::Color "colors".

    /// \brief Return the color index of the node

    /// This function returns the color index of the given node. The value is

    /// in the range \c [0..4] or \c [0..5] according to the coloring method.

    /// \brief Return the color of the node

    /// This function returns the color of the given node. The value is among

    /// five or six distinct \ref lemon::Color "colors".

    /// \brief Calculate a coloring with at most six colors

    /// \return \c true if the algorithm could color the graph with six colors.

    /// If the algorithm fails, then the graph is not planar.

    /// \note This function can return \c true if the graph is not

    /// planar, but it can be colored with at most six colors.

    /// \brief Calculate a coloring with at most five colors

    /// \param embedding This map should contain a valid combinatorical

    /// embedding, i.e. a valid cyclic order of the arcs.

    /// It can be computed using PlanarEmbedding.

    /// \brief Calculate a coloring with at most five colors

    /// \return \c true if the graph is planar.