# 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](/files/u/software/sourcecode/old/sph-lib-dg/modules/sph/storage/dg/relation/)