Have ideas to improve npm?Join in the discussion! »

    disjoint-set

    1.1.8 • Public • Published

    Disjoint-set

    Disjoint-set is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non overlapping) subsets. A union–find algorithm is an algorithm that performs two useful operations on such a data structure:

    • Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset;
    • Union: Join two subsets into a single subset.

    Use to solve network connectivity problem.

    Build Status

    API

    Creation

    Factory Description
    disjointSet() Instantiates disjoint-set data structure.

    Methods

    Method Returns Order of growth (worst case) Description
    add(<Object> val) this Constant Adds object to the set.
    union(<Object> val1, <Object> val2) Boolean Logarithmic Сonnects val1 with val2.
    find(<Object> val) String Logarithmic Returns identifier of the subset by given value.
    connected(<Object> val1, <Object> val2) Boolean Logarithmic Returns true when val1 and val2 are connected.
    extract() Array Linear Returns all items grouped by subsets.
    destroy() Constant Clears data structure.

    Usage example

    var set = disjointSet(); // instantiate disjoint-set data structure
    
    var person1 = {
        name: 'Volodymyr',
        surname: 'Velykyj'
    }
    var person2 = {
        name: 'Yaroslav',
        surname: 'Mydryi'
    }
    var person3 = {
        name: 'Bohdan',
        surname: 'Khmelnytskyi'
    }
    var person4 = {
        name: 'Ivan',
        surname: 'Mazepa'
    }
    var person5 = {
        name: 'Viktor',
        surname: 'Yanukovich'
    }
    var person6 = {
        name: 'Volodymyr',
        surname: 'Putin'
    }
    
    // add objects to the set
    set.add(person1)
        .add(person2)
        .add(person3)
        .add(person4)
        .add(person5)
        .add(person6);
    
    // connect some objects to each other
    set.union(person1, person2);
    set.union(person2, person3);
    set.union(person3, person4);
    set.union(person5, person6);
    
    // check connections
    console.log(set.connected(person1, person2)); // returns true. Direct connection
    console.log(set.connected(person1, person4)); // returns true. Indirect connection
    console.log(set.connected(person5, person6)); // returns true. Another direct connection
    console.log(set.connected(person4, person5)); // returns false. No connection
    
    /**
     * returns two arrays grouped by connection:
     * [
     *     [person1, person2, person3, person4],
     *     [person5, person6]
     * ]
     */
    console.log(set.extract());
    

    Development

    npm install # install dependencies
    npm test    # check the code with JSHint and run tests
    

    Papers

    • Robert Sedgewick and Kevin Wayne, Algorithms, 4th edition, page 216

    Changelog

    1.1.8 — 04.02.2015

    • minor fixes (readme, package.json)

    1.1.7 — 04.02.2015

    • minor fixes (readme, package.json)

    1.1.6 — 21.10.2014

    • minor fixes (readme, package.json)

    1.1.5 — 01.05.2014

    • critical bug (wrong subtree connections) fixed

    1.1.4 — 25.04.2014

    • performance optimization: stringify key generator changed to Numerical ids

    1.1.3 — 10.04.2014

    • quick-union algorithm changed to weighted quick-union

    1.1.2 — 08.04.2014

    • quick-find algorithm changed to quick-union

    1.1.1 — 08.04.2014

    • unit tests done

    1.1.0 — 07.04.2014

    • connected() method added
    • find() method changed

    1.0.0 — 06.04.2014

    • First Disjoint-set release

    Install

    npm i disjoint-set

    DownloadsWeekly Downloads

    74

    Version

    1.1.8

    License

    none

    Last publish

    Collaborators

    • avatar