1.1 --- a/lemon/planarity.h Wed Nov 07 21:52:57 2007 +0000
1.2 +++ b/lemon/planarity.h Thu Nov 08 14:21:28 2007 +0000
1.3 @@ -20,17 +20,21 @@
1.4
1.5 /// \ingroup planar
1.6 /// \file
1.7 -/// \brief Planarity checking, embedding
1.8 +/// \brief Planarity checking, embedding, drawing and coloring
1.9
1.10 #include <vector>
1.11 #include <list>
1.12
1.13 #include <lemon/dfs.h>
1.14 +#include <lemon/bfs.h>
1.15 #include <lemon/radix_sort.h>
1.16 #include <lemon/maps.h>
1.17 #include <lemon/path.h>
1.18 #include <lemon/iterable_maps.h>
1.19 #include <lemon/edge_set.h>
1.20 +#include <lemon/bucket_heap.h>
1.21 +#include <lemon/ugraph_adaptor.h>
1.22 +#include <lemon/color.h>
1.23
1.24
1.25 namespace lemon {
1.26 @@ -2438,6 +2442,298 @@
1.27
1.28 };
1.29
1.30 + namespace _planarity_bits {
1.31 +
1.32 + template <typename ColorMap>
1.33 + class KempeFilter {
1.34 + public:
1.35 + typedef typename ColorMap::Key Key;
1.36 + typedef bool Value;
1.37 +
1.38 + KempeFilter(const ColorMap& color_map,
1.39 + const typename ColorMap::Value& first,
1.40 + const typename ColorMap::Value& second)
1.41 + : _color_map(color_map), _first(first), _second(second) {}
1.42 +
1.43 + Value operator[](const Key& key) const {
1.44 + return _color_map[key] == _first || _color_map[key] == _second;
1.45 + }
1.46 +
1.47 + private:
1.48 + const ColorMap& _color_map;
1.49 + typename ColorMap::Value _first, _second;
1.50 + };
1.51 + }
1.52 +
1.53 + /// \ingroup planar
1.54 + ///
1.55 + /// \brief Coloring planar graphs
1.56 + ///
1.57 + /// The graph coloring problem is the coloring of the graph nodes
1.58 + /// such way that there are not adjacent nodes with the same
1.59 + /// color. The planar graphs can be always colored with four colors,
1.60 + /// it is proved by Appel and Haken and their proofs provide a
1.61 + /// quadratic time algorithm for four coloring, but it could not be
1.62 + /// used to implement efficient algorithm. The five and six coloring
1.63 + /// can be made in linear time, but in this class the five coloring
1.64 + /// has quadratic worst case time complexity. The two coloring (if
1.65 + /// possible) is solvable with a graph search algorithm and it is
1.66 + /// implemented in \ref bipartitePartitions() function in Lemon. To
1.67 + /// decide whether the planar graph is three colorable is
1.68 + /// NP-complete.
1.69 + ///
1.70 + /// This class contains member functions for calculate colorings
1.71 + /// with five and six colors. The six coloring algorithm is a simple
1.72 + /// greedy coloring on the backward minimum outgoing order of nodes.
1.73 + /// This order can be computed such way, that in each phase the node
1.74 + /// with least outgoing edges to unprocessed nodes is choosen. This
1.75 + /// order guarantees that at the time of coloring of a node it has
1.76 + /// at most five already colored adjacents. The five coloring
1.77 + /// algorithm works in the same way, but if the greedy approach
1.78 + /// fails to color with five color, ie. the node has five already
1.79 + /// different colored neighbours, it swaps the colors in one
1.80 + /// connected two colored set with the Kempe recoloring method.
1.81 + template <typename UGraph>
1.82 + class PlanarColoring {
1.83 + public:
1.84 +
1.85 + UGRAPH_TYPEDEFS(typename UGraph);
1.86 +
1.87 + /// \brief The map type for store color indexes
1.88 + typedef typename UGraph::template NodeMap<int> IndexMap;
1.89 + /// \brief The map type for store colors
1.90 + typedef ComposeMap<Palette, IndexMap> ColorMap;
1.91 +
1.92 + /// \brief Constructor
1.93 + ///
1.94 + /// Constructor
1.95 + /// \pre The ugraph should be simple, ie. loop and parallel edge free.
1.96 + PlanarColoring(const UGraph& ugraph)
1.97 + : _ugraph(ugraph), _color_map(ugraph), _palette(0) {
1.98 + _palette.add(Color(1,0,0));
1.99 + _palette.add(Color(0,1,0));
1.100 + _palette.add(Color(0,0,1));
1.101 + _palette.add(Color(1,1,0));
1.102 + _palette.add(Color(1,0,1));
1.103 + _palette.add(Color(0,1,1));
1.104 + }
1.105 +
1.106 + /// \brief Returns the \e NodeMap of color indexes
1.107 + ///
1.108 + /// Returns the \e NodeMap of color indexes. The values are in the
1.109 + /// range \c [0..4] or \c [0..5] according to the five coloring or
1.110 + /// six coloring.
1.111 + IndexMap colorIndexMap() const {
1.112 + return _color_map;
1.113 + }
1.114 +
1.115 + /// \brief Returns the \e NodeMap of colors
1.116 + ///
1.117 + /// Returns the \e NodeMap of colors. The values are five or six
1.118 + /// distinct \ref lemon::Color "colors".
1.119 + ColorMap colorMap() const {
1.120 + return composeMap(_palette, _color_map);
1.121 + }
1.122 +
1.123 + /// \brief Returns the color index of the node
1.124 + ///
1.125 + /// Returns the color index of the node. The values are in the
1.126 + /// range \c [0..4] or \c [0..5] according to the five coloring or
1.127 + /// six coloring.
1.128 + int colorIndex(const Node& node) const {
1.129 + return _color_map[node];
1.130 + }
1.131 +
1.132 + /// \brief Returns the color of the node
1.133 + ///
1.134 + /// Returns the color of the node. The values are five or six
1.135 + /// distinct \ref lemon::Color "colors".
1.136 + int color(const Node& node) const {
1.137 + return _palette[_color_map[node]];
1.138 + }
1.139 +
1.140 +
1.141 + /// \brief Calculates a coloring with at most six colors
1.142 + ///
1.143 + /// This function calculates a coloring with at most six colors. The time
1.144 + /// complexity of this variant is linear in the size of the graph.
1.145 + /// \return %True when the algorithm could color the graph with six color.
1.146 + /// If the algorithm fails, then the graph could not be planar.
1.147 + bool runSixColoring() {
1.148 +
1.149 + typename UGraph::template NodeMap<int> heap_index(_ugraph, -1);
1.150 + BucketHeap<typename UGraph::template NodeMap<int> > heap(heap_index);
1.151 +
1.152 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
1.153 + _color_map[n] = -2;
1.154 + heap.push(n, countOutEdges(_ugraph, n));
1.155 + }
1.156 +
1.157 + std::vector<Node> order;
1.158 +
1.159 + while (!heap.empty()) {
1.160 + Node n = heap.top();
1.161 + heap.pop();
1.162 + _color_map[n] = -1;
1.163 + order.push_back(n);
1.164 + for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
1.165 + Node t = _ugraph.runningNode(e);
1.166 + if (_color_map[t] == -2) {
1.167 + heap.decrease(t, heap[t] - 1);
1.168 + }
1.169 + }
1.170 + }
1.171 +
1.172 + for (int i = order.size() - 1; i >= 0; --i) {
1.173 + std::vector<bool> forbidden(6, false);
1.174 + for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) {
1.175 + Node t = _ugraph.runningNode(e);
1.176 + if (_color_map[t] != -1) {
1.177 + forbidden[_color_map[t]] = true;
1.178 + }
1.179 + }
1.180 + for (int k = 0; k < 6; ++k) {
1.181 + if (!forbidden[k]) {
1.182 + _color_map[order[i]] = k;
1.183 + break;
1.184 + }
1.185 + }
1.186 + if (_color_map[order[i]] == -1) {
1.187 + return false;
1.188 + }
1.189 + }
1.190 + return true;
1.191 + }
1.192 +
1.193 + private:
1.194 +
1.195 + bool recolor(const Node& u, const Node& v) {
1.196 + int ucolor = _color_map[u];
1.197 + int vcolor = _color_map[v];
1.198 + typedef _planarity_bits::KempeFilter<IndexMap> KempeFilter;
1.199 + KempeFilter filter(_color_map, ucolor, vcolor);
1.200 +
1.201 + typedef NodeSubUGraphAdaptor<const UGraph, const KempeFilter> KempeUGraph;
1.202 + KempeUGraph kempe_ugraph(_ugraph, filter);
1.203 +
1.204 + std::vector<Node> comp;
1.205 + Bfs<KempeUGraph> bfs(kempe_ugraph);
1.206 + bfs.init();
1.207 + bfs.addSource(u);
1.208 + while (!bfs.emptyQueue()) {
1.209 + Node n = bfs.nextNode();
1.210 + if (n == v) return false;
1.211 + comp.push_back(n);
1.212 + bfs.processNextNode();
1.213 + }
1.214 +
1.215 + int scolor = ucolor + vcolor;
1.216 + for (int i = 0; i < static_cast<int>(comp.size()); ++i) {
1.217 + _color_map[comp[i]] = scolor - _color_map[comp[i]];
1.218 + }
1.219 +
1.220 + return true;
1.221 + }
1.222 +
1.223 + template <typename EmbeddingMap>
1.224 + void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) {
1.225 + std::vector<Node> nodes;
1.226 + nodes.reserve(4);
1.227 +
1.228 + for (Edge e = OutEdgeIt(_ugraph, node); e != INVALID; e = embedding[e]) {
1.229 + Node t = _ugraph.target(e);
1.230 + if (_color_map[t] != -1) {
1.231 + nodes.push_back(t);
1.232 + if (nodes.size() == 4) break;
1.233 + }
1.234 + }
1.235 +
1.236 + int color = _color_map[nodes[0]];
1.237 + if (recolor(nodes[0], nodes[2])) {
1.238 + _color_map[node] = color;
1.239 + } else {
1.240 + color = _color_map[nodes[1]];
1.241 + recolor(nodes[1], nodes[3]);
1.242 + _color_map[node] = color;
1.243 + }
1.244 + }
1.245 +
1.246 + public:
1.247 +
1.248 + /// \brief Calculates a coloring with at most five colors
1.249 + ///
1.250 + /// This function calculates a coloring with at most five
1.251 + /// colors. The wirst case time complexity of this variant is
1.252 + /// quadratic in the size of the graph.
1.253 + template <typename EmbeddingMap>
1.254 + void runFiveColoring(const EmbeddingMap& embedding) {
1.255 +
1.256 + typename UGraph::template NodeMap<int> heap_index(_ugraph, -1);
1.257 + BucketHeap<typename UGraph::template NodeMap<int> > heap(heap_index);
1.258 +
1.259 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
1.260 + _color_map[n] = -2;
1.261 + heap.push(n, countOutEdges(_ugraph, n));
1.262 + }
1.263 +
1.264 + std::vector<Node> order;
1.265 +
1.266 + while (!heap.empty()) {
1.267 + Node n = heap.top();
1.268 + heap.pop();
1.269 + _color_map[n] = -1;
1.270 + order.push_back(n);
1.271 + for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
1.272 + Node t = _ugraph.runningNode(e);
1.273 + if (_color_map[t] == -2) {
1.274 + heap.decrease(t, heap[t] - 1);
1.275 + }
1.276 + }
1.277 + }
1.278 +
1.279 + for (int i = order.size() - 1; i >= 0; --i) {
1.280 + std::vector<bool> forbidden(5, false);
1.281 + for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) {
1.282 + Node t = _ugraph.runningNode(e);
1.283 + if (_color_map[t] != -1) {
1.284 + forbidden[_color_map[t]] = true;
1.285 + }
1.286 + }
1.287 + for (int k = 0; k < 5; ++k) {
1.288 + if (!forbidden[k]) {
1.289 + _color_map[order[i]] = k;
1.290 + break;
1.291 + }
1.292 + }
1.293 + if (_color_map[order[i]] == -1) {
1.294 + kempeRecoloring(order[i], embedding);
1.295 + }
1.296 + }
1.297 + }
1.298 +
1.299 + /// \brief Calculates a coloring with at most five colors
1.300 + ///
1.301 + /// This function calculates a coloring with at most five
1.302 + /// colors. The worst case time complexity of this variant is
1.303 + /// quadratic in the size of the graph, but it most cases it does
1.304 + /// not have to use Kempe recoloring method, in this case it is
1.305 + /// equivalent with the runSixColoring() algorithm.
1.306 + /// \return %True when the graph is planar.
1.307 + bool runFiveColoring() {
1.308 + PlanarEmbedding<UGraph> pe(_ugraph);
1.309 + if (!pe.run()) return false;
1.310 +
1.311 + runFiveColoring(pe.embeddingMap());
1.312 + return true;
1.313 + }
1.314 +
1.315 + private:
1.316 +
1.317 + const UGraph& _ugraph;
1.318 + IndexMap _color_map;
1.319 + Palette _palette;
1.320 + };
1.321 +
1.322 }
1.323
1.324 #endif