Bezdepbonusu7Программирование: статьи и ответы
Меню

Вопрос

Как рассчитать среднюю длину кратчайшего пути в разнонаправленном графе с несколькими несвязанными узлами?

Автор вопроса: LancelotHolmesОтветов: 1

Я хотел бы вычислить average_shortest_path_length в моем разнонаправленном графе, но есть узел, не связанный с другими узлами

например, у меня есть сеть с узлами и ребрами, как показано ниже:

lst_nodes=[2782, 27118, 28931, 28936, 43162, 28770, 48325, 33783]

lst_edge = [(28931, 28936L), (28931, 27118L), (28931, 27118L), (28931, 33783L), (48325, 28936L), (28936, 43162L),
            (28936, 48325L), (27118, 28936L), (27118, 28936L), (27118, 48325L), (43162, 48325L), (2782, 28931L),
            (2782, 48325L), (2782, 48325L), (2782, 27118L), (2782, 33783L)]

MDG = nx.MultiDiGraph()
MDG.add_nodes_from(lst_nodes)
MDG.add_edges_from(lst_edge)

print 'avg shortest path length:', nx.average_shortest_path_length(MDG)

это закончится исключением, например

networkx.exception.NetworkXError: Graph is not connected.

но в соответствии с примечаниями в NetworkX

Для несвязных графов вы можете вычислить среднюю длину кратчайшего пути для каждого компонента: >>> G = nx.Graph ([(1,2), (3,4)]) >>> для g в nx.connected_component_subgraphs (G) : ... print (nx.average_shortest_path_length (g)) 1.0 1.0

он должен работать с компонентами, поэтому я пробую код перед

for g in nx.connected_component_subgraphs(MDG):
    print nx.average_shortest_path_length(g)

но заканчивается исключением типа networkx.exception.NetworkXNotImplemented: not implemented for directed type, однако, если я удаляю один узел из сети, я могу вычислить среднюю длину кратчайшего пути для сети, поэтому мне интересно, как я могу вычислить среднюю длину кратчайшего пути в разнонаправленном графе с несколько узлов не подключены?

  • Вы можете преобразовать каждый из компонентов в неориентированный граф: for g in nx.connected_component_subgraphs(G): F=nx.Graph(g); ... DYZ 07.03.2017
  • @DYZ ну, это неверно, во-первых, средняя длина кратчайшего пути для ориентированного графа и неориентированного графа отличается, и я попробовал ваше решение, оно закончится новым исключением ZeroDivisionError: float division by zero, так как существует единственный узел в сети. Спасибо, в любом случае LancelotHolmes 07.03.2017
  • Вы правы, средний кратчайший путь для орграфов и неориентированных графов различается. Но nx.average_shortest_path_length работает только с неориентированными графами (поэтому возникает исключение), поэтому я думаю, у вас нет выбора. Вы, конечно, можете вычислить nx.shortest_path_length и взять среднее значение. DYZ 07.03.2017

pythonnetworkx

Ответы

Ответ 1 · DYZ

На самом деле, я думаю, что nx.shortest_path_length - наиболее разумное решение:

import statistics
from itertools import chain
# This includes the isolated node!
path_lengths = (x.values() for x in nx.shortest_path_length(MDG).values())
statistics.mean(chain.from_iterable(path_lengths))
# 1

Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.

Похожие материалы