You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Count paths of three or more hops from node degrees #135
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.
Activity