unmaintained/graph-theory/graph-theory-docs.factor

   1 ! See http://factorcode.org/license.txt for BSD licence.
   2 USING: help.markup help.syntax ;
   3
   4 IN: graph-theory
   5
   6 ARTICLE: "graph-protocol" "Graph protocol"
   7 "All graphs must be instances of the graph mixin:"
   8 { $subsections graph }
   9 "All graphs must implement a method on the following generic word:"
  10 { $subsections vertices }
  11 "At least one of the following two generic words must have a method; the " { $link graph } " mixin has default definitions which are mutually recursive:"
  12 { $subsections
  13     adjlist
  14     adj?
  15 }
  16 "All mutable graphs must implement a method on the following generic word:"
  17 { $subsections add-blank-vertex }
  18 "All mutable undirected graphs must implement a method on the following generic word:"
  19 { $subsections add-edge }
  20 "Mutable directed graphs should not implement the above word, as it has a default definition defined in terms of the following generic word:"
  21 { $subsections add-edge* }
  22 "The following two words have default definitions, but are available as generics to allow implementations to optimize them:"
  23 { $subsections
  24     num-vertices
  25     num-edges
  26 } ;
  27
  28 HELP: graph
  29 { $class-description "A mixin class whose instances are graphs.  Custom implementations of the graph protocol should be declared as instances of this mixin for all graph functionality to work correctly:"
  30     { $code "INSTANCE: hex-board graph" }
  31 } ;
  32
  33 { vertices num-vertices num-edges } related-words
  34
  35 HELP: vertices
  36 { $values { "graph" graph } { "seq" "The vertices" } }
  37 { $description "Returns the vertices of the graph." } ;
  38
  39 HELP: num-vertices
  40 { $values { "graph" graph } { "n" "The number of vertices" } }
  41 { $description "Returns the number of vertices in the graph." } ;
  42
  43 HELP: num-edges
  44 { $values { "graph" "A graph" } { "n" "The number of edges" } }
  45 { $description "Returns the number of edges in the graph." } ;
  46
  47 { adjlist adj? } related-words
  48
  49 HELP: adjlist
  50 { $values
  51     { "from" "The index of a vertex" }
  52     { "graph" "The graph to be examined" }
  53     { "seq" "The adjacency list" } }
  54 { $description "Returns a sequence of vertices that this vertex links to" } ;
  55
  56 HELP: adj?
  57 { $values
  58     { "from" "The index of a vertex" }
  59     { "to" "The index of a vertex" }
  60     { "graph" "A graph" }
  61     { "?" "A boolean" } }
  62 { $description "Returns a boolean describing whether there is an edge in the graph between from and to." } ;
  63
  64 { add-blank-vertex add-blank-vertices add-edge add-edge* } related-words
  65
  66 HELP: add-blank-vertex
  67 { $values
  68     { "index" "A vertex index" }
  69     { "graph" "A graph" } }
  70 { $description "Adds a vertex to the graph." } ;
  71
  72 HELP: add-blank-vertices
  73 { $values
  74     { "seq" "A sequence of vertex indices" }
  75     { "graph" "A graph" } }
  76 { $description "Adds vertices with indices in seq to the graph." } ;
  77
  78 HELP: add-edge*
  79 { $values
  80     { "from" "The index of a vertex" }
  81     { "to" "The index of another vertex" }
  82     { "graph" "A graph" } }
  83 { $description "Adds a one-way edge to the graph, between " { $snippet "from" } " and " { $snippet "to" } "."
  84   $nl
  85   "If you want to add a two-way edge, use " { $link add-edge } " instead." } ;
  86
  87 HELP: add-edge
  88 { $values
  89     { "u" "The index of a vertex" }
  90     { "v" "The index of another vertex" }
  91     { "graph" "A graph" } }
  92 { $description "Adds a two-way edge to the graph, between " { $snippet "u" } " and " { $snippet "v" } "."
  93   $nl
  94   "If you want to add a one-way edge, use " { $link add-edge* } " instead." } ;
  95
  96 { depth-first full-depth-first dag? topological-sort } related-words
  97
  98 HELP: depth-first
  99 { $values
 100     { "v" "The vertex to start the search at" }
 101     { "graph" "The graph to search" }
 102     { "pre" "A quotation of the form ( n -- )" }
 103     { "post" "A quotation of the form ( n -- )" }
 104     { "?list" "A list of booleans describing the vertices visited in the search" }
 105     { "?" "A boolean describing whether or not the end-search error was thrown" } }
 106 { $description "Performs a depth-first search on " { $emphasis "graph" } ".  The variable " { $emphasis "graph" } " can be accessed in both quotations."
 107   $nl
 108   "The " { $emphasis "pre" } " quotation is run before the recursive application of depth-first."
 109   $nl
 110   "The " { $emphasis "post" } " quotation is run after the recursive application of depth-first."
 111   $nl
 112   { $emphasis "?list" } " is a list of booleans, " { $link t } " for every vertex visted during the search, and " { $link f } " for every vertex not visited." } ;
 113
 114 HELP: full-depth-first
 115 { $values
 116     { "graph" "The graph to search" }
 117     { "pre" "A quotation of the form ( n -- )" }
 118     { "post" "A quotation of the form ( n -- )" }
 119     { "tail" "A quotation of the form ( -- )" }
 120     { "?" "A boolean describing whether or not the end-search error was thrown" } }
 121 { $description "Performs a depth-first search on " { $emphasis "graph" } ".  The variable " { $emphasis "graph" } "can be accessed in both quotations."
 122   $nl
 123   "The " { $emphasis "pre" } " quotation is run before the recursive application of depth-first."
 124   $nl
 125   "The " { $emphasis "post" } " quotation is run after the recursive application of depth-first."
 126   $nl
 127   "The " { $emphasis "tail" } " quotation is run after each time the depth-first search runs out of nodes.  On an undirected graph this will be each connected subgroup but on a directed graph it can be more complex." } ;
 128
 129 HELP: dag?
 130 { $values
 131     { "graph" graph }
 132     { "?" "A boolean indicating if the graph is acyclic" } }
 133 { $description "Using a depth-first search, determines if the specified directed graph is a directed acyclic graph.  An undirected graph will produce a false result, as the algorithm does not eliminate cycles of length 2, which will include any edge that goes both ways." } ;
 134
 135 HELP: topological-sort
 136 { $values
 137     { "graph" graph }
 138     { "seq/f" "Either a sequence of values or f" } }
 139 { $description "Using a depth-first search, topologically sorts the specified directed graph.  Returns f if the graph contains any cycles, and a topologically sorted sequence otherwise." } ;