我正在尝试根据一组关键顶点将网络划分为一个或多个部分。我有一些代码，我相信可以解决我的问题(至少，对于我感兴趣的情况)，但为了确保总体正确性，我正在寻找我正在做的事情的名称来自图论，甚至是等效算法或过程的引用。
输入网络是具有单个源和汇顶点的有向图。生成的分区必须具有与原始分区相同的属性(有向图、单源顶点、单汇顶点)，附加要求是每个分区只能有两个位于临界集中的顶点，并且它们必须是初始和终端顶点。
编辑
如果源和汇是同一顶点，则生成的子图将包含一个循环。现有代码可用于检测和消除此类循环。 .
结束编辑
在这种情况下，一张图值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
最佳答案
我认为您正在尝试查找 cuts between connected components .
关于graph - 有向图的划分，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1752623/