Crashes and strange results in random_spanning_tree, information_centrality, intersection_array, and rich_club_coefficient

[joyemang33]

Hello~ Here are seven new crash reports, and I merged them here since they are triggered by some similar graph structures.

1. nx.random_spanning_tree for a graph with a single node

import networkx as nx

G = nx.Graph()
G.add_node(0)
print(nx.minimum_spanning_tree(G))
print(nx.random_spanning_tree(G))

Graph with 1 nodes and 0 edges
Exception: Something went wrong! Only 0 edges in the spanning tree!

2. nx.information_centrality for a graph with a single node, and a graph with a single node and self-loop

import networkx as nx

G = nx.Graph()
G.add_node(0)
print(nx.information_centrality(G))
G.add_edge(0, 0)
print(nx.information_centrality(G))

{0 : inf}
TypeError: rowind and colptr must be of type cint

3. nx.intersection_array for an empty graph, and a graph with a single edge

import networkx as nx

G = nx.DiGraph()
print(nx.intersection_array(G))
G = nx.DiGraph([(0, 1)])
print(nx.intersection_array(G))

StopIteration
KeyError: 0

4. nx.rich_club_coefficien for an empty graph, and a graph with a single node

import networkx as nx

G = nx.Graph()
print(nx.rich_club_coefficient(G))
G.add_node(0)
print(nx.rich_club_coefficient(G))

ValueError: max() arg is an empty sequence
IndexError: pop from empty list

Thanks a lot for your further confirmation and investigation!

Best regards,
Joye

[nyooc]

Hey, I just encountered a very similar problem on AWS SageMaker. Even the given example for nx.resistance_distance() didn't work:

>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> nx.resistance_distance(G, 1, 3)
TypeError: rowind and colptr must be of type cint

The current environment AWS is supplying by default uses networkx == 3.1 and scipy == 1.11.1. But these are currently incompatible as per pyproject.toml. So the solution for me was to downgrade scipy to 1.10.1, and now everything is running well. Perhaps this is also your problem @joyemang33?

[joyemang33]

Hey, I just encountered a very similar problem on AWS SageMaker. Even the given example for nx.resistance_distance() didn't work:

>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> nx.resistance_distance(G, 1, 3)
TypeError: rowind and colptr must be of type cint

The current environment AWS is supplying by default uses networkx == 3.1 and scipy == 1.11.1. But these are currently incompatible as per pyproject.toml. So the solution for me was to downgrade scipy to 1.10.1, and now everything is running well. Perhaps this is also your problem @joyemang33?

Thanks for your mentioning the solution to the exception TypeError: rowind and colptr must be of type cint. I will try to downgrade my scipy version and check whether the problem still occurs.

Best regards,
Joye

[rossbar]

@joyemang33 can you share info about the environment where you encountered these errors (e.g. the output of pip list or the equivalent for whichever build/env management system you use)

[joyemang33]

@rossbar Sure! Here (env.txt) is my output of pip list, and I believe that the scipy may not be proper.
When I downgrade the scipy version, the issue of the nx.intersection_array is solved.
However, I can still reproduce other issues reported here when using scipy == 1.10.1

Best regards,
Joye

[nihalgeorge01]

Hi, I was trying to fix this issue. The reference paper for information_centrality() considers only undirected connected graphs of 3 vertices or more. What is the expected result for a single node (or 2 node) graph? Should the user check for these preconditions before passing into information_centrality()?

intersection_array() is currently defined only for undirected graphs, but the definition of distance regular may hold for directed graphs as well, would this function need to handle the directed case?

[nihalgeorge01]

For rich_club_coefficient()

For the empty graph, it errors out in degree_histogram(), where max() is called on an empty collections.Counter

For the single node graph, the function errors out in _compute_rc(), where edge_degrees is popped outside the for loop. This assumes that there is at least 1 edge in the graph. For edgeless graphs, rich club coefficient dictionary should probably be empty since it is defined only for non-negative degree values d where there exist at least 2 nodes of degree > d. In an edgeless graph, there are no such nodes for any non-negative d.

[dschult]

When the paper doesn't handle the case (number of nodes less than 3 ) then raise an exception saying that. The OP intent is to make those exceptions more user friendly.

[nihalgeorge01]

Understood, I'll add the exception and try to open a PR for it