Узлы обрезки не в сетевом простом пути?

Question

У меня есть DiGrraph, и я хочу обрезать любой узел, который не содержится в одном из simple paths между двумя указанными мной узлами. (Еще один способ подумать об этом - любой узел, который не может достигнуть иstart и end баллов следует обрезать).

Лучший способ, которым я нашел это, - получить all_simple_paths, а затем перестроить новый график, используя эти функции, но я надеюсь на более элегантное и менее подверженное ошибкам решение. Например, есть ли способ определить, что НЕ на простом пути, а затем удалить эти узлы?

Answer 1

Вы можете использовать метод all_simple_paths, который возвращает генератор, но вам нужен только первый путь. Затем вы можете использовать G.subgraph(nbunch), чтобы вернуть индуцированный граф из вашего пути.

EDIT: для возврата подграфов, вызванных всеми простыми путями, просто конкатенировать узлы uniques, возвращаемые all_simple_paths.

import networkx as nx 
import itertools 

G = nx.complete_graph(10) # or DiGraph, MultiGraph, MultiDiGraph, etc 
# Concatenate all the paths and keep unique nodes (in one line) 
all_path_nodes = set(itertools.chain(*list(nx.all_simple_paths(G, source=0, target=3)))) 
# Extract the induced subgraph from a given list of nodes 
H = G.subgraph(all_path_nodes) 
print(nx.info(H)) 

Выход:

Name: complete_graph(10) 
Type: Graph 
Number of nodes: 10 
Number of edges: 45 
Average degree: 9.0000 

Answer 2

Я делал некоторые успехи на это время @kikohs работал, чтобы понять мой вопрос и предоставить ему ответ, поэтому я отправляю это в качестве альтернативного решения проблемы , Я действительно думаю, что его ответ превосходен!

def _trim_branches(self, g, start, end): 
    """Find all the paths from start to finish, and nuke any nodes that 
    aren't in those paths. 
    """ 
    good_nodes = set() 
    for path in networkx.all_simple_paths(
      g, 
      source=start, 
      target=end): 
     [good_nodes.add(n) for n in path] 

    for node in g.nodes: 
     if node not in good_nodes: 
      g.remove_node(node) 

    return g 

Использование subgraph сделать второй цикл, очевидно, лучше, как его один вкладыш с использованием itertools.chain. Сегодня великолепные вещи вокруг этих частей!