MinSpanningTree {rlemon}

Solver for Minimum Spanning Tree

Description

The minimum spanning tree is the minimal connected acyclic subgraph of a graph, assuming the graph is undirected.

Usage

MinSpanningTree(
  arcSources,
  arcTargets,
  arcDistances,
  numNodes,
  algorithm = "Kruskal"
)

Arguments

arcSources

Vector corresponding to the source nodes of a graph's edges

arcTargets

Vector corresponding to the destination nodes of a graph's edges

arcDistances

Vector corresponding to the distances of nodes of a graph's edges

numNodes

The number of nodes in the graph

algorithm

Choices of algorithm include "Kruskal". "Kruskal" is the default.

Details

For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00610.html#ga233792b2c44a3581b85a775703e045af

Value

A named list containing three entries: 1) "sources": a vector corresponding the source nodes of the edges in the tree, 2) "targets": a vector corresponding the target nodes of the edges in the tree, and 3) "value": the total minimum spanning tree value.