The graphs vocabulary is pretty primitive. Until recently, it belonged to
Factor's core vocabulary root, used early-on in the bootstrapping process.
[1] It was written awhile ago, using idioms that existed before the
current sets vocabulary. [2] But mostly, it's not much of a
general-purpose graph library. The only purpose it's built for is its
limited usage in cross-referencing (e.g., in the classes, tools.crossref,
and compilers.crossref vocabs). There was some work on a better vocab, but
it's unmaintained and incomplete. [3]
The graphs vocab treats directed graphs as a hash table from a vertex to a
set of vertices representing its in-neighborhood a.k.a. predecessor set.
[4] In various parts of the code base (not just the graphs vocab), you
still see hashtables getting used as sets [5], so hashtables like H{ { 1 1
} } are used instead of HS{ 1 }. Thus, we get the following:
IN: scratchpad USE: graphs
IN: scratchpad H{ } ! this is our graph
IN: scratchpad 1 { 2 3 } pick add-vertex ! add the edges 1 -> 2 & 1 -> 3
IN: scratchpad . ! show the graph
H{ { 2 H{ { 1 1 } } } { 3 H{ { 1 1 } } } }
Alternatively, you could think of `add-vertex` as instead adding the edges
1 <- 2 & 1 <- 3. Then the digraph becomes a hash table from vertices to
out-neighborhoods, and the `closure` word makes more sense. But the docs
[7] insist on the above interpretation! And it's a more ordinary way to
read the call---think like in graphviz, where you would write `1 -> { 2 3
}`.
The `closure` word computes the transitive closure of the graph [6] at a
given vertex---telling us which vertices are reachable from the input
vertex. Instead of taking a graph as its input, it takes a quotation that
tells you how to get the in/out-neighborhood of any given vertex. Now, the
way the graphs vocab is set up, this pretty much means you'll get the
transitive closure flowing in the *backwards* direction of your edges,
because your hashtable will only be able to access the vertex's
in-neighborhood. Which is confusing! But again, suitable for the graphs
vocab's usages.
An example would be clearer. So, say we set up the following:
IN: scratchpad USE: graphs
IN: scratchpad H{ } clone ! our graph
IN: scratchpad 1 { 2 } pick add-vertex ! 1 -> 2
IN: scratchpad 2 { 3 } pick add-vertex ! 2 -> 3
IN: scratchpad 3 { 4 } pick add-vertex ! 3 -> 4
IN: scratchpad dup . ! our graph: 1 -> 2 -> 3 -> 4
H{ { 4 H{ { 3 3 } } } { 2 H{ { 1 1 } } } { 3 H{ { 2 2 } } } }
IN: scratchpad '[ _ at ] ! quot to get the in-neighborhood of a vertex
Now we can start querying the `closure`. But somewhat confusingly, it's a
"backwards" closure. Maybe think of it as the closure of the graph "4 -> 3
-> 2 -> 1" instead of "1 -> 2 -> 3 -> 4".
IN: scratchpad 1 over closure .
H{ { 1 1 } }
IN: scratchpad 2 over closure .
H{ { 1 1 } { 2 2 } }
IN: scratchpad 3 over closure .
H{ { 1 1 } { 2 2 } { 3 3 } }
IN: scratchpad 4 over closure .
H{ { 1 1 } { 2 2 } { 3 3 } { 4 4 } }
Or how about trying this graph on for size?
IN: scratchpad H{ } clone
IN: scratchpad 1 { 2 3 } pick add-vertex
IN: scratchpad 2 { 4 5 } pick add-vertex
IN: scratchpad 3 { 6 } pick add-vertex
IN: scratchpad '[ _ at ]
IN: scratchpad 6 over closure .
H{ { 1 1 } { 6 6 } { 3 3 } }
IN: scratchpad 5 over closure .
H{ { 1 1 } { 5 5 } { 2 2 } }
IN: scratchpad 4 over closure .
H{ { 4 4 } { 1 1 } { 2 2 } }
IN: scratchpad 3 over closure .
H{ { 1 1 } { 3 3 } }
IN: scratchpad 2 over closure .
H{ { 1 1 } { 2 2 } }
IN: scratchpad 1 over closure .
H{ { 1 1 } }
Now, the duplicated code in the classes vocab has a much shorter
explanation: that was John fucking around with speed improvements a couple
weeks back. :) [8] He uses HS{ } instead of H{ } to represent the sets,
since (as explained) H{ } is kind of vestigial. Then, sets:members is used
to turn the HS{ } into a sequence. [9]
Hope that helps,
--Alex Vondrak
[1] See
http://factor-language.blogspot.com/2010/01/factors-bootstrap-process-explained.htmlfor
more on that. Pretty much all the links are now broken, but you can
easily track down the source code at https://github.com/slavapestov/factor
[2]
https://github.com/slavapestov/factor/commit/0f0571e48ad5e91d5fdf3717204d3812f0e72787
[3]
https://github.com/slavapestov/factor/tree/master/unmaintained/graph-theory
[4] https://en.wikipedia.org/wiki/Adjacent_%28graph_theory%29#Direction
[5] http://docs.factorcode.org/content/article-assocs-sets.html
[6] https://en.wikipedia.org/wiki/Transitive_closure#In_graph_theory
[7] http://docs.factorcode.org/content/word-add-vertex%2Cgraphs.html
[8]
https://github.com/slavapestov/factor/commit/03e6f48943c767d286e402b5c1833e8673339b3dWhich,
incidentally, is also around the time graphs got moved from core to
basis:
https://github.com/slavapestov/factor/commit/3ffacf75d269d58f6f28fe14590f6e472a6fa6cf
[9] http://docs.factorcode.org/content/word-members,sets.html
------------------------------------------------------------------------------
Everyone hates slow websites. So do we.
Make your web apps faster with AppDynamics
Download AppDynamics Lite for free today:
http://p.sf.net/sfu/appdyn_d2d_mar
_______________________________________________
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
