#python-3.x #graph #networkx
#python-3.x #График #networkx
Вопрос:
У меня есть график Networkx, как показано на следующем изображении
Изображение было создано с использованием приведенного ниже кода
import networkx as nx
import matplotlib.pyplot as plt
G = nx.gnm_random_graph(n=20, m=30, seed=1)
nx.draw(G, with_labels=True)
plt.show()
G.add_edges_from([(2, 20), (20, 8)])
n = len(G.nodes())
retain_node_ids = [1,2]
G.add_edges_from([(u, v) for u in retain_node_ids for v in (n, n 1)])
G = nx.k_core(G, k=2)
G.remove_nodes_from([n, n 1])
nx.draw(G, with_labels=True)
plt.show()
Это потоковая сеть, и я хочу удалить циклы, подобные тому, который отмечен красным. Это примерный график; в реальных сетях есть много подобных циклов, и я хочу обнаружить и удалить все ребра из таких циклов.
Например, направление потока от 7 -> 8 и выхода нет, ребро (7,8) не является многоэтапным.
Предложения о том, как удалить такие циклы, будут действительно оценены.
РЕДАКТИРОВАТЬ: почему я хочу удалить область цикла внутри red box? Это потому, что график направлен. Давайте рассмотрим направление потока от 7 до 8, и это транспортная сеть, как только груз поступает в 8, его можно транспортировать из 8 -> 2 или 8-> 20, но выхода из цикла нет.
Комментарии:
1. Похоже, вы хотите вычислить минимальное связующее дерево .
2. Ваш график направлен? Я предполагаю, что это потому, что вы говорите о потоке, если да, то какой начальный узел? Вас интересует только поиск изолированных циклов (связанных с остальной частью графика только 1 ребром)?
3. @AzimMazinani Да, мой график направлен
4. @Oil L Спасибо за предложение. Но я ищу способ удалить только циклы, как указано выше, минимальное связующее дерево также удалит другие циклы.
5. Вопрос сформулирован некорректно. Чем цикл в красном поле отличается от любого другого цикла на графике? Представленный график также неориентирован, но вопрос, похоже, связан с конкретным шаблоном циклов в ориентированном графе? По крайней мере, опубликуйте ориентированный график, который четко показывает, что вы пытаетесь сделать.
Ответ №1:
Алгоритм Тарьяна обнаруживает циклы в ориентированном графе и сообщает об узлах, попавших в цикл. В зависимости от реализации вам придется повторно запускать его несколько раз, пока он не станет чистым.
https://en.wikipedia.org/wiki/Tarjan’s_strongly_connected_components_algorithm
Комментарии:
1. Спасибо за предложение. Но цикл, который я хочу удалить, имеет только 3 узла (также показано выше). Мне непонятно, как здесь можно использовать алгоритм Тарьяна. Не могли бы вы подробнее остановиться на этом?