Skip to content

Count paths of three or more hops from node degrees #135

Open

Description

@prrao87

Problem

The two-hop count rewrite counts MATCH (a)-[:R]->(b)-[:S]->(c) RETURN count(*) as Σ_b n1(b) × n2(b), the product of each middle node's neighbours on either side, without building any path. A longer pattern, such as (a)-[:R]->(b)-[:S]->(c)-[:T]->(d) RETURN count(*), keeps the join plan and builds every path before counting it.

The first-hop count from #113 collapses only the first hop of a longer pattern; the hops after it still emit one row per match. Variable-length hops (-[:R*2..3]->) are never counted from degrees.

Idea

Count each end hop per node in place and sum their products over the middle hop's edges: Σ_(b,c) in(b) × out(c) for three hops, which follows the edges rather than the paths. Longer fixed-length patterns chain the same per-node sums.

Two things limit it:

  • Same-type hops. Cypher's rule that a path uses each edge once can exclude pairs of hops that aren't adjacent, such as r1 = r3 on a two-cycle, so the correction goes beyond the self-loop and shared-end cases the two-hop count handles. A first version could apply only when no two hops share a type.
  • Variable-length hops. The rule applies across the whole path, so degree products overcount any path that would revisit an edge. Short bounded lengths may be countable with corrections; otherwise they keep the current plan.

Split from #78.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions