Partitioning of a directed graph

Question

I'm trying to partition a network into one or more parts based on a set of critical vertices. I've got code that I believe solves my problem (at least, it has for the cases I'm interested in), but for the sake of ensuring correctness in general, I'm looking for the name of what I'm doing from graph theory, or even a reference on an equivalent algorithm or process.

The input network is a directed graph with a single source and sink vertex. The resultant partitions must have the same property as the original (directed graphs, single source vertex, single sink vertex), with the additional requirement that each partition should only have two vertices that are in the critical set, and they must be the initial and terminal vertices.

Edit

If the source and sink are the same vertex, the resultant sub-graph would contain a cycle. Existing code is available to detect and remove such cycles. .

End Edit

In this case a diagram is worth 1000 words, I've drawn up a simple graph, the colored vertices represent the critical vertices, and the dotted lines are the partitions of the graph.

In this case, the intention is to find any possible partitions between 1-1, 1-3, 1-7, 3-1, 3-3, 3-7, 7-1, 7-3 or 7-7. Only the partitions 1-3, 3-3 and 3-7 actually exist (see image below). Additionally, because the 3-3 partition is invalid, the graph has been relabeled to remove the inconsistancy.

If it helps, my python-eque psuedocode works by performing a series of forward and backward graph traversals to identify all of the possible partitions.

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

Answer 1

I think you're trying to find cuts between connected components.