diff options
Diffstat (limited to '02-graph-coloring/CP-solver.rb')
| -rwxr-xr-x | 02-graph-coloring/CP-solver.rb | 229 |
1 files changed, 229 insertions, 0 deletions
diff --git a/02-graph-coloring/CP-solver.rb b/02-graph-coloring/CP-solver.rb new file mode 100755 index 0000000..c157c07 --- /dev/null +++ b/02-graph-coloring/CP-solver.rb @@ -0,0 +1,229 @@ +#! /usr/bin/ruby + +class Node + # + def initialize i, a + @i = i # index + @a = [a] # adjacents + @c = nil # colour + @f = 0 # finished adjacents + @l = nil + end + # + attr_reader :i, :a + attr_accessor :c, :f + # + def add a + @a << a + end + # + def to_s + "#{@i} #{@c.to_s} " + @a.to_s + end + # + def l + return @l if not @l.nil? + @l = @a.length + end + # + def blocked? + (l == @f) + end + # +end + +class Step + # + def initialize n, c + @n = n # nodes + @c = c # max color + @k = nil # current + @f = [] # failed + @p = n.select { |n| n.c.nil? } # possible + # puts @p.inspect + # @p[0].c = 666 + # puts @p[0].to_s + end + attr_reader :c, :n + def done? + @p.empty? + end + # + def sort ar + ar.sort { |a,b| + r = b.l <=> a.l + if r == 0 + b.f <=> a.f + else + r + end + } + end + # + def chose_node + b = @p.select { |n| n.blocked? } + if not b.empty? + return sort(b).shift + end + sort(@p).shift + end + # + def test c + @k.a.each do |i| + if @n[i].c == c + return false + end + end + true + end + # + def set_color c + @k.c = c + @k.a.each do |i| + @n[i].f += 1 + end + end + # + def try + while not @p.empty? + if @k.nil? + @k = chose_node + @p.delete @k + end + # puts "try #{@k.to_s}" + co = nil + cs = (@k.c.nil? ? 0 : @k.c ) + (cs..@c).each do |c| + if test c + co = c + break + end + end + if co.nil? + @f << @k + @k = nil + else + set_color co + break + end + end + # @n.each do |n| puts n.inspect end + # puts @k.inspect + # puts 'OK' + true + end + # + def next + # TODO @k might be nil !! + Step.new(@n.inject([]) {|a,n| a << n.clone}, ( (@k.c < @c) ? @c: @c+1)) + end + # +end + +class Graph + # + def initialize p, n, e + @path = p + @n = n + @e = e + @nodes = {} + @edges = [] + @steps = [] + @c = 0 + end + # + def add e + @edges << e + + a, b = *e + a = a.to_i + b = b.to_i + + n = @nodes[a] + if n.nil? + @nodes[a] = Node.new a, b + else + n.add b + end + + n = @nodes[b.to_i] + if n.nil? + @nodes[b] = Node.new b, a + else + n.add a + end + end + # + def solve + s = Step.new(@nodes.values.inject([]) {|a,n| a << n.clone}, @c) + @steps << s + while true + if @steps.empty? + puts 'unsolvable' + return + end + if @steps[-1].try + @steps << @steps[-1].next + if @steps[-1].done? + puts 'success' + return + end + else + @steps.pop + end + end + end + # + def to_s + r = "#{@p}: N:#{@n} E:#{@e}\n" + @nodes.sort_by { |k,v| k } .each do |k,v| + r += " #{v.to_s}\n" + end + r + end + # + def draw + puts "colors : #{@steps[-1].c}" + require 'paleta' + color = Paleta::Color.new(:hex, "0000ff") + colors = Paleta::Palette.generate(:type => :complementary, :from => :color, :color => color, :size => @steps[-1].c).to_array(:rgb) + df = @path+'.dot' + pf = @path+'.png' + open(df,'w') do |f| + f << "graph {\n" + f << "node [style=filled];\n" + @steps[-1].n.each do |n| + f << " #{n.i} [color=\"#{"#%02X%02X%02X" % colors[n.c]}\"]\n" + end + @edges.each do |a,b| + f << " #{a} -- #{b}\n" + end + f << "}\n" + end + system "dot -Tpng -o '#{pf}' '#{df}'" + end + # +end + +def read_graph path + puts "read #{path}…" + g = nil + open(path).read.each_line do |line| + if g.nil? + g = Graph.new path, *line.split + next + end + g.add line.split + end + puts "done." + g +end + +ARGV.each do |path| + + g = read_graph path + g.solve + puts g + g.draw +end + |