diff -r 6520edb2c3f3 -r c86db0f7f917 lemon/planarity.h
--- a/lemon/planarity.h	Wed Nov 07 21:52:57 2007 +0000
+++ b/lemon/planarity.h	Thu Nov 08 14:21:28 2007 +0000
@@ -20,17 +20,21 @@
 
 /// \ingroup planar
 /// \file
-/// \brief Planarity checking, embedding
+/// \brief Planarity checking, embedding, drawing and coloring
 
 #include <vector>
 #include <list>
 
 #include <lemon/dfs.h>
+#include <lemon/bfs.h>
 #include <lemon/radix_sort.h>
 #include <lemon/maps.h>
 #include <lemon/path.h>
 #include <lemon/iterable_maps.h>
 #include <lemon/edge_set.h>
+#include <lemon/bucket_heap.h>
+#include <lemon/ugraph_adaptor.h>
+#include <lemon/color.h>
 
 
 namespace lemon {
@@ -2438,6 +2442,298 @@
     
   };
 
+  namespace _planarity_bits {
+
+    template <typename ColorMap>
+    class KempeFilter {
+    public:
+      typedef typename ColorMap::Key Key;
+      typedef bool Value;
+
+      KempeFilter(const ColorMap& color_map, 
+		  const typename ColorMap::Value& first,
+		  const typename ColorMap::Value& second)
+	: _color_map(color_map), _first(first), _second(second) {}
+
+      Value operator[](const Key& key) const {
+	return _color_map[key] == _first || _color_map[key] == _second;
+      }
+
+    private:
+      const ColorMap& _color_map;
+      typename ColorMap::Value _first, _second;
+    };
+  }
+
+  /// \ingroup planar
+  ///
+  /// \brief Coloring planar graphs
+  ///
+  /// The graph coloring problem is the coloring of the graph nodes
+  /// such way that there are not adjacent nodes with the same
+  /// color. The planar graphs can be always colored with four colors,
+  /// it is proved by Appel and Haken and their proofs provide a
+  /// quadratic time algorithm for four coloring, but it could not be
+  /// used to implement efficient algorithm. The five and six coloring
+  /// can be made in linear time, but in this class the five coloring
+  /// has quadratic worst case time complexity. The two coloring (if
+  /// possible) is solvable with a graph search algorithm and it is
+  /// implemented in \ref bipartitePartitions() function in Lemon. To
+  /// decide whether the planar graph is three colorable is
+  /// NP-complete.
+  ///
+  /// This class contains member functions for calculate colorings
+  /// with five and six colors. The six coloring algorithm is a simple
+  /// greedy coloring on the backward minimum outgoing order of nodes.
+  /// This order can be computed such way, that in each phase the node
+  /// with least outgoing edges to unprocessed nodes is choosen. This
+  /// order guarantees that at the time of coloring of a node it has
+  /// at most five already colored adjacents. The five coloring
+  /// algorithm works in the same way, but if the greedy approach
+  /// fails to color with five color, ie. the node has five already
+  /// different colored neighbours, it swaps the colors in one
+  /// connected two colored set with the Kempe recoloring method.
+  template <typename UGraph>
+  class PlanarColoring {
+  public:
+
+    UGRAPH_TYPEDEFS(typename UGraph);
+
+    /// \brief The map type for store color indexes
+    typedef typename UGraph::template NodeMap<int> IndexMap;
+    /// \brief The map type for store colors
+    typedef ComposeMap<Palette, IndexMap> ColorMap;
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    /// \pre The ugraph should be simple, ie. loop and parallel edge free. 
+    PlanarColoring(const UGraph& ugraph)
+      : _ugraph(ugraph), _color_map(ugraph), _palette(0) {
+      _palette.add(Color(1,0,0));
+      _palette.add(Color(0,1,0));
+      _palette.add(Color(0,0,1));
+      _palette.add(Color(1,1,0));
+      _palette.add(Color(1,0,1));
+      _palette.add(Color(0,1,1));
+    }
+
+    /// \brief Returns the \e NodeMap of color indexes
+    ///
+    /// Returns the \e NodeMap of color indexes. The values are in the
+    /// range \c [0..4] or \c [0..5] according to the five coloring or 
+    /// six coloring.
+    IndexMap colorIndexMap() const {
+      return _color_map;
+    }
+
+    /// \brief Returns the \e NodeMap of colors
+    ///
+    /// Returns the \e NodeMap of colors. The values are five or six
+    /// distinct \ref lemon::Color "colors".
+    ColorMap colorMap() const {
+      return composeMap(_palette, _color_map);
+    }
+
+    /// \brief Returns the color index of the node
+    ///
+    /// Returns the color index of the node. The values are in the
+    /// range \c [0..4] or \c [0..5] according to the five coloring or
+    /// six coloring.
+    int colorIndex(const Node& node) const {
+      return _color_map[node];
+    }
+
+    /// \brief Returns the color of the node
+    ///
+    /// Returns the color of the node. The values are five or six
+    /// distinct \ref lemon::Color "colors".
+    int color(const Node& node) const {
+      return _palette[_color_map[node]];
+    }
+    
+
+    /// \brief Calculates a coloring with at most six colors
+    ///
+    /// This function calculates a coloring with at most six colors. The time
+    /// complexity of this variant is linear in the size of the graph.
+    /// \return %True when the algorithm could color the graph with six color.
+    /// If the algorithm fails, then the graph could not be planar.
+    bool runSixColoring() {
+      
+      typename UGraph::template NodeMap<int> heap_index(_ugraph, -1);
+      BucketHeap<typename UGraph::template NodeMap<int> > heap(heap_index);
+      
+      for (NodeIt n(_ugraph); n != INVALID; ++n) {
+	_color_map[n] = -2;
+	heap.push(n, countOutEdges(_ugraph, n));
+      }
+      
+      std::vector<Node> order;
+      
+      while (!heap.empty()) {
+	Node n = heap.top();
+	heap.pop();
+	_color_map[n] = -1;
+	order.push_back(n);
+	for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
+	  Node t = _ugraph.runningNode(e); 
+	  if (_color_map[t] == -2) {
+	    heap.decrease(t, heap[t] - 1);
+	  }
+	}
+      }
+
+      for (int i = order.size() - 1; i >= 0; --i) {
+	std::vector<bool> forbidden(6, false);
+	for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) {
+	  Node t = _ugraph.runningNode(e); 
+	  if (_color_map[t] != -1) {
+	    forbidden[_color_map[t]] = true;
+	  }
+	}
+       	for (int k = 0; k < 6; ++k) {
+	  if (!forbidden[k]) {
+	    _color_map[order[i]] = k;
+	    break;
+	  }
+	}
+	if (_color_map[order[i]] == -1) {
+	  return false;
+	}
+      }
+      return true;
+    }
+
+  private:
+
+    bool recolor(const Node& u, const Node& v) {
+      int ucolor = _color_map[u];
+      int vcolor = _color_map[v];
+      typedef _planarity_bits::KempeFilter<IndexMap> KempeFilter;
+      KempeFilter filter(_color_map, ucolor, vcolor);
+
+      typedef NodeSubUGraphAdaptor<const UGraph, const KempeFilter> KempeUGraph;
+      KempeUGraph kempe_ugraph(_ugraph, filter);
+      
+      std::vector<Node> comp;
+      Bfs<KempeUGraph> bfs(kempe_ugraph);
+      bfs.init();
+      bfs.addSource(u);
+      while (!bfs.emptyQueue()) {
+	Node n = bfs.nextNode();
+	if (n == v) return false;
+	comp.push_back(n);
+	bfs.processNextNode();
+      }
+
+      int scolor = ucolor + vcolor;
+      for (int i = 0; i < static_cast<int>(comp.size()); ++i) {
+	_color_map[comp[i]] = scolor - _color_map[comp[i]]; 
+      }
+
+      return true;
+    }
+
+    template <typename EmbeddingMap>
+    void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) {
+      std::vector<Node> nodes;
+      nodes.reserve(4);
+
+      for (Edge e = OutEdgeIt(_ugraph, node); e != INVALID; e = embedding[e]) {
+	Node t = _ugraph.target(e); 
+	if (_color_map[t] != -1) {
+	  nodes.push_back(t);
+	  if (nodes.size() == 4) break;
+	}
+      }
+      
+      int color = _color_map[nodes[0]];
+      if (recolor(nodes[0], nodes[2])) {
+	_color_map[node] = color;
+      } else {
+	color = _color_map[nodes[1]];
+	recolor(nodes[1], nodes[3]);
+	_color_map[node] = color;
+      }
+    }
+
+  public:
+
+    /// \brief Calculates a coloring with at most five colors
+    ///
+    /// This function calculates a coloring with at most five
+    /// colors. The wirst case time complexity of this variant is
+    /// quadratic in the size of the graph.
+    template <typename EmbeddingMap>
+    void runFiveColoring(const EmbeddingMap& embedding) {
+      
+      typename UGraph::template NodeMap<int> heap_index(_ugraph, -1);
+      BucketHeap<typename UGraph::template NodeMap<int> > heap(heap_index);
+      
+      for (NodeIt n(_ugraph); n != INVALID; ++n) {
+	_color_map[n] = -2;
+	heap.push(n, countOutEdges(_ugraph, n));
+      }
+      
+      std::vector<Node> order;
+      
+      while (!heap.empty()) {
+	Node n = heap.top();
+	heap.pop();
+	_color_map[n] = -1;
+	order.push_back(n);
+	for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
+	  Node t = _ugraph.runningNode(e); 
+	  if (_color_map[t] == -2) {
+	    heap.decrease(t, heap[t] - 1);
+	  }
+	}
+      }
+
+      for (int i = order.size() - 1; i >= 0; --i) {
+	std::vector<bool> forbidden(5, false);
+	for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) {
+	  Node t = _ugraph.runningNode(e); 
+	  if (_color_map[t] != -1) {
+	    forbidden[_color_map[t]] = true;
+	  }
+	}
+	for (int k = 0; k < 5; ++k) {
+	  if (!forbidden[k]) {
+	    _color_map[order[i]] = k;
+	    break;
+	  }
+	}
+	if (_color_map[order[i]] == -1) {
+	  kempeRecoloring(order[i], embedding);
+	}
+      }
+    }
+
+    /// \brief Calculates a coloring with at most five colors
+    ///
+    /// This function calculates a coloring with at most five
+    /// colors. The worst case time complexity of this variant is
+    /// quadratic in the size of the graph, but it most cases it does
+    /// not have to use Kempe recoloring method, in this case it is
+    /// equivalent with the runSixColoring() algorithm.
+    /// \return %True when the graph is planar.
+    bool runFiveColoring() {
+      PlanarEmbedding<UGraph> pe(_ugraph);
+      if (!pe.run()) return false;
+      
+      runFiveColoring(pe.embeddingMap());
+      return true;
+    }
+
+  private:
+    
+    const UGraph& _ugraph;
+    IndexMap _color_map;
+    Palette _palette;
+  };
+
 }
 
 #endif