# A path modification problem in directed graphs

We start with a given finite directed graph. It could represent transitive relations such as:

• data transfer paths in social networks,
• transportation connections, etc.

Let us use the notation

• A->B to denote a directed edge from node A to node B and
• A=>B to denote a path from A to B.

Example 1: Social networks. An edge A->B can mean: A can send data to B. So if we have edges A->B and B->C we have a path A=>C and data can be sent from A to C.

Example 2: Rail connections. An edge A->B can mean: there exists a rail connection from A to B. So if we have edges A->B and B->C we have a path A=>C and there is a rail connection from A to C.

We would like to locally modify the graph, in order to add or remove directed paths (not just edges). For example, we may wish to add or delete data paths or rail connections. We may wish to make it possible or impossible for C to receive data, directly or indirectly, from A. Or we may wish to make it possible or impossible to go by rail from A to C. We may have several (possibly conflicting) requirements such as these. Local modifications are rarely possible without implying other changes, some of which can be unwanted.

1. Adding paths. Adding a path X=>Y, is simple because it is sufficient to add an edge X->Y. However by doing this we will also add paths from all Z such that Z=>X to all W such that Y=>W. Some of these paths may be unwanted. Is the addition of the new path important enough to justify the addition of some unwanted paths? Or: how can the new path be added with a minimal effect on the rest of the graph?
2. Removing paths. For example, if we want to remove a path A=>C such as A->B->C we must remove either A->B or B->C. The removal of either edge may imply the removal of other paths that contains this edge. Hence the need of removing certain paths may force the removal of others, some of which can be wanted. Is the removal of the unwanted path important enough to justify the removal of the others? If there is a choice of paths to be removed, which ones to remove? Or: how can a path be removed with a minimal effect on the rest of the graph?

So in general, locally adding or removing paths can have ripple effects that can involve other paths, possibly the whole graph. After adding some paths, others should perhaps be removed and after removing some, others should perhaps be added. This becomes messy. If several path constraints are present, the problem may be infeasible. This could perhaps be seen as an optimization problem, where we must weigh the relative importance of paths: of those we explicitly want to add or remove and of those whose addition-removal may result.

This seems an interesting practical problem. How can this problem be formulated in a way that may lead to a solution? Has this problem, or similar ones, already been studied? I have found some literature on the problem of adding-removing nodes, but I have not found any on the problem of adding-removing edges. In any case, this problem is different, as we want to add-remove paths.

• Also, please make sure you're asking one question per post. We can't tell you whether one path is "important" or not -- only you can decide what is important. Figuring out how to formulate your practical situation as a well-defined problem statement might be beyond the scope of what this site can help with -- I'm not sure. We can answer questions about computer science, but we probably can't answer questions about the application domain (e.g., rail transport).
– D.W.
May 15 '17 at 21:23
• Concerning the first question (adding paths), if you only add (and do not remove at the same time), then adding an edge X->Y will certainly have minimal effect on the rest of the graph. Jun 20 '17 at 11:35
• I once built a Petri net editor that worked like this. It maintained a couple of graph constraints in the form of constraint-restoring operations that were automatically applied after each edit operation. I couldn't find a sufficiently intuitive order-independent set of operations, and it proved difficult to find an intuitive, provably consistent order-dependent sequence of operations (where consistent means: every operation always restores its own constraint without breaking any of the previous constraints). I didn't work things out mathematically, and I probably should have. Sep 18 '17 at 15:51

I am assuming you are using some lists of node pointers at the source nodes for keeping record of outgoing edges and paths.i.e. if you have a source node A which has directed edges towards the nodes B,C and D then you have a list containing pointers to B,C and D which is called $edges$ stored in node A

edges=[B,C,D];


and if some other edges lets say E ,F and G have a directed path towards them then you have a list of paths called $paths$

paths=[E,F,G];


Now let's say you want to delete the paths towards E and F from A then you should remove E and F from paths but still keep it in another list called $forbiddenPaths$.

forbiddenPaths=[];// this list will initially be empty


Here's how the lists will be updated after you have removed E and F from $paths$

edges=[B,C,D];
paths=[G];
forbiddenPaths=[E,F];


This way all you need to do before transmitting data is check if the destination node exists in the $paths$ list.If it does then transmit otherwise don't.You can also keep a $forbiddenEdges$ list in the same manner for avoiding some edges of your choice.