2
$\begingroup$

I've got spanning tree for some weighted graph (edges labeled 1-6) - for example:

graphMatrix = {{0, 0.140892, 0.298153, 1.13827, 1.27866, 1.4}, {0.140892, 0, 
0.167897, 1.16492, 1.3422, 1.49614}, {0.298153, 0.167897, 0, 
1.13035, 1.35045, 1.54743}, {1.13827, 1.16492, 1.13035, 0, 0.375184,
0.773562}, {1.27866, 1.3422, 1.35045, 0.375184, 0, 0.412249}, {1.4,
1.49614, 1.54743, 0.773562, 0.412249, 0}};

graph = Graph[WeightedAdjacencyGraph[graphMatrix], 
  VertexLabels -> "Name"];
tree = Graph[FindSpanningTree[graph], VertexLabels -> "Name"]

How can I get vertices of tree in order in which they appear in this tree?

(In this case it should be {1,2,3,4,5,6}).

Edit: Second example, when given such tree:

quite specific tree

Result should be {68, 2, 193, 88, 129, …} or {197, 198, …}

Improve this question
$\endgroup$
5
  • $\begingroup$ For your graph, VertexList[tree] does the right thing... $\endgroup$
    – Igor Rivin
    Sep 23, 2014 at 10:36
  • $\begingroup$ VertexList[tree] will always return all vertices with normal ordering (1,2,3,…) - even if tree is something like (3 -> 1, 1 -> 2). $\endgroup$
    – Esse
    Sep 23, 2014 at 12:40
  • $\begingroup$ Notice that there is no canonical ordering on trees that I am aware of, so what would you expect? $\endgroup$
    – Igor Rivin
    Sep 23, 2014 at 12:47
  • $\begingroup$ @IgorRivin I've added some clarification. $\endgroup$
    – Esse
    Sep 23, 2014 at 14:39
  • $\begingroup$ Esse, VertexList returns all vertices in the order they are appear in the input to Graph. So, if you don't use an explicit vertex list as the first argument in Graph VertexList gives the vertices in the order they appear in the edge list you enter as the first argument of Graph. Try, for example, g= Graph[{3 -> 1, 1 -> 2}]; VertexList[g]. $\endgroup$
    – kglr
    Sep 23, 2014 at 14:41

2 Answers 2

Reset to default
2
$\begingroup$

If your graph is a path graph, only thing you need to do is finding root (starting vertex). Once you find root, you could do DepthFirstScan (like Igor Rivin suggested), BreadthFirstScan, VertexComponent, etc...

For example:

g = PathGraph[RandomSample[Range[100], 100], VertexLabels -> "Name"]

enter image description here

roots = VertexList[g][[Flatten[Position[VertexDegree[g], 1]]]]

{21, 83}

r1 = Reap[DepthFirstScan[g, roots[[1]], {"PrevisitVertex" -> Sow}]][[2, 1]]

{21, 12, 5, 6, 97, 99, 29, 47, 96, 10, 26, 14, 56, 78, 46, 44, 70, 92, 42, 24, 91, 16, 40, 87, 65, 48, 77, 79, 69, 31, 43, 85, 9, 3, 64, 35, 58, 7, 67, 81, 60, 20, 8, 19, 36, 11, 13, 86, 90, 62, 4, 53, 84, 51, 52, 22, 72, 88, 2, 95, 30, 18, 1, 61, 93, 45, 80, 34, 39, 37, 25, 50, 75, 68, 71, 27, 32, 49, 82, 73, 57, 100, 28, 17, 76, 55, 59, 15, 74, 54, 41, 94, 89, 66, 23, 98, 63, 38, 33, 83}

r2 = Reap[
   BreadthFirstScan[g, roots[[1]], {"PrevisitVertex" -> Sow}]][[2, 1]]

r3 = VertexComponent[g, 21]

r1 == r2 == r3

True

Improve this answer
$\endgroup$
2
  • $\begingroup$ runs like a charm - thank you very much! $\endgroup$
    – Esse
    Sep 24, 2014 at 14:37
  • $\begingroup$ +1 p.s. That's quite nice form of your roots function: Pick[VertexList[#], VertexDegree[#], 1]& $\endgroup$
    – Kuba ♦
    Nov 17, 2015 at 12:12
1
$\begingroup$

What you want is DepthFirstScan, as in:

vlist = {}
DepthFirstScan[tree, 1, {"PrevisitVertex"-> (vlist = Append[vlist, #]&)}]

UPDATE

As Mark points out, that does not work, what does work (almost) is

Reap[DepthFirstScan[tree2, 1, {"PrevisitVertex" -> Sow}]]

However, this will give non-leaf vertices multiple times. What do you actually want it to do?

Improve this answer
$\endgroup$
3
  • $\begingroup$ I get a sequence of errors of the form: Function::flpar: Parameter specification Append[vlist,#1] in Function[Append[vlist,#1],1] should be a symbol or a list of symbols. >> I guess this can be fixed using SetDelayed rather than Set. $\endgroup$
    – Mark McClure
    Sep 23, 2014 at 13:07
  • $\begingroup$ @MarkMcClure See the edit for a more elegant solution, sorry. $\endgroup$
    – Igor Rivin
    Sep 23, 2014 at 13:21
  • $\begingroup$ I'e added some clarification - I'm interested in some particular trees, with only one branch (in other words where such ordering occurs). $\endgroup$
    – Esse
    Sep 23, 2014 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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