2017-08-27

path-find

selector expressions to filter relations of a directed graph by set relations between nodes

features

matching of paths of arbitrary length

expressions can be nested

divergent searches and skipping of intermediate path parts

minimum and maximum number of intermediate nodes to skip

example queries

integers stand for nodes/node-identifiers

(1)

(1 *)

(1 * 2)

((only 14 15) *)

(11 21 31)

(* (1 2) (3 4))

((and 11 12) (not 24) (or 32 31))

((and 11 12) (not 24) (not (or (and 41) (or 32 31) 32 31)))

(11 (* 3 2) 12) ;a path between 11 and 12 with a maximum and minimum number of nodes inbetween

definitions

path: (skip/node ..1)

path: (source target/source ...)

node: (combinator id/node ..1)

combinator: and/or/only/not

skip: */(* integer:max [integer:min])

id: integer

null: ()

direction: "left"/"right"

result: ((relation-left relation-right) ...)

description

result

the relations in path between the last two node-expressions

path

source and target are the left and right (or start and end) nodes of a relation

interpretation: ((targets in relation with these sources) (sources in relation with these targets) _ ...)

reversing the order of the path is not the same as reversing the search direction

combinators

interpretation

matches relations whose targets are each...

or: in relation to any of the given sources. union

and: in relation to all of the given sources. intersection

not: not in relation to any of the given sources. complement

only: only in relation with all of the given sources

equivalence

(not _ ...) = (not (or _ ...))

(and (and)) = (and)

(or (or)) = (or)

(not (not)) != (not)

all non-negating combinators match subsets of "or"

"not" is semantically unary

null

if any node-expression or non-negated sub-expression matches no nodes then result is an empty set

the rationale for this is that this allows simpler composition of path-find paths. only sets have to be considered as input arguments and if there is an empty set in one part of a node-expression that is not a negation then the result will also be empty

direction

search direction for directed graphs. for example "left" or "right"

implementations

_ from _


tags: start document specification computer sph-dg graph filter dg-read-pairs-by-relation