2 people like it.

union find

This module implements a generic union-find data structure (from https://gist.github.com/vanaur/bea2b0ea57b58140b9c1d39a9b02e998).

  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: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 
/// This module implements a generic [union-find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) data structure.
/// This structure is used to manage disjoint sets, often used in partitioning or clustering problems.
/// 
/// Here is a summary of the features and members of this data structure:
/// 
/// 1. **Constructor**: The `UnionFind` constructor initializes a new instance of the Union-Find data structure with
///    default elements of the original set specified as a sequence. This set can be extended.
///
/// 2. **Public Members** :
///  - `UnionFind.AddElement` Adds a new element to the set.
///  - `UnionFind.AddRange` Adds a sequence of elements to the set.
///  - `UnionFind.Connect`: Combines two equivalence classes to which two given representatives belong into a single class.
///  - `UnionFind.ConnectRange`: Combines all equivalence classes to which the given representatives belong into a single class.
///  - `UnionFind.GetConnections`: Retrieves all elements of the equivalence class to which a given element belongs.
///  - `UnionFind.GetAllConnections`: Retrieves all equivalence classes.
///  - `UnionFind.AreConnected`: Checks whether two elements belong to the same equivalence class.
/// 
/// 3. **Inline functions**: These functions allow you to access members of the `UnionFind` instance more concisely.
/// 
/// Example:
///     <example>
///     let uf = UnionFind [| 1..6 |]
///     connectRange uf [| 1; 2; 3 |]
///     connectRange uf [| 4; 5 |]
///     </example>
///
module public UnionFind =
    open System.Collections.Generic
    open System.Linq

    /// Generic [union-find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) data structure
    /// using the path compression find amelioration, making `Find` and `Connect` O(log n) in the worst case.
    type public UnionFind<'t when 't: equality>(defaultElements: 't seq) =
        let mutable parents = Dictionary<'t, 't>()
        let mutable ranks = Dictionary<'t, int>()

        do
            Seq.iter
                (fun element ->
                    parents.Add(element, element)
                    ranks.Add(element, 1))
                defaultElements

        let find (element: 't) =
            let rec inner (element: 't) =
                match parents.TryGetValue element with
                | true, parent when parent <> element ->
                    let grandParent = parents.[parent]
                    parents.[element] <- grandParent
                    inner grandParent
                | _ -> element

            inner element

        let treeSize (element: 't) = ranks.[element]

        member internal __.GetParents
            with get () = parents
            and set value = parents <- value

        member internal __.GetRanks
            with get () = ranks
            and set value = ranks <- value

        /// Adds an element to the original set.
        member public __.AddElement(element: 't) =
            match parents.TryGetValue element with
            | false, _ ->
                parents.Add(element, element)
                ranks.Add(element, 1)
            | _ -> ()

        /// Adds the list of elements given in the original set.
        member public this.AddRange(elements: 't seq) = Seq.iter this.AddElement elements

        /// Combines the two equivalence classes to which the two given representatives belong into a single class.
        member public __.Connect (left: 't) (right: 't) =
            assert (parents.ContainsKey left)
            assert (parents.ContainsKey right)

            let leftTree = find left
            let rightTree = find right

            if leftTree = rightTree then
                ()

            let leftTreeSize = treeSize leftTree
            let rightTreeSize = treeSize rightTree

            if leftTreeSize < rightTreeSize then
                parents.[leftTree] <- rightTree
                ranks.[rightTree] <- leftTreeSize + rightTreeSize
            else
                parents.[rightTree] <- leftTree
                ranks.[leftTree] <- leftTreeSize + rightTreeSize

        /// Combines all the equivalence classes to which the list of given representatives belong into a single class.
        member public this.ConnectRange(xs: 't seq) =
            if Seq.length xs < 2 then
                ()

            let head = Seq.head xs
            let tail = Seq.tail xs

            Seq.iter (this.Connect head) tail

        /// Retrieves the equivalence class to which the given element belongs.
        member public __.GetConnections(item: 't) =
            if not (parents.ContainsKey item) then
                Array.empty
            else
                let representative = find item

                parents
                    .GroupBy(fun kvp -> kvp.Value)
                    .Where(fun x -> x.Key = representative)
                    .Select(fun gp -> gp.Select(fun kvp -> kvp.Key) |> Seq.toArray)
                |> Seq.toArray

        /// Gets the set of equivalence classes.
        member public __.GetAllConnections() =
            parents
                .GroupBy(fun kvp -> kvp.Value)
                .Select(fun gp -> gp.Select(fun kvp -> kvp.Key) |> Seq.toArray)
            |> Seq.toArray

        /// Check whether two elements belong to the same equivalence class.
        member public __.AreConnected (left: 't) (right: 't) = find left = find right

    /// Adds an element to the original set.
    let inline public addElement (uf: 't UnionFind) = uf.AddElement
    /// Adds the list of elements given in the original set.
    let inline public addRange (uf: 't UnionFind) = uf.AddRange
    /// Combines the two equivalence classes to which the two given representatives belong into a single class.
    let inline public connect (uf: 't UnionFind) = uf.Connect
    /// Combines all the equivalence classes to which the list of given representatives belong into a single class.
    let inline public connectRange (uf: 't UnionFind) = uf.ConnectRange
    /// Retrieves the equivalence class to which the given element belongs.
    let inline public getConnections (uf: 't UnionFind) = uf.GetConnections
    /// Gets the set of equivalence classes.
    let inline public getAllConnections (uf: 't UnionFind) = uf.GetAllConnections()
    /// Check whether two elements belong to the same equivalence class.
    let inline public areConnected (uf: 't UnionFind) = uf.AreConnected
namespace System
namespace System.Collections
namespace System.Collections.Generic
namespace System.Linq
Multiple items
type UnionFind<'t (requires equality)> =
  new : defaultElements:seq<'t> -> UnionFind<'t>
  member AddElement : element:'t -> unit
  member AddRange : elements:seq<'t> -> unit
  member AreConnected : left:'t -> right:'t -> bool
  member Connect : left:'t -> right:'t -> unit
  member ConnectRange : xs:seq<'t> -> unit
  member GetAllConnections : unit -> 't [] []
  member GetConnections : item:'t -> 't [] []
  member internal GetParents : Dictionary<'t,'t>
  member internal GetRanks : Dictionary<'t,int>
 Generic [union-find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) data structure
 using the path compression find amelioration, making `Find` and `Connect` O(log n) in the worst case.


--------------------
new : defaultElements:seq<'t> -> UnionFind<'t>
val defaultElements : seq<'t> (requires equality)
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

--------------------
type seq<'T> = IEnumerable<'T>
val mutable parents : Dictionary<'t,'t> (requires equality)
Multiple items
type Dictionary<'TKey,'TValue> =
  interface IDictionary<'TKey,'TValue>
  interface ICollection<KeyValuePair<'TKey,'TValue>>
  interface IEnumerable<KeyValuePair<'TKey,'TValue>>
  interface IEnumerable
  interface IDictionary
  interface ICollection
  interface IReadOnlyDictionary<'TKey,'TValue>
  interface IReadOnlyCollection<KeyValuePair<'TKey,'TValue>>
  interface ISerializable
  interface IDeserializationCallback
  ...

--------------------
Dictionary() : Dictionary<'TKey,'TValue>
Dictionary(capacity: int) : Dictionary<'TKey,'TValue>
Dictionary(comparer: IEqualityComparer<'TKey>) : Dictionary<'TKey,'TValue>
Dictionary(dictionary: IDictionary<'TKey,'TValue>) : Dictionary<'TKey,'TValue>
Dictionary(collection: IEnumerable<KeyValuePair<'TKey,'TValue>>) : Dictionary<'TKey,'TValue>
Dictionary(capacity: int, comparer: IEqualityComparer<'TKey>) : Dictionary<'TKey,'TValue>
Dictionary(dictionary: IDictionary<'TKey,'TValue>, comparer: IEqualityComparer<'TKey>) : Dictionary<'TKey,'TValue>
Dictionary(collection: IEnumerable<KeyValuePair<'TKey,'TValue>>, comparer: IEqualityComparer<'TKey>) : Dictionary<'TKey,'TValue>
val mutable ranks : Dictionary<'t,int> (requires equality)
Multiple items
val int : value:'T -> int (requires member op_Explicit)

--------------------
[<Struct>]
type int = int32

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

from Microsoft.FSharp.Collections
val iter : action:('T -> unit) -> source:seq<'T> -> unit
val element : 't (requires equality)
Dictionary.Add(key: 't, value: 't) : unit
Dictionary.Add(key: 't, value: int) : unit
val find : ('t -> 't) (requires equality)
val inner : ('t -> 't) (requires equality)
Dictionary.TryGetValue(key: 't, value: byref<'t>) : bool
val parent : 't (requires equality)
val grandParent : 't (requires equality)
val treeSize : ('t -> int) (requires equality)
val set : elements:seq<'T> -> Set<'T> (requires comparison)
val value : Dictionary<'t,'t> (requires equality)
val __ : UnionFind<'t> (requires equality)
val value : Dictionary<'t,int> (requires equality)
val this : UnionFind<'t> (requires equality)
val elements : seq<'t> (requires equality)
member UnionFind.AddElement : element:'t -> unit
 Adds an element to the original set.
val left : 't (requires equality)
val right : 't (requires equality)
Dictionary.ContainsKey(key: 't) : bool
val leftTree : 't (requires equality)
val rightTree : 't (requires equality)
val leftTreeSize : int
val rightTreeSize : int
val xs : seq<'t> (requires equality)
val length : source:seq<'T> -> int
val head : 't (requires equality)
val head : source:seq<'T> -> 'T
val tail : seq<'t> (requires equality)
val tail : source:seq<'T> -> seq<'T>
member UnionFind.Connect : left:'t -> right:'t -> unit
 Combines the two equivalence classes to which the two given representatives belong into a single class.
val item : 't (requires equality)
val not : value:bool -> bool
module Array

from Microsoft.FSharp.Collections
val empty<'T> : 'T []
val representative : 't (requires equality)
val kvp : KeyValuePair<'t,'t> (requires equality)
property KeyValuePair.Value: 't with get
val x : IGrouping<'t,KeyValuePair<'t,'t>> (requires equality)
property IGrouping.Key: 't with get
val gp : IGrouping<'t,KeyValuePair<'t,'t>> (requires equality)
(extension) IEnumerable.Select<'TSource,'TResult>(selector: System.Func<'TSource,'TResult>) : IEnumerable<'TResult>
(extension) IEnumerable.Select<'TSource,'TResult>(selector: System.Func<'TSource,int,'TResult>) : IEnumerable<'TResult>
property KeyValuePair.Key: 't with get
val toArray : source:seq<'T> -> 'T []
val addElement : uf:UnionFind<'t> -> ('t -> unit) (requires equality)
 Adds an element to the original set.
val uf : UnionFind<'t> (requires equality)
val addRange : uf:UnionFind<'t> -> (seq<'t> -> unit) (requires equality)
 Adds the list of elements given in the original set.
member UnionFind.AddRange : elements:seq<'t> -> unit
 Adds the list of elements given in the original set.
val connect : uf:UnionFind<'t> -> ('t -> 't -> unit) (requires equality)
 Combines the two equivalence classes to which the two given representatives belong into a single class.
val connectRange : uf:UnionFind<'t> -> (seq<'t> -> unit) (requires equality)
 Combines all the equivalence classes to which the list of given representatives belong into a single class.
member UnionFind.ConnectRange : xs:seq<'t> -> unit
 Combines all the equivalence classes to which the list of given representatives belong into a single class.
val getConnections : uf:UnionFind<'t> -> ('t -> 't [] []) (requires equality)
 Retrieves the equivalence class to which the given element belongs.
member UnionFind.GetConnections : item:'t -> 't [] []
 Retrieves the equivalence class to which the given element belongs.
val getAllConnections : uf:UnionFind<'t> -> 't [] [] (requires equality)
 Gets the set of equivalence classes.
member UnionFind.GetAllConnections : unit -> 't [] []
 Gets the set of equivalence classes.
val areConnected : uf:UnionFind<'t> -> ('t -> 't -> bool) (requires equality)
 Check whether two elements belong to the same equivalence class.
member UnionFind.AreConnected : left:'t -> right:'t -> bool
 Check whether two elements belong to the same equivalence class.
Raw view Test code New version

More information

Link:http://fssnip.net/8as
Posted:2 months ago
Author:vanaur
Tags: algorithms , collection , fast , union-find