Fork me on GitHub
#off-topic
<
2022-01-21
>
p-himik21:01:18

I'm looking for some prior art in declaratively specifying graph nodes/edges filter where the inputs are the graph itself and a non-empty set of nodes or edges of interest (in the actual application, those nodes/edges will be selected by a user). A simple example would be "get all nodes that are neighbors of the given nodes", a variation of that would be same but with "along with the edges connecting the neighbors to the given nodes". A more complicated example is "get all nodes that are once or twice removed from the given nodes that have their path weight less than 0.5" (assuming each edge has a corresponding weight assigned to it). Such examples can get arbitrarily complex but seems like the vast majority of real life usages could be reduced down to a combination of some primitives. Has anyone seen anything like it in some paper or maybe even code?

Ben Sless05:01:51

Take a look at CAD programs used in the VLSI industry, they have pretty declarative way of interacting with the circuit model

noisesmith21:01:22

the code for that is pretty straightforward if you transform the graph into an adjacency list

p-himik22:01:13

I'm less concerned with the code and more with the actual declarative format of such filters that would be as composable, as flexible, and as effective as possible. My initial idea is to have a vector of operations where each operation is either an expansion of the working set or its filtering. But before I delve into actual implementation, I'd like to see if there are already such systems because maybe I'm missing something here. It's definitely a possibility given that I almost never work with graphs.

dpsutton22:01:41

i wonder if asami could handle that. Your queries would just be datalog queries. Not sure if it could handle the weights in the declarative query off hand. Wouldn’t be surprised if it could

1
quoll22:01:04

Weights are currently handled as integers, but that’s not set in stone. The main issue with that is the API

dpsutton22:01:27

I like declarative stuff but I always remember that the more declarative something is, the more you are just relying on a machine to understand that language. At some point you have to trade off debugging the runtime for your declarative stuff with just “doing the work” yourself

p-himik07:01:08

Thanks, will check it out. Yeah, but here the trade-off is worth it.

👍 1
hiredman22:01:58

this is datalog

hiredman22:01:20

each element being either a filter or an expansion of the working set is joins

hiredman22:01:43

https://arxiv.org/abs/2106.09799 might be interesting to look at, it is a paper about a graph query language at google, but it all just looks like datalog with a goofy syntax to me