color_graph.rb - coloring bipartite graphs.

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

https://twitter.com/hyuki/status/1281555790537437185