#include <lemon/bfs.h>

 #include <lemon/bucket_heap.h>

 #include <lemon/ugraph_adaptor.h>

 #include <lemon/color.h>

   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;

   };