Skip to content

Implement shortestpathbounded to respect path length bounds #291

@nicolas-geysse

Description

@nicolas-geysse

Problem

After fixing #67 with iterativelengthbounded, there's still an edge case: when using ANY SHORTEST with bounds like {1,3}, self-loops (e.g., Daniel→Daniel) can appear with path length 0.

This happens because:

  1. iterativelengthbounded(src, dst, lower, upper) correctly finds that a path exists within bounds (e.g., a cycle of length 2)
  2. But shortestpath(src, dst) returns the shortest path without respecting bounds (length 0 for self)

Example

FROM GRAPH_TABLE (pg
    MATCH
    p = ANY SHORTEST (a:Person WHERE a.name = 'Daniel')-[k:knows]->{1,3}(b:Person)
    COLUMNS (path_length(p), a.name, b.name)
)

Current behavior: Returns (0, Daniel, Daniel) with path [0]
Expected behavior: Should return the shortest path within bounds or exclude the pair if no such path exists

Proposed Solution

Implement shortestpathbounded(csr_id, v_size, src, dst, lower, upper) that:

  1. Finds the shortest path with length between lower and upper
  2. Returns NULL/empty if no path exists within bounds
  3. Modify GenerateShortestPathCTE in match.cpp to use this function when bounds are specified

Related

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions