Re: Port graphs: What would Rich Hickey do?
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?
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?
€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?
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? --
How to spec reducible collections
Suppose I want to spec a function like run!. run! takes an ifn? and a ‘coll’, where the coll argument may be any reducible collection (so coll? is really not the right choice, nor is seqable?). I tried to construct a spec for reducible collections but failed. The protocol used in reduce is extended to java.lang.Object, so (satisfies? CollReduce coll) will never produce a useful answer. How does one spec a function like run!? -- David -- 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.
