Re: Port graphs: What would Rich Hickey do?

2018-01-10 Thread Ben Kovitz 
On Monday, January 8, 2018 at 12:14:59 AM UTC-5, James Gatannah wrote:
 

> FWIW, I think https://leanpub.com/specter looks extremely interesting. 
> (Or it may be awful...I haven't had a chance to read it yet, much less work 
> through the exercises).
>

Actually, I worked through that ebook last week. (Or at least the version 
of the ebook in Google's cache. Leanpub's web site appears to be down.) 
It's excellent! It didn't go all that far, but it got across the main ideas 
very effectively.

I've been continuing to look at Specter, and the more I've learned, the 
better it's seemed. I have yet to try it myself on anything beyond toy 
examples, though. Currently I'm stumped on how to make a navigator for a 
data structure that doesn't work with 'get' and 'assoc'. There's probably 
still something elementary that I haven't understood yet. I just posted a 
question on the github site:
https://github.com/nathanmarz/specter/issues/241

--
Ben Kovitz
http://pages.iu.edu/~bkovitz/

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Port graphs: What would Rich Hickey do?

2018-01-07 Thread James Gatannah 


On Thursday, January 4, 2018 at 5:51:27 PM UTC-6, Ben Kovitz wrote:
>
>
> Well! So far, Specter appears to have taken the "path map" idea that I'd 
> been toying with to its ultimate logical conclusion—far better than I could 
> ever do it. Nathan Marz even says that needing to manipulate tricky graphs 
> "forced" him to come up with Specter. If I understand it correctly, Specter 
> would even allow me to map these peculiar port graphs to simplicial graphs 
> without adding any performance overhead.
>
> It looks like I'd need to write a custom navigator or two. I haven't yet 
> found a good tutorial for getting beyond the most elementary concepts of 
> Specter, though. Can you recommend one?
>

FWIW, I think https://leanpub.com/specter looks extremely interesting. (Or 
it may be awful...I haven't had a chance to read it yet, much less work 
through the exercises).

Regards,
James


> --
> Ben Kovitz
> http://pages.iu.edu/~bkovitz/
>
>

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Port graphs: What would Rich Hickey do?

2018-01-04 Thread Ben Kovitz 
I replied to Gary Verhaegen:

If you’re shopping around for ideas as to how to define data manipulation 
>> API, it may be worth taking some time looking at Specter too.
>>
>
> Thanks for this suggestion, too. I'm now checking it out.
>

Well! So far, Specter appears to have taken the "path map" idea that I'd 
been toying with to its ultimate logical conclusion—far better than I could 
ever do it. Nathan Marz even says that needing to manipulate tricky graphs 
"forced" him to come up with Specter. If I understand it correctly, Specter 
would even allow me to map these peculiar port graphs to simplicial graphs 
without adding any performance overhead.

It looks like I'd need to write a custom navigator or two. I haven't yet 
found a good tutorial for getting beyond the most elementary concepts of 
Specter, though. Can you recommend one?

--
Ben Kovitz
http://pages.iu.edu/~bkovitz/

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Port graphs: What would Rich Hickey do?

2018-01-04 Thread Christopher Small 
Yes; Datomic really is great. There's plenty of wonderful stuff I haven't
even mentioned, like database as a value, persistent history, snapshots at
a timepoint, transaction metadata, smart peer replication etc. It's kind of
the best thing since sliced bread. But if you don't need all that jazz and
are fine with keeping things in memory for your problem, you may wish to
consider DataScript. It's free and open source and has remarkably good
coverage of the entity, pull and q APIs, and can run in cljs or clj.

One final note: with respect to "type headache" and "chain[ing] anything to
anything", you're right; this is a major benefit over traditional SQL.
Attribute are fundamentally polymorphic, which can be super helpful with
tricky modelling problems.

Chris


On Thu, Jan 4, 2018 at 10:48 AM, Ben Kovitz  wrote:

> On Tuesday, January 2, 2018 at 3:11:45 PM UTC-5, Christopher Small wrote:
>
>
>> http://docs.datomic.com/entities.html
>>
>
>
>> http://docs.datomic.com/pull.html
>>
>
> Thanks—this is really good stuff! Not that I expected anything less, but
> it's a happy surprise that it applies so well to graphs. Now I'm wondering
> if I should just use Datomic rather than borrow ideas from it.
>
> One thing I'm convinced of now is that it's OK to assign ids to
> everything. I was cringing at that idea before, because it seems like an
> unnecessary layer of indirection and one more thing that could go wrong.
> But clearly Datomic's approach of assigning every "entity" an id enables
> some wonderful simplicity, since it enables one to very conveniently chain
> entities together. And when basically everything is an entity, that means
> you can chain anything to anything—which addresses the "type headache" I
> was trying to avoid.
>
> --
> Ben Kovitz
> http://pages.iu.edu/~bkovitz/
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with
> your first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to a topic in the
> Google Groups "Clojure" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/
> topic/clojure/uSwY475pbGA/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> clojure+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Port graphs: What would Rich Hickey do?

2018-01-04 Thread Gary Verhaegen 
Unfortunately most of the contexts were fairly specific and a few
years ago, so I don't remember all of the details, and mostly in the
context of private research that I'm not at liberty to share. Some of
the results have been published (though not my specific work) by a
then-colleague of mine; you can find his papers by googling "amine
ghrab graph olap".

On 4 January 2018 at 18:19, Ben Kovitz  wrote:
> On Thursday, January 4, 2018 at 4:01:41 AM UTC-5, Gary Verhaegen wrote:
>
>> Have you considered encoding your port graph into a normal graph?
>
>
> That was the first idea I had, and I quickly rejected it as adding
> complication. The consideration that led me to port graphs in the first
> place was that when, say, I have a node for "plus", and it has neighbor
> nodes for "operand" and "sum", which other nodes connect to, an easy bug is
> that when the "plus" is deleted, its "operand" and "sum" nodes might not get
> deleted—leaving the graph in an invalid state. I figured it would be best to
> just absorb those connection nodes into the "plus" node in the form of a
> list of "ports", and include the port labels in the edges. Then deleting the
> "plus" automatically deletes the ports, you can easily query for "what nodes
> are connected to the plus" (where you want to skip connection nodes), and
> generally there are fewer ways to make mistakes in the code.
>
> However, following Christopher Small's suggestion to check out the Datomic
> APIs, I'm now thinking that a layer to map the port graphs to simplicial
> ("normal", undirected) graphs might actually be the simplest thing. Nodes,
> ports, and edges are easily represented by nodes in a simplicial graph. This
> escapes the "type headache" that led me to start this thread, since all
> edges in the port graph are just plain nodes in the simplicial graph,
> whether they're port-to-port edges, port-to-edge edges, or edge-to-edge
> edges. The layer of indirection might cost some performance—and performance
> does matter here, since this program is extremely CPU-bound—but it's more
> important to preëmpt bugs by keeping code simple.
>
> And now you make this interesting point, which I hadn't previously
> considered:
>
>> That would require you to define a mapping, but would then allow you to
>> fairly easily reuse theorems, algorithms and libraries by having them
>> operate on the encoded graph, with a hopefully thin layer of translation.
>
>
> I could even use ubergraph to represent the simplicial graph, and thereby
> get access to all code that follows the loom protocols.
>
>> I have seen this approach of encoding graphs into other graphs work out
>> pretty well in other contexts.
>
>
> Do you remember any of those other contexts? Maybe I could check one out and
> learn something from it.
>
>> If you’re shopping around for ideas as to how to define data manipulation
>> API, it may be worth taking some time looking at Specter too.
>
>
> Thanks for this suggestion, too. I'm now checking it out.
>
> --
> Ben Kovitz
> http://pages.iu.edu/~bkovitz/
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups
> "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to clojure+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Port graphs: What would Rich Hickey do?

2018-01-04 Thread Ben Kovitz 
On Thursday, January 4, 2018 at 4:01:41 AM UTC-5, Gary Verhaegen wrote:

Have you considered encoding your port graph into a normal graph?


That was the first idea I had, and I quickly rejected it as adding 
complication. The consideration that led me to port graphs in the first 
place was that when, say, I have a node for "plus", and it has neighbor 
nodes for "operand" and "sum", which other nodes connect to, an easy bug is 
that when the "plus" is deleted, its "operand" and "sum" nodes might not 
get deleted—leaving the graph in an invalid state. I figured it would be 
best to just absorb those connection nodes into the "plus" node in the form 
of a list of "ports", and include the port labels in the edges. Then 
deleting the "plus" automatically deletes the ports, you can easily query 
for "what nodes are connected to the plus" (where you want to skip 
connection nodes), and generally there are fewer ways to make mistakes in 
the code.

However, following Christopher Small's suggestion to check out the Datomic 
APIs, I'm now thinking that a layer to map the port graphs to simplicial 
("normal", undirected) graphs might actually be the simplest thing. Nodes, 
ports, and edges are easily represented by nodes in a simplicial graph. 
This escapes the "type headache" that led me to start this thread, since 
all edges in the port graph are just plain nodes in the simplicial graph, 
whether they're port-to-port edges, port-to-edge edges, or edge-to-edge 
edges. The layer of indirection might cost some performance—and performance 
does matter here, since this program is extremely CPU-bound—but it's more 
important to preëmpt bugs by keeping code simple.

And now you make this interesting point, which I hadn't previously 
considered:

That would require you to define a mapping, but would then allow you to 
> fairly easily reuse theorems, algorithms and libraries by having them 
> operate on the encoded graph, with a hopefully thin layer of translation.


I could even use ubergraph to represent the simplicial graph, and thereby 
get access to all code that follows the loom protocols. 

I have seen this approach of encoding graphs into other graphs work out 
> pretty well in other contexts.


Do you remember any of those other contexts? Maybe I could check one out 
and learn something from it.

If you’re shopping around for ideas as to how to define data manipulation 
> API, it may be worth taking some time looking at Specter too.
>

Thanks for this suggestion, too. I'm now checking it out.
 
--
Ben Kovitz
http://pages.iu.edu/~bkovitz/

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Port graphs: What would Rich Hickey do?

2018-01-04 Thread Ben Kovitz 
On Tuesday, January 2, 2018 at 3:11:45 PM UTC-5, Christopher Small wrote:
 

> http://docs.datomic.com/entities.html
>
 

> http://docs.datomic.com/pull.html
>

Thanks—this is really good stuff! Not that I expected anything less, but 
it's a happy surprise that it applies so well to graphs. Now I'm wondering 
if I should just use Datomic rather than borrow ideas from it.

One thing I'm convinced of now is that it's OK to assign ids to everything. 
I was cringing at that idea before, because it seems like an unnecessary 
layer of indirection and one more thing that could go wrong. But clearly 
Datomic's approach of assigning every "entity" an id enables some wonderful 
simplicity, since it enables one to very conveniently chain entities 
together. And when basically everything is an entity, that means you can 
chain anything to anything—which addresses the "type headache" I was trying 
to avoid.

--
Ben Kovitz
http://pages.iu.edu/~bkovitz/

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Port graphs: What would Rich Hickey do?

2018-01-04 Thread Gary Verhaegen 
If you’re shopping around for ideas as to how to define data manipulation API, 
it may be worth taking some time looking at Specter too.

Have you considered encoding your port graph into a normal graph? That would 
require you to define a mapping, but would then allow you to fairly easily 
reuse theorems, algorithms and libraries by having them operate on the encoded 
graph, with a hopefully thin layer of translation.

One possible encoding based on what you’ve described could be to turn nodes and 
edges in the port graph into nodes in the encoded graph, and ports in the port 
graph into edges in the encoded graph. It’s hard to say how well that specific 
transform would work in your case without more details about your type of graph 
and somewhat more considerate thinking than I’ve given this, but I have seen 
this approach of encoding graphs into other graphs work out pretty well in 
other contexts.

> On 2 Jan 2018, at 20:11, Christopher Small  wrote:
> 
> > ...noticed that the attribute names in the datoms are a lot like the port 
> > labels in port graphs. A port label is essentially an attribute key whose 
> > value is the edges incident to it. And when you chain data patterns in 
> > Datalog queries, that's a lot like navigating through a graph.
> 
> That's very much in line with what I was thinking you might want to do in 
> this setting.
> 
> You should also take a look at the entity api. It let's you traverse the 
> graph via these entity objects which behave more or less like a dictionary of 
> the av pairs associated with a particular entity in the database. Importantly 
> though, when an attribute points to another entity (a reference attribute), 
> it is returned as yet another of these entity objects, letting you traverse 
> the graph using get, in a pretty similar fashion to what you're describing.
> 
> http://docs.datomic.com/entities.html
> 
> You may also check out the pull api. It let's you pull facts out of the graph 
> as regular old maps by specifying what attributes & paths you wish to pull 
> out of the graph. The result is that you can read from the underlying graph 
> database as though it was a document store, but where the documents are 
> dynamically computed/queried from the graph based on the pull expression you 
> provide. You can also use pull expressions inside the `:find` clause of 
> either a DataScript of Datomic datalog query, which is often a convenient way 
> of specifying both a set of entities (via a datalog query) and statement of 
> facts to pull about them.
> 
> http://docs.datomic.com/pull.html
> 
> Collectively, these three interfaces give you quite a lot of expressiveness 
> and flexibility in how you query/traverse your data.
> 
> 
> 
>> On Tue, Jan 2, 2018 at 12:31 PM, Ben Kovitz  wrote:
>> Christopher Small,
>> 
>> Your suggestion to look into Datomic definitely turned up a new idea. I went 
>> through the Datalog tutorial at http://www.learndatalogtoday.org (which is 
>> excellent, by the way), and noticed that the attribute names in the datoms 
>> are a lot like the port labels in port graphs. A port label is essentially 
>> an attribute key whose value is the edges incident to it. And when you chain 
>> data patterns in Datalog queries, that's a lot like navigating through a 
>> graph.
>> 
>> The new, hopefully simple, easy-to-use, and not error-prone idea is to use 
>> the clojure.lang.IPersistentMap  interface to query and update graphs. 
>> Nodes, edge, attribute names, port labels, and a few "reserved keywords" 
>> like :adj-nodes and :edge, could navigate the graph as if it were an 
>> ordinary nested map with get-in, assoc-in, and the like, without ever 
>> needing to wrap anything inside a record to tell what it is. Here are some 
>> sample queries and what they could return:
>> 
>> (get-in g [node port-label :adj-nodes])
>>   a coll of all the nodes with an edge to [node port-label]
>> (get-in g [node port-label :adj-node])
>>   one node with an edge to [node port-label], or nil
>> (get-in g [node port-label])
>>   true or false, according to whether node has a port named port-label
>> (get-in g [node k])
>>   value of node's attr k
>> (get-in g [edge k])
>>   value of edge's attr k
>> (get g node-or-edge)
>>   the entire map of attrs associated with node-or-edge, or nil if it does 
>> not exist
>> (get-in g [node k1 k2 k3])
>>   treat node's attrs as a nested map
>> (get-in [node port-label :edges])
>>   a coll of all the edges that link to [node port-label]
>> (get-in [node port-label :edge])
>>   a single edge that links to port-label, or nil
>> (get-in [node port-label1 port-label2])
>>   coll of all nodes that link to [node port-label1] from a port named 
>> port-label2
>> 
>> And here are some function calls that would return a modified graph:
>> 
>> (assoc-in g [node k] v)
>>   sets node attr k to v
>> (assoc-in g [edge k] v)
>>   sets edge attr k to v  (and similarly for multiple keys)
>>

Re: Port graphs: What would Rich Hickey do?

2018-01-02 Thread Christopher Small 
> ...noticed that the attribute names in the datoms are a lot like the port
labels in port graphs. A port label is essentially an attribute key whose
value is the edges incident to it. And when you chain data patterns in
Datalog queries, that's a lot like navigating through a graph.

That's very much in line with what I was thinking you might want to do in
this setting.

You should also take a look at the entity api. It let's you traverse the
graph via these entity objects which behave more or less like a dictionary
of the av pairs associated with a particular entity in the database.
Importantly though, when an attribute points to another entity (a reference
attribute), it is returned as yet another of these entity objects, letting
you traverse the graph using get, in a pretty similar fashion to what
you're describing.

http://docs.datomic.com/entities.html

You may also check out the pull api. It let's you pull facts out of the
graph as regular old maps by specifying what attributes & paths you wish to
pull out of the graph. The result is that you can read from the underlying
graph database as though it was a document store, but where the documents
are dynamically computed/queried from the graph based on the pull
expression you provide. You can also use pull expressions inside the
`:find` clause of either a DataScript of Datomic datalog query, which is
often a convenient way of specifying both a set of entities (via a datalog
query) and statement of facts to pull about them.

http://docs.datomic.com/pull.html

Collectively, these three interfaces give you quite a lot of expressiveness
and flexibility in how you query/traverse your data.



On Tue, Jan 2, 2018 at 12:31 PM, Ben Kovitz  wrote:

> Christopher Small,
>
> Your suggestion to look into Datomic definitely turned up a new idea. I
> went through the Datalog tutorial at http://www.learndatalogtoday.org
> (which is excellent, by the way), and noticed that the attribute names in
> the datoms are a lot like the port labels in port graphs. A port label is
> essentially an attribute key whose value is the edges incident to it. And
> when you chain data patterns in Datalog queries, that's a lot like
> navigating through a graph.
>
> The new, hopefully simple, easy-to-use, and not error-prone idea is to use
> the clojure.lang.IPersistentMap  interface to query and update graphs.
> Nodes, edge, attribute names, port labels, and a few "reserved keywords"
> like :adj-nodes and :edge, could navigate the graph as if it were an
> ordinary nested map with get-in, assoc-in, and the like, without ever
> needing to wrap anything inside a record to tell what it is. Here are some
> sample queries and what they could return:
>
> (get-in g [node port-label :adj-nodes])
>   a coll of all the nodes with an edge to [node port-label]
> (get-in g [node port-label :adj-node])
>   one node with an edge to [node port-label], or nil
> (get-in g [node port-label])
>   true or false, according to whether node has a port named port-label
> (get-in g [node k])
>   value of node's attr k
> (get-in g [edge k])
>   value of edge's attr k
> (get g node-or-edge)
>   the entire map of attrs associated with node-or-edge, or nil if it does
> not exist
> (get-in g [node k1 k2 k3])
>   treat node's attrs as a nested map
> (get-in [node port-label :edges])
>   a coll of all the edges that link to [node port-label]
> (get-in [node port-label :edge])
>   a single edge that links to port-label, or nil
> (get-in [node port-label1 port-label2])
>   coll of all nodes that link to [node port-label1] from a port named
> port-label2
>
> And here are some function calls that would return a modified graph:
>
> (assoc-in g [node k] v)
>   sets node attr k to v
> (assoc-in g [edge k] v)
>   sets edge attr k to v  (and similarly for multiple keys)
> (assoc-in g [node1 port-label1 port-label2 node2] :edge)
>   makes an edge between [node1 port-label1] and [node2 port-label2]
> (assoc-in g [node1 port-label1 port-label2 :edge k] v)
>   sets value of edge attr k to v
>
> I haven't yet thought this through completely, and I suspect that some
> parts are still error-prone. For example, notice in the last function call
> that it's not clear whether you should include node2. The approach might be
> "too cute"—that is, brittle because it tries to impose one kind of
> structure (nested maps) onto one that isn't fully isomorphic (graphs).
>
> But I like the basic idea of having a "little language" for designating
> whatever you want, and the little language is nothing but a sequence that
> tells how to navigate through the graph to find (or make) what you're
> interested in.
>
> This would solve the fundamental problem of how to designate an edge
> without imposing type restrictions. For each connection point, you just
> have a sequence that describes a path to that point. If the sequence ends
> on a port label, the connection point is a port. If it ends on :edge, the
> connection point is an edge.

Re: Port graphs: What would Rich Hickey do?

2018-01-02 Thread Ben Kovitz 
Christopher Small,

Your suggestion to look into Datomic definitely turned up a new idea. I 
went through the Datalog tutorial at http://www.learndatalogtoday.org 
(which is excellent, by the way), and noticed that the attribute names in 
the datoms are a lot like the port labels in port graphs. A port label is 
essentially an attribute key whose value is the edges incident to it. And 
when you chain data patterns in Datalog queries, that's a lot like 
navigating through a graph.

The new, hopefully simple, easy-to-use, and not error-prone idea is to use 
the clojure.lang.IPersistentMap  interface to query and update graphs. 
Nodes, edge, attribute names, port labels, and a few "reserved keywords" 
like :adj-nodes and :edge, could navigate the graph as if it were an 
ordinary nested map with get-in, assoc-in, and the like, without ever 
needing to wrap anything inside a record to tell what it is. Here are some 
sample queries and what they could return:

(get-in g [node port-label :adj-nodes])
  a coll of all the nodes with an edge to [node port-label]
(get-in g [node port-label :adj-node])
  one node with an edge to [node port-label], or nil
(get-in g [node port-label])
  true or false, according to whether node has a port named port-label
(get-in g [node k])
  value of node's attr k
(get-in g [edge k])
  value of edge's attr k
(get g node-or-edge)
  the entire map of attrs associated with node-or-edge, or nil if it does 
not exist
(get-in g [node k1 k2 k3])
  treat node's attrs as a nested map
(get-in [node port-label :edges])
  a coll of all the edges that link to [node port-label]
(get-in [node port-label :edge])
  a single edge that links to port-label, or nil
(get-in [node port-label1 port-label2])
  coll of all nodes that link to [node port-label1] from a port named 
port-label2

And here are some function calls that would return a modified graph:

(assoc-in g [node k] v)
  sets node attr k to v
(assoc-in g [edge k] v)
  sets edge attr k to v  (and similarly for multiple keys)
(assoc-in g [node1 port-label1 port-label2 node2] :edge)
  makes an edge between [node1 port-label1] and [node2 port-label2]
(assoc-in g [node1 port-label1 port-label2 :edge k] v)
  sets value of edge attr k to v

I haven't yet thought this through completely, and I suspect that some 
parts are still error-prone. For example, notice in the last function call 
that it's not clear whether you should include node2. The approach might be 
"too cute"—that is, brittle because it tries to impose one kind of 
structure (nested maps) onto one that isn't fully isomorphic (graphs).

But I like the basic idea of having a "little language" for designating 
whatever you want, and the little language is nothing but a sequence that 
tells how to navigate through the graph to find (or make) what you're 
interested in. 

This would solve the fundamental problem of how to designate an edge 
without imposing type restrictions. For each connection point, you just 
have a sequence that describes a path to that point. If the sequence ends 
on a port label, the connection point is a port. If it ends on :edge, the 
connection point is an edge. So, instead of type restrictions, there are 
just a few reserved words in the tiny DSL for navigating the graph.

This hopefully makes simple editing and querying of port graphs easy, but 
it does not even try to solve the problem of conveniently entering a graph. 
I figure that a "shorthand", i.e. a separate tiny DSL, is the solution for 
that. I found with my current implementation of port graphs that it really 
helped to use a custom shorthand for each specific type of graph. For 
example, there's a obvious and very nice shorthand for specifying graphs 
that represent mathematical expressions, but it's terrible for graphs of 
social networks. Graphs of social networks, though, can be conveniently 
described by their own custom sexprs.

I figure that implementing it will force me to think this idea through the 
rest of the way. Here goes…

--
Ben Kovitz
http://pages.iu.edu/~bkovitz/


-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Port graphs: What would Rich Hickey do?

2018-01-01 Thread Ben Kovitz 
On Monday, January 1, 2018 at 7:57:11 PM UTC-5, Christopher Small wrote:

…you might want to look at Datomic (also authored by Rich Hickey), 
> DataScript (an in-memory approximation) or RDF (data language of the 
> Semantic Web). They model graphs as `(entity, attribute, value)` triples, 
> where `attribute`s can act as labeled, directional arrows between entities, 
> and can themselves show up in the `entity` position of other triples, thus 
> allowing you to have "meta-attributes" (attributes pointing to/from other 
> attributes).


Datomic might be just the dose of simplicity I was looking for! I haven't 
yet used Datomic, so now is probably a very good time to try it out. I had 
thought that Datomic might make a good underlying implementation rather 
than the API, but now I wonder if the Datomic API has ideas I could use. 
The entity-attribute-value approach sounds to me like one of the best ideas 
ever (long predating computers, even). Thanks! I'll have a closer look. 
This might even be what Rich Hickey would do! :)

Do you need to be able to attach data to specific edges instances?
>

Yes. Every edge needs to be able to have an arbitrary map of attributes.

Or would it be sufficient to be able to have different types of edges, and 
> be able to associate data with those abstract edge types?
>

I'd like to be able to treat all edges the same.
 

> This is for a research project, so I need to be able to try out new ideas 
quickly to see how they perform. I've been using an implementation of port 
graphs modeled on ubergraph with some success, where all nodes and edges 
can have arbitrary attribute maps associated with them. Where I've needed 
edges that link to edges, I've used a couple hacks, like making a separate 
graph where some of the nodes are edges from the main graph. The nuisance 
of using those hacks has been steering me away from trying out promising 
ideas that freely make use of edge-to-edge edges. So, I figure that it's 
time to just implement this right and be done with it.

The fact that it's a research project makes minimal error-proneness 
especially important. It's often hard to know in advance what the correct 
behavior looks like. The reason for writing the program is to find out.
 

> Obviously, this is a little bit different from your "ports" idea (I 
> haven't read about this; is it published on anywhere?), but in some ways a 
> helpful restriction.
>

If you google for "port graphs", you'll find some stuff. It's not clear to 
me why, but port graphs seem to be popular for "graph-rewriting systems" 
(also googlable). I'm working on something like a graph rewriting system. I 
hit on the idea as a way to make the graph simpler, and only later found 
out that there's already a standard name for these graphs and even some 
good research literature. There's *some* sort of natural fit here.
 

> For example, `mom` vs `child` is isomorphic to an edge labeled 
> `isMotherOf`. But simpler, because there's less to specify, and in 
> particular, less to get wrong with respect to which kinds of ports can 
> connect to which kinds of other ports.
>

Something I've liked about the port graphs up until now is that it's easy 
to add an explicit representation of rules for which kinds of ports can 
connect and which can't. The current implementation (the one without 
edge-to-edge edges) has some "shorthand" functions that exploit those rules 
so that you can specify some edges very simply, often without explicitly 
providing the port labels, since the system can (in some cases) deduce 
them. Most of my previous experiences with programming involving graphs 
have involved a lot of hard-to-read code and a lot of sweating and gritting 
my teeth while trying to avoid bugs. The ports-rules-and-shorthand approach 
has enabled to me keep the code mostly readable. In fact, much of the code 
is just static data that specifies small subgraphs—in a pretty readable way.

The rules are also nicely separable from the generic aspects of the graph. 
I added a couple protocols beyond the loom protocols: one for creating new 
nodes of a given 'class', so they can get ids and attributes assigned to 
them automatically; and one for consulting the rules for legal connections.

But it's clearly time for me to look at this in a new way. I like your 
observation that (in effect) edge classes of the form (port-label1, 
port-label2) are isomorphic to edges between ports. That and Datomic might 
be exactly the whack(s) on the side of the head that I needed!

--
Ben Kovitz
http://pages.iu.edu/~bkovitz/


-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You

Re: Port graphs: What would Rich Hickey do?

2018-01-01 Thread Christopher Small 

Do you need to be able to attach data to specific edges instances? Or would 
it be sufficient to be able to have different types of edges, and be able 
to associate data with those abstract edge types?

If the latter, you might want to look at Datomic (also authored by Rich 
Hickey), DataScript (an in-memory approximation) or RDF (data language of 
the Semantic Web). They model graphs as `(entity, attribute, value)` 
triples, where `attribute`s can act as labeled, directional arrows between 
entities, and can themselves show up in the `entity` position of other 
triples, thus allowing you to have "meta-attributes" (attributes pointing 
to/from other attributes).

Obviously, this is a little bit different from your "ports" idea (I haven't 
read about this; is it published on anywhere?), but in some ways a helpful 
restriction. For example, `mom` vs `child` is isomorphic to an edge labeled 
`isMotherOf`. But simpler, because there's less to specify, and in 
particular, less to get wrong with respect to which kinds of ports can 
connect to which kinds of other ports. So IMHO, simple labeled directional 
edges are best when semantically sufficient.

If either data needs to be attached to edges, or there are semantics of the 
modeling of things in terms of ports which are advantageous, you can still 
use EAV to model this data. You would just have entities modeling the edges 
and/or ports, and connect them using triples along the lines of `[[edge 
:my.graph.edge/from node-or-port-1] [edge :my.graph.edge/to node-or-port-2] 
[edge :my.graph.edge/label "a really cool edge"]]`. With Datomic or 
DataScript, you'd then be able to put together a set of Datalog rules which 
represent whatever higher level graph relations that might be useful. 
(Datalog is awesome, BTW)

Interested to hear what you think of this idea :-)

Chris



On Monday, January 1, 2018 at 3:07:28 PM UTC-7, Ben Kovitz wrote:
>
> I'm making a little library for myself to represent a kind of graph. I 
> want to
> make it simple, the way Rich Hickey designed much of Clojure. My designs so
> far have lacked that kind of plainness and ease of use. I keep wondering,
> "What would Rich Hickey do?" Even if you're not Rich Hickey, maybe you can
> suggest something. I'd love to hear some ideas about how to design this.
>
> This kind of graph is different from most graphs in two ways:
>
> (1) Edges connect to "ports" rather than simply to nodes. A port is a tuple
> (node, port-label). So, for example, if you had nodes :elizabeth and 
> :charles,
> you might have an edge connecting :elizabeth's "child" port to :charles's
> "mother" port, rather than simply an edge connecting :elizabeth and 
> :charles.
>
> (2) Edges can connect to edges as well as to ports. For example, the
> aforementioned edge might itself be connected by an edge to the "attests" 
> port
> of a node :royal-document-22416.
>
> These differences from ordinary graphs preclude the use of the loom 
> protocols
> or implementations such as ubergraph. I would like also to allow any 
> arbitrary
> map to be associated with any node or edge, just as ubergraph allows. By 
> the
> way, if you know of a standard name for this kind of graph, please tell me.
> It's not quite the same as a hypergraph. Note also that directed graphs 
> are a
> special case of this kind of graph, since the port labels can imply 
> asymmetry
> if you like. For example, if you only use labels :in and :out for ports, 
> then
> you have an ordinary directed graph.
>
> The fact that edges can connect to edges seems to be the main source of my
> difficulties. I would like to allow nodes and port labels to be of any data
> type: keywords, strings, vectors, anything, even graphs and edges from 
> graphs.
> The library should make no assumptions about the data types of the nodes 
> and
> port labels. So, when passing arguments to functions in the library, you 
> can't
> have a convention like "a 2-element vector represents a port" or "a 
> 2-element
> vector of 2-element vectors represents an edge".
>
> 
>
> Here are the main design ideas that I've entertained so far:
>
> 1. I could wrap nodes, ports, and edges in records, like this:
>
>   (defrecord Node [nodeid])
>   (defrecord Port [nodeid port-label])
>   (defrecord Edge [connpt1 connpt2])
>
> where connpt1 and connpt2 are "connection points": either a port or an 
> edge.
> This completely disambiguates everything. Library functions never look 
> inside
> a nodeid or port-label, but they can look inside a connection point as 
> needed.
>
> To add a node or edge to a graph g, you could call:
>
>   (defn add [g elem] ...)
>
> where elem must be a Node or Edge record.
>
> A problem with this is that it's a pain to use. Every time you call a 
> function
> like 'add', you have to wrap all the nodes. Wrapping edges is slightly 
> more of
> a nuisance.
>
> Another problem is that some decisions seem unclear and

Re: Port graphs: What would Rich Hickey do?

2018-01-01 Thread Raoul Duke 
€0.02 i like option #3, i think it would be possibly nice for edges to be
named based on the ports they connect.

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Port graphs: What would Rich Hickey do?

2018-01-01 Thread Ben Kovitz 
I'm making a little library for myself to represent a kind of graph. I want 
to
make it simple, the way Rich Hickey designed much of Clojure. My designs so
far have lacked that kind of plainness and ease of use. I keep wondering,
"What would Rich Hickey do?" Even if you're not Rich Hickey, maybe you can
suggest something. I'd love to hear some ideas about how to design this.

This kind of graph is different from most graphs in two ways:

(1) Edges connect to "ports" rather than simply to nodes. A port is a tuple
(node, port-label). So, for example, if you had nodes :elizabeth and 
:charles,
you might have an edge connecting :elizabeth's "child" port to :charles's
"mother" port, rather than simply an edge connecting :elizabeth and 
:charles.

(2) Edges can connect to edges as well as to ports. For example, the
aforementioned edge might itself be connected by an edge to the "attests" 
port
of a node :royal-document-22416.

These differences from ordinary graphs preclude the use of the loom 
protocols
or implementations such as ubergraph. I would like also to allow any 
arbitrary
map to be associated with any node or edge, just as ubergraph allows. By the
way, if you know of a standard name for this kind of graph, please tell me.
It's not quite the same as a hypergraph. Note also that directed graphs are 
a
special case of this kind of graph, since the port labels can imply 
asymmetry
if you like. For example, if you only use labels :in and :out for ports, 
then
you have an ordinary directed graph.

The fact that edges can connect to edges seems to be the main source of my
difficulties. I would like to allow nodes and port labels to be of any data
type: keywords, strings, vectors, anything, even graphs and edges from 
graphs.
The library should make no assumptions about the data types of the nodes and
port labels. So, when passing arguments to functions in the library, you 
can't
have a convention like "a 2-element vector represents a port" or "a 
2-element
vector of 2-element vectors represents an edge".



Here are the main design ideas that I've entertained so far:

1. I could wrap nodes, ports, and edges in records, like this:

  (defrecord Node [nodeid])
  (defrecord Port [nodeid port-label])
  (defrecord Edge [connpt1 connpt2])

where connpt1 and connpt2 are "connection points": either a port or an edge.
This completely disambiguates everything. Library functions never look 
inside
a nodeid or port-label, but they can look inside a connection point as 
needed.

To add a node or edge to a graph g, you could call:

  (defn add [g elem] ...)

where elem must be a Node or Edge record.

A problem with this is that it's a pain to use. Every time you call a 
function
like 'add', you have to wrap all the nodes. Wrapping edges is slightly more 
of
a nuisance.

Another problem is that some decisions seem unclear and arbitrary, hence
error-prone for a caller. For example, what should the 'nodes' function
return: nodes wrapped in Node records, or unwrapped nodes? Each choice seems
reasonable—hence you can easily assume the wrong choice when writing code 
that
calls the library.

2. I could put two kinds of function in the library: some with wrapped
arguments and return values, and equivalents with unwrapped values. So, for
example, there could be:

  (defn add [g elem] ...)  ;same as above
  (defn add-nodes [g & nodeids] ...)
  (defn add-edges [g & edges] ...)  ;each edge is, uh, I'm not sure
  (defn has? [g elem] ...)  ;elem must be wrapped
  (defn has-node? [g nodeid] ...)  ;unwrapped
  (defn has-edge? [g connpt1 connpt2) ...)  ;uh...
  (defn nodes [g] ...)  ;returns Node records
  (defn nodes-unwrapped [g] ...)  ;returns nodeids

It's still not fully clear how to pass edges to 'add-edges' and 'has-edge?'.
You can't assume a convention like [nodeid1 port-label1 nodeid2 port-label2]
because edges are allowed as connection points. Maybe edges would still 
always
need to be wrapped.

3. Inspired by this hypergraph library by bdesham:
https://github.com/bdesham/hitting-set/blob/master/README.md
I could give ids to edges as well as to nodes. However, most edges that I
anticipate working with will not have a meaningful id other than "the edge
between these connection points."

4. I could have a few "shorthand" functions for describing graphs with a
little DSL, in addition to the core API which would require all graph
elements to be wrapped. The shorthand DSL could be written to make the most
common kinds of graphs and subgraphs very convenient to describe, maybe even
sacrificing full generality.



OK, that's enough. I'm probably missing something obvious here—obvious, at
least, to Rich Hickey or someone with more Clojure experience. Would you 
care
to smack me on the side of the head with the bit of sense that I'm missing?
How could you keep this simple and easy to use?

--