basis/disjoint-sets/disjoint-sets-docs.factor

   1 IN: disjoint-sets
   2 USING: help.markup help.syntax kernel assocs math ;
   3
   4 HELP: <disjoint-set>
   5 { $values { "disjoint-set" disjoint-set } }
   6 { $description "Creates a new disjoint set data structure with no elements." } ;
   7
   8 HELP: add-atom
   9 { $values { "a" object } { "disjoint-set" disjoint-set } }
  10 { $description "Adds a new element to the disjoint set, initially only equivalent to itself." } ;
  11
  12 HELP: equiv-set-size
  13 { $values { "a" object } { "disjoint-set" disjoint-set } { "n" integer } }
  14 { $description "Outputs the number of elements in the equivalence class of " { $snippet "a" } "." } ;
  15
  16 HELP: equiv?
  17 { $values { "a" object } { "b" object } { "disjoint-set" disjoint-set } { "?" boolean } }
  18 { $description "Tests if two elements belong to the same equivalence class." } ;
  19
  20 HELP: equate
  21 { $values { "a" object } { "b" object } { "disjoint-set" disjoint-set } }
  22 { $description "Merges the equivalence classes of two elements, which must previously have been added with " { $link add-atom } "." } ;
  23
  24 HELP: assoc>disjoint-set
  25 { $values { "assoc" assoc } { "disjoint-set" disjoint-set } }
  26 { $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." }
  27 { $examples
  28     { $example
  29         "USING: disjoint-sets kernel prettyprint ;"
  30         "H{ { 1 1 } { 2 1 } { 3 4 } { 4 4 } { 5 3 } } assoc>disjoint-set"
  31         "1 2 pick equiv? ."
  32         "4 5 pick equiv? ."
  33         "1 5 pick equiv? ."
  34         "drop"
  35         "t\nt\nf"
  36     }
  37 } ;
  38
  39 ARTICLE: "disjoint-sets" "Disjoint sets"
  40 "The " { $vocab-link "disjoint-sets" } " vocabulary implements the " { $emphasis "disjoint set" } " data structure (also known as " { $emphasis "union-find" } ", after the two main operations which it supports) that represents a set of elements partitioned into disjoint equivalence classes, or alternatively, an equivalence relation on a set."
  41 $nl
  42 "The two main supported operations are equating two elements, which joins their equivalence classes, and checking if two elements belong to the same equivalence class. Both operations have the time complexity of the inverse Ackermann function, which for all intents and purposes is constant time."
  43 $nl
  44 "The class of disjoint sets:"
  45 { $subsections disjoint-set }
  46 "Creating new disjoint sets:"
  47 { $subsections
  48     <disjoint-set>
  49     assoc>disjoint-set
  50 }
  51 "Queries:"
  52 { $subsections
  53     equiv?
  54     equiv-set-size
  55 }
  56 "Adding elements:"
  57 { $subsections add-atom }
  58 "Equating elements:"
  59 { $subsections equate }
  60 "Additionally, disjoint sets implement the " { $link clone } " generic word." ;
  61
  62 ABOUT: "disjoint-sets"