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<string>) =
    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 Head : '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
Raw view Test code New version

More information

Link:http://fssnip.net/kP
Posted:10 years ago
Author:Faisal Waris
Tags: graph , graph theory , minimum spanning tree , mst , kruskal