Setting up a graph for an ordered traversal

(Chris Bird) #1


I have a set of nodes and some basic edges already defined. I now wish to add a series of edges that represent a traversal (for an arbitrary purpose) through these nodes. The traversal must support an ordering of node visits. As an abstract example, imagien the following nodes:
N1, N2, N3, N4, N5, N6 their basic relationships (amongst themselves) are irrelevant for this question.

Now I wish to define a Directed Acyclic Graph (DAG) called G1. G1 visits nodes N1, N3, and N5 in that order.
Another DAG (G2) visits nodes N2, N1, N4 in that order. (yes N2 before N1 in this ordering, different from the G1 ordering)
A third DAG (G3) visits nodes N1, N2, N4, N5, N6 in that order

I know wish to add a new node N7 and redefine DAG G3 to become N1, N2,N4, N7, N5, N6 - i.e. I have inserted a new node into an existing ordering. I want to be able to preserve the existing sequence after N4. I also want to preserve the N1/N2/N4 ordering.

I can imagine some quite tedious ways of doing this, but would like to know if there are any "canned" approaches or better ways of thinking about this kind of a problem.

Thanks in advance for any assistance.


(Andrew Bowman) #2

For restricting the traversal order of these nodes, you would probably need to create an explicit relationship chain (or linked list) to enforce this.

You could do this by connecting the nodes by relationships with a common property (so all rels connecting the nodes in order might have something like {dag:'G3'}, which would let you specify a pattern starting at a start node and continuing to the end:

MATCH p = (:DAG {name:'G3'})-[* {dag:'G3'}]->(end)
WHERE NOT ((end)-[{dag:'G3'}]->())

Insertion of a node would just require deletion of the relationship (used by the DAG) between two nodes, and creation of the new relationships (with corresponding properties) to link in the new node(s).

It would be up to you to maintain the linked list structures, and ensure mutually exclusive changes to the structure by locking on the DAG node (such as via APOC Procedures) before you even match out to the connected list.

(Chris Bird) #3

Thanks, I will definitely give this approach a go. In my pet project, I have a fundamental list of nodes and simple "contains" type relationships. I then need multiple "visitors" to the nodes, some where ordering is necessary, and some where a simple list would work.