assoc>disjoint-set ( assoc -- disjoint-set )
Factor handbook » The language » Collections » Disjoint sets

Prev:	<disjoint-set> ( -- disjoint-set )
Next:	equiv? ( a b disjoint-set -- ? )

Vocabulary
disjoint-sets

Inputs

assoc

an assoc

Outputs

disjoint-set

a disjoint-set

Word description
Given an assoc representation of a graph where the keys are vertices and key/value pairs are edges, creates a disjoint set whose elements are the keys of assoc, and two keys are equivalent if they belong to the same connected component of the graph.

Examples

USING: disjoint-sets kernel prettyprint ; H{ { 1 1 } { 2 1 } { 3 4 } { 4 4 } { 5 3 } } assoc>disjoint-set 1 2 pick equiv? . 4 5 pick equiv? . 1 5 pick equiv? . drop
t t f

Definition

USING: assocs kernel ;

IN: disjoint-sets

: assoc>disjoint-set ( assoc -- disjoint-set )
    <disjoint-set> [
        [
            [ [ drop ] ] dip [ add-atom ] curry compose
            assoc-each
        ] [ [ equate ] curry assoc-each ] 2bi
    ] keep ;