current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
up vote 4 down vote favorite

While working to self-answer FindCurvePath for lines (rather than points) using Graph functions I came upon a seemingly silly conundrum: how do I programmatically list the vertex names of a PathGraph-like-graph in order? For example I have:

enter image description here

How can I extract {9, 10, 1, 2, 4, ..., 41, 34, 33} from this?

I am using version 10.1.0 and I do not have FindHamiltonianPath as proposed by Jason. I suppose that is the canonical approach in recent versions.

Code:

Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 
  22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 
  42, 43, 44}, {Null, 
  SparseArray[Automatic, {44, 44}, 
   0, {1, {{0, 2, 4, 6, 8, 10, 12, 14, 16, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 
      37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 64, 66, 68, 70, 72, 
      74, 76, 78, 80, 82, 84, 
      86}, {{2}, {10}, {1}, {4}, {4}, {8}, {2}, {3}, {6}, {24}, {5}, {7}, {6}, {8}, \
{3}, {7}, {10}, {1}, {9}, {12}, {20}, {11}, {16}, {14}, {15}, {13}, {18}, {13}, \
{16}, {12}, {15}, {18}, {22}, {14}, {17}, {20}, {42}, {11}, {19}, {22}, {28}, {17}, \
{21}, {24}, {25}, {5}, {23}, {23}, {26}, {25}, {29}, {28}, {32}, {21}, {27}, {26}, \
{30}, {29}, {37}, {32}, {36}, {27}, {31}, {34}, {33}, {41}, {36}, {44}, {31}, {35}, \
{30}, {38}, {37}, {39}, {38}, {40}, {39}, {43}, {34}, {42}, {19}, {41}, {40}, {44}, \
{35}, {43}}}, Pattern}]}, {VertexLabels -> {"Name"}}]
share|improve this question
3  
FindHamiltonianPath@g? – Jason B. 12 hours ago
    
@JasonB It seems I do not have that function in 10.1.0. Any other ideas? – Mr.Wizard♦ 12 hours ago
    
Maybe add in Q version dependency. – Feyre 12 hours ago
up vote 8 down vote

You could use DepthFirstScan:

Choose the starting vertex:

svertex = Cases[VertexList[g], x_ /; VertexDegree[g, x] == 1]

{9, 33}

Extract the order of vertices:

Reap[DepthFirstScan[g, 
    svertex[[1]], {"PrevisitVertex" -> (Sow[#] &)}];][[2, 1]]

{9, 10, 1, 2, 4, 3, 8, 7, 6, 5, 24, 23, 25, 26, 29, 30, 37, 38, 39, 40, 43, 44, 35, 36, 31, 32, 27, 28, 21, 22, 17, 18, 14, 13, 15, 16, 12, 11, 20, 19, 42, 41, 34, 33}

share|improve this answer
    
That would not have occurred to me I think. Thanks. – Mr.Wizard♦ 12 hours ago
up vote 7 down vote

We can use GraphPeriphery to get the start and endpoints, and then use these in FindPath:

periphery = GraphPeriphery[g]

FindPath[g, ##]& @@ periphery

{9,33}

{{9,10,1,2,4,3,8,7,6,5,24,23,25,26,29,30,37,38,39,40,43,44,35,36,31,32,27,28,21,22,17,18,14,13,15,16,12,11,20,19,42,41,34,33}}

share|improve this answer
    
Nice and clean. Thank you. :-) – Mr.Wizard♦ 11 hours ago
up vote 3 down vote

If g is the graph from the OP, then you can do this in versions 9 through 11

combGrData = {EdgeRules@g, 
    GraphEmbedding@g} /. {{a_Real, b_Real} :> {{a, b}}, 
    HoldPattern@Rule[a__] :> {{a}}};
<< Combinatorica`
Graph @@ combGrData // HamiltonianPath

(* {9, 10, 1, 2, 4, 3, 8, 7, 6, 5, 24, 23, 25, 26, 29, 30, 37, 38, 39, 
    40, 43, 44, 35, 36, 31, 32, 27, 28, 21, 22, 17, 18, 14, 13, 15, 16, 
    12, 11, 20, 19, 42, 41, 34, 33}

If someone can explain the SetDelayed error I get in version 11 I'd be much abliged.

share|improve this answer

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.