Created
July 10, 2020 11:44
-
-
Save hyuki/a0285da6f334ae7f63ac9ccf1abb7241 to your computer and use it in GitHub Desktop.
color_graph.rb - coloring bipartite graphs.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |
Author
hyuki
commented
Jul 10, 2020
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment