dgraph-io / dgraph-io/dgraph

Why does Dgraph shortest path return more hops than Neo4j for the same data and how to get Neo4j-like paths in Dgraph?

Open
#9,458 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug Stale
Dominant language
Go
Stars
21.8k
Forks
1.6k
Avg merge
2d 5h
Merged PRs (30d)
9

Description

I'm working with both Dgraph and Neo4j to find the shortest path between two nodes in a graph. However, I'm seeing different results in terms of path length (number of hops) for what should be the same data and relationships.

Dgraph Query

{ 
  var(func: eq(nt, "People")) @filter(eq(title, "person1")) { 
    start as uid 
  } 

  var(func: eq(nt, "Initiative")) @filter(eq(title, "test")) { 
    end as uid 
  } 

  path as shortest(from: uid(start), to: uid(end)) { 
    CONNECTED 
    OWNER 
    ~CONNECTED 
    ~OWNER 
  } 

  path(func: uid(path)) { 
    uid 
    nt 
    title 
  } 
}

Dgraph Result (5 hops):

"path": [
  { "uid": "0x972107", "nt": "People", "title": "person1" },
  { "uid": "0x9d3b7f", "nt": "Entity", "title": "abc llc" },
  { "uid": "0xbecd37", "nt": "People", "title": "person23" },
  { "uid": "0xa97091", "nt": "Function", "title": "admistrative assistant" },
  { "uid": "0xb8b27b", "nt": "Entity", "title": "test entity" },
  { "uid": "0xc053ee", "nt": "Initiative", "title": "test" }
]

So, Dgraph returns a path with 5 hops.


Neo4j Query

MATCH p=shortestPath((x:People {title: "person1"})-[*1..4]-(y:Initiative {title: "test"})) 
WHERE x <> y 
RETURN 
  extract(x IN nodes(p) | x.title) as titles, 
  extract(i IN relationships(p)| type(i)) as edge_titles, 
  extract(j IN nodes(p) | j.nt) as node_types

Neo4j Result (3 hops):

titles = [ "person1", "rfp", "test entity", "test" ]
edge_titles = [ "CONNECTED", "CONNECTED", "CONNECTED" ]
node_types = [ "People", "Function", "Entity", "Initiative" ]

Neo4j returns a path with 3 hops.


My Questions

  • Why is Dgraph returning a longer path (more hops) than Neo4j for what should be the same data and relationships?
  • How can I get Dgraph to return the same (shortest) path as Neo4j?
  • Is there something about how Dgraph's shortest function works, or about the way I’m specifying the edges, that causes this difference?
  • Are there any best practices for modeling or querying in Dgraph to ensure shortest path queries behave like Neo4j's?

Additional Info
  • Both databases have the same data and relationships.
  • In Dgraph, I’m using both forward and reverse edges in the shortest block.
  • In Neo4j, I’m using an undirected variable-length path.

Any insights or suggestions would be appreciated!

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the Dgraph shortest query and the Neo4j shortestPath query shown in the issue, comparing their edge patterns, reverse-edge usage, and hop limits on the same data. Reproduce the differing paths and inspect how Dgraph's shortest-path entry point interprets these edges; done means identifying the cause and documenting whether an equivalent Dgraph query is possible.

Written by the indexing model from the issue text.

Assessment

Domain
databases
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.