John, Alex -
Thanks for these very interesting replies. It seems I am looking past a
simple interpretation of what *closure* is aiming to do,
on one hand, yet I've also dog-paddled into the deep end of the graph
development pool. Curiouser & curiouser!
Both insights are helpful; I'll try to squint them into focus, 'cuz I
really want to use this idiom.
Cheers!
~cw
On Sun, Mar 24, 2013 at 9:28 AM, Alex Vondrak <ajvond...@gmail.com> wrote:
> 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
>
--
*~ Memento Amori*
------------------------------------------------------------------------------
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
