# Most efficient way to output a cycle starting from an unordered list of graph vertices

I have some graph $G$ and a list of vertices $(v_1, ..., v_N) \in V$. Using graph structures in Mathematica version 9.0, what is the most efficient way to determine whether or not $(v_1, ..., v_N)$ represents a cycle, and then, if so, to output a permutation cycle starting from some desired $v_i$?

Let me provide a specific example:

Say I have a ring of eight vertices where:

$v_1 \to v_2$

$v_2 \to v_3$

$v_3 \to v_4$

$v_4 \to v_5$

$v_5 \to v_6$

$v_6 \to v_7$

$v_7 \to v_8$

$v_8 \to v_1$

And also:

$v_2 \to v_4$

$v_4 \to v_6$

$v_6 \to v_8$

$v_8 \to v_2$

Say the above list is scrambled (i.e. we randomly assign the vertex labels). Without scrambling things here, and specifying that I want a permutation to start from $v_2$, how would I output a permutation:

$(v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_1)$

Scrambling, we could maybe map the labels: $(v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8)$ to something like: $(v_{1111111111}, v_{11011}, v_{111110011}, v_{100101}, v_{11}, v_{1010111}, v_{111}, v_{101010101})$ where the labels convey no ordering information.

-
you can check the link about Ordering vertices in GraphPlot mathematica.stackexchange.com/questions/10755/… –  s.s.o Feb 11 '13 at 15:27
Is your graph directed? –  Szabolcs Feb 11 '13 at 19:43

HamiltonianGraphQ@Subgraph[g, {v1, v2, ...}]


You can use FindHamiltonianCycle to actually find a cycle (an ordering of vertices).

-
Please let me know if I misunderstood. –  Szabolcs Feb 11 '13 at 19:47
Right, calling "FindHamiltonianCycle" solves my problem, though I have a special very easy case of what would otherwise by an NP-complete problem. I suppose I could also cut the connections between a pair of vertices $v_i$ and $v_j$ and then run "FindShortestPath". –  Roger Harris Feb 11 '13 at 22:04
Note that FindHamiltonianCycle is not necessarily slow ("bad" complexity). It is slow for some input graphs, but it isn't for a cycle graph. –  Szabolcs Feb 11 '13 at 22:08
I think I should be able to make my set of vertices a cycle... Do we know the time complexity for "FindHamiltonianCycle" on a cycle graph? –  Roger Harris Feb 11 '13 at 22:53
@Roget I don't know how it is implemented, but it makes sense to assume that it is linear complexity (in the number of nodes). There aren't that many ways to traverse a cycle graphs. If you want to make sure, you can measure directly. –  Szabolcs Feb 11 '13 at 23:12

If you just want to verify a given list of vertices is a cycle, you could define the following function to check it's cycle:

cycleQ[g_, vs_] :=
Block[{edge},
edge = If[DirectedGraphQ[g], DirectedEdge, UndirectedEdge];
VectorQ[Partition[vs, 2, 1, 1], EdgeQ[g, edge @@ #] &]
]


For example,

g = CycleGraph[10];

In[96]:= cycleQ[g, Range[5]]
Out[96]= False

In[97]:= cycleQ[g, Range[10]]
Out[97]= True


To permute the list, you could use RotateLeft or RotateRight with Position:

In[91]:= RotateLeft[{a, b, c, d, e},
Position[{a, b, c, d, e}, d][[1, 1]] - 1]
Out[91]= {d, e, a, b, c}

-
Thanks, the CycleQ[...] function addresses the first part of my question! –  Roger Harris Feb 11 '13 at 14:23
However, let's say the vertices are unordered and not necessarily just connected to their nearest-neighbors in the cycle (i.e. vertex $i$ could be connected to vertex $j$ and $j+1$, etc.). We are only guaranteed that there is a unique solution for the cycle that only uses each vertex once. How would we output a cycle permutation? –  Roger Harris Feb 11 '13 at 14:24