Weighted Quick-Union with Path Compression

Implementation of Mutable Weighted Quick-Union with Path Compression in F#

 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: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 
74: 
75: 
76: 
77: 
78:

// From Wikipedia: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
// In computing, a disjoint-set data structure is a data structure that keeps track 
// of a set of elements partitioned into a number of disjoint (nonoverlapping) 
// subsets. A union-find algorithm is an algorithm that performs two useful 
// operations on such a data structure:

// Find: Determine which set a particular element is in. Also useful for 
//       determining if two elements are in the same set.
// Union: Combine or merge two sets into a single set.

// Implementation from: http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

/// Quick-find... Union is O(N), Flat Trees
/// Quick-union... Trees are tall, Find is O(N), Find requires union
/// Overall: O(MN) -- M union-find ops on a set of N objects
type QuickUnion (N) =
    //Parent index, id[i] is parent of i

    let mutable id : int[] = Array.init N (fun i -> i)
    let root i = 
        let mutable q = i
        while (q <> id.[q]) do q <- id.[q] 
        q

    member t.find(p, q) =
        root(p) = root(q)

    member t.unite(p, q) =
        let i = root(p)
        let j = root(q)
        id.[i] = j;

/// Weighted QuickUnion 
/// Now with logN union, lgN find
/// Overall: O(N+MLogN) -- M union-find ops on a set of N objects
type WeightedQuickUnion (N) =
    //Parent index, id[i] is parent of i
    let id : int[] = Array.init N (fun i -> i)
    //Number of elements rooted at i
    let sz : int[] = Array.create N 0
    
    let root i = 
        let mutable q = i
        while (q <> id.[q]) do q <- id.[q] 
        q

    member t.find(p, q) =
        root(p) = root(q)

    member t.unite(p, q) =
        let i = root(p)
        let j = root(q)
        if sz.[i] < sz.[j] then id.[i] <- j; sz.[j] <- sz.[j] + sz.[i]
        else id.[j] <- i; sz.[i] <- sz.[i] + sz.[j]

/// Weighted quick-union with path compression
/// Overall O((M+N)lg*N) -- M union-find ops on a set of N objects
type QuickUWPC (N) =
    //Parent index, id[i] is parent of i
    let id : int[] = Array.init N (fun i -> i)
    //Number of elements rooted at i
    let sz : int[] = Array.create N 0
     
    let root i = 
        let mutable q = i
        while (q <> id.[q]) do 
            id.[q] <- id.[id.[q]]
            q <- id.[q] 
        q

    member t.find(p, q) =
        root(p) = root(q)

    member t.unite(p, q) =
        let i = root(p)
        let j = root(q)
        if sz.[i] < sz.[j] then id.[i] <- j; sz.[j] <- sz.[j] + sz.[i]
        else id.[j] <- i; sz.[i] <- sz.[i] + sz.[j]

Multiple items
type QuickUnion =
  new : N:int -> QuickUnion
  member find : p:int * q:int -> bool
  member unite : p:int * q:int -> bool

Full name: Script.QuickUnion

Quick-find... Union is O(N), Flat Trees
Quick-union... Trees are tall, Find is O(N), Find requires union
Overall: O(MN) -- M union-find ops on a set of N objects

--------------------
new : N:int -> QuickUnion

val N : int

val mutable id : 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<_>

module Array

from Microsoft.FSharp.Collections

val init : count:int -> initializer:(int -> 'T) -> 'T []

Full name: Microsoft.FSharp.Collections.Array.init

val i : int

val root : (int -> int)

val mutable q : int

val t : QuickUnion

member QuickUnion.find : p:int * q:int -> bool

Full name: Script.QuickUnion.find

val p : int

val q : int

member QuickUnion.unite : p:int * q:int -> bool

Full name: Script.QuickUnion.unite

val j : int

Multiple items
type WeightedQuickUnion =
  new : N:int -> WeightedQuickUnion
  member find : p:int * q:int -> bool
  member unite : p:int * q:int -> unit

Full name: Script.WeightedQuickUnion

Weighted QuickUnion
Now with logN union, lgN find
Overall: O(N+MLogN) -- M union-find ops on a set of N objects

--------------------
new : N:int -> WeightedQuickUnion

val id : int []

val sz : int []

val create : count:int -> value:'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create

val t : WeightedQuickUnion

member WeightedQuickUnion.find : p:int * q:int -> bool

Full name: Script.WeightedQuickUnion.find

member WeightedQuickUnion.unite : p:int * q:int -> unit

Full name: Script.WeightedQuickUnion.unite

Multiple items
type QuickUWPC =
  new : N:int -> QuickUWPC
  member find : p:int * q:int -> bool
  member unite : p:int * q:int -> unit

Full name: Script.QuickUWPC

Weighted quick-union with path compression
Overall O((M+N)lg*N) -- M union-find ops on a set of N objects

--------------------
new : N:int -> QuickUWPC

val t : QuickUWPC

member QuickUWPC.find : p:int * q:int -> bool

Full name: Script.QuickUWPC.find

member QuickUWPC.unite : p:int * q:int -> unit

Full name: Script.QuickUWPC.unite

Previous Version Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/5D
Posted:	13 years ago
Author:	Rick Minerich
Tags:	data structures , union-find