Changeset 2508:c86db0f7f917 in lemon-0.x

Timestamp:

11/08/07 15:21:28 (16 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3362

Message:

Planar graph coloring

File:

• lemon/planarity.h (modified) (4 diffs)

lemon/planarity.h

@@ -21 +21 @@
 /// \ingroup planar
 /// \file
-/// \brief Planarity checking, embedding
+/// \brief Planarity checking, embedding, drawing and coloring
 
 #include <vector>
@@ -27 +27 @@
 
 #include <lemon/dfs.h>
+#include <lemon/bfs.h>
 #include <lemon/radix_sort.h>
 #include <lemon/maps.h>
@@ -32 +33 @@
 #include <lemon/iterable_maps.h>
 #include <lemon/edge_set.h>
+#include <lemon/bucket_heap.h>
+#include <lemon/ugraph_adaptor.h>
+#include <lemon/color.h>
 
 
@@ -2439 +2443 @@
   };
 
+  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;
+  };
+
 }