Minimum Spanning Tree

General Usage
1

Hi everyone, I want the vectors combination of a minimum spanning tree. I don’t think that I was very clear, but its like the following example, I have this array, generated by the function kruskal_mst from the LightGraphs package:
12-element Array{Array{Int64,1},1}:
[1, 2]
[2, 3]
[3, 4]
[3, 8]
[4, 5]
[4, 6]
[6, 7]
[8, 9]
[9, 10]
[10, 11]
[11, 12]
[12, 13]
But the result I want is this one (some of the combinations that I saw):
[1, 2, 3, 4, 5]
[1, 2, 3, 8, 9, 10, 11, 12, 13]
[1, 2, 3, 4, 6, 7]
[7, 6, 4, 3, 8, 9, 10, 11, 12, 13]

What I coded until now is a great mess that only combine, sometimes wrongly, some of the vertices of the initial array, so I’m asking if anyone knows anything that can do what I want.

2

Just off the top of my head (and if I’m understanding the problem correctly), what you want to do is create the subgraph with those array elements as edges, and then use something like dfs to pull out all the paths. That’s going to be very expensive, I think, and I don’t have a quick solution in code for this right now. (The new 1.4.0 / 2.0.0 code should make this easier but it’s not ready for prime time yet.)

3

Yes, even though i was trying to make it hard, you do get it, I was wanting a array with all possible paths.

Thanks for the information.

4

So, something to try:

h = DiGraph(nv(g))
for e in kruskal_mst(g)
    add_edge!(h, e)
end
f = floyd_warshall_shortest_paths(h)
p = enumerate_paths(f)

and then see what you can do with that output.

1 Like