Hacked-up code to three-color the Sonobe Model.

graph.rb

# 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