Utilities#

Helper Functions#

Miscellaneous Helpers for NetworkX.

These are not imported into the base networkx namespace but can be accessed, for example, as

>>> import networkx
>>> networkx.utils.make_list_of_ints({1, 2, 3})
[1, 2, 3]
>>> networkx.utils.arbitrary_element({5, 1, 7})  
1

`arbitrary_element`(iterable)	Returns an arbitrary element of `iterable` without removing it.
`flatten`(obj[, result])	Return flattened version of (possibly nested) iterable object.
`make_list_of_ints`(sequence)	Return list of ints from sequence of integral numbers.
`dict_to_numpy_array`(d[, mapping])	Convert a dictionary of dictionaries to a numpy array with optional mapping.
`pairwise`(iterable[, cyclic])	s -> (s0, s1), (s1, s2), (s2, s3), ...
`groups`(many_to_one)	Converts a many-to-one mapping into a one-to-many mapping.
`create_random_state`([random_state])	Returns a numpy.random.RandomState or numpy.random.Generator instance depending on input.
`create_py_random_state`([random_state])	Returns a random.Random instance depending on input.
`nodes_equal`(nodes1, nodes2)	Check if nodes are equal.
`edges_equal`(edges1, edges2)	Check if edges are equal.
`graphs_equal`(graph1, graph2)	Check if graphs are equal.

Data Structures and Algorithms#

Union-find data structure.

UnionFind.union(*objects)

Find the sets containing the objects and merge them all.

Random Sequence Generators#

Utilities for generating random numbers, random sequences, and random selections.

`powerlaw_sequence`(n[, exponent, seed])	Return sample sequence of length n from a power law distribution.
`cumulative_distribution`(distribution)	Returns normalized cumulative distribution from discrete distribution.
`discrete_sequence`(n[, distribution, ...])	Return sample sequence of length n from a given discrete distribution or discrete cumulative distribution.
`zipf_rv`(alpha[, xmin, seed])	Returns a random value chosen from the Zipf distribution.
`random_weighted_sample`(mapping, k[, seed])	Returns k items without replacement from a weighted sample.
`weighted_choice`(mapping[, seed])	Returns a single element from a weighted sample.

Decorators#

`open_file`(path_arg[, mode])	Decorator to ensure clean opening and closing of files.
`not_implemented_for`(*graph_types)	Decorator to mark algorithms as not implemented
`nodes_or_number`(which_args)	Decorator to allow number of nodes or container of nodes.
`np_random_state`(random_state_argument)	Decorator to generate a `numpy.random.RandomState` instance.
`py_random_state`(random_state_argument)	Decorator to generate a random.Random instance (or equiv).
`argmap`(func, *args[, try_finally])	A decorator to apply a map to arguments before calling the function

Cuthill-Mckee Ordering#

Cuthill-McKee ordering of graph nodes to produce sparse matrices

`cuthill_mckee_ordering`(G[, heuristic])	Generate an ordering (permutation) of the graph nodes to make a sparse matrix.
`reverse_cuthill_mckee_ordering`(G[, heuristic])	Generate an ordering (permutation) of the graph nodes to make a sparse matrix.

Mapped Queue#

Priority queue class with updatable priorities.

MappedQueue([data])

The MappedQueue class implements a min-heap with removal and update-priority.

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 backend, a package must register an entry_point of networkx.backends with a key pointing to the handler.

For example:

entry_points={'networkx.backends': 'sparse = networkx_backend_sparse'}

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

Continuing the example above:

class WrappedSparse:
    __networkx_backend__ = "sparse"
    ...

When a dispatchable NetworkX algorithm encounters a Graph-like object with a __networkx_backend__ 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_TEST_BACKEND is set to a registered backend key, the dispatch machinery will automatically convert regular networkx Graphs and DiGraphs to the backend equivalent by calling <backend dispatcher>.convert_from_nx(G, edge_attrs=edge_attrs, name=name). Set NETWORKX_FALLBACK_TO_NX environment variable to have tests use networkx graphs for algorithms not implemented by the backend.

The arguments to convert_from_nx are:

G : networkx Graph
edge_attrsdict, optional
Dict that maps edge attributes to default values if missing in G. If None, then no edge attributes will be converted and default may be 1.
node_attrs: dict, optional
Dict that maps node attribute to default values if missing in G. If None, then no node attributes will be converted.
preserve_edge_attrsbool
Whether to preserve all edge attributes.
preserve_node_attrsbool
Whether to preserve all node attributes.
preserve_graph_attrsbool
Whether to preserve all graph attributes.
preserve_all_attrsbool
Whether to preserve all graph, node, and edge attributes.
namestr
The name of the algorithm.
graph_namestr
The name of the graph argument being converted.

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_TEST_BACKEND=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.

If a backend only partially implements some algorithms, it can define a can_run(name, args, kwargs) function that returns True or False indicating whether it can run the algorithm with the given arguments.

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])