Planar graph coloring
authordeba
Thu, 08 Nov 2007 14:21:28 +0000
changeset 2508c86db0f7f917
parent 2507 6520edb2c3f3
child 2509 a8081c9cd96a
Planar graph coloring
lemon/planarity.h
     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