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 { $subsection graph }
   9 "All graphs must implement a method on the following generic word:"
  10 { $subsection 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 { $subsection adjlist }
  13 { $subsection adj? }
  14 "All mutable graphs must implement a method on the following generic word:"
  15 { $subsection add-blank-vertex }
  16 "All mutable undirected graphs must implement a method on the following generic word:"
  17 { $subsection add-edge }
  18 "Mutable directed graphs should not implement the above word, as it has a default definition defined in terms of the following generic word:"
  19 { $subsection add-edge* }
  20 "The following two words have default definitions, but are available as generics to allow implementations to optimize them:"
  21 { $subsection num-vertices }
  22 { $subsection num-edges } ;
  23
  24 HELP: graph
  25 { $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:"
  26     { $code "INSTANCE: hex-board graph" }
  27 } ;
  28
  29 { vertices num-vertices num-edges } related-words
  30
  31 HELP: vertices
  32 { $values { "graph" graph } { "seq" "The vertices" } }
  33 { $description "Returns the vertices of the graph." } ;
  34
  35 HELP: num-vertices
  36 { $values { "graph" graph } { "n" "The number of vertices" } }
  37 { $description "Returns the number of vertices in the graph." } ;
  38
  39 HELP: num-edges
  40 { $values { "graph" "A graph" } { "n" "The number of edges" } }
  41 { $description "Returns the number of edges in the graph." } ;
  42
  43 { adjlist adj? } related-words
  44
  45 HELP: adjlist
  46 { $values
  47     { "from" "The index of a vertex" }
  48     { "graph" "The graph to be examined" }
  49     { "seq" "The adjacency list" } }
  50 { $description "Returns a sequence of vertices that this vertex links to" } ;
  51
  52 HELP: adj?
  53 { $values
  54     { "from" "The index of a vertex" }
  55     { "to" "The index of a vertex" }
  56     { "graph" "A graph" }
  57     { "?" "A boolean" } }
  58 { $description "Returns a boolean describing whether there is an edge in the graph between from and to." } ;
  59
  60 { add-blank-vertex add-blank-vertices add-edge add-edge* } related-words
  61
  62 HELP: add-blank-vertex
  63 { $values
  64     { "index" "A vertex index" }
  65     { "graph" "A graph" } }
  66 { $description "Adds a vertex to the graph." } ;
  67
  68 HELP: add-blank-vertices
  69 { $values
  70     { "seq" "A sequence of vertex indices" }
  71     { "graph" "A graph" } }
  72 { $description "Adds vertices with indices in seq to the graph." } ;
  73
  74 HELP: add-edge*
  75 { $values
  76     { "from" "The index of a vertex" }
  77     { "to" "The index of another vertex" }
  78     { "graph" "A graph" } }
  79 { $description "Adds a one-way edge to the graph, between " { $snippet "from" } " and " { $snippet "to" } "."
  80   $nl
  81   "If you want to add a two-way edge, use " { $link add-edge } " instead." } ;
  82
  83 HELP: add-edge
  84 { $values
  85     { "u" "The index of a vertex" }
  86     { "v" "The index of another vertex" }
  87     { "graph" "A graph" } }
  88 { $description "Adds a two-way edge to the graph, between " { $snippet "u" } " and " { $snippet "v" } "."
  89   $nl
  90   "If you want to add a one-way edge, use " { $link add-edge* } " instead." } ;
  91
  92 { depth-first full-depth-first dag? topological-sort } related-words
  93
  94 HELP: depth-first
  95 { $values
  96     { "v" "The vertex to start the search at" }
  97     { "graph" "The graph to search" }
  98     { "pre" "A quotation of the form ( n -- )" }
  99     { "post" "A quotation of the form ( n -- )" }
 100     { "?list" "A list of booleans describing the vertices visited in the search" }
 101     { "?" "A boolean describing whether or not the end-search error was thrown" } }
 102 { $description "Performs a depth-first search on " { $emphasis "graph" } ".  The variable " { $emphasis "graph" } " can be accessed in both quotations."
 103   $nl
 104   "The " { $emphasis "pre" } " quotation is run before the recursive application of depth-first."
 105   $nl
 106   "The " { $emphasis "post" } " quotation is run after the recursive application of depth-first."
 107   $nl
 108   { $emphasis "?list" } " is a list of booleans, " { $link t } " for every vertex visted during the search, and " { $link f } " for every vertex not visited." } ;
 109
 110 HELP: full-depth-first
 111 { $values
 112     { "graph" "The graph to search" }
 113     { "pre" "A quotation of the form ( n -- )" }
 114     { "post" "A quotation of the form ( n -- )" }
 115     { "tail" "A quotation of the form ( -- )" }
 116     { "?" "A boolean describing whether or not the end-search error was thrown" } }
 117 { $description "Performs a depth-first search on " { $emphasis "graph" } ".  The variable " { $emphasis "graph" } "can be accessed in both quotations."
 118   $nl
 119   "The " { $emphasis "pre" } " quotation is run before the recursive application of depth-first."
 120   $nl
 121   "The " { $emphasis "post" } " quotation is run after the recursive application of depth-first."
 122   $nl
 123   "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." } ;
 124
 125 HELP: dag?
 126 { $values
 127     { "graph" graph }
 128     { "?" "A boolean indicating if the graph is acyclic" } }
 129 { $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." } ;
 130
 131 HELP: topological-sort
 132 { $values
 133     { "graph" graph }
 134     { "seq/f" "Either a sequence of values or f" } }
 135 { $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." } ;