5 people like it.

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
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