Я пытаюсь разделить сеть на одну или несколько частей на основе набора критических вершин. У меня есть код, который, по моему мнению, решает мою проблему (по крайней мере, для случаев, которые меня интересуют), но для обеспечения правильности в целом я ищу название того, что я делаю из теории графов или даже ссылки на эквивалентный алгоритм или процесс.
Исходная сеть - это ориентированный граф с одним источником и вершиной-приемником. Результирующие разбиения должны иметь то же свойство, что и исходные (ориентированные графы, вершина с одним источником, вершина с одним приемником), с дополнительным требованием, чтобы у каждого разбиения было только две вершины в критическом наборе, и они должны быть начальными и конечные вершины.
Редактировать
Если источник и приемник - это одна и та же вершина, результирующий подграф будет содержать цикл. Существующий код доступен для обнаружения и удаления таких циклов. .
Конец редактирования
В этом случае диаграмма стоит 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 является недопустимым, график был помечен для удаления несоответствия.
Если это помогает, мой psuedocode на языке 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