Search code examples
pythonnetworkx

Will constructing a sparse graph in NetworkX automatically store the full adjacency matrix?

If I have a sparse graph that I would like to instantiate as a NetworkX graph and currently have stored as a (say) adjacency dictionary, will it automatically store the data also as a full adjacency matrix (which is very large and thus costly to instantiate), or will the adjacency matrix only be created when explicitly called (or another method requiring it is called)?

Solution

  • From Graph

    Edges are represented as links between nodes with optional key/value attributes.

    So the Graph isn't stored internally as an adjacency matrix. It's stored as something comparable to a dictionary of edge lists. In fact, if we dig into the source a bit, the adjacency_matrix function ends up constructing a SciPy sparse array as well.

    return nx.to_scipy_sparse_array(G, nodelist=nodelist, dtype=dtype, weight=weight)

    So even if you did construct a full adjacency matrix by calling that function explicitly, it'll use a sparse representation anyway.

    You can check DiGraph and the others, but they all have a similar comment in the documentation and are stored similarly.