CODEWITHSUNDEEP
neo4j
Michael Cole
Michael Cole

Reputation: 16257

Neo4j db design. Edges with relationship? Filtered shortest path?

H-i, I want to display a force directed graph using in D3. I'm trying to model it with Neo4j.

The requirements are to decorate "Topics" and "Edges" with "Attachments". Topics and Edges display in the D3 graph. Attachments in a detail view of a Topic or Edge.

This is the conceptual model (Topics and Edges graphed in D3):

(attach1) -> (topic1) --edge12--> (topic2) <--edge23-- (topic3) <- (attach2)
                |         |           |          |
          (attach3)    (attach4)   (attach4)  (attach5)

The simplest thing that doesn't seem to work is:

Topics -> Nodes
Edges -> Relationships
Attachments -> Nodes

Neo4j doesn't have "hyperedges", so this instead:

Topics -> Nodes
Edges -> Nodes that relate only to Topics
Attachments -> Nodes that relate to Topics and Edges

That's wonky, but workable. An alternative would be make an Edge property with Attachment Ids, but that seems messy.

The next requirement is to do "Multi-topic search", which is a list of shortest paths between 2+ Topics - but only over Topics and Edges.

I found these questions that give I don't completely grok, but seem to explain how to filter the results. They don't seem very performant for an OLAP.

Is there a better way to model this directed graph in Neo4j?

Is there a better way to do the filtered multi-node search?

Thanks!

Upvotes: 2

Views: 309

Answers (2)

cybersam
cybersam

Reputation: 67044

[UPDATED]

Original answer

For historical interest, and as a comparison to the final solution, below, here is my original answer.

Since you cannot have a relationship connected directly to another relationship, you can reify Edge as a node. For example, here is a possible model:

(:Attachment) -[:FOR]-> (:Topic)
(:Attachment) -[:FOR]-> (:Edge)
(:Topic) <-[:FROM]- (:Edge) -[:TO]-> (:Topic)

Here is the query find the shortest path (or paths, if there is a tie) between any 2 specific Topics:

MATCH (t1:Topic { id: 't1' }), (t2:Topic { id: 't2' })
RETURN ALLSHORTESTPATHS((t1)-[:FROM|TO*]-(t2))

And here is a console that demos this.

Caveat: The above query does not enforce "sensible" directionality. So, for example, suppose the data looked like this (I replace the Edge nodes with arrows, for simplicity): (t1)->(t2)<-(t3). If we wanted the shortest path from t1 to t3, my query would return a path consisting of t1, t2, and t3, even though you cannot go from t2 to t3. Enforcing sensibility should be possible, but would make the query a bit more complex...

Improved answer

To enable "sensible" directionality (see above), we just have to make a minor change to my original data model by making the relationships to/from each Edge point in the same direction.

That is, instead of doing this:

(:Topic) <-[:FROM]- (:Edge) -[:TO]-> (:Topic)

we do this:

(:Topic) -[:TO_EDGE]-> (:Edge) -[:FROM_EDGE]-> (:Topic)

With this improved data model, the following query will enforce "sensible" directionality. Notice how the query now includes the < or > arrow to indicate the desired directionality:

MATCH (t1:Topic { id: 't1' }),(t2:Topic { id: 't2' })
RETURN ALLSHORTESTPATHS((t1)-[:FROM_EDGE|TO_EDGE*]->(t2))

Here is a console that demonstrates this improved data model and query. It returns the 2-edge path (from t1 to t2) as the "shortest path", since the 1-edge path has the wrong directionality.

Upvotes: 2

maxymoo
maxymoo

Reputation: 36555

What about this kind of graph structure:

(topic_attachment_1)--(topic1)--(edge_attachment_1_2)--(topic2)--(topic_attachment_2)
                          |                                |
                      (topic3)                          topic(4)

Basically the idea is that attachments are modeled as nodes; a topic attachment just hangs off a topic, where an edge attachment sits between the two topics (so the edge attachment requires you to split the edge into two edges.

Upvotes: 1

Related Questions