Discrete : wip-worktree-statedescrete

6 files changed, 261 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
+
diff --git a/02-graph-coloring/README b/02-graph-coloring/README
new file mode 100644
index 0000000..76ff5f0
--- /dev/null
+++ b/02-graph-coloring/README
@@ -0,0 +1,15 @@
+
+break symetries (colours are interchangeable);
+   - max colour + 1
+
+try first where you fail:
+   - nodes with bigger degree && less possible colour
+
+think about distinct graphs:
+   - ??
+
+a step is:
+   - possible nodes
+   - failed nodes
+   - chosen node
+
diff --git a/02-graph-coloring/data/gc_4_1.dot b/02-graph-coloring/data/gc_4_1.dot
new file mode 100644
index 0000000..32b343b
--- /dev/null
+++ b/02-graph-coloring/data/gc_4_1.dot
@@ -0,0 +1,10 @@
+graph {
+node [style=filled];
+ 0 [color="#FFFF00"]
+ 1 [color="#0000FF"]
+ 2 [color="#FFFF00"]
+ 3 [color="#FFFF00"]
+ 0 -- 1
+ 1 -- 2
+ 1 -- 3
+}
diff --git a/02-graph-coloring/data/gc_4_1.png b/02-graph-coloring/data/gc_4_1.png
new file mode 100644
index 0000000..b783995
--- /dev/null
+++ b/02-graph-coloring/data/gc_4_1.png
diff --git a/02-graph-coloring/draw b/02-graph-coloring/draw
new file mode 100755
index 0000000..656c60b
--- /dev/null
+++ b/02-graph-coloring/draw
@@ -0,0 +1,7 @@
+#! /bin/bash
+
+for data in ./data/*; do
+   echo "draw $data …"
+   cat $data | sed -e '1agraph G {' -e '1d; s/ / -- /; s/$/;/' -e '$a}' | dot -Tpng -o ${data}.png
+done
+
diff --git a/02-graph-coloring/gc_20_1.png b/02-graph-coloring/gc_20_1.png
new file mode 100644
index 0000000..20eac27
--- /dev/null
+++ b/02-graph-coloring/gc_20_1.png