Можно ли определить, будет ли данный узел всегда посещаться в ориентированном графе? - PullRequest
Новая
       11

Можно ли определить, будет ли данный узел всегда посещаться в ориентированном графе?

2 голосов
/ 09 марта 2019

Я работаю над проблемой, когда у меня есть куча ориентированных графов с одним источником / приемником для каждого, а ребра являются вероятностными связями (хотя 90% узлов имеют только 1 вход и 1 выход).В каждом графе также есть критический узел, и я хотел бы определить, есть ли какой-нибудь способ пересечь график, который обходит этот узел.В идеале я также хотел бы перечислить конкретные пути, которые будут обходить этот узел.Мне удалось импортировать пример графика в NetworkX и я могу без труда запустить некоторые функции на графике, но я не уверен, является ли то, что я ищу, обычным запросом, и япросто не знаю правильной терминологии, чтобы найти ее в файлах справки, или, если это что-то, мне нужно написать код вручную.Я также открыт для альтернативных инструментов или методов.

1 Ответ

1 голос
/ 09 марта 2019

Во-первых, вам может потребоваться какой-либо способ количественной оценки критических узлов.Для этого вы можете использовать некоторую меру центральности, возможно, центральность в вашем случае. Подробнее читайте здесь.

Далее, если вы знаете два узла, между которыми вы хотите перемещаться, вы можете использовать это как своего рода псевдокод, чтобы помочь вам туда добраться.Вы также можете перебрать все возможные пары узлов, через которые можно пройти, но это может занять некоторое время. 

import NetworkX as nx
important_nodes=[]#list of important nodes    
paths = nx.all_simple_paths(G, source, target)
paths=list(paths)
#This is pseudocode, next four lines could be done with list comprehension
exclusive_paths=[]
for path in paths:
    if important_nodes not in path:
        exclusive_paths.append(path)

Подробнее о all_simple_paths здесь .

понимание списка может выглядеть следующим образом 

exclusive_paths=[x for x in paths if important_nodes not in x]
...