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

$\endgroup$
  • $\begingroup$ For your graph, VertexList[tree] does the right thing... $\endgroup$ – Igor Rivin Sep 23 '14 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 '14 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 '14 at 12:47
  • $\begingroup$ @IgorRivin I've added some clarification. $\endgroup$ – Esse Sep 23 '14 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 '14 at 14:41
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

$\endgroup$
  • $\begingroup$ runs like a charm - thank you very much! $\endgroup$ – Esse Sep 24 '14 at 14:37
  • $\begingroup$ +1 p.s. That's quite nice form of your roots function: Pick[VertexList[#], VertexDegree[#], 1]& $\endgroup$ – Kuba Nov 17 '15 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?

$\endgroup$
  • $\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 '14 at 13:07
  • $\begingroup$ @MarkMcClure See the edit for a more elegant solution, sorry. $\endgroup$ – Igor Rivin Sep 23 '14 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 '14 at 13:50

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.