Calculate minimum distances to meaningful nodes in transformation graph

3 files changed, 98 insertions, 5 deletions

diff --git a/dot.lua b/dot.lua
index 8ef5685..b9c6fee 100755
--- a/dot.lua
+++ b/dot.lua
@@ -1,10 +1,7 @@
 #!/usr/bin/env lua
 local automaton = require "automaton"
-local init = {}
-for i=1, 25 do
-	table.insert(init, i)
-end
-init = automaton(init)
+local generate = require "generate"
+local init = automaton(generate.trange(1, 25))
 
 
 local function dump_edges (state, prefix, color)
diff --git a/generate.lua b/generate.lua
new file mode 100644
index 0000000..f046356
--- /dev/null
+++ b/generate.lua
@@ -0,0 +1,33 @@
+local function next_number (last, current)
+	current = current + 1
+	if current > last then
+		return nil
+	end
+	return current
+end
+
+
+local function range (first, last)
+	if first > last then
+		error "start of range must be less or equal to last value"
+	end
+	return next_number, last, first - 1
+end
+
+
+local generate = {
+	next_number = next_number,
+	range = range,
+}
+
+
+function generate.trange (first, last)
+	local x = {}
+	for i in range(first, last) do
+		table.insert(x, i)
+	end
+	return x
+end
+
+
+return generate
diff --git a/graph.lua b/graph.lua
new file mode 100755
index 0000000..1feefd1
--- /dev/null
+++ b/graph.lua
@@ -0,0 +1,63 @@
+#!/usr/bin/env lua
+local automaton = require "automaton"
+local generate = require "generate"
+local init = automaton(generate.trange(1, 25))
+
+
+local function node (graph, id)
+	local x = graph.nodes[id]
+	if x then
+		return x
+	end
+	x = {
+		id = id,
+		outcoming = {},
+		incoming = {},
+		distance = {},
+	}
+	graph.nodes[id] = x
+	return x
+end
+
+
+local function add_edges (graph, state, kind)
+	for dst, src in ipairs(state) do
+		local a = node(graph, src)
+		local b = node(graph, dst)
+		a.outcoming[kind] = b
+		b.incoming[kind] = a
+	end
+end
+
+
+local graph = {
+	nodes = {},
+}
+add_edges(graph, init:left(), "left")
+add_edges(graph, init:right(), "right")
+add_edges(graph, init:pivot(), "centre")
+add_edges(graph, init:up(), "up")
+add_edges(graph, init:down(), "down")
+
+
+local function calculate_distances_from (start)
+	local visited = {}
+	local queue = {{node=start, distance=0}}
+	while #queue > 0 do
+		local step = table.remove(queue, 1)
+		if not visited[step.node.id] then
+			step.node.distance[start.id] = step.distance
+			for _, x in pairs(step.node.incoming) do
+				table.insert(queue, {node=x, distance=step.distance+1})
+			end
+			visited[step.node.id] = true
+		end
+	end
+end
+
+
+calculate_distances_from(graph.nodes[3])
+calculate_distances_from(graph.nodes[19])
+for _, v in ipairs(graph.nodes) do
+	print(v.id, v.distance[3], v.distance[19])
+end