Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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).

share|improve this answer
    
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
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 '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
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}
share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.