walk question

[webyrd]

Hi Eric!

Percival is cool!

I'm confused by the walk example:

walk(x: v, y: v, len: 0) :- edge(x: v, _).
walk(x: v, y: v, len: 0) :- edge(_, y: v).

Why are both of these cases needed? It looks to me that the clauses are redundant, but commenting out the second clause loses answers. What am I missing?

Thanks!

--Will

[ekzhang]

Thanks for the question! The second rule is needed because you want to find all nodes to start paths in the graph. If your only input relations are edges, then you can find the nodes in the graph implicitly by taking all of the identifiers that are referenced as the start or end of an edge.

Also, now that you point it out, this code sample is a bit misleading, as the underscores don't actually do anything - I'll fix this. It should say

walk(x: v, y: v, len: 0) :- edge(x: v).
walk(x: v, y: v, len: 0) :- edge(y: v).

[webyrd]

Thanks, Eric!

I'm still not sure I understand.

Would either or both of

walk(x: v, y: v, len: 0) :- edge(x: v).
walk(x: v, y: v, len: 0) :- edge(y: v).

be equivalent to:

walk(x: v, y: v, len: 0) :- edge(x: v, y: v).

?

[ekzhang]

No, this isn't the same. The relation edge(x: v) in Percival matches all edges with x assigned to variable v, and y assigned to any value.

walk(x: v, y: v, len: 0) :- edge(x: v, y: v).

This rule would only match vertices v that have an explicit self-loop.