COIN-OR::LEMON - Graph Library

Changeset 2508:c86db0f7f917 in lemon-0.x


Ignore:
Timestamp:
11/08/07 15:21:28 (17 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3362
Message:

Planar graph coloring

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/planarity.h

    r2500 r2508  
    2121/// \ingroup planar
    2222/// \file
    23 /// \brief Planarity checking, embedding
     23/// \brief Planarity checking, embedding, drawing and coloring
    2424
    2525#include <vector>
     
    2727
    2828#include <lemon/dfs.h>
     29#include <lemon/bfs.h>
    2930#include <lemon/radix_sort.h>
    3031#include <lemon/maps.h>
     
    3233#include <lemon/iterable_maps.h>
    3334#include <lemon/edge_set.h>
     35#include <lemon/bucket_heap.h>
     36#include <lemon/ugraph_adaptor.h>
     37#include <lemon/color.h>
    3438
    3539
     
    24392443  };
    24402444
     2445  namespace _planarity_bits {
     2446
     2447    template <typename ColorMap>
     2448    class KempeFilter {
     2449    public:
     2450      typedef typename ColorMap::Key Key;
     2451      typedef bool Value;
     2452
     2453      KempeFilter(const ColorMap& color_map,
     2454                  const typename ColorMap::Value& first,
     2455                  const typename ColorMap::Value& second)
     2456        : _color_map(color_map), _first(first), _second(second) {}
     2457
     2458      Value operator[](const Key& key) const {
     2459        return _color_map[key] == _first || _color_map[key] == _second;
     2460      }
     2461
     2462    private:
     2463      const ColorMap& _color_map;
     2464      typename ColorMap::Value _first, _second;
     2465    };
     2466  }
     2467
     2468  /// \ingroup planar
     2469  ///
     2470  /// \brief Coloring planar graphs
     2471  ///
     2472  /// The graph coloring problem is the coloring of the graph nodes
     2473  /// such way that there are not adjacent nodes with the same
     2474  /// color. The planar graphs can be always colored with four colors,
     2475  /// it is proved by Appel and Haken and their proofs provide a
     2476  /// quadratic time algorithm for four coloring, but it could not be
     2477  /// used to implement efficient algorithm. The five and six coloring
     2478  /// can be made in linear time, but in this class the five coloring
     2479  /// has quadratic worst case time complexity. The two coloring (if
     2480  /// possible) is solvable with a graph search algorithm and it is
     2481  /// implemented in \ref bipartitePartitions() function in Lemon. To
     2482  /// decide whether the planar graph is three colorable is
     2483  /// NP-complete.
     2484  ///
     2485  /// This class contains member functions for calculate colorings
     2486  /// with five and six colors. The six coloring algorithm is a simple
     2487  /// greedy coloring on the backward minimum outgoing order of nodes.
     2488  /// This order can be computed such way, that in each phase the node
     2489  /// with least outgoing edges to unprocessed nodes is choosen. This
     2490  /// order guarantees that at the time of coloring of a node it has
     2491  /// at most five already colored adjacents. The five coloring
     2492  /// algorithm works in the same way, but if the greedy approach
     2493  /// fails to color with five color, ie. the node has five already
     2494  /// different colored neighbours, it swaps the colors in one
     2495  /// connected two colored set with the Kempe recoloring method.
     2496  template <typename UGraph>
     2497  class PlanarColoring {
     2498  public:
     2499
     2500    UGRAPH_TYPEDEFS(typename UGraph);
     2501
     2502    /// \brief The map type for store color indexes
     2503    typedef typename UGraph::template NodeMap<int> IndexMap;
     2504    /// \brief The map type for store colors
     2505    typedef ComposeMap<Palette, IndexMap> ColorMap;
     2506
     2507    /// \brief Constructor
     2508    ///
     2509    /// Constructor
     2510    /// \pre The ugraph should be simple, ie. loop and parallel edge free.
     2511    PlanarColoring(const UGraph& ugraph)
     2512      : _ugraph(ugraph), _color_map(ugraph), _palette(0) {
     2513      _palette.add(Color(1,0,0));
     2514      _palette.add(Color(0,1,0));
     2515      _palette.add(Color(0,0,1));
     2516      _palette.add(Color(1,1,0));
     2517      _palette.add(Color(1,0,1));
     2518      _palette.add(Color(0,1,1));
     2519    }
     2520
     2521    /// \brief Returns the \e NodeMap of color indexes
     2522    ///
     2523    /// Returns the \e NodeMap of color indexes. The values are in the
     2524    /// range \c [0..4] or \c [0..5] according to the five coloring or
     2525    /// six coloring.
     2526    IndexMap colorIndexMap() const {
     2527      return _color_map;
     2528    }
     2529
     2530    /// \brief Returns the \e NodeMap of colors
     2531    ///
     2532    /// Returns the \e NodeMap of colors. The values are five or six
     2533    /// distinct \ref lemon::Color "colors".
     2534    ColorMap colorMap() const {
     2535      return composeMap(_palette, _color_map);
     2536    }
     2537
     2538    /// \brief Returns the color index of the node
     2539    ///
     2540    /// Returns the color index of the node. The values are in the
     2541    /// range \c [0..4] or \c [0..5] according to the five coloring or
     2542    /// six coloring.
     2543    int colorIndex(const Node& node) const {
     2544      return _color_map[node];
     2545    }
     2546
     2547    /// \brief Returns the color of the node
     2548    ///
     2549    /// Returns the color of the node. The values are five or six
     2550    /// distinct \ref lemon::Color "colors".
     2551    int color(const Node& node) const {
     2552      return _palette[_color_map[node]];
     2553    }
     2554   
     2555
     2556    /// \brief Calculates a coloring with at most six colors
     2557    ///
     2558    /// This function calculates a coloring with at most six colors. The time
     2559    /// complexity of this variant is linear in the size of the graph.
     2560    /// \return %True when the algorithm could color the graph with six color.
     2561    /// If the algorithm fails, then the graph could not be planar.
     2562    bool runSixColoring() {
     2563     
     2564      typename UGraph::template NodeMap<int> heap_index(_ugraph, -1);
     2565      BucketHeap<typename UGraph::template NodeMap<int> > heap(heap_index);
     2566     
     2567      for (NodeIt n(_ugraph); n != INVALID; ++n) {
     2568        _color_map[n] = -2;
     2569        heap.push(n, countOutEdges(_ugraph, n));
     2570      }
     2571     
     2572      std::vector<Node> order;
     2573     
     2574      while (!heap.empty()) {
     2575        Node n = heap.top();
     2576        heap.pop();
     2577        _color_map[n] = -1;
     2578        order.push_back(n);
     2579        for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
     2580          Node t = _ugraph.runningNode(e);
     2581          if (_color_map[t] == -2) {
     2582            heap.decrease(t, heap[t] - 1);
     2583          }
     2584        }
     2585      }
     2586
     2587      for (int i = order.size() - 1; i >= 0; --i) {
     2588        std::vector<bool> forbidden(6, false);
     2589        for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) {
     2590          Node t = _ugraph.runningNode(e);
     2591          if (_color_map[t] != -1) {
     2592            forbidden[_color_map[t]] = true;
     2593          }
     2594        }
     2595        for (int k = 0; k < 6; ++k) {
     2596          if (!forbidden[k]) {
     2597            _color_map[order[i]] = k;
     2598            break;
     2599          }
     2600        }
     2601        if (_color_map[order[i]] == -1) {
     2602          return false;
     2603        }
     2604      }
     2605      return true;
     2606    }
     2607
     2608  private:
     2609
     2610    bool recolor(const Node& u, const Node& v) {
     2611      int ucolor = _color_map[u];
     2612      int vcolor = _color_map[v];
     2613      typedef _planarity_bits::KempeFilter<IndexMap> KempeFilter;
     2614      KempeFilter filter(_color_map, ucolor, vcolor);
     2615
     2616      typedef NodeSubUGraphAdaptor<const UGraph, const KempeFilter> KempeUGraph;
     2617      KempeUGraph kempe_ugraph(_ugraph, filter);
     2618     
     2619      std::vector<Node> comp;
     2620      Bfs<KempeUGraph> bfs(kempe_ugraph);
     2621      bfs.init();
     2622      bfs.addSource(u);
     2623      while (!bfs.emptyQueue()) {
     2624        Node n = bfs.nextNode();
     2625        if (n == v) return false;
     2626        comp.push_back(n);
     2627        bfs.processNextNode();
     2628      }
     2629
     2630      int scolor = ucolor + vcolor;
     2631      for (int i = 0; i < static_cast<int>(comp.size()); ++i) {
     2632        _color_map[comp[i]] = scolor - _color_map[comp[i]];
     2633      }
     2634
     2635      return true;
     2636    }
     2637
     2638    template <typename EmbeddingMap>
     2639    void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) {
     2640      std::vector<Node> nodes;
     2641      nodes.reserve(4);
     2642
     2643      for (Edge e = OutEdgeIt(_ugraph, node); e != INVALID; e = embedding[e]) {
     2644        Node t = _ugraph.target(e);
     2645        if (_color_map[t] != -1) {
     2646          nodes.push_back(t);
     2647          if (nodes.size() == 4) break;
     2648        }
     2649      }
     2650     
     2651      int color = _color_map[nodes[0]];
     2652      if (recolor(nodes[0], nodes[2])) {
     2653        _color_map[node] = color;
     2654      } else {
     2655        color = _color_map[nodes[1]];
     2656        recolor(nodes[1], nodes[3]);
     2657        _color_map[node] = color;
     2658      }
     2659    }
     2660
     2661  public:
     2662
     2663    /// \brief Calculates a coloring with at most five colors
     2664    ///
     2665    /// This function calculates a coloring with at most five
     2666    /// colors. The wirst case time complexity of this variant is
     2667    /// quadratic in the size of the graph.
     2668    template <typename EmbeddingMap>
     2669    void runFiveColoring(const EmbeddingMap& embedding) {
     2670     
     2671      typename UGraph::template NodeMap<int> heap_index(_ugraph, -1);
     2672      BucketHeap<typename UGraph::template NodeMap<int> > heap(heap_index);
     2673     
     2674      for (NodeIt n(_ugraph); n != INVALID; ++n) {
     2675        _color_map[n] = -2;
     2676        heap.push(n, countOutEdges(_ugraph, n));
     2677      }
     2678     
     2679      std::vector<Node> order;
     2680     
     2681      while (!heap.empty()) {
     2682        Node n = heap.top();
     2683        heap.pop();
     2684        _color_map[n] = -1;
     2685        order.push_back(n);
     2686        for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
     2687          Node t = _ugraph.runningNode(e);
     2688          if (_color_map[t] == -2) {
     2689            heap.decrease(t, heap[t] - 1);
     2690          }
     2691        }
     2692      }
     2693
     2694      for (int i = order.size() - 1; i >= 0; --i) {
     2695        std::vector<bool> forbidden(5, false);
     2696        for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) {
     2697          Node t = _ugraph.runningNode(e);
     2698          if (_color_map[t] != -1) {
     2699            forbidden[_color_map[t]] = true;
     2700          }
     2701        }
     2702        for (int k = 0; k < 5; ++k) {
     2703          if (!forbidden[k]) {
     2704            _color_map[order[i]] = k;
     2705            break;
     2706          }
     2707        }
     2708        if (_color_map[order[i]] == -1) {
     2709          kempeRecoloring(order[i], embedding);
     2710        }
     2711      }
     2712    }
     2713
     2714    /// \brief Calculates a coloring with at most five colors
     2715    ///
     2716    /// This function calculates a coloring with at most five
     2717    /// colors. The worst case time complexity of this variant is
     2718    /// quadratic in the size of the graph, but it most cases it does
     2719    /// not have to use Kempe recoloring method, in this case it is
     2720    /// equivalent with the runSixColoring() algorithm.
     2721    /// \return %True when the graph is planar.
     2722    bool runFiveColoring() {
     2723      PlanarEmbedding<UGraph> pe(_ugraph);
     2724      if (!pe.run()) return false;
     2725     
     2726      runFiveColoring(pe.embeddingMap());
     2727      return true;
     2728    }
     2729
     2730  private:
     2731   
     2732    const UGraph& _ugraph;
     2733    IndexMap _color_map;
     2734    Palette _palette;
     2735  };
     2736
    24412737}
    24422738
Note: See TracChangeset for help on using the changeset viewer.