TopolearnKnowing the representation explains why NetworkX is flexible but memory-hungry, and which operations are cheap.
A NetworkX Graph is a set of nested Python dicts:
G._node: node -> node attribute dictG._adj: node -> {neighbour -> edge attribute dict}, a dict of dicts of dictsG.graph: graph attributes
In an undirected graph, the edge attribute dict is shared: G._adj[u][v] is G._adj[v][u], so changing an attribute through either side updates both. A DiGraph keeps two structures, _succ and _pred (with _adj aliasing _succ), so it can answer predecessor queries quickly at roughly double the memory. Multigraphs add one more level, keyed by edge key.
Consequences:
- Adding, removing and testing nodes and edges, and iterating neighbours, are all O(1) or O(degree), and anything hashable can be a node.
- Memory is high: each edge costs a few hundred bytes of dict overhead, so 100 million edges is far beyond a typical machine. Libraries with compact array storage use a fraction of that.
- Algorithms are pure Python loops, so they run much slower than compiled implementations on large graphs.
The classes are designed for subclassing. Class attributes such as node_dict_factory, adjlist_outer_dict_factory, adjlist_inner_dict_factory and edge_attr_dict_factory let you swap the dict types, for example to use ordered or disk-backed mappings. The views (G.adj, G.nodes) are thin read-only wrappers over these dicts.
Example
import sys
import networkx as nx
G = nx.Graph()
G.add_edge("a", "b", weight=3)
print(G._adj) # {'a': {'b': {'weight': 3}}, 'b': {'a': {'weight': 3}}}
print(G._adj["a"]["b"] is G._adj["b"]["a"]) # True: one shared attribute dict
G["a"]["b"]["weight"] = 7
print(G["b"]["a"]["weight"]) # 7
D = nx.DiGraph([("a", "b")])
print(D._succ, D._pred) # {'a': {'b': {}}, 'b': {}} {'a': {}, 'b': {'a': {}}}
print(D._adj is D._succ) # True
class TinyAttrGraph(nx.Graph):
edge_attr_dict_factory = dict # swap in any MutableMapping type here
big = nx.gnm_random_graph(2_000, 20_000, seed=1)
per_edge = sum(sys.getsizeof(nbrs) + sum(sys.getsizeof(d) for d in nbrs.values())
for nbrs in big._adj.values()) / big.number_of_edges()
print(per_edge > 100) # True: hundreds of bytes per edgeRemember
- Graphs are nested dicts: node -> neighbour -> attribute dict
- Undirected edges share one attribute dict; DiGraphs store succ and pred
- Flexible and O(1) updates, but heavy memory and pure-Python speed
Watch out for
- Loading a 100-million-edge graph into NetworkX without estimating its dict overhead first.