author Peter Kovacs Thu, 11 Feb 2010 07:40:29 +0100 changeset 828 5fd7fafc4470 parent 827 8131c2b9f59a child 829 7762cab7f372
Doc improvements for planarity related tools (#62)
 lemon/planarity.h file | annotate | diff | comparison | revisions
1.1 --- a/lemon/planarity.h	Thu Feb 11 07:39:57 2010 +0100
1.2 +++ b/lemon/planarity.h	Thu Feb 11 07:40:29 2010 +0100
1.3 @@ -518,9 +518,9 @@
1.4    /// \brief Planarity checking of an undirected simple graph
1.5    ///
1.6    /// This function implements the Boyer-Myrvold algorithm for
1.7 -  /// planarity checking of an undirected graph. It is a simplified
1.8 +  /// planarity checking of an undirected simple graph. It is a simplified
1.9    /// version of the PlanarEmbedding algorithm class because neither
1.10 -  /// the embedding nor the kuratowski subdivisons are not computed.
1.11 +  /// the embedding nor the Kuratowski subdivisons are computed.
1.12    template <typename GR>
1.13    bool checkPlanarity(const GR& graph) {
1.14      _planarity_bits::PlanarityChecking<GR> pc(graph);
1.15 @@ -532,16 +532,17 @@
1.16    /// \brief Planar embedding of an undirected simple graph
1.17    ///
1.18    /// This class implements the Boyer-Myrvold algorithm for planar
1.19 -  /// embedding of an undirected graph. The planar embedding is an
1.20 +  /// embedding of an undirected simple graph. The planar embedding is an
1.21    /// ordering of the outgoing edges of the nodes, which is a possible
1.22    /// configuration to draw the graph in the plane. If there is not
1.23 -  /// such ordering then the graph contains a \f$K_5 \f$ (full graph
1.24 -  /// with 5 nodes) or a \f$K_{3,3} \f$ (complete bipartite graph on
1.25 -  /// 3 ANode and 3 BNode) subdivision.
1.26 +  /// such ordering then the graph contains a K<sub>5</sub> (full graph
1.27 +  /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
1.28 +  /// 3 Red and 3 Blue nodes) subdivision.
1.29    ///
1.30    /// The current implementation calculates either an embedding or a
1.31 -  /// Kuratowski subdivision. The running time of the algorithm is
1.32 -  /// \f$O(n) \f$.
1.33 +  /// Kuratowski subdivision. The running time of the algorithm is O(n).
1.34 +  ///
1.35 +  /// \see PlanarDrawing, checkPlanarity()
1.36    template <typename Graph>
1.37    class PlanarEmbedding {
1.38    private:
1.39 @@ -591,22 +592,26 @@
1.41    public:
1.43 -    /// \brief The map for store of embedding
1.44 +    /// \brief The map type for storing the embedding
1.45 +    ///
1.46 +    /// The map type for storing the embedding.
1.47 +    /// \see embeddingMap()
1.48      typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
1.50      /// \brief Constructor
1.51      ///
1.52 -    /// \note The graph should be simple, i.e. parallel and loop arc
1.53 -    /// free.
1.54 +    /// Constructor.
1.55 +    /// \pre The graph must be simple, i.e. it should not
1.56 +    /// contain parallel or loop arcs.
1.57      PlanarEmbedding(const Graph& graph)
1.58        : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
1.60 -    /// \brief Runs the algorithm.
1.61 +    /// \brief Run the algorithm.
1.62      ///
1.63 -    /// Runs the algorithm.
1.64 -    /// \param kuratowski If the parameter is false, then the
1.65 +    /// This function runs the algorithm.
1.66 +    /// \param kuratowski If this parameter is set to \c false, then the
1.67      /// algorithm does not compute a Kuratowski subdivision.
1.68 -    ///\return %True when the graph is planar.
1.69 +    /// \return \c true if the graph is planar.
1.70      bool run(bool kuratowski = true) {
1.71        typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
1.73 @@ -699,30 +704,32 @@
1.74        return true;
1.75      }
1.77 -    /// \brief Gives back the successor of an arc
1.78 +    /// \brief Give back the successor of an arc
1.79      ///
1.80 -    /// Gives back the successor of an arc. This function makes
1.81 +    /// This function gives back the successor of an arc. It makes
1.82      /// possible to query the cyclic order of the outgoing arcs from
1.83      /// a node.
1.84      Arc next(const Arc& arc) const {
1.85        return _embedding[arc];
1.86      }
1.88 -    /// \brief Gives back the calculated embedding map
1.89 +    /// \brief Give back the calculated embedding map
1.90      ///
1.91 -    /// The returned map contains the successor of each arc in the
1.92 -    /// graph.
1.93 +    /// This function gives back the calculated embedding map, which
1.94 +    /// contains the successor of each arc in the cyclic order of the
1.95 +    /// outgoing arcs of its source node.
1.96      const EmbeddingMap& embeddingMap() const {
1.97        return _embedding;
1.98      }
1.100 -    /// \brief Gives back true if the undirected arc is in the
1.101 -    /// kuratowski subdivision
1.102 +    /// \brief Give back \c true if the given edge is in the Kuratowski
1.103 +    /// subdivision
1.104      ///
1.105 -    /// Gives back true if the undirected arc is in the kuratowski
1.106 -    /// subdivision
1.107 -    /// \note The \c run() had to be called with true value.
1.108 -    bool kuratowski(const Edge& edge) {
1.109 +    /// This function gives back \c true if the given edge is in the found
1.110 +    /// Kuratowski subdivision.
1.111 +    /// \pre The \c run() function must be called with \c true parameter
1.112 +    /// before using this function.
1.113 +    bool kuratowski(const Edge& edge) const {
1.114        return _kuratowski[edge];
1.117 @@ -2059,29 +2066,32 @@
1.118    /// \brief Schnyder's planar drawing algorithm
1.119    ///
1.120    /// The planar drawing algorithm calculates positions for the nodes
1.121 -  /// in the plane which coordinates satisfy that if the arcs are
1.122 -  /// represented with straight lines then they will not intersect
1.123 +  /// in the plane. These coordinates satisfy that if the edges are
1.124 +  /// represented with straight lines, then they will not intersect
1.125    /// each other.
1.126    ///
1.127 -  /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
1.128 -  /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square.
1.129 +  /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
1.130 +  /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
1.131    /// The time complexity of the algorithm is O(n).
1.132 +  ///
1.133 +  /// \see PlanarEmbedding
1.134    template <typename Graph>
1.135    class PlanarDrawing {
1.136    public:
1.138      TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.140 -    /// \brief The point type for store coordinates
1.141 +    /// \brief The point type for storing coordinates
1.142      typedef dim2::Point<int> Point;
1.143 -    /// \brief The map type for store coordinates
1.144 +    /// \brief The map type for storing the coordinates of the nodes
1.145      typedef typename Graph::template NodeMap<Point> PointMap;
1.148      /// \brief Constructor
1.149      ///
1.150      /// Constructor
1.151 -    /// \pre The graph should be simple, i.e. loop and parallel arc free.
1.152 +    /// \pre The graph must be simple, i.e. it should not
1.153 +    /// contain parallel or loop arcs.
1.154      PlanarDrawing(const Graph& graph)
1.155        : _graph(graph), _point_map(graph) {}
1.157 @@ -2366,10 +2376,10 @@
1.159    public:
1.161 -    /// \brief Calculates the node positions
1.162 +    /// \brief Calculate the node positions
1.163      ///
1.164 -    /// This function calculates the node positions.
1.165 -    /// \return %True if the graph is planar.
1.166 +    /// This function calculates the node positions on the plane.
1.167 +    /// \return \c true if the graph is planar.
1.168      bool run() {
1.169        PlanarEmbedding<Graph> pe(_graph);
1.170        if (!pe.run()) return false;
1.171 @@ -2378,12 +2388,13 @@
1.172        return true;
1.175 -    /// \brief Calculates the node positions according to a
1.176 +    /// \brief Calculate the node positions according to a
1.177      /// combinatorical embedding
1.178      ///
1.179 -    /// This function calculates the node locations. The \c embedding
1.180 -    /// parameter should contain a valid combinatorical embedding, i.e.
1.181 -    /// a valid cyclic order of the arcs.
1.182 +    /// This function calculates the node positions on the plane.
1.183 +    /// The given \c embedding map should contain a valid combinatorical
1.184 +    /// embedding, i.e. a valid cyclic order of the arcs.
1.185 +    /// It can be computed using PlanarEmbedding.
1.186      template <typename EmbeddingMap>
1.187      void run(const EmbeddingMap& embedding) {
1.188        typedef SmartEdgeSet<Graph> AuxGraph;
1.189 @@ -2423,14 +2434,15 @@
1.191      /// \brief The coordinate of the given node
1.192      ///
1.193 -    /// The coordinate of the given node.
1.194 +    /// This function returns the coordinate of the given node.
1.195      Point operator[](const Node& node) const {
1.196        return _point_map[node];
1.199 -    /// \brief Returns the grid embedding in a \e NodeMap.
1.200 +    /// \brief Return the grid embedding in a node map
1.201      ///
1.202 -    /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
1.203 +    /// This function returns the grid embedding in a node map of
1.204 +    /// \c dim2::Point<int> coordinates.
1.205      const PointMap& coords() const {
1.206        return _point_map;
1.208 @@ -2470,23 +2482,22 @@
1.209    /// \brief Coloring planar graphs
1.210    ///
1.211    /// The graph coloring problem is the coloring of the graph nodes
1.212 -  /// that there are not adjacent nodes with the same color. The
1.213 -  /// planar graphs can be always colored with four colors, it is
1.214 -  /// proved by Appel and Haken and their proofs provide a quadratic
1.215 +  /// so that there are no adjacent nodes with the same color. The
1.216 +  /// planar graphs can always be colored with four colors, which is
1.217 +  /// proved by Appel and Haken. Their proofs provide a quadratic
1.218    /// time algorithm for four coloring, but it could not be used to
1.219 -  /// implement efficient algorithm. The five and six coloring can be
1.220 -  /// made in linear time, but in this class the five coloring has
1.221 +  /// implement an efficient algorithm. The five and six coloring can be
1.222 +  /// made in linear time, but in this class, the five coloring has
1.223    /// quadratic worst case time complexity. The two coloring (if
1.224    /// possible) is solvable with a graph search algorithm and it is
1.225    /// implemented in \ref bipartitePartitions() function in LEMON. To
1.226 -  /// decide whether the planar graph is three colorable is
1.227 -  /// NP-complete.
1.228 +  /// decide whether a planar graph is three colorable is NP-complete.
1.229    ///
1.230    /// This class contains member functions for calculate colorings
1.231    /// with five and six colors. The six coloring algorithm is a simple
1.232    /// greedy coloring on the backward minimum outgoing order of nodes.
1.233 -  /// This order can be computed as in each phase the node with least
1.234 -  /// outgoing arcs to unprocessed nodes is chosen. This order
1.235 +  /// This order can be computed by selecting the node with least
1.236 +  /// outgoing arcs to unprocessed nodes in each phase. This order
1.237    /// guarantees that when a node is chosen for coloring it has at
1.239    /// use the same method, but if the greedy approach fails to color
1.240 @@ -2499,15 +2510,19 @@
1.242      TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.244 -    /// \brief The map type for store color indexes
1.245 +    /// \brief The map type for storing color indices
1.246      typedef typename Graph::template NodeMap<int> IndexMap;
1.247 -    /// \brief The map type for store colors
1.248 +    /// \brief The map type for storing colors
1.249 +    ///
1.250 +    /// The map type for storing colors.
1.251 +    /// \see Palette, Color
1.252      typedef ComposeMap<Palette, IndexMap> ColorMap;
1.254      /// \brief Constructor
1.255      ///
1.256 -    /// Constructor
1.257 -    /// \pre The graph should be simple, i.e. loop and parallel arc free.
1.258 +    /// Constructor.
1.259 +    /// \pre The graph must be simple, i.e. it should not
1.260 +    /// contain parallel or loop arcs.
1.261      PlanarColoring(const Graph& graph)
1.262        : _graph(graph), _color_map(graph), _palette(0) {
1.264 @@ -2518,47 +2533,47 @@
1.268 -    /// \brief Returns the \e NodeMap of color indexes
1.269 +    /// \brief Return the node map of color indices
1.270      ///
1.271 -    /// Returns the \e NodeMap of color indexes. The values are in the
1.272 -    /// range \c [0..4] or \c [0..5] according to the coloring method.
1.273 +    /// This function returns the node map of color indices. The values are
1.274 +    /// in the range \c [0..4] or \c [0..5] according to the coloring method.
1.275      IndexMap colorIndexMap() const {
1.276        return _color_map;
1.279 -    /// \brief Returns the \e NodeMap of colors
1.280 +    /// \brief Return the node map of colors
1.281      ///
1.282 -    /// Returns the \e NodeMap of colors. The values are five or six
1.283 -    /// distinct \ref lemon::Color "colors".
1.284 +    /// This function returns the node map of colors. The values are among
1.285 +    /// five or six distinct \ref lemon::Color "colors".
1.286      ColorMap colorMap() const {
1.287        return composeMap(_palette, _color_map);
1.290 -    /// \brief Returns the color index of the node
1.291 +    /// \brief Return the color index of the node
1.292      ///
1.293 -    /// Returns the color index of the node. The values are in the
1.294 -    /// range \c [0..4] or \c [0..5] according to the coloring method.
1.295 +    /// This function returns the color index of the given node. The value is
1.296 +    /// in the range \c [0..4] or \c [0..5] according to the coloring method.
1.297      int colorIndex(const Node& node) const {
1.298        return _color_map[node];
1.301 -    /// \brief Returns the color of the node
1.302 +    /// \brief Return the color of the node
1.303      ///
1.304 -    /// Returns the color of the node. The values are five or six
1.305 -    /// distinct \ref lemon::Color "colors".
1.306 +    /// This function returns the color of the given node. The value is among
1.307 +    /// five or six distinct \ref lemon::Color "colors".
1.308      Color color(const Node& node) const {
1.309        return _palette[_color_map[node]];
1.313 -    /// \brief Calculates a coloring with at most six colors
1.314 +    /// \brief Calculate a coloring with at most six colors
1.315      ///
1.316      /// This function calculates a coloring with at most six colors. The time
1.317      /// complexity of this variant is linear in the size of the graph.
1.318 -    /// \return %True when the algorithm could color the graph with six color.
1.319 -    /// If the algorithm fails, then the graph could not be planar.
1.320 -    /// \note This function can return true if the graph is not
1.321 -    /// planar but it can be colored with 6 colors.
1.322 +    /// \return \c true if the algorithm could color the graph with six colors.
1.323 +    /// If the algorithm fails, then the graph is not planar.
1.324 +    /// \note This function can return \c true if the graph is not
1.325 +    /// planar, but it can be colored with at most six colors.
1.326      bool runSixColoring() {
1.328        typename Graph::template NodeMap<int> heap_index(_graph, -1);
1.329 @@ -2660,11 +2675,14 @@
1.331    public:
1.333 -    /// \brief Calculates a coloring with at most five colors
1.334 +    /// \brief Calculate a coloring with at most five colors
1.335      ///
1.336      /// This function calculates a coloring with at most five
1.337      /// colors. The worst case time complexity of this variant is
1.338      /// quadratic in the size of the graph.
1.339 +    /// \param embedding This map should contain a valid combinatorical
1.340 +    /// embedding, i.e. a valid cyclic order of the arcs.
1.341 +    /// It can be computed using PlanarEmbedding.
1.342      template <typename EmbeddingMap>
1.343      void runFiveColoring(const EmbeddingMap& embedding) {
1.345 @@ -2711,12 +2729,12 @@
1.349 -    /// \brief Calculates a coloring with at most five colors
1.350 +    /// \brief Calculate a coloring with at most five colors
1.351      ///
1.352      /// This function calculates a coloring with at most five
1.353      /// colors. The worst case time complexity of this variant is
1.354      /// quadratic in the size of the graph.
1.355 -    /// \return %True when the graph is planar.
1.356 +    /// \return \c true if the graph is planar.
1.357      bool runFiveColoring() {
1.358        PlanarEmbedding<Graph> pe(_graph);
1.359        if (!pe.run()) return false;