All,

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.

Chris