Graph types#

NetworkX provides data structures and methods for storing graphs.

All NetworkX graph classes allow (hashable) Python objects as nodes and any Python object can be assigned as an edge attribute.

The choice of graph class depends on the structure of the graph you want to represent.

Which graph class should I use?#

Networkx Class

Type

Self-loops allowed

Parallel edges allowed

Graph

undirected

Yes

No

DiGraph

directed

Yes

No

MultiGraph

undirected

Yes

Yes

MultiDiGraph

directed

Yes

Yes

Basic graph types#

Note

NetworkX uses dicts to store the nodes and neighbors in a graph. So the reporting of nodes and edges for the base graph classes may not necessarily be consistent across versions and platforms; however, the reporting for CPython is consistent across platforms and versions after 3.6.

Graph Views#

View of Graphs as SubGraph, Reverse, Directed, Undirected.

In some algorithms it is convenient to temporarily morph a graph to exclude some nodes or edges. It should be better to do that via a view than to remove and then re-add. In other algorithms it is convenient to temporarily morph a graph to reverse directed edges, or treat a directed graph as undirected, etc. This module provides those graph views.

The resulting views are essentially read-only graphs that report data from the original graph object. We provide an attribute G._graph which points to the underlying graph object.

Note: Since graphviews look like graphs, one can end up with view-of-view-of-view chains. Be careful with chains because they become very slow with about 15 nested views. For the common simple case of node induced subgraphs created from the graph class, we short-cut the chain by returning a subgraph of the original graph directly rather than a subgraph of a subgraph. We are careful not to disrupt any edge filter in the middle subgraph. In general, determining how to short-cut the chain is tricky and much harder with restricted_views than with induced subgraphs. Often it is easiest to use .copy() to avoid chains.

generic_graph_view(G[, create_using])

Returns a read-only view of G.

subgraph_view(G, *[, filter_node, filter_edge])

View of G applying a filter on nodes and edges.

reverse_view(G)

View of G with edge directions reversed

Core Views#

Views of core data structures such as nested Mappings (e.g. dict-of-dicts). These Views often restrict element access, with either the entire view or layers of nested mappings being read-only.

AtlasView(d)

An AtlasView is a Read-only Mapping of Mappings.

AdjacencyView(d)

An AdjacencyView is a Read-only Map of Maps of Maps.

MultiAdjacencyView(d)

An MultiAdjacencyView is a Read-only Map of Maps of Maps of Maps.

UnionAtlas(succ, pred)

A read-only union of two atlases (dict-of-dict).

UnionAdjacency(succ, pred)

A read-only union of dict Adjacencies as a Map of Maps of Maps.

UnionMultiInner(succ, pred)

A read-only union of two inner dicts of MultiAdjacencies.

UnionMultiAdjacency(succ, pred)

A read-only union of two dict MultiAdjacencies.

FilterAtlas(d, NODE_OK)

A read-only Mapping of Mappings with filtering criteria for nodes.

FilterAdjacency(d, NODE_OK, EDGE_OK)

A read-only Mapping of Mappings with filtering criteria for nodes and edges.

FilterMultiInner(d, NODE_OK, EDGE_OK)

A read-only Mapping of Mappings with filtering criteria for nodes and edges.

FilterMultiAdjacency(d, NODE_OK, EDGE_OK)

A read-only Mapping of Mappings with filtering criteria for nodes and edges.

Reporting Views#

View Classes provide node, edge and degree “views” of a graph.

As with dicts, the graph should not be updated while iterating through the view. Views can be iterated multiple times.

Views are quick-to-create, read-only iterable containers, live (they reflect changes to the graph), and provide Pythonic access patterns for all base graph classes:

  • set-like membership and set operations for nodes and edges (n in G.nodes, G.nodes & H.nodes, (u, v) in G.edges),

  • iteration (for n in G.nodes, for u, v in G.edges),

  • mapping-style lookups (G.nodes[n] returns the node attribute dict; G.edges[u, v] returns the edge attribute dict),

  • data-filtered iteration via .data(...) and conversion to concrete containers via list(...) or dict(...).

The resulting attribute dict is writable as G.edges[3, 4]['color'] = 'red' Degree views allow lookup of degree values for single nodes. Weighted degree is supported with the weight argument.

NodeView#

V = G.nodes (or V = G.nodes()) allows len(V), n in V, set operations e.g. G.nodes & H.nodes, and dd = G.nodes[n], where dd is the node data dict. Iteration is over the nodes by default.

NodeDataView#

To iterate over (node, data) pairs, use arguments to G.nodes() to create a DataView e.g. DV = G.nodes(data='color', default='red'). The DataView iterates as for n, color in DV and allows (n, 'red') in DV. Using DV = G.nodes(data=True), the DataViews use the full datadict in writeable form also allowing contain testing as (n, {'color': 'red'}) in VD. DataViews allow set operations when data attributes are hashable.

DegreeView#

V = G.degree allows iteration over (node, degree) pairs as well as lookup: deg = V[n]. There are many flavors of DegreeView for In/Out/Directed/Multi. For Directed Graphs, G.degree counts both in and out going edges. G.out_degree and G.in_degree count only specific directions. Weighted degree using edge data attributes is provide via V = G.degree(weight='attr_name') where any string with the attribute name can be used. weight=None is the default. No set operations are implemented for degrees, use NodeView.

The argument nbunch restricts iteration to nodes in nbunch. The DegreeView can still lookup any node even if nbunch is specified.

EdgeView#

V = G.edges or V = G.edges() allows iteration over edges as well as e in V, set operations and edge data lookup dd = G.edges[2, 3]. Iteration is over 2-tuples (u, v) for Graph/DiGraph. For multigraphs edges 3-tuples (u, v, key) are the default but 2-tuples can be obtained via V = G.edges(keys=False).

Set operations for directed graphs treat the edges as a set of 2-tuples. For undirected graphs, 2-tuples are not a unique representation of edges. So long as the set being compared to contains unique representations of its edges, the set operations will act as expected. If the other set contains both (0, 1) and (1, 0) however, the result of set operations may contain both representations of the same edge.

EdgeDataView#

Edge data can be reported using an EdgeDataView typically created by calling an EdgeView: DV = G.edges(data='weight', default=1). The EdgeDataView allows iteration over edge tuples, membership checking but no set operations.

Iteration depends on data and default and for multigraph keys If data is False (the default) then iterate over 2-tuples (u, v). If data is True iterate over 3-tuples (u, v, datadict). Otherwise iterate over (u, v, datadict.get(data, default)). For Multigraphs, if keys is True, replace u, v with u, v, key to create 3-tuples and 4-tuples.

The argument nbunch restricts edges to those incident to nodes in nbunch.

Common usage patterns#

NodeView / NodeDataView#

  • Use G.nodes when you need membership tests, set-like operations, or to look up a node’s attribute dict with G.nodes[n].

  • Use G.nodes(data=...) or G.nodes.data(attr_name, default=...) to iterate node/data pairs or to extract a single attribute for all nodes.

  • Use list(G) or for node in G: to iterate over nodes.

Example:

>>> G = nx.path_graph(3)
>>> list(G.nodes)
[0, 1, 2]
>>> G.add_node(3, color="red")
>>> list(G.nodes.data("color", default=None))
[(0, None), (1, None), (2, None), (3, 'red')]

EdgeView / EdgeDataView#

  • Use G.edges to iterate or test membership for edges.

  • Call G.edges(data=...) or G.edges(nbunch=..., data=..., keys=...) to iterate edges with data, restrict to edges incident to a set of nodes, or include multigraph keys.

Note

Iteration of G.edges() yields node pairs as 2-tuples even for multigraphs. Iteration of G.edges yields 3-tuples for multigraphs and 2-tuples otherwise. You can also use G.edges(keys=True, data=True) to receive 4-tuples (u, v, key, data) for multigraphs.

Example:

>>> G = nx.Graph()
>>> G.add_edge(0, 1, weight=3)
>>> list(G.edges(data="weight", default=1))
[(0, 1, 3)]

DegreeView#

  • Use G.degree to iterate (node, degree) pairs or query a single node with G.degree[n].

  • The function interface G.degree(nbunch=..., weight=...) allows: * weight="attr" to compute weighted degree using the named edge attribute, and * nbunch to restrict iteration to a subset of nodes while still allowing direct lookups.

Example:

>>> G = nx.cycle_graph(4)
>>> dict(G.degree())
{0: 2, 1: 2, 2: 2, 3: 2}
>>> G.degree[0]
2
>>> # Add an edge with a weight attribute and compute weighted degrees:
>>> G.add_edge(0, 1, weight=5)
>>> dict(G.degree(weight="weight"))
{0: 6, 1: 6, 2: 2, 3: 2}

Degree Computation#

NetworkX does not store a persistent degree value for each node. Instead, the degree is computed when requested by examining the neighbor dictionary for a node and counting or summing edge attributes as needed. For multigraphs the key dict for each neighbor is scanned; for weighted degree the requested edge attribute values are summed.

Because computing degree accesses the adjacency structures, some applications cache degree values in a separate dictionary to avoid repeated recomputation:

>>> G_degree = dict(G.degree)   # make a cached snapshot of degrees

If degrees are cached, update the cached dictionary when edges are modified.

Performance & pitfalls#

  • Views are read-only wrappers — they do not copy graph data. If you need a stable snapshot (for example when you will modify the graph while iterating), materialize the view using list(view) or dict(view).

  • Avoid modifying the graph while iterating over a view (same rule as iterating a dict).

  • DataViews that return full attribute dicts expose writable dicts (modifying those dicts modifies the underlying graph attributes). Use this intentionally.

  • Edge set operations on undirected graphs use 2-tuple representations; be careful when comparing sets that may contain both (u, v) and (v, u).

  • DegreeView with weight performs a sum over edge attributes and can be more expensive than unweighted degree calculations.

  • When G will not change and you need many degree lookups, store the precomputed degrees using degrees = dict(G.degree).

NodeView(graph)

A NodeView class to act as G.nodes for a NetworkX Graph

NodeDataView(nodedict[, data, default])

A DataView class for nodes of a NetworkX Graph

EdgeView(G)

A EdgeView class for edges of a Graph

EdgeDataView(viewer[, nbunch, data, default])

A EdgeDataView class for edges of Graph

DegreeView(G[, nbunch, weight])

A DegreeView class to act as G.degree for a NetworkX Graph

Filters#

Note

Filters can be used with views to restrict the view (or expand it). They can filter nodes or filter edges. These examples are intended to help you build new ones. They may instead contain all the filters you ever need.

Filter factories to hide or show sets of nodes and edges.

These filters return the function used when creating SubGraph.

no_filter(*items)

Returns a filter function that always evaluates to True.

hide_nodes(nodes)

Returns a filter function that hides specific nodes.

hide_edges(edges)

Returns a filter function that hides specific undirected edges.

hide_diedges(edges)

Returns a filter function that hides specific directed edges.

hide_multidiedges(edges)

Returns a filter function that hides specific multi-directed edges.

hide_multiedges(edges)

Returns a filter function that hides specific multi-undirected edges.

show_nodes(nodes)

Filter class to show specific nodes.

show_edges(edges)

Returns a filter function that shows specific undirected edges.

show_diedges(edges)

Returns a filter function that shows specific directed edges.

show_multidiedges(edges)

Returns a filter function that shows specific multi-directed edges.

show_multiedges(edges)

Returns a filter function that shows specific multi-undirected edges.