Background: I'm trying to program a generic method to add a node to a Directed Acyclic Graph. This method should allow the caller to specify the possible effects on the graph, specifically the edges.
So far, I have identified the following possible changes, but I'm not sure if this set is complete.
- Add a new edge from an existing node to the new node
- Add a new edge from the new node to an existing node
- Change one existing edge to point to the new node, keeping the existing tail
- Change one existing edge to originate from the new node, keeping the existing head
- Splice in the new node between two existing nodes, removing the original direct edge and replacing it with two new edges.
Of course, combinations of these changes are also possible. But is this set of changes complete? My problem in proving the completeness of this set of operations is relating the old and new set of edges. I think it's obvious that changes 1 and 2 keep the old graph as a subgraph of the new graph; changes 1,2 and 5 do not decrease reachability of the existing nodes, but you can create new reachability if you combine changes of type 1 & 2. Changes 3 and 4 can decrease reachability, not increase it.
Just for clarity: I do not consider changes to "unrelated" edges, e.g. adding a new edge between two existing nodes is out of scope.