dag.nmo

dag.nmo

% directed acyclical graph related queries in nemo/datalog

% example from sedgewick, algorithms in C++, part 5, figure 19.21, §19.6, p. 191
% edge(from, to)
e(0,1). e(0,2). e(0,3). e(0,5). e(0,6).
e(2,3).
e(3,4). e(3,5).
e(4,9).
e(6,4). e(6,9).
e(7,6).
e(8,7).
e(9,10). e(9,11). e(9,12).
e(11,12).

% all vertices seen by e()
v(?x) :- e(?x,?y).
v(?x) :- e(?y,?x).

% sources and sinks of graph (no in/out-edges)
source(?x) :- v(?x), ~e(?y,?x).
sink(?x) :- v(?x), ~e(?x,?y).

% number of in/out-edges for each vertex
% in_valence(?x, 0) :- v(?x), ~e(?y, ?x). % uncomment to include zeros
in_valence(?x, #count(?y)) :- v(?x), e(?y, ?x).
% out_valence(?x, 0) :- v(?x), ~e(?x, ?y). % uncomment to include zeros
out_valence(?x, #count(?y)) :- v(?x), e(?x, ?y).

% all possible paths between two nodes and the number of hops they take
% reachable(0, ?x, ?y) :- v(?x), v(?y), ~e(?x, ?y), ?x != ?y.
reachable(1, ?x, ?y) :- e(?x, ?y).
reachable(?n + 1, ?x, ?y) :- e(?x, ?z), reachable(?n, ?z, ?y).
% only the shortest paths between two nodes, if any
min_reachable(#min(?n), ?x, ?y) :- reachable(?n, ?x, ?y).
% only the longest path between two nodes, if any
max_reachable(#max(?n), ?x, ?y) :- reachable(?n, ?x, ?y).

% the longest incoming path of each node (for outgoing, just switch ?y and ?x)
% sorting this already gives us a parallelized topological order
max_in_path(0, ?x) :- v(?x), ~max_reachable(?n, ?y, ?x).
max_in_path(#max(?n), ?x) :- max_reachable(?n, ?y, ?x).

@export max_in_path :- csv{resource = ""}.