Harmonize spelling

[factor.git] / extra / path-finding / path-finding-docs.factor

diff --git a/extra/path-finding/path-finding-docs.factor b/extra/path-finding/path-finding-docs.factor
index dd66e4f76a91d69a715938951e8965075c8b6c0b..8d8b1c07980aeb86ccf21b30e81f86dde20ccb31 100644 (file)
--- a/extra/path-finding/path-finding-docs.factor
+++ b/extra/path-finding/path-finding-docs.factor
@@ -1,11 +1,13 @@
 ! Copyright (C) 2010 Samuel Tardieu.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: help.markup help.syntax ;
+USING: assocs help.markup help.syntax math sequences ;
 IN: path-finding
 
+{ <astar> <bfs> <dijkstra> } related-words
+
 HELP: astar
 { $description "This tuple must be subclassed and its method " { $link cost } ", "
-  { $link heuristic } ", and " { $link neighbours } " must be implemented. "
+  { $link heuristic } ", and " { $link neighbors } " must be implemented. "
   "Alternatively, the " { $link <astar> } " word can be used to build a non-specialized version." } ;
 
 HELP: cost
@@ -13,10 +15,10 @@ HELP: cost
   { "from" "a node" }
   { "to" "a node" }
   { "astar" "an instance of a subclassed " { $link astar } " tuple" }
-  { "n" "a number" }
+  { "n" number }
 }
 { $description "Return the cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
-  { $snippet "to" } " is necessarily a neighbour of " { $snippet "from" } "."
+  { $snippet "to" } " is necessarily a neighbor of " { $snippet "from" } "."
 } ;
 
 HELP: heuristic
@@ -24,13 +26,13 @@ HELP: heuristic
   { "from" "a node" }
   { "to" "a node" }
   { "astar" "an instance of a subclassed " { $link astar } " tuple" }
-  { "n" "a number" }
+  { "n" number }
 }
 { $description "Return the estimated (undervalued) cost to go from " { $snippet "from" } " to " { $snippet "to" } ". "
-  { $snippet "from" } " and " { $snippet "to" } " are not necessarily neighbours."
+  { $snippet "from" } " and " { $snippet "to" } " are not necessarily neighbors."
 } ;
 
-HELP: neighbours
+HELP: neighbors
 { $values
   { "node" "a node" }
   { "astar" "an instance of a subclassed " { $link astar } " tuple" }
@@ -40,24 +42,46 @@ HELP: neighbours
 
 HELP: <astar>
 { $values
-  { "neighbours" "a quotation with stack effect ( node -- seq )" }
-  { "cost" "a quotation with stack effect ( from to -- cost )" }
-  { "heuristic" "a quotation with stack effect ( pos target -- cost )" }
-  { "astar" "a astar tuple" }
+  { "neighbors" { $quotation ( node -- seq ) } }
+  { "cost" { $quotation ( from to -- cost ) } }
+  { "heuristic" { $quotation ( pos target -- cost ) } }
+  { "astar" astar }
 }
 { $description "Build an astar object from the given quotations. The "
-  { $snippet "neighbours" } " one builds the list of neighbours. The "
+  { $snippet "neighbors" } " one builds the list of neighbours. The "
   { $snippet "cost" } " and " { $snippet "heuristic" } " ones represent "
-  "respectively the cost for transitioning from a node to one of its neighbour, "
+  "respectively the cost for transitioning from a node to one of its neighbor, "
   "and the underestimated cost for going from a node to the target. This solution "
   "may not be as efficient as subclassing the " { $link astar } " tuple."
 } ;
 
+HELP: <bfs>
+{ $values
+  { "neighbors" assoc }
+  { "astar" astar }
+}
+{ $description "Build an astar object from the " { $snippet "neighbors" } " assoc. "
+  "When used with " { $link find-path } ", this astar tuple will use the breadth-first search (BFS) "
+  "path finding algorithm which is a particular case of the general A* algorithm."
+} ;
+
+HELP: <dijkstra>
+{ $values
+  { "costs" assoc }
+  { "astar" astar }
+}
+{ $description "Build an astar object from the " { $snippet "costs" } " assoc. "
+  "The assoc keys are edges of the graph, while the corresponding values are assocs whose keys are "
+  "the edges that can be reached and whose values are the costs to reach those edges. When used with "
+  { $link find-path } ", this astar tuple will use the Dijkstra path finding algorithm which is "
+  "a particular case of the general A* algorithm."
+} ;
+
 HELP: find-path
 { $values
   { "start" "a node" }
   { "target" "a node" }
-  { "astar" "a astar tuple" }
+  { "astar" astar }
   { "path/f" "an optimal path from " { $snippet "start" } " to " { $snippet "target" }
     ", or f if no such path exists" }
 }
@@ -67,19 +91,19 @@ HELP: find-path
 
 HELP: considered
 { $values
-  { "astar" "a astar tuple" }
-  { "considered" "a sequence" }
+  { "astar" astar }
+  { "considered" sequence }
 }
 { $description "When called after a call to " { $link find-path } ", return a list of nodes "
   "which have been examined during the A* exploration."
 } ;
 
-ARTICLE: "astar" "A* algorithm"
-"The " { $vocab-link "path-finding" } " vocabulary implements a graph search algorithm for finding the least-cost path from one node to another." $nl
-"The " { $link astar } " tuple may be derived from and its " { $link cost } ", " { $link heuristic } ", and " { $link neighbours } " methods overwritten, or the " { $link <astar> } " word can be used to build such an object from quotations." $nl
+ARTICLE: "path-finding" "Path finding using the A* algorithm"
+"The " { $vocab-link "path-finding" } " vocabulary implements a graph search algorithm for finding the least-cost path from one node to another using the A* algorithm." $nl
+"The " { $link astar } " tuple may be derived from and its " { $link cost } ", " { $link heuristic } ", and " { $link neighbors } " methods overwritten, or the " { $link <astar> } " or " { $link <bfs> } " words can be used to build a new tuple." $nl
 "Make an A* object:"
-{ $subsections <astar> }
+{ $subsections <astar> <bfs> }
 "Find a path between nodes:"
 { $subsections find-path } ;
 
-ABOUT: "astar"
+ABOUT: "path-finding"