# 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 at 15:27
Is your graph directed? – Szabolcs Feb 11 at 19:43

## 2 Answers

If I am reading your question correctly, you are looking for

````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 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 at 22:04

1
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 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 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 at 23:12
show 2 more comments

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 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 at 14:24
lang-mma
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 25, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8717896938323975, "perplexity_flag": "middle"}