有向图的划分
有向图的划分
提问于 2009-11-17 23:30:31
我试图根据一组关键顶点将网络划分为一个或多个部分。我有一些代码可以解决我的问题(至少，对于我感兴趣的情况是这样的)，但是为了确保总体的正确性，我正在从图论中寻找我正在做的事情的名称，甚至是一个类似的算法或过程的引用。
输入网络是一个有向图，有一个源和汇点。生成的分区必须具有与原始图(有向图、单源顶点、单接收器顶点)相同的属性，并附加一个要求，即每个分区应该只有两个处于临界集中的顶点，并且它们必须是初始顶点和终端顶点。
编辑
如果源和接收器是相同的顶点，则生成的子图将包含一个循环。现有代码可用于检测和删除此类循环。。
端编辑
在这种情况下，图值为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 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回答 1
Stack Overflow用户
发布于 2009-11-17 23:36:40
我想你是在找连接部件之间的割线。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1752623
复制相关文章
相似问题
腾讯云开发者
