graph - 有向图的划分

Question

我正在尝试根据一组关键顶点将网络划分为一个或多个部分。我有一些代码，我相信可以解决我的问题(至少，对于我感兴趣的情况)，但为了确保总体正确性，我正在寻找我正在做的事情的名称来自图论，甚至是等效算法或过程的引用。

输入网络是具有单个源和汇顶点的有向图。生成的分区必须具有与原始分区相同的属性(有向图、单源顶点、单汇顶点)，附加要求是每个分区只能有两个位于临界集中的顶点，并且它们必须是初始和终端顶点。

编辑

如果源和汇是同一顶点，则生成的子图将包含一个循环。现有代码可用于检测和消除此类循环。 .

结束编辑

在这种情况下，一张图值1000字，我画了一个简单的图，彩色顶点代表关键顶点，虚线是图的分区。

在本例中，目的是找到 1-1、1-3、1-7、3-1、3-3、3-7、7-1、7-3 或 7- 之间任何可能的分区7.实际上仅存在分区 1-3、3-3 和 3-7(见下图)。此外，由于 3-3 分区无效，因此已重新标记该图以消除不一致的情况。

如果有帮助的话，我的 python-eque psuedocode 通过执行一系列向前和向后的图形遍历来识别所有可能的分区。

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

我认为您正在尝试查找 cuts between connected components .