Я создал облегченную графическую библиотеку, которая имеет 3 объекта (Вершина, Край, График) и 1 функцию (topo_sort), которая выглядит так:
class DAGError(Exception): pass
def topo_sort(graph):
sorted_list = []
def visit(vertex):
nonlocal sorted_list
if vertex.idle:
raise DAGError('Graph has at least one cycle.')
if not vertex.done:
vertex.idle = True
for neighbor in vertex.vertices():
visit(neighbor)
vertex.done = True
vertex.idle = False
sorted_list.insert(0, vertex)
queue = [vertex for vertex in graph.vertices() if not vertex.done]
while queue:
visit(queue.pop(0))
return iter(sorted_list)
И это работает нормально, если у меня плоский DAG. Но чего я хочу добиться, так это добавить подграфы (или вложенные графы) в мой основной граф, как вы можете видеть на этой иллюстрации:
Это по-прежнему группа обеспечения доступности баз данных, поэтому, если я запустил свою функцию для нее, обычный вывод topo_sort будет примерно таким:
V0, V3, V1, V5, V4, V8, V7, V12, V11, V13, V14, V2, V6, V10, V9, V15, V17, V16
Однако я предпочитаю вывод, когда все вершины, от которых зависит подграф, "обрабатываются" до того, как будут обработаны вершины подграфа, поэтому должно быть что-то вроде этого:
V0, V1, V8, # vertices of maingraph
V3, V5, V4, V12 # vertices of subgraph_0
V7, V11, V13, # vertices of subgraph_1
V14 # vertex of subgraph_0
V2 # vertex of maingraph
V6, V10, V9, V15 # vertices of subgraph_2
V16, V17 # vertices of maingraph
Но я не смог найти никаких ресурсов на:
- как «отметить» или «сохранить» вершину в графе как часть подграфа?
- как отсортировать вершины на основе их зависимостей подграфа (как в примере выше)?
- как получить или обработать подграф как независимый граф?
Я надеюсь, что смог достаточно подробно объяснить свою проблему - хотя, если чего-то не хватает, сообщите мне, и я дополню свой вопрос недостающими частями.
Заранее спасибо!
ИЗМЕНИТЬ:
Я нашел это (библиотека Boost Graph, BGL) и похоже, что он решает очень похожую (или точно такую же?) проблему, что и у меня, хотя я не знаком с C++, поэтому не понимаю, как это работает и что именно он делает - но я поместил это здесь, может быть, кому-то будет полезно ответить на мои вопросы.
РЕДАКТИРОВАТЬ 2:
Я также принимаю псевдокод, а не только питон! Конечно, если об этом знает существующая библиотека Python, мне это интересно, однако я не хочу использовать такую огромную библиотеку, как graph-tools, например, - поэтому я создал свою собственную, поэтому я предпочитаю реализации больше, чем библиотеки .
