graph.reachable_paths does not return all reachable paths

[ericjkao]

Short description

In OPA 0.51.0, the graph.reachable_paths builtin function does not seem to return all reachable paths or even all maximal reachable paths in many cases.

Steps To Reproduce

1. Evaluate the following Rego package (or use this playground link):

package play
import future.keywords.if
import future.keywords.in

testing_graph:= {
  "1": [],
  "2": [
    "1",
  ],
  "3": [
    "2",
  ],
  "4": [
    "3",
    "2"
  ],
  "5": [
    "4",
  ]
}

paths := (graph.reachable_paths(testing_graph, ["5"]))

2. See that paths evaluates to:

[ 
  ["5", "4"],
  ["5", "4", "3", "2", "1"]
]

Expected behavior

Based on the doc and the original PR, I would expect the path ["5", "4", "2", "1"] to be included.

Additional context

Seems to work for shorter paths:
https://play.openpolicyagent.org/p/fpy0cgnYjb

[ericjkao]

Mentioning the authors of this builtin to see if they have thoughts or comments 😀 @justinlindh-wf @fredallen-wk

[stale]

This issue has been automatically marked as inactive because it has not had any activity in the last 30 days. Although currently inactive, the issue could still be considered and actively worked on in the future. More details about the use-case this issue attempts to address, the value provided by completing it or possible solutions to resolve it would help to prioritize the issue.

[charlieegan3]

I've been having a think about this one and it's not 100% clear what the 'correct' result for reachable_paths. Is it:

A) all paths from nodes in the initial set to leaf nodes?
B) all paths of any length from the initial set to any other node with no cycles?
C) or what we have now, paths discovered while visiting all reachable nodes?

B) feels like an improvement on C)'s results, while being worse on performance. I think that we could implement B) using IDDFS if we wanted to do that.

[ericjkao]

I’d also propose a variation of A: A2: all the paths in B which are maximal (that is, not a prefix of another path in B) It clarifies that if there are no leaf nodes (say 1->2->1), we still return some path. Among these: B is intuitive and easy to use. I suspect this is the behavior people intuitively expects based on name. A2 may offer a performance improvement but is harder to use (it’s like an encoding of B) C: I struggle of think of realistic cases where this is the desired behavior, but perhaps others will. I’m 2-cents would be to go with B. A2 could always be introduced as a new function if a need arises. I do slightly worry about making a breaking change. From the issue discussions, it seems that the original function was introduced to solve a specific use case the author had. So I wonder if the change would break that case.

…

On Mon, Jul 10, 2023 at 8:51 AM Charlie Egan ***@***.***> wrote: I've been having a think about this one and it's not 100% clear what the 'correct' result for reachable_paths. Is it: A) all paths from nodes in the initial set to leaf nodes? B) all paths of any length from the initial set to any other node with no cycles? C) or what we have now, paths discovered while visiting all reachable nodes? B) feels like an improvement on C)'s results, while being worse on performance. I think that we could implement B) using IDDFS <https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search> if we wanted to do that. — Reply to this email directly, view it on GitHub <#5871 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADIKDKDE2KKHGKSZ7OOLGTLXPQQJPANCNFSM6AAAAAAXMWOGLE> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[charlieegan3]

Indeed, I'm just imagining what we might actually do here if we were to make a change.

I think the options are:

X) update docs only
Y) edit the existing function
Z) add a new function

X seems pretty likely, Y seems pretty unlikely, Z also feels pretty unlikely without a clearer use case.

[benweint]

@charlieegan3 regarding whether to just update the docs or make a behavior change / new function, I want to point out that in #6128, which was marked as a dup of this issue, there's a test case which demonstrates that the current implementation not only omits some paths, but also concocts nonsensical paths (where some path steps don't correspond to actual edges in the input graph) in some cases.

To me, this is a strong indicator that this warrants an actual behavior change for this builtin.

[anderseknert]

Yeah, that should just be considered a bug and get fixed @benweint 👍 Perhaps it should be treated as a different issue and be re-opened, but OTOH it also makes sense that we agree on what the expected behavior of this built-in function should be before we do that. Do you have any opinion on #5871 (comment) ?

[benweint]

@anderseknert agreed - we should figure out the desired behavior first!

Option B (all paths of any length from the initial set to any other node with no cycles) is what I expected / wanted the function to do.

A would be fine, except for the caveat that there may not be any leaf nodes in the case of cycle-containing graphs.

[benweint]

For my specific use case at the moment, it actually would be sufficient to have a function that takes a graph, a set of initial nodes, and a target node, and returns a path (or set of paths) from the initial set to the target, but I'm not sure that that's generally useful enough to be it's own function. (It's also easy enough to implement from option B by just filtering the set of returned paths)

[anderseknert]

Agreed, and it seems most of us do, so perhaps we should go with that. While there are valid concerns about backwards compatibility, I would consider the current behavior a bug. @ashutosh-narkar WDYT?

[ashutosh-narkar]

I would have expected option B as well. So this seems to be a bug. Both not returning all the paths as well as returning invalid paths.

[stale]

This issue has been automatically marked as inactive because it has not had any activity in the last 30 days. Although currently inactive, the issue could still be considered and actively worked on in the future. More details about the use-case this issue attempts to address, the value provided by completing it or possible solutions to resolve it would help to prioritize the issue.