Skip to content

Instantly share code, notes, and snippets.

@belkadan
Last active August 29, 2015 13:57
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save belkadan/c3005d4e2574c2d9928f to your computer and use it in GitHub Desktop.
Save belkadan/c3005d4e2574c2d9928f to your computer and use it in GitHub Desktop.
Hacked-up code to three-color the Sonobe Model.
# Hardcode the faces of a dodecahedron.
# http://mathworld.wolfram.com/DodecahedralGraph.html
Faces = [
[0, 1, 2, 3, 4],
[0, 1, 7, 6, 5],
[1, 2, 9, 8, 7],
[2, 3, 11, 10, 9],
[3, 4, 13, 12, 11],
[4, 0, 5, 14, 13],
[5, 6, 15, 19, 14],
[7, 8, 16, 15, 6],
[9, 10, 17, 16, 8],
[11, 12, 18, 17, 10],
[13, 14, 19, 18, 12],
[15, 16, 17, 18, 19]
]
# Take a graph of faces and make a "spike graph" out of them.
# This involves taking each vertex and making a copy of it
# for each face it appears in, then connecting the new vertices
# that came from the same original vertex.
def make_spike_graph(faces)
# Note: hardcoded to only handle graphs where each vertex appears in three faces.
counts = [0] * (faces.flatten.max + 1)
new_graph = [nil] * counts.count * 3
# First make faces in the new graph.
faces.each do |face|
new_face = []
face.each do |i|
current_count = counts[i]
counts[i] += 1
new_face << i * 3 + current_count
end
(0...new_face.size).each do |i|
new_graph[new_face[i]] = [new_face[i-1], new_face[(i+1) % new_face.size]]
end
end
# Consistency-check the new graph.
raise if counts.any? { |x| x != 3 }
raise if new_graph.flatten.uniq.size != new_graph.flatten.size/2
# Then add edges between new-vertices that came from the same original vertex.
new_graph.each_with_index do |edges, i|
major, minor = i.divmod(3)
major *= 3
edges << major + (minor + 1) % 3
edges << major + (minor + 2) % 3
end
return new_graph
end
# Generate the graph of spikes.
# https://math.lsu.edu/~verrill/origami/sonobe/instructions/
Graph = make_spike_graph(Faces)
# Consistency check: all edges should be symmetric.
Graph.each_with_index do |edges, i|
edges.each do |j|
puts "#{i} -> #{j}" unless Graph[j].member?(i)
raise unless Graph[j].member?(i)
end
end
# Brute-force color the graph, given a current coloring
# and a queue of neighboring vertices that haven't been colored.
def try_coloring(colors, queue)
queue = queue.dup
# Find the first vertex in the queue that hasn't been colored.
# This can happen when we've already reached it by another path.
i = loop do
return colors if queue.empty?
i = queue.pop
break i if colors[i].nil?
end
# Find out which colors are available. If none, this coloring fails.
adj = Graph[i]
available_colors = (0..2).to_a - adj.map { |j| colors[j] }
return nil if available_colors.empty?
# Otherwise, get ready to color other neighboring uncolored faces...
queue += adj.select { |j| colors[j].nil? }
# ...and try each color.
colors = colors.dup
available_colors.each do |color|
colors[i] = color
result = try_coloring(colors, queue)
return result if result
end
# If none of the colors worked, this coloring fails.
return nil
end
# Start with no colors, except that node 0 is color 0.
colors = [nil] * Graph.count
colors[0] = 0
result = try_coloring(colors, Graph[0])
puts(result.to_s)
# Verify the result: no colors should be neighboring.
Graph.each_with_index do |edges, i|
edges.each do |j|
raise if result[j] == result[i]
end
end if result
# The rest of this file is all about writing the result out to a file.
# Calculate a nice position for face-vertex #i.
#
# We find the location of the original vertex in the dodecahedral graph,
# then spread out the three faces that started at that vertex into a
# little triangle.
def coords(i)
# The "major" coordinate determines which ring the point is on,
# and where it is on the ring.
major = i / 3
scale, theta = case major
when 0..4
[1, major / 5.0]
when 5..14
if major.odd?
[0.7, (major-5) / 10.0]
else
[0.50, (major-10) / 10.0 + 1.5]
end
when 15..19
[0.25, (major-15) / 5.0 + 0.1]
end
theta *= 2 * Math::PI
theta -= (0.85 * Math::PI)
result = [scale * Math::cos(theta), scale * Math::sin(theta)]
# The minor coordinate determines how to draw the little triangle.
# I fudged this to get a non-overlapping graph; the ifs are just
# trial and error to get something pretty
minor = i % 3
if (major > 0 && major < 5) || (major >= 5 && major < 14 && major.even?)
if minor == 1
minor = 2
elsif minor == 2
minor = 1
end
elsif major == 5 || major == 19
if minor == 0
minor = 1
elsif minor == 1
minor = 0
end
end
# Notice that the minor orientation change is relative to the
# major orientation, theta.
orientation = minor * 2 / 3.0 * Math::PI + theta
case major
when 0..4
# do nothing
when 5..14
orientation += -0.33 * Math::PI if major.odd?
when 15..19
orientation += -0.33 * Math::PI
end
result[0] += 0.05 * Math::cos(orientation)
result[1] += 0.05 * Math::sin(orientation)
return result
end
# Write to an SVG file!
# ...using https://github.com/aseldawy/rasem
require 'rasem'
ColorNames = ['green', 'purple', 'orange']
File.open('/Users/jrose/Desktop/graph.svg', 'w') do |f|
Rasem::SVGImage.new(420,420,f) do |f|
def scale(xy)
return xy.map {|x| x*190.0 + 210.0 }
end
# First draw lines between the face-vertices.
Graph.each_with_index do |edges, i|
edges.each do |j|
line *scale(coords(i)), *scale(coords(j)), :stroke=>'grey'
end
end
# Then draw the vertices themselves, and color them.
(0...Graph.count).each do |i|
fill = if result then ColorNames[result[i]] else 'black' end
circle *scale(coords(i)), 3, :fill=>fill
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment