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 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? > > -- > 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.
