2024-06-13

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"

implementation

an implementation is part of the discontinued but still available sph-lib-dg