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
5

The package OperationsResearchModels.jl also implements the Minimum Spanning Tree with a more clear interface. Here is the usage:

julia> using OperationsResearchModels
julia> conns = Connection[
                       Connection(1, 2, 10),
                       Connection(2, 3, 10),
                       Connection(3, 4, 10),
                       Connection(1, 4, 10)
                   ]
4-element Vector{Connection}:
 Connection(1, 2, 10, "x12")
 Connection(2, 3, 10, "x23")
 Connection(3, 4, 10, "x34")
 Connection(1, 4, 10, "x14")

julia> result = mst(conns)
MstResult(Connection[Connection(3, 4, 10, "x34"), Connection(1, 4, 10, "x14"), Connection(2, 3, 10, "x23")], 30.0)

julia> result.distance
30.0

julia> result.connections
3-element Vector{Connection}:
 Connection(3, 4, 10, "x34")
 Connection(1, 4, 10, "x14")
 Connection(2, 3, 10, "x23")

The Connection struct shows the distance between nodes so Connection(1, 2, 30) means that the distance between nodes 1 and 2 is 30.

6

What algorithm is used to construct this spanning tree? Thx.

7

It implements Prim’s Algorithm. Starts with a random node and continuously adds a node with minimum distance to tree in each single iteration.

1 Like
8

Cool! Does the implementation carry over to parallel decomposed graphs?

1 Like
9

I did nothing for special kind of problems, just as described in Taha’s Operations Research book. The main aim of developing such a package was educational purposes only for the undergrad and grad students which take OR and related courses.

1 Like
10

Cool! Congrats.

1 Like