CODEWITHSUNDEEP
pythonnetworkx
LancelotHolmes
LancelotHolmes

Reputation: 699

how to calculate the average shortest path length in a multi-directed graph with several node not connected?

I'd like to calculate the average_shortest_path_length in my multi-directed graph but there is a node not connected with other nodes

for example I have a network with nodes and edges as below:

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)

figure_1-1.png

it will ends up with an exception like

networkx.exception.NetworkXError: Graph is not connected.

but according to the notes in NetworkX

For disconnected graphs you can compute the average shortest path length for each component: >>> G=nx.Graph([(1,2),(3,4)]) >>> for g in nx.connected_component_subgraphs(G): ... print(nx.average_shortest_path_length(g)) 1.0 1.0

it should work with components, so I try the code before

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

but ends up with an exception like networkx.exception.NetworkXNotImplemented: not implemented for directed type however if I remove the single node from the network,I can compute the average shortest path length for the network, so I wonder how I can calculate the average shortest path length in a multi-directed graph with several node not connected?

Upvotes: 1

Views: 7322

Answers (1)

DYZ
DYZ

Reputation: 57033

In fact, I think that nx.shortest_path_length is the most reasonable solution:

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

Upvotes: 0

Related Questions