Computing path lengths

[remysucre]

Hi, I'm attempting to run the following program:

path(Start,End,W) :- edge(Start,End,W).
path(Start,End,U+V) :- path(Start,Mid,U), edge(Mid,End,V).

edge(1, 2, 3).
edge(2, 3, 1).
edge(1, 3, 2).

After loading the program in the dyna repl and querying for path(X,Y,W), I see the correct results printed but also the following error:

(dyna) ~/datalog-sys/dyna-R dyna
$> load demo.dyna
$> path(X, Y, W)
user query: path(X, Y, W)
result: {'X': 1, 'Y': 2, 'W': 3, 'Result': True} @ ('Terminal', 1)
result: {'X': 1, 'Y': 3, 'W': 2, 'Result': True} @ ('Terminal', 1)
result: {'X': 1, 'Y': 3, 'W': 4, 'Result': True} @ ('Terminal', 1)
result: {'X': 2, 'Y': 3, 'W': 1, 'Result': True} @ ('Terminal', 1)
Traceback (most recent call last):
  File "/home/remywang/datalog-sys/dyna-R/dyna/repl.py", line 528, in cmdloop
    user_query(text)
  File "/home/remywang/datalog-sys/dyna-R/dyna/syntax/normalizer.py", line 261, in user_query
    loop(rr,
  File "/home/remywang/datalog-sys/dyna-R/dyna/interpreter.py", line 645, in loop
    loop_partition(R, frame, cb, partition)
  File "/home/remywang/datalog-sys/dyna-R/dyna/interpreter.py", line 585, in loop_partition
    for bd in partition.run(frame):
  File "/home/remywang/datalog-sys/dyna-R/dyna/interpreter.py", line 421, in run
    if self.iterators[j].bind_iterator(frame, self.variable, vv):
  File "/home/remywang/datalog-sys/dyna-R/dyna/interpreter.py", line 408, in bind_iterator
    return any(v.bind_iterator(self.variable, value) for v in self.iterators)
  File "/home/remywang/datalog-sys/dyna-R/dyna/interpreter.py", line 408, in <genexpr>
    return any(v.bind_iterator(self.variable, value) for v in self.iterators)
TypeError: bind_iterator() missing 1 required positional argument: 'value'

[matthewfl]

Thanks for the bug report.

It seems like that line was not properly tested. It just needs to changed to:

        return any(v.bind_iterator(frame, self.variable, value) for v in self.iterators)

The variable frame was missing from that line.

I will push an update for this a bit later today

[remysucre]

Thanks! Could you show me how to aggregate over path? E.g. I'd like to write something in the line of spath(X,Y) min= path(X, Y, W) * W., which should find the shortest paths (it doesn't). I know the better way to define spath directly just with min=, but here I'm trying to do it the dumb way.

[remysucre]

Also tried spath(X,Y) min= W for path(X,Y,W). which didn't work either. It assigns both 'W':2 and 'W':4 for the path 1->3.

[matthewfl]

spath(X,Y) min= W for path(X,Y,W). worked for me in that it returned only 3 different paths as it was only returning the value for the shortest path between X and Y.

A more idiomatic way to write this in Dyna would be something like:

path(X, Y) min= edge(X, Y).
path(X, Y) min= path(X, Z) + edge(Z, Y).

edge(1, 2) = 3.
edge(2, 3) = 1.
edge(1, 3) = 2.

This just returns the distance between any two nodes in the graph. It does not return all paths in the graph, but that is generally what you want in a dynamic program.

[remysucre]

Indeed, I'm actually trying to compare the performance of the idiomatic definition with the more datalog-ish one I gave. What I got by running the following program:

path(Start,End,W) :- edge(Start,End,W).
path(Start,End,U+V) :- path(Start,Mid,U), edge(Mid,End,V).
spath(X,Y) min= W for path(X,Y,W).

edge(1, 2, 3).
edge(2, 3, 1).
edge(1, 3, 2).

is:

(dyna) ~/datalog-sys/dyna-R dyna
$> load demo.dyna
$> spath(1,2)
user query: spath(1,2)
result: {'Result': 3} @ ('Terminal', 1)

$> spath(1,3)
user query: spath(1,3)
result: {'Result': 2} @ ('Terminal', 1)

$> spath(2,3)
user query: spath(2,3)
result: {'Result': 1} @ ('Terminal', 1)

$> spath(X,Y)
user query: spath(X,Y)
result: {'X': 1, 'Y': 2, 'Result': 3} @ ('Terminal', 1)
result: {'X': 1, 'Y': 3, 'Result': 2} @ ('Terminal', 1)
result: {'X': 1, 'Y': 3, 'Result': 4} @ ('Terminal', 1)
result: {'X': 2, 'Y': 3, 'Result': 1} @ ('Terminal', 1)

$>

The result of the first 3 queries make sense, but spath(X,Y) contains 4 different paths.