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.40
1.41 public:
1.42
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.49
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.59
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.72
1.73 @@ -699,30 +704,32 @@
1.74 return true;
1.75 }
1.76
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.87
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.99
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.115 }
1.116
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.137
1.138 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.139
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.146
1.147
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.156
1.157 @@ -2366,10 +2376,10 @@
1.158
1.159 public:
1.160
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.173 }
1.174
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.190
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.197 }
1.198
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.207 }
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.238 /// most five already colored adjacents. The five coloring algorithm
1.239 /// use the same method, but if the greedy approach fails to color
1.240 @@ -2499,15 +2510,19 @@
1.241
1.242 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.243
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.253
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.263 _palette.add(Color(1,0,0));
1.264 @@ -2518,47 +2533,47 @@
1.265 _palette.add(Color(0,1,1));
1.266 }
1.267
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.277 }
1.278
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.288 }
1.289
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.299 }
1.300
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.310 }
1.311
1.312
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.327
1.328 typename Graph::template NodeMap<int> heap_index(_graph, -1);
1.329 @@ -2660,11 +2675,14 @@
1.330
1.331 public:
1.332
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.344
1.345 @@ -2711,12 +2729,12 @@
1.346 }
1.347 }
1.348
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;