Блог

Я новичок в использовании NetworkX, и я пытаюсь найти способ определить, какие узлы имеют расстояние x друг от друга. Я начал с использования этого алгоритма для получения всех пар

 path=nx.all_pairs_dijkstra_path(G)
  

Но я все еще не уверен, как определить расстояние между узлами с помощью цикла for.

Я был бы признателен за любую помощь. Спасибо

NetworkX имеет методы для автоматического вычисления кратчайших путей (или просто длины пути) для взвешенных и невзвешенных графиков. Убедитесь, что вы используете правильный метод для вашего варианта использования.

networkx.all_pairs_shortest_path — вычисляет кратчайшие пути между всеми узлами в невзвешенном графе

networkx.all_pairs_shortest_path_length — вычисляет длины кратчайших путей между всеми узлами в невзвешенном графе

networkx.all_pairs_dijkstra_path — вычисляет кратчайшие пути между всеми узлами во взвешенном графе

networkx.all_pairs_dijkstra_path_length — вычисляет длины кратчайших путей между всеми узлами во взвешенном графе

Каждый из этих методов при выполнении на графике вычисляет словарную матрицу («словарь словарей») узлов с соответствующим кратчайшим путем или длиной кратчайшего пути в качестве значений. Я продемонстрирую это на примере:

 >>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_nodes_from(["A", "B", "C", "D", "E"])
>>> G.add_edges_from([("A", "B"), ("B", "C"), ("C", "D"), ("D", "E")])
>>> sp = dict(nx.all_pairs_shortest_path(G))
>>> sp["A"]["E"]
['A', 'B', 'C', 'D', 'E']
>>> spl = dict(nx.all_pairs_shortest_path_length(G))
>>> spl["A"]["E"]
4
  

Как вы можете видеть, я сгенерировал график с пятью узлами и связал каждый узел со следующим ребром. Я сохранил матрицу кратчайших путей sp и матрицу длин кратчайших путей spl . Когда мне нужно знать кратчайший путь между двумя узлами, например, node "A" и node "E" , я просто обращаюсь sp к матрице или словарю словарей : sp["A"]["E"] . Затем он вернет весь кратчайший путь между двумя узлами. Метод для кратчайшей длины пути работает аналогичным образом, но он вернет только количество ребер между любыми двумя заданными узлами.

Следующий фрагмент кода может прояснить, что я имею в виду под матрицей словаря. Если я запрашиваю все записи в sp для узла "A" , он возвращает другой словарь с записями для каждого другого узла:

 >>> sp["A"]
{'B': ['A', 'B'], 'A': ['A'], 'E': ['A', 'B', 'C', 'D', 'E'], 'C': ['A', 'B', 'C
'], 'D': ['A', 'B', 'C', 'D']}
  

Если вы хотите проверить расстояние между всеми узлами с помощью for циклов, вы можете просто выполнить итерацию по ключам первого словаря матрицы, а затем по словарям внутри этого словаря. Это проще, чем кажется:

 >>> for node1 in spl:
...   for node2 in spl[node1]:
...     print("Length between", node1, "and", node2, "is", spl[node1][node2])
...
Length between B and B is 0
Length between B and A is 1
Length between B and E is 3
Length between B and C is 1
Length between B and D is 2
Length between A and B is 1
... (and so on!)
  

Вот одно из решений для определения расстояний между узлами:

 G = nx.Graph()
G.add_edges_from([(1,2), (1,3), (2,3), (2,4), (3,4)])
path = nx.all_pairs_shortest_path_length(G) # This is a generator
dpath = {x[0]:x[1] for x in path}           # Create a dictionary from it 
# To find e.g. the distance between node 1 and node 4: 
print(dpath[1][4]) # = 2
  

В зависимости от размера графика вы можете использовать

 distances = nx.floyd_warshall_numpy(graph)
nodes = np.where(distances==4)
  

Чтобы получить матрицу расстояний. Исходя из этого, вы можете отфильтровать свое расстояние. Строки и столбцы являются узлами в list(g)

Я использовал это для разработки самых длинных путей — общеизвестно сложно с ориентированными графами, но достаточно просто для древовидного графа. Хотя вы не просите об этом конкретно, это может помочь другим. К вашему сведению, использование all_pairs_shortest_path_length чрезвычайно дорого для больших сетей.

         # Find the longest path for a tree
        # Choose a random start. (or first).
        rnd_node = choice(nodes)
        # Find distances from random node by calculating all distances
        r_dists = dict(nx.single_source_shortest_path_length(g, rnd_node))
        begins = [node for node, dist in r_dists.items() if dist == max(r_dists.values())]
        # being the longest from a random start, makes it suitable as a start to the longest path.
        begin = choice(begins)
        # Find distances from begin by calculating all distances.
        # If we want to know the actual journey, use 'single_source_shortest_path()' instead.
        s_dists = dict(nx.single_source_shortest_path_length(g, begin))
        stops = [node for node, dist in s_dists.items() if dist == max(s_dists.values())]
        dist, stop = choice(stops)