Using Kruskal algorithm for Minimum Spanning Forest

[Torsten Knüppel]

Hi,

I'd like to compute a minimal spanning forest of a given graph using e.g. Kruskal's algorithm.

I managed to create a graph, but I don't know how to apply Kruskal. If I understand correctly, the documentation (https://pkg.go.dev/gonum.org/v1/gonum/graph/path#Kruskal) says, that as an output, I need an object that implements the WeightBuilder-interface.
Do I need to write my own type that implements this interface or is there already something I can use? If yes, is there a recommend way to find a useful type - the vast amount of types and functions is hard to grasp for me.

Eventually, I need separate Minimum Spanning Trees.
From what I understand,  Kruskal is is giving me a graph (not necessarily connected) that is a Minimum Spanning Forest - is there a chance to immediately get a slice of connected MS trees.

If not, my idea was to use the connected components method from the topo package (https://pkg.go.dev/gonum.org/v1/gonum/graph/topo#ConnectedComponents) and apply it to the result of Kruskal. This gives me a  slice of nodes for each component - is there a function to use each slice and get a subgraph of the initial graph? Or do I need to construct the graphs manually?

Thanks
Torsten

P.S. Here a small code snippet for illustration

package main

import (
"fmt"

"gonum.org/v1/gonum/graph/simple"
"gonum.org/v1/gonum/graph/topo"
)

type Edge struct {
thing_1 ThingType
thing_2 ThingType
weight float64
}

type ThingType uint64

type ThingNode struct {
id int64
thing ThingType
}

func (tn ThingNode) ID() int64 {
return tn.id
}

func main() {

edges := make([]Edge, 0)
edges = append(edges, Edge{10, 12, 1})
edges = append(edges, Edge{10, 13, 2})
edges = append(edges, Edge{10, 14, 1})
edges = append(edges, Edge{12, 14, 5})
edges = append(edges, Edge{14, 16, 1})
edges = append(edges, Edge{16, 18, 2})
edges = append(edges, Edge{26, 28, 2})

_, syncGraph := createGraph(edges)

// var msForest simple.WeightedUndirectedGraph
// path.Kruskal(&msForest, syncGraph)
// fmt.Println(msForest)

connectedComponents := topo.ConnectedComponents(syncGraph)
fmt.Println(connectedComponents)
}

func createGraph(edges []Edge) (map[ThingType]ThingNode, *simple.WeightedUndirectedGraph) {
syncGraph := simple.NewWeightedUndirectedGraph(0, 1)
// Map to map initial graph nodes to densely numbered nodes
nodes := make(map[ThingType]ThingNode)
index := int64(0)
for _, edge := range edges {
index = addNode(nodes, edge.thing_1, index)
index = addNode(nodes, edge.thing_2, index)
}

// Add edges to graph
for _, edge := range edges {
syncGraph.SetWeightedEdge(syncGraph.NewWeightedEdge(nodes[edge.thing_1], nodes[edge.thing_2], edge.weight))
}

return nodes, syncGraph
}

func addNode(thingToNode map[ThingType]ThingNode, thing ThingType, index int64) int64 {
if _, known := thingToNode[thing]; !known {
thingToNode[thing] = ThingNode{id: index, thing: thing}
index++
}
return index
}

[Dan Kortschak]

Hi Torsten,

On Tue, 2022-03-29 at 01:36 -0700, Torsten Knüppel wrote:
> Hi,
>
> I'd like to compute a minimal spanning forest of a given graph using
> e.g. Kruskal's algorithm.
> I managed to create a graph, but I don't know how to apply Kruskal.
> If I understand correctly, the documentation (
> https://pkg.go.dev/gonum.org/v1/gonum/graph/path#Kruskal) says, that
> as an output, I need an object that implements the WeightBuilder-
> interface.
> Do I need to write my own type that implements this interface or is
> there already something I can use? If yes, is there a recommend way
> to find a useful type - the vast amount of types and functions is
> hard to grasp for me.

Yes, this is a problem, but unfortunately not a solvable one. In
general all graphs implementations that you will need to get you
started are in graph/simple and graph/multi (the latter for
multigraphs). For this case, a simple.WeightedUndirected would do. You
can see this in the test code
https://github.com/gonum/gonum/blob/1c2a04ccb910f9b234b461b4f555a6a494b579d7/graph/path/spanning_tree_test.go#L250-L251
where mst is just one of the spanning-tree functions.

> Eventually, I need separate Minimum Spanning Trees.
> From what I understand, Kruskal is is giving me a graph (not
> necessarily connected) that is a Minimum Spanning Forest - is there a
> chance to immediately get a slice of connected MS trees.
>
> If not, my idea was to use the connected components method from the
> topo package (
> https://pkg.go.dev/gonum.org/v1/gonum/graph/topo#ConnectedComponents)
> and apply it to the result of Kruskal.

I would do this.

> This gives me a slice of nodes for each component - is there a
> function to use each slice and get a subgraph of the initial graph?
> Or do I need to construct the graphs manually?
>

I think there is an induce somewhere... no. But I have one that you can
use here
https://github.com/kortschak/graphprac/blob/7d1a4bf82cee21703ab28e5aa666f5439c12048b/graph.go#L149-L226
. This graph is based on a teaching graph type, but the basis for the
code is translatable to any graph.Graph.

Dan

[Torsten Knüppel]

Hi Dan,

thanks a lot for your quick reply - it should solve my problems.

Best regards
Torsten