2023-02-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"

# implementation

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