I am trying to split a network into one or more parts based on a set of critical vertices. I have code that, in my opinion, solves my problem (at least for cases that interest me), but to ensure correctness in general, I am looking for the name of what I am doing from graph theory or even a reference to an equivalent algorithm or process.
The input network is a directed graph with a single source and a drain peak. The resulting partitions must have the same property as the original ones (oriented graphs, a vertex with one source, a vertex with one receiver), with the additional requirement that each partition has only two vertices in the critical set, and they must be start and end vertices .
edit
If the source and the receiver are the same vertex, the resulting subgraph will contain a loop. Existing code is available to detect and remove such loops. ,
End Edit
In this case, the chart is worth 1000 words, I drew a simple graph, colored vertices represent critical vertices, and dashed lines are sections of the graph.
In this case, it is supposed to find possible sections between 1-1, 1-3, 1-7, 3-1, 3-3, 3-7, 7-1, 7-3 or 7-7. In fact, only sections 1-3, 3-3, and 3-7 exist (see image below). In addition, since section 3-3 is not valid, the schedule has been re-marked to remove the inconsistency.
If that helps, my psuedocode on python-eque works by doing a series of forward and backward traversal of the graph to identify all possible sections.
def graphTraversal(graph,srcid,endids): ''' Given a graph, start a traversal from srcid, stopping search along a branch any time a vertex is in endids. Return the visited subgraph ''' closed = set() open = set([srcid]) while len(open) != 0: i = open.pop() for j in graph.succ(i): if (i,j) not in closed: if j not in endids: open.add(j) closed.add( (i,j) ) return = graphFromList(closed) def findAllValidPartitions(graph,srcids): res = [] for n in srcids: g2 = graphTraversal(graph,n,t) g2rev = reverseEdgesInGraph(g2) for s in srcids: g3 = graphTraversal(g2rev ,s,t) g3rev = reverseEdgesInGraph(g3) g3rev = removeCycles(g3rev,s) if len(g3rev .E) > 0: res.append(g3rev) return res