GreedyColouring.hpp File Reference

Plans regarding the greedy graph colouring algorithm. More...

Go to the source code of this file.

Detailed Description

Plans regarding the greedy graph colouring algorithm.

Relations to other modules
  • In GreedyColouring.hpp the components
    • Out_degree_order
    • output_vertex_degrees
    • Edge DONE (not needed anymore)
    • EdgeVector DONE (not needed anymore)
    • read DONE (replaced by using the dot-syntax)
    should be moved to the SupportBoost-module.
Class Greedy_colouring
  • The design needs an overhaul.
  • Use Boost::permutation_iterator (and it should be made possible to iterate through the vertex-permutations in some user-defined order).
  • Test it.
  • Extend doxygen documentation.
  • Eliminate code repetition.
  • Use general components from module Graphs.
  • Use Messages.
  • Use ProgramOptions.
  • Complete doxygen documentation.
  • Write docus.
  • Test it.
  • Transfer todos here.
  • Search for literature on heuristics for vertex orderings.
  • From CS-232 we have the traversing greedy colouring; it seems sensible to combine this with a largest degree first-stratey.
    1. If there is a choice, then a vertex with largest degree is chosen.
    2. Such choice points happen when entering a new connected component, and when choosing an edge from the buffer.
    3. The graph traversal algorithm is available in boost as boost::breadth_first_search; unclear whether it exists also for undirected graphs. Easiest to sort the vertices at the beginning, to store the associated ranks as vertex properties, and to use a priority queue as buffer using these ranks, while perhaps after a connected component has been processed, the used vertices are taken out, and then simply the first vertex can be chosen.
    4. Since we are computing the order dynamically, we might alternatively use the strategy for choice points: Maximise the number of yet uncoloured vertices! This is somewhat harder to compute (the priorities for the buffer need update), but should still be very fast.
How do these algorithms translate into SAT algorithms?
  • We need to consider the decision variants.
  • One could hope to find a new heuristical principles for finding a satisfying assignment by generalising the various greedy algorithms.
  • Translating the decision problem, whether a vertex ordering achieving at most k colours exist, into a SAT problem:
    1. Variables are i_v, the index for vertex v, with domain {1,...,|V|}, and c_v, the colour of v, with domain {1,...,k}.
    2. Constraints are
      • the bijectivity constraint for the i_v,
      • the active clause-set for the colouring conditions (no adjacent vertices get the same colour),
      • and the active clause-set stating that if all neighbours which are also predecessors are coloured, then the colour of the vertex is determined as the minimal available colour.
    3. Instead of the permutation one could also use a lineare ordering with the corresponding axioms reflexivity, antisymmetry, transitivity and totality.
  • This SAT problem could be treated as a minimisation problem for k, the domain size of the colour-variables.
  • One could treat the conditions regarding the i_v as "soft constraints", since they are only there to guide the search for a colouring (we know that an ordering exists iff a colouring exists).
  • Via this SAT formulation we also capture a backtracking search for an ordering achieving k colours (though the question is whether this SAT-approach can be as efficient as a direct implementation).
  • Of course it is questionable whether in this way something for graph colouring is gained:
    1. The only strength of the greedy approach seems to be that the number of colours is not restricted.
    2. But for the SAT translation it needs to be restricted.
    3. The direct search space condition is k^n = n! for the given n: for k with n! < k^n at least the primary search space is smaller.
    4. In other words, the critical k is k = (n!)^(1/n), and for larger k the direct search space of greedy colouring is smaller.
    One simply should experiment with the approach.
Local search for a good vertex ordering
  • The direct approach is to consider it just as a standard optimisation problem, where the search space is the space of all vertex permutations, and where the goal function is the number of colours obtained by the permutation, to be minimised.
  • The natural notion of a move would be a transposition (possibly restricted to a neighbour swap).
  • A more restricted approach would consider the decision problem with bound k, and would only construct the colouring corresponding to a permutation until it gets larger than k, in which case the current "problematic" vertex could simply be swapped with one of its coloured neighbours.
  • See Optimisation/LocalSearch/plans/general.hpp for a generic local search algorithm.
Generalisation to hypergraphs
  • Same as before, for a given order give always the lowest number possible.
  • However, apparently now there does not need to exist an order producing an optimal colouring?
  • Are there other greedy strategies?

Definition in file GreedyColouring.hpp.