hyuki/color_graph.rb

## color_graph.rb
#!/usr/bin/env ruby
# See 「数学ガールの秘密ノート」第296回 https://link.hyuki.net/girlnote296
# by Hiroshi Yuki.

class Graph

  def info(depth, s)
    puts ' ' * depth + s
  end

  def another_color(color)
    case color
    when :white
      :black
    when :black
      :white
    else
      abort "another_color error."
    end
  end

  def push(u)
    @stack.push(u)
    # puts "#{u[:name]} is pushed. Stack is now [ #{@stack.map{|v| v[:name] }.join(', ')} ]."
  end

  def pop(expected)
    u = @stack.pop
    # puts "#{u[:name]} is popped. Stack is now [ #{@stack.map{|v| v[:name] }.join(', ')} ]."
    if u != expected
      abort "Unexpected result: #{u[:name]} is popped from the stack, but it should be = #{expected[:name]}"
    end
  end

  def show_cycle_in_stack
    a = []
    @stack.reverse.each do |v|
      a << v
      break if a.size > 1 and a[0] == v
    end
    puts a.map {|v| "#{v[:name]}(#{v[:color]})"}.join(' - ')
  end

  def show_coloring
    puts "White vertices are " + @vertices.values.select { |v| v[:color] == :white }.map {|v| v[:name] }.join(',') + "."
    puts "Black vertices are " + @vertices.values.select { |v| v[:color] == :black }.map {|v| v[:name] }.join(',') + "."
  end

  def color_graph
    info 0,"Start coloring #{@name}."
    @vertices.values.each do |v|
      v[:color] = nil
    end
    @vertices.values.each do |v|
      if not v[:color]
        info 0,"#{v[:name]} is not colored. Start coloring #{v[:name]} deeply."
        if not color_dfs(1, v, :white)
          info 0,"Graph #{@name} cannot be colored."
          return false
        end
      else
        info 0,"#{v[:name]} is already colored. No need coloring."
      end
    end
    info 0,"Graph #{@name} is colored."
    show_coloring
    return true
  end

  def color_dfs(depth, u, color)
    push(u)
    if not u[:color]
      info depth,"#{u[:name]} is not colored yet."
      info depth,"#{u[:name]} is has #{u[:adj].size} adjacents."
      u[:color] = color
      info depth,"#{u[:name]} is colored in #{u[:color]}."
      u[:adj].each do |v|
        if not color_dfs(depth + 1, v, another_color(color))
          return false
        end
      end
      info depth,"#{u[:name]} is deeply colored successfully."
      pop(u)
      return true
    elsif u[:color] == color
      info depth,"#{u[:name]} is already colored in #{u[:color]}, and it is consistent."
      pop(u)
      return true
    else
      info depth,"#{u[:name]} is already colored in #{u[:color]}, but it should be colored in #{color}, failed."
      puts "I found an odd cycle as follows:"
      show_cycle_in_stack
      pop(u)
      return false
    end
  end

  def initialize(name, edgelist)
    @name = name
    @vertices = {}
    @stack = []
    edgelist.each do |link|
      if link.match(/^([^-]+)-([^-]+)$/)
        uname = $1.to_s
        vname = $2.to_s
        abort if uname == vname
        u = @vertices[uname]
        if not u
          u = { :name => uname, :adj => [] }
          @vertices[uname] = u
        end
        v = @vertices[vname]
        if not v
          v = { :name => vname, :adj => [] }
          @vertices[vname] = v
        end
        u[:adj] << v
        v[:adj] << u
      end
    end
  end
end

puts
Graph.new("sample", [
  "1-2", "2-3",
  "4-5", "5-6", "5-8", "4-7", "7-8",
]).color_graph
puts "↑「数学ガールの秘密ノート」第296回の例 https://link.hyuki.net/girlnote296"

puts
Graph.new("oddCycledGraph", [
  "A-B",
  "B-C",
  "C-A",
]).color_graph
puts "↑奇数のサイクルがあるから色分けできない例"

puts
Graph.new("evenCycledGraph", [
  "A-B",
  "B-C",
  "C-D",
  "D-A",
]).color_graph
puts "↑偶数のサイクルだから色分けできる例"

puts
Graph.new("rhoGraph", [
  "A-B",
  "B-C",
  "C-D",
  "D-B",
]).color_graph
puts "↑ρの文字のように途中にサイクルができる例"

puts
Graph.new("binaryTree", [
  "1-11",
  "1-12",
  "11-111",
  "11-112",
  "12-121",
  "12-122",
  "111-1111",
  "111-1112",
]).color_graph
puts "↑名前の長さの偶奇で色分けされてる（ツリーの深さ）"
puts

Graph.new("cube", [
  "000-001",
  "000-010",
  "000-100",
  "001-011",
  "001-101",
  "010-011",
  "010-110",
  "100-101",
  "100-110",
  "011-111",
  "101-111",
  "110-111",
]).color_graph
puts "↑パリティになっている例"
puts

Graph.new("forest", [
  "A-B",
  "B-C",
  "C-D",
  "D-A",
  "X-Y",
  "X-Z",
  "Y-W",
  "Y-U",
]).color_graph
puts "↑二つの連結成分からなる例"
puts

srand(314)
s = []
100.times do |n|
  a = ('A'.ord + rand(26)).chr
  b = ('a'.ord + rand(26)).chr
  s << "#{a}-#{b}"
end
Graph.new("bigPartite", s).color_graph
puts "↑ランダムな二部グラフ（大文字と小文字の間のみに辺がある）"
puts
	#!/usr/bin/env ruby
	# See 「数学ガールの秘密ノート」第296回 https://link.hyuki.net/girlnote296
	# by Hiroshi Yuki.

	class Graph

	def info(depth, s)
	puts ' ' * depth + s
	end

	def another_color(color)
	case color
	when :white
	:black
	when :black
	:white
	else
	abort "another_color error."
	end
	end

	def push(u)
	@stack.push(u)
	# puts "#{u[:name]} is pushed. Stack is now [ #{@stack.map{\|v\| v[:name] }.join(', ')} ]."
	end

	def pop(expected)
	u = @stack.pop
	# puts "#{u[:name]} is popped. Stack is now [ #{@stack.map{\|v\| v[:name] }.join(', ')} ]."
	if u != expected
	abort "Unexpected result: #{u[:name]} is popped from the stack, but it should be = #{expected[:name]}"
	end
	end

	def show_cycle_in_stack
	a = []
	@stack.reverse.each do \|v\|
	a << v
	break if a.size > 1 and a[0] == v
	end
	puts a.map {\|v\| "#{v[:name]}(#{v[:color]})"}.join(' - ')
	end

	def show_coloring
	puts "White vertices are " + @vertices.values.select { \|v\| v[:color] == :white }.map {\|v\| v[:name] }.join(',') + "."
	puts "Black vertices are " + @vertices.values.select { \|v\| v[:color] == :black }.map {\|v\| v[:name] }.join(',') + "."
	end

	def color_graph
	info 0,"Start coloring #{@name}."
	@vertices.values.each do \|v\|
	v[:color] = nil
	end
	@vertices.values.each do \|v\|
	if not v[:color]
	info 0,"#{v[:name]} is not colored. Start coloring #{v[:name]} deeply."
	if not color_dfs(1, v, :white)
	info 0,"Graph #{@name} cannot be colored."
	return false
	end
	else
	info 0,"#{v[:name]} is already colored. No need coloring."
	end
	end
	info 0,"Graph #{@name} is colored."
	show_coloring
	return true
	end

	def color_dfs(depth, u, color)
	push(u)
	if not u[:color]
	info depth,"#{u[:name]} is not colored yet."
	info depth,"#{u[:name]} is has #{u[:adj].size} adjacents."
	u[:color] = color
	info depth,"#{u[:name]} is colored in #{u[:color]}."
	u[:adj].each do \|v\|
	if not color_dfs(depth + 1, v, another_color(color))
	return false
	end
	end
	info depth,"#{u[:name]} is deeply colored successfully."
	pop(u)
	return true
	elsif u[:color] == color
	info depth,"#{u[:name]} is already colored in #{u[:color]}, and it is consistent."
	pop(u)
	return true
	else
	info depth,"#{u[:name]} is already colored in #{u[:color]}, but it should be colored in #{color}, failed."
	puts "I found an odd cycle as follows:"
	show_cycle_in_stack
	pop(u)
	return false
	end
	end

	def initialize(name, edgelist)
	@name = name
	@vertices = {}
	@stack = []
	edgelist.each do \|link\|
	if link.match(/^([^-]+)-([^-]+)$/)
	uname = $1.to_s
	vname = $2.to_s
	abort if uname == vname
	u = @vertices[uname]
	if not u
	u = { :name => uname, :adj => [] }
	@vertices[uname] = u
	end
	v = @vertices[vname]
	if not v
	v = { :name => vname, :adj => [] }
	@vertices[vname] = v
	end
	u[:adj] << v
	v[:adj] << u
	end
	end
	end
	end

	puts
	Graph.new("sample", [
	"1-2", "2-3",
	"4-5", "5-6", "5-8", "4-7", "7-8",
	]).color_graph
	puts "↑「数学ガールの秘密ノート」第296回の例 https://link.hyuki.net/girlnote296"

	puts
	Graph.new("oddCycledGraph", [
	"A-B",
	"B-C",
	"C-A",
	]).color_graph
	puts "↑奇数のサイクルがあるから色分けできない例"

	puts
	Graph.new("evenCycledGraph", [
	"A-B",
	"B-C",
	"C-D",
	"D-A",
	]).color_graph
	puts "↑偶数のサイクルだから色分けできる例"

	puts
	Graph.new("rhoGraph", [
	"A-B",
	"B-C",
	"C-D",
	"D-B",
	]).color_graph
	puts "↑ρの文字のように途中にサイクルができる例"

	puts
	Graph.new("binaryTree", [
	"1-11",
	"1-12",
	"11-111",
	"11-112",
	"12-121",
	"12-122",
	"111-1111",
	"111-1112",
	]).color_graph
	puts "↑名前の長さの偶奇で色分けされてる（ツリーの深さ）"
	puts

	Graph.new("cube", [
	"000-001",
	"000-010",
	"000-100",
	"001-011",
	"001-101",
	"010-011",
	"010-110",
	"100-101",
	"100-110",
	"011-111",
	"101-111",
	"110-111",
	]).color_graph
	puts "↑パリティになっている例"
	puts

	Graph.new("forest", [
	"A-B",
	"B-C",
	"C-D",
	"D-A",
	"X-Y",
	"X-Z",
	"Y-W",
	"Y-U",
	]).color_graph
	puts "↑二つの連結成分からなる例"
	puts

	srand(314)
	s = []
	100.times do \|n\|
	a = ('A'.ord + rand(26)).chr
	b = ('a'.ord + rand(26)).chr
	s << "#{a}-#{b}"
	end
	Graph.new("bigPartite", s).color_graph
	puts "↑ランダムな二部グラフ（大文字と小文字の間のみに辺がある）"
	puts