"nx.trophic_levels" returning strange INF value caused by insufficient checking for singular matrix

[joyemang33]

Hello here and sorry for bothering you again. I noticed that nx.trophic_levels will sometimes return INF values for an unsupported graph instead of the following message.

networkx.exception.NetworkXError: 
Trophic levels are only defined for graphs where every node has a path from a basal node (basal nodes are nodes with no incoming edges).

By investigating the source code, I found that the root cause may be the insufficient checking for whether the matrix can be inverse (reference link).

To solve the issue, the lines 57 to 66 of trophic.py could be changed by the following code:

    if np.linalg.cond(i - p) < np.finfo((i - p).dtype).eps:
        n = np.linalg.inv(i - p)
    else:
        # LinAlgError is raised when there is a non-basal node
        msg = (
            "Trophic levels are only defined for graphs where every "
            + "node has a path from a basal node (basal nodes are nodes "
            + "with no incoming edges)."
        )
        raise nx.NetworkXError(msg) 

After I use this effective way to check it, this problem is solved well. It would be highly appreciated if you could further confirm and investigate the issue. I will also create a PR for fixing it if you approve.

Best regards,
Joye

Step to Reproduce

Running the following Python code:

import networkx as nx

edges = [(0, 5), (0, 3), (0, 33), (3, 2), (3, 24), (3, 32), (33, 1), (33, 10), (2, 3), (2, 16), (1, 33), (10, 16), (16, 4), (16, 9), (18, 11), (11, 5), (11, 21), (4, 2), (4, 33), (9, 16), (9, 26), (9, 17), (26, 19), (17, 10), (19, 10), (19, 9), (19, 7), (19, 0)]
G = nx.DiGraph(edges)
res = nx.trophic_levels(G)
print(res[0])

Actual Result:

an extremely large positive value

Expected Result:

networkx.exception.NetworkXError

Environment

Python 3.10
NetworkX 3.1

[joyemang33]

I also found that using np.linalg.cond(i - p) < np.finfo((i - p).dtype).eps to fix the issue may not be good, since it will crash in the empty graph. I think it will be good that if we use a method other than Linear Algebra to check whether the graph is supported. Because it will let us get rid of the rounding and the corner cases.

To fully avoid this issue, we can also use BFS to determine whether the graph is supported first. This will not cost much time since its time complexity is linear, compared with the time-consuming matrix operations.

[Aditya-Shandilya1182]

I made a PR addressing this issue. Can someone please review it?
Link: #7453
Thank You!