How can I store this kind of graph in neo4j for fast traversal?

Question

This is a graph whose nodes exist in many connected components at once because a node's relationships are a collection of edge groups such that only one edge per edge group can be present at once. I need to be able to find all of the connected components that a node exists in. What would be the best way to store this graph in neo4j to quickly find all of the connected components that a node exists in? Is there a way to use the built in traversals to do this?

Also: is there a name for this kind of graph? I'd appreciate any help/ideas.

Update:

Sorry for not being clear. All nodes are of the same type. Nodes have a variable number of edge groups. Exactly one edge from each edge group needs to be chosen for a particular connected component. I'm going to try to explain through example:

Node x1 is related to: (x2 or x3 or x4) AND (x5 or x6) AND (x7)
Node x2 is related to: (x8) AND (x9 or x10)

So x1's first edge group is (x2, x3, x4), its second edge group is (x5, x6), and its third edge group is (x7).

So here are a few connected components that x1 exists in:

CC1:

x1 is related to: x2, x5, x7
x2 is related to: x8 x9 

CC2:

x1 is related to: x2, x6, x7
x2 is related to: x8, x9

CC3:

x1 is related to: x3, x5, x7

CC4:

x1 is related to: x3, x6, x7

etc.

I'm grateful for your help in this.

Update2:

I think I'll be able to do this if there's an answer to this question: How can I specify which relationship type to use as a function of the current node at every step of a traversal with neo4j?

Answer 1

They way I understand your question you have a number of nodes, let's call them X nodes, that are connected to a number of type nodes (or something similar), let's call these nodes T nodes. An X node can have connections to multiple T nodes, but only one connection to each T node, or possibly only one connection to each kind of T node (your description is a bit fuzzy here).

The way I would model this is by using one RelationshipType for each (kind of) T node. Then you can use x_node.getRelationships(T_TYPE_ONE, T_TYPE_TWO, ...etc...) to get all the T nodes from an X node. When you mutate an X node is where you need to maintain your invariant that it can only have at most one relationship to each (kind of) T node. You do this by using x_node.getSingleRelationship(THE_T_TYPE_YOURE_MUTATING), if that returns null, it's safe to add a new relationship of that type, if it returns a relationship, you will have to remove it before you can add the new one.

ASCII-art example of this model (as I interpret it):

(x1)--T_ONE-->(t1a)   (t1b)<--T_ONE--(x2)--T_FOUR-->(t4a)
 |\                                   |
 \ |---T_TWO-->(t2a)                 /
  \                                 /
   |---T_THREE-->(t3a)<--T_THREE---/

In the example above both X nodes are part of T_ONE components, but x1 is part of T_ONE component t1a and x2 is part of t1b. They are both part of T_THREE component t3a, then x1 is part of T_TWO component t2a, and x2 is part of T_FOUR component t4a. Querying in this example would look something like:

Iterable<Relationship> x1_comps = x1.getRelationships(T_ONE, T_TWO, T_THREE, T_FOUR);
Iterable<Relationship> x2_comps = x2.getRelationships(T_ONE, T_TWO, T_THREE, T_FOUR);

And updating would look like this:

void setComponent(Node xNode, RelationshipType tType, Node tNode) {
    Relationship current = xNode.getSingleRelationship(tType);
    if (current != null) current.delete();
    xNode.createRelationshipTo(tNode, tType);
}

Please let me know if I've misinterpreted your requirements, and I'll be happy to give your updated description a stab.

Answer 2

Regarding the other query, I pointed out some possibilities for fine grained functions at http://stackoverflow.com/questions/2430196/how-can-i-specify-which-relationship-type-to-use-as-a-function-of-the-current-nod Basically, don't use a traverser but the more direct node.getRelationship* API and build your own iteration for fine grained control.

Does that solve your problem?

/peter neubauer