有向图的分区

Question

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

输入网络是具有单个源和宿顶点的有向图.生成的分区必须具有与原始分区相同的属性(有向图,单个源顶点,单个宿顶点),并且要求每个分区应该只有两个顶点位于关键集中,并且它们必须是初始和终端顶点.

编辑

如果源和接收器是相同的顶点,则生成的子图将包含一个循环.现有代码可用于检测和删除此类循环..

结束编辑

在这种情况下,图表值1000个单词,我绘制了一个简单的图形,彩色顶点表示关键顶点,虚线是图形的分区.

alt text http://i50.tinypic.com/1254bkg.jpg

在这种情况下,目的是找到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分区无效,因此已重新标记图表以消除不一致性.

替代文字http://i49.tinypic.com/2qdsf42.png

如果它有帮助,我的python-eque伪代码通过执行一系列前向和后向图遍历来识别所有可能的分区.

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

我认为您正在尝试找到连接组件之间的切口。