7
$\begingroup$

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"}}]
$\endgroup$
  • 4
    $\begingroup$ FindHamiltonianPath@g? $\endgroup$ – Jason B. Jan 25 '17 at 19:21
  • $\begingroup$ @JasonB It seems I do not have that function in 10.1.0. Any other ideas? $\endgroup$ – Mr.Wizard Jan 25 '17 at 19:31
  • $\begingroup$ Maybe add in Q version dependency. $\endgroup$ – Feyre Jan 25 '17 at 19:48
10
$\begingroup$

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}}

$\endgroup$
  • $\begingroup$ Nice and clean. Thank you. :-) $\endgroup$ – Mr.Wizard Jan 25 '17 at 20:26
11
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ That would not have occurred to me I think. Thanks. $\endgroup$ – Mr.Wizard Jan 25 '17 at 19:47
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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