Re: [Factor-talk] Directed graph queries via closure?
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 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.
Re: [Factor-talk] Directed graph queries via closure?
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 d
Re: [Factor-talk] Directed graph queries via closure?
The change to ``classes.private`` was to simplify the code, since it was a
simplified collection routine, albeit very similar to what is in ``graphs``.
If you try out the graphs code:
CONSTANT: my-graph H{
{ 1 H{ { 1 1 } { 2 2 } } }
{ 2 H{ { 3 3 } { 6 6 } } }
{ 4 H{ { 4 4 } { 5 5 } } }
{ 5 H{ { 5 5 } { 1 1 } } }
{ 6 H{ { 6 6 } { 1 1 } } }
}
IN: scratchpad 2 [ my-graph at ] closure keys natural-sort .
{ 1 2 3 6 }
IN: scratchpad 3 [ my-graph at ] closure keys natural-sort .
{ 3 }
IN: scratchpad 4 [ my-graph at ] closure keys natural-sort .
{ 1 2 3 4 5 6 }
You can see it follows all the edges generated by the quotation (my-graph
at) from a starting vertex.
If it isn't the right abstraction for you, I'm sure it wouldn't be too hard
to write a different routine?
On Sun, Mar 24, 2013 at 12:48 AM, CW Alston wrote:
> Greetings folks -
>
>
> I'm experimenting with directed graph possibilites over an inverted index
> (of terms in files)
>
> that I've designed. I'm stumbling on the use of the word closure defined
> IN: graphs,
>
> using hashtables:
>
>
> USING: graphs.private kernel ;
>
> IN: graphs
>
> : closure ( obj quot -- assoc )
>
> H{ } clone [ swap (closure) ] keep ; inline
>
>
> The article on 'Directed graph utilities' suggests that:
>
>
> "You can perform queries on the graph:
>
> closure ( obj quot -- assoc )
>
>
> Directed graphs are used to maintain cross-referencing information for
> Definitions."
>
>
> I want to implement just such cross-referencing & querying with my
> inverted index graph.
>
> It seems there are no example usages of the graphs-vocab closure, but
> there is a dopplegänger
>
> definition of closure IN: classes.private, which appears to do the same
> work using hash-sets:
>
>
> USING: kernel ;
>
> IN: classes.private
>
> : closure ( obj quot -- set )
>
> HS{ } clone [ swap (closure) ] keep ; inline
>
>
> I find the only(?) example use of the classes.private closure is in the
> definition of class-usages,
>
> which is opaque to me. I can't suss out what the construction
> sets:membersthere is doing.
>
> Although the recursive (closure) in its def has an obvious analogue in
> graph's (closure), both
>
> are a mite hairy.
>
>
> Can anyone soothe my perplexity with an illustration using closure on a
> directed graph?
>
> Much obliged,
>
> ~cw
>
>
>
> --
> 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
>
>
--
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
[Factor-talk] Directed graph queries via closure?
Greetings folks -
I'm experimenting with directed graph possibilites over an inverted index
(of terms in files)
that I've designed. I'm stumbling on the use of the word closure defined
IN: graphs,
using hashtables:
USING: graphs.private kernel ;
IN: graphs
: closure ( obj quot -- assoc )
H{ } clone [ swap (closure) ] keep ; inline
The article on 'Directed graph utilities' suggests that:
"You can perform queries on the graph:
closure ( obj quot -- assoc )
Directed graphs are used to maintain cross-referencing information for
Definitions."
I want to implement just such cross-referencing & querying with my inverted
index graph.
It seems there are no example usages of the graphs-vocab closure, but there
is a dopplegänger
definition of closure IN: classes.private, which appears to do the same
work using hash-sets:
USING: kernel ;
IN: classes.private
: closure ( obj quot -- set )
HS{ } clone [ swap (closure) ] keep ; inline
I find the only(?) example use of the classes.private closure is in the
definition of class-usages,
which is opaque to me. I can't suss out what the construction
sets:membersthere is doing.
Although the recursive (closure) in its def has an obvious analogue in
graph's (closure), both
are a mite hairy.
Can anyone soothe my perplexity with an illustration using closure on a
directed graph?
Much obliged,
~cw
--
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
