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

• Graph—Undirected graphs with self loops
  • Overview
  • Methods
• DiGraph—Directed graphs with self loops
  • Overview
  • Methods
• MultiGraph—Undirected graphs with self loops and parallel edges
  • Overview
  • Methods
• MultiDiGraph—Directed graphs with self loops and parallel edges
  • Overview
  • Methods

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])
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)
FilterAdjacency(d, NODE_OK, EDGE_OK)
FilterMultiInner(d, NODE_OK, EDGE_OK)
FilterMultiAdjacency(d, NODE_OK, EDGE_OK)

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)
hide_nodes(nodes)
hide_edges(edges)
hide_diedges(edges)
hide_multidiedges(edges)
hide_multiedges(edges)
show_nodes(nodes)
show_edges(edges)
show_diedges(edges)
show_multidiedges(edges)
show_multiedges(edges)

Backends

Note

This is an experimental feature to dispatch your computations to an alternate backend like GraphBLAS, instead of using pure Python dictionaries for computation. Things will change and break in the future!

Code to support various backends in a plugin dispatch architecture.

Create a Dispatcher

To be a valid plugin, a package must register an entry_point of networkx.plugins with a key pointing to the handler.

For example:

entry_points={'networkx.plugins': 'sparse = networkx_plugin_sparse'}

The plugin must create a Graph-like object which contains an attribute __networkx_plugin__ with a value of the entry point name.

Continuing the example above:

class WrappedSparse:
    __networkx_plugin__ = "sparse"
    ...

When a dispatchable NetworkX algorithm encounters a Graph-like object with a __networkx_plugin__ attribute, it will look for the associated dispatch object in the entry_points, load it, and dispatch the work to it.

Testing

To assist in validating the backend algorithm implementations, if an environment variable NETWORKX_GRAPH_CONVERT is set to a registered plugin keys, the dispatch machinery will automatically convert regular networkx Graphs and DiGraphs to the backend equivalent by calling <backend dispatcher>.convert_from_nx(G, weight=weight, name=name).

The converted object is then passed to the backend implementation of the algorithm. The result is then passed to <backend dispatcher>.convert_to_nx(result, name=name) to convert back to a form expected by the NetworkX tests.

By defining convert_from_nx and convert_to_nx methods and setting the environment variable, NetworkX will automatically route tests on dispatchable algorithms to the backend, allowing the full networkx test suite to be run against the backend implementation.

Example pytest invocation:

NETWORKX_GRAPH_CONVERT=sparse pytest --pyargs networkx

Dispatchable algorithms which are not implemented by the backend will cause a pytest.xfail(), giving some indication that not all tests are working, while avoiding causing an explicit failure.

A special on_start_tests(items) function may be defined by the backend. It will be called with the list of NetworkX tests discovered. Each item is a test object that can be marked as xfail if the backend does not support the test using item.add_marker(pytest.mark.xfail(reason=...)).

_dispatch([func, name])

Dispatches to a backend algorithm when the first argument is a backend graph-like object.