2 people like it.

# Minimum Spanning Tree

An implementation of a minimum spanning tree calculation algorithm based on Kruskal's algorithm

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: ``` ``````type E = {Node1:string; Node2:string; Weight:int} type G = E list //one of the nodes should be in the set and the other not //returns the node not in the set //O(log n) let hasOneNodeOf (e:E) (nodeSet:Set) = if nodeSet.Contains e.Node1 && not( nodeSet.Contains e.Node2) then Some e.Node2 elif nodeSet.Contains e.Node2 && not( nodeSet.Contains e.Node1) then Some e.Node1 else None //finds the mininum weight edge from a set of nodes and a list of available edges //the edges must be sorted in increasing order of weight //retruns the minium edge, the new node, and the remaining edges (order is preserved) //O(n log n) worst case - amortized complextity should be much better - O(log n)? let minEdge nodeSet sortedEdges = let rec minEdge' vs esDone esLeft = //recursive inner function that does the work match esLeft with | [] -> None | e::rest -> match nodeSet |> hasOneNodeOf e with | Some n -> Some(e, n, (esDone |> List.rev) @ rest) | None -> minEdge' vs (e::esDone) rest minEdge' nodeSet [] sortedEdges //find the minimum spanning tree of a non-empty, connected graph //based on Kruskal's algorithm //O(E log E) let mst (g:G) = let sortedEdges = g |> List.sortBy (fun e -> e.Weight) //list of available edges O(n log n) let nodeSet = set [sortedEdges.[0].Node1] //starting node set let numNodes = //O(n log n) g |> Seq.collect (fun e -> [e.Node1; e.Node2]) |> Seq.distinct |> Seq.length let rec mst' nodeSet nodeCount minEdges availableEdges = //recursive inner function if nodeCount = numNodes then minEdges else match minEdge nodeSet availableEdges with //O(n log n) worst case, O(log n) amortized | Some (e,n,rest) -> mst' (nodeSet.Add n) (nodeCount + 1) (e::minEdges) rest | None -> failwith "not a connected graph" mst' nodeSet 1 [] sortedEdges let g = [ {Node1="a"; Node2="b"; Weight=4} {Node1="a"; Node2="c"; Weight=2} {Node1="a"; Node2="e"; Weight=3} {Node1="b"; Node2="d"; Weight=5} {Node1="c"; Node2="d"; Weight=1} {Node1="c"; Node2="e"; Weight=6} {Node1="c"; Node2="f"; Weight=3} {Node1="d"; Node2="f"; Weight=6} {Node1="e"; Node2="f"; Weight=2} ] let minSpanTree = mst g ``````
type E =
{Node1: string;
Node2: string;
Weight: int;}

Full name: Script.E
E.Node1: string
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string
E.Node2: string
E.Weight: int
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
type G = E list

Full name: Script.G
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val hasOneNodeOf : e:E -> nodeSet:Set<string> -> string option

Full name: Script.hasOneNodeOf
val e : E
val nodeSet : Set<string>
Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
interface IComparable
interface IEnumerable
interface IEnumerable<'T>
interface ICollection<'T>
new : elements:seq<'T> -> Set<'T>
member Add : value:'T -> Set<'T>
member Contains : value:'T -> bool
override Equals : obj -> bool
member IsProperSubsetOf : otherSet:Set<'T> -> bool
member IsProperSupersetOf : otherSet:Set<'T> -> bool
...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>
member Set.Contains : value:'T -> bool
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
val minEdge : nodeSet:Set<string> -> sortedEdges:E list -> (E * string * E list) option

Full name: Script.minEdge
val sortedEdges : E list
val minEdge' : ('a -> E list -> E list -> (E * string * E list) option)
val vs : 'a
val esDone : E list
val esLeft : E list
val rest : E list
val n : string
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val mst : g:G -> E list

Full name: Script.mst
val g : G
val sortBy : projection:('T -> 'Key) -> list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sortBy
val set : elements:seq<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.set
val numNodes : int
module Seq

from Microsoft.FSharp.Collections
val collect : mapping:('T -> #seq<'U>) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.collect
val distinct : source:seq<'T> -> seq<'T> (requires equality)

Full name: Microsoft.FSharp.Collections.Seq.distinct
val length : source:seq<'T> -> int

Full name: Microsoft.FSharp.Collections.Seq.length
val mst' : (Set<string> -> int -> E list -> E list -> E list)
val nodeCount : int
val minEdges : E list
val availableEdges : E list
member Set.Add : value:'T -> Set<'T>
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val g : E list

Full name: Script.g
val minSpanTree : E list

Full name: Script.minSpanTree