I'm writing a test suite for a state machine where every state is reachable from every other state except itself by exactly one step, so the state graph of the system is a complete digraph. I'd like to test every possible state transition / edge in the graph. However, each state transition is somewhat costly, which is why I'd like to minimise the number of transitions while still covering all edges. That is, I want to find a path starting from an arbitrary vertex in the graph that'll return to that original vertex after traversing every edge exactly once.
Using intuition and straight up guessing, I came up with the following approach:
Given a list of states (a, b, c, d, and e, for the purpose of an example), generate all rotations of that list, e.g.:
a b c d e
b c d e a
c d e a b
d e a b c
e a b c d
Consider the first element of each rotation to be the state we're currently in, and the other elements to be the "todo list" of other states we still need to reach from there.
a: b c d e
b: c d e a
c: d e a b
d: e a b c
e: a b c d
Now, given any starting state (a for the purpose of the example), you seem to always be able to find a path covering all edges by visiting the next unvisited state in the "todo list" of whichever the current state is. Following that path in the example yields:
a -> b
b -> c
c -> d
d -> e
e -> a
a -> c
c -> e
e -> b
b -> d
d -> a
a -> d
d -> b
b -> e
e -> c
c -> a
a -> e
e -> d
d -> c
c -> b
b -> a
My questions about this are:
There are trivial solutions for 1 and 2 vertices.
Say we have a solution for k vertices, and we want a solution for k+1 vertices.
Let 'A' be the solution for k vertices, which will be a list of vertices with repetition representing the order in which they're visited to traverse every arc once. So for 2 vertices, one valid arrangement would be [1,2,1].
Let 'x' be the new vertex, and let 'z' = A[-1] be the last vertex of A.
Then the solution including x is A, followed by alternating x's and elements of {1-k} \ {z}, and ending with a final x, z once we're done.
Example
[1, 2, 1] # trivial solution for 2.
[1, 2, 1, 3, 2, 3, 1] # 2 => 3
[1, 2, 1, 3, 2, 3, 1, 4, 2, 4, 3, 4, 1] # 3 => 4
[1, 2, 1, 3, 2, 3, 1, 4, 2, 4, 3, 4, 1, 5, 2, 5, 3, 5, 4, 5, 1] # 4 => 5
etc...
This is linear in the output, which is the number of arcs, or for n nodes, O(n * (n-1)) = O(n^2)
Ruby Code:
def f(n)
return [1] if n == 1
arr = [1,2,1]
3.upto(n) do |i|
2.upto(i-1) do |j|
arr.append(i)
arr.append(j)
end
arr.append(i)
arr.append(1)
end
puts arr.to_s
end
f(5) = [1, 2, 1, 3, 2, 3, 1, 4, 2, 4, 3, 4, 1, 5, 2, 5, 3, 5, 4, 5, 1]
f(7) = [1, 2, 1, 3, 2, 3, 1, 4, 2, 4, 3, 4, 1, 5, 2, 5, 3, 5, 4, 5, 1, 6, 2, 6, 3, 6, 4, 6, 5, 6, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7, 6, 7, 1]
Q1) I think your method is sound. The only way it can fail is if you traverse all the arcs in and out of your starting node before traversing all other arcs. You don't need to worry about other nodes since indegree == outdegree, so any node you can enter you can also leave. Assuming we take your approach but with numbers, we start at 1, so our grid is:
1) 2, 3, ..., n
2) 3, 4, ..., n, 1
3) 4, 5, ..., n, 1, 2
...
n) 1, 2, ..., n-1
There are n-1 arcs into 1. One of them is from 2, which we only hit after entering 2 n-1 times. But to do that, we need to get the node visited from 3, which requires visiting 3 n-1 times, and so on...
This is an idea sketch not a proof, but I think this could be extended to a proof showing that before you visit 1 n-1 times, you need to visit every other vertex n-1 times, and there are no duplicate arcs possible in your approach, so every arc has been traversed exactly once.