Making navigators for port graphs

[bkovitz]

I'm trying to make some navigators that would implement a mapping from a port-graph abstraction where edges can connect to edges to simplicial graphs represented in in ubergraph. Ubergraph follows the loom protocols, with some helpful extensions, especially set-attrs. I'm hoping to enable something like this:

(select [:node] g)                   ;return [:node] if it exists in g, else [nil]
(select [:node :port-label] g)       ;return [:port-id] of designated port
(select [:node :port-label EDGES] g) ;return all edges that link to port
(select [:edge :port-label NODE] g)  ;return [:node] that owns :port-label connected to :edge
(select [:node ATTRS :k1 :k2] g)     ;same as [(get-in (uber/attrs g :node) [:k1 :k2])]
(transform [:node ATTRS MAP-VALS] inc g) ;etc.

There are a couple things I haven't figured out yet. Could you point me in a useful direction or perhaps correct some elementary conceptual confusion on my part?

(1) It appears that somehow I need to override the ImplicitNavs defined in specter.cljc to work differently when operating on a graph. I haven't yet found a hook for this. Would I somehow override keypath*? This is because get isn't the right function to call to look up a node or edge. Or is this just completely the wrong approach?

(2) While navigating through a graph, we always have the same "structure"—the graph—but with a different "current location" in it. This is slightly different than navigating through nested maps, where there is always a new "structure" each time you take the next step down a "path". Perhaps I could wrap the graph plus the id of the node/port/edge in a little record and pass that around? I don't like that idea, though, since it would generate a lot of dynamic memory allocation, and I haven't found anything that looks like that in the Specter code.

Does Specter just require that the "structure" satisfy IPersistentMap or something like it?

If it's simpler to answer, just ignore the ports. If this can't be done with a simplicial graph, then it can't be done with a port graph. But if you give me a hint about how to make it work with simplicial graphs, that might be enough for me to figure out how to do it for port graphs.

[nathanmarz]

Specter has no requirements upon the data structures it operates on. Data structure manipulation is entirely encapsulated by navigators, which are completely extensible using defnav and friends.

To build your graph navigators, you want to make your own navigators using the navigator building abstractions, primarily defnav. It's helpful to read the source to see how existing navigators are defined: https://github.com/nathanmarz/specter/blob/master/src/clj/com/rpl/specter.cljc#L627

I have my own private graph navigation library where I can do things like: (transform [TOPSORT (collect PARENTS (attr :name)) (attr :family-name)] (fn [parent-names _] ...) graph). That adds the :family-name attribute to every node in a graph in topological order based on the :name attributes of the parent nodes in the graph.

Your instinct to navigate to pair of [graph node-id] is exactly what I do with my graph navigators. TOPSORT for instance navigates to those pairs in topological order, doing a reduce in the transform so that future steps operate on the updtaed graph. NODE navigates from that pair to whatever the value is for that node id. PARENTS is an easy navigation from [graph node-id] to [graph parent-id] for each parent.

[bkovitz]

Thanks. That definitely gives me some hints. Any suggestion for how to change the behavior of keywords so they do something other than get? Or do I need to wrap a keyword in a navigator with a parameter, like (find-node :nodeid)?

[nathanmarz]

You should supply the keyword as an argument to a navigator.

[bkovitz]

Just wanted to say thanks—for your answers and for writing Specter! Once I got over the idea that I needed to override the ImplicitNavs for keywords, numbers, etc., I got some basic graph navigators working in a couple hours. Writing the code for select* and transform* was surprisingly easy. And then it became wonderfully easy to do things to graphs that previously had been quite painful (so painful that I wouldn't even try most of them). What's hard, it turns out, is thinking of how to go with the grain of Specter: choosing what navigators to implement. I'm sure that will come with more practice and seeing more examples of custom navigators.

[nathanmarz]

Graph navigation is extremely interesting and rewarding. My most powerful graph navigators are subgraph navigators – they replace a subgraph with a new subgraph, and metadata on the new subgraph indicates how to re-attach into the surrounding graph. I've been encouraging someone from the community to make an open source graph navigation library on top of something like Loom. If this is something you're interested in let me know.

[bkovitz]

Yes, I am interested in helping to make open-source graph navigators. I haven't yet "suffered" enough to design them in a way that's easy and practical for many applications (to use a term from your blog), but I can certainly make my navigators publicly available. Hopefully that'll enable others to sort out the good and bad ideas. It'll probably take several generations of "evolution" to find the stable attractors in the design space.

Two days ago, I couldn't think of a nice way to do spreading activation with navigators. I was thinking that I needed to add some sort of indirection, something like value-based indexing in Matlab. That was such a mess even on paper, I didn't even think about implementing it. Yesterday, I hit on a clean and "obvious" way to do it. I'll move my current navigators into a separate project and post them on GitHub—as soon as I figure out how to do that.

[nathanmarz]

Great, I'd be happy to take a look and comment / provide suggestions.

[mathpunk]

My recent interests have been in graph rewriting, replacement grammars for graphs, and operads, which are a kind of category theoretic gadget that can be represented as port graphs. I'm solidly intermediate in my Clojuring but I'm keeping an eye on this thread and will contribute or test if I can.