# Release Notes¶

## 0.11.0¶

### Prelude¶

This release includes many new features and bug fixes. Highlights include
additional methods to improve working with edges in both
`PyGraph`

and `PyDiGraph`

,
several new graph generators, and a new set of interactive traversal
functions: `bfs_search()`

, `dfs_search()`

,
`dijkstra_search()`

, and `TopologicalSorter`

,
which enable iterative interaction with the graph during different types
of traversal.

This release also introduces a new separate Rust crate
retworkx-core which
is a library for use in Rust that’s built on top of
petgraph that extends the
functionality provided by petgraph. The functionality in this crate is generic
and can work with any petgraph graph, not just the `PyGraph`

amd `PyDiGraph`

.

The 0.11.0 release fully supports Python 3.10. Precompiled binaries for Python 3.10 are published on PyPI (previous releases worked with 3.10 but required compiling from source to install). This is also the last release to support Python 3.6. Starting in retworkx 0.12.0, Python >=3.7 will be required to run retworkx. Additionally, for users compiling retworkx from source, this will be the last release with a minimum supported Rust version (MSRV) of 1.41. In retworkx 0.12.0, the MSRV will be increased to 1.48.

### New Features¶

Added a new function,

`cartesian_product()`

(and its per type variants`digraph_cartesian_product()`

and`graph_cartesian_product()`

), which calculates the Cartesian product of two graphs. For example:import retworkx from retworkx.visualization import mpl_draw graph_1 = retworkx.generators.path_graph(2) graph_2 = retworkx.generators.path_graph(3) graph_product, _ = retworkx.cartesian_product(graph_1, graph_2) mpl_draw(graph_product)

Added a new method,

`node_indices()`

, to the`PyDiGraph`

and`PyGraph`

classes. This method is identical to the previously existing`node_indexes()`

method but changes the name to be consistent with the use of “indices” throughout the rest of retworkx. The`node_indexes()`

will likely be deprecated in a future release prior to it’s removal in an eventual 1.0 release.

The

`unweighted_average_shortest_path_length()`

function has a new kwarg`disconnected`

. When`disconnected`

is set to`True`

the output value calculated by the function will only account for connected node pairs.

Added a new generator function,

`barbell_graph()`

, to the`retworkx.generators`

module that will generate a barbell graph. For example:import retworkx.generators from retworkx.visualization import mpl_draw graph = retworkx.generators.barbell_graph(4, 3) mpl_draw(graph)

Added a new

`bfs_search()`

(and it’s per type variants`graph_bfs_search()`

and`digraph_bfs_search()`

) that traverses the graph in a breadth-first manner and emits events at specified points. The events are handled by a visitor object that subclasses`BFSVisitor`

through the appropriate callback functions. For example:import retworkx from retworkx.visit import BFSVisitor class TreeEdgesRecorder(BFSVisitor): def __init__(self): self.edges = [] def tree_edge(self, edge): self.edges.append(edge) graph = retworkx.PyGraph() graph.extend_from_edge_list([(1, 3), (0, 1), (2, 1), (0, 2)]) vis = TreeEdgesRecorder() retworkx.bfs_search(graph, [0], vis) print('Tree edges:', vis.edges)

Tree edges: [(0, 2, None), (0, 1, None), (1, 3, None)]

Added a new function

`articulation_points()`

that finds the articulation points of an undirected`PyGraph`

. An articulation point or cut vertex is any node whose removal increases the number of connected components of a graph. For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.PyGraph() graph.extend_from_edge_list([ (0, 1), (1, 2), (0, 2), (1, 3) ]) points = retworkx.articulation_points(graph) colors = ['black'] * len(graph) for node in points: colors[node] = 'blue' mpl_draw(graph, node_color=colors)

Added a new function

`biconnected_components()`

that returns the biconnected components of an undirected`PyGraph`

. A biconnected component is a maximal subgraph that remains connected after removal of a node. For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.PyGraph() graph.extend_from_edge_list([ (0, 1), (1, 2), (0, 2), (1, 3), (2, 4) ]) components = retworkx.biconnected_components(graph) COLORS = ["blue", "red", "orange"] edge_colors = [] for (u, v) in graph.edge_list(): if (u, v) in components: comp = components[(u, v)] else: comp = components[(v, u)] edge_colors += [COLORS[comp]] mpl_draw(graph, node_color='black', node_size=150, edge_color=edge_colors)

Added a new function

`chain_decomposition()`

that finds a chain decomposition of an undirected`PyGraph`

. A chain decomposition is a set of cycles or paths derived from the set of fundamental cycles of a depth-first tree. It’s defined in https://doi.org/10.1016/j.ipl.2013.01.016 For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.PyGraph() graph.extend_from_edge_list([ (0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (3, 5), (4, 5), ]) chains = retworkx.chain_decomposition(graph) def color_edges(graph, chains): COLORS = ['blue', 'red'] edges_in_chain = {} for idx, chain in enumerate(chains): for edge in chain: edge = tuple(sorted(edge)) edges_in_chain[edge] = COLORS[idx] edge_colors = [] for edge in graph.edge_list(): edge = tuple(sorted(edge)) edge_colors += [edges_in_chain.get(edge, 'black')] return edge_colors mpl_draw(graph, node_color='black', node_size=150, edge_color=color_edges(graph, chains))

Added new constructor methods

`retworkx.PyDiGraph.from_complex_adjacency_matrix()`

and`retworkx.PyGraph.from_complex_adjacency_matrix()`

for creating a`PyDiGraph`

and a`PyGraph`

respectively from a numpy adjacency matrix with a`complex`

`dtype`

. For example:import numpy as np import retworkx from retworkx.visualization import mpl_draw adj_matrix = np.array([ [0, 0 - 1j, 0, 1 + 2j], [0 - 1j, 0, 1 + 0j, 0], [0, 1 + 0j, 0, 2 + 0.5j], [1 + 2j, 0, 2 + 0.5j, 0] ], dtype=complex) graph = retworkx.PyDiGraph.from_complex_adjacency_matrix(adj_matrix) mpl_draw(graph, with_labels=True, edge_labels=str)

Adds

`connected_components()`

for finding connected components in an undirected`PyGraph`

graph.

Adds

`number_connected_components()`

for finding the number of connected components in an undirected`PyGraph`

graph.

Adds

`node_connected_component()`

for finding the connected component that a node belongs in an undirected`PyGraph`

graph.

Adds

`is_connected()`

for checking if an undirected`PyGraph`

graph is connected.

Added new graph methods

`retworkx.PyDiGraph.contract_nodes()`

, and`retworkx.PyGraph.contract_nodes()`

. These methods can be used to replace a set of graph nodes with a single new equivalent node. Incoming edges and outgoing edges of and to the replaced set become the incoming and outgoing edges of the new node, respectively. In a multi-graph, all edges are preserved by default. For all graph types, parallel edges can optionally be combined via a user-specified Python callable.`retworkx.PyDiGraph.contract_nodes()`

supports cycle checking / guarding to prevent the contraction from introducing cycles. In the following example, two nodes are contracted to a single new node. First, creating a new graph:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.directed_path_graph(5) mpl_draw(graph, with_labels=True)

perform the contraction:

graph.contract_nodes([2, 3], "abc") mpl_draw(graph, with_labels=True)

Added a new

`dfs_search()`

(and it’s per type variants`graph_dfs_search()`

and`digraph_dfs_search()`

) that traverses the graph in a depth-first manner and emits events at specified points. The events are handled by a visitor object that subclasses`DFSVisitor`

through the appropriate callback functions. For example:import retworkx from retworkx.visit import DFSVisitor class TreeEdgesRecorder(DFSVisitor): def __init__(self): self.edges = [] def tree_edge(self, edge): self.edges.append(edge) graph = retworkx.PyGraph() graph.extend_from_edge_list([(1, 3), (0, 1), (2, 1), (0, 2)]) vis = TreeEdgesRecorder() retworkx.dfs_search(graph, [0], vis) print('Tree edges:', vis.edges)

Tree edges: [(0, 2, None), (2, 1, None), (1, 3, None)]

Added a new

`dijkstra_search()`

(and it’s per type variants`graph_dijkstra_search()`

and`digraph_dijkstra_search()`

) that traverses the graph using dijkstra algorithm and emits events at specified points. The events are handled by a visitor object that subclasses`DijkstraVisitor`

through the appropriate callback functions. For example:import retworkx from retworkx.visit import DijkstraVisitor class DijkstraTreeEdgesRecorder(retworkx.visit.DijkstraVisitor): def __init__(self): self.edges = [] self.parents = dict() def discover_vertex(self, v, _): u = self.parents.get(v, None) if u is not None: self.edges.append((u, v)) def edge_relaxed(self, edge): u, v, _ = edge self.parents[v] = u graph = retworkx.PyGraph() graph.extend_from_weighted_edge_list([(1, 3, 1), (0, 1, 10), (2, 1, 1), (0, 2, 1)]) vis = DijkstraTreeEdgesRecorder() retworkx.graph_dijkstra_search(graph, [0], float, vis) print('Tree edges:', vis.edges)

Tree edges: [(0, 2), (2, 1), (1, 3)]

Added a new method,

`incident_edges()`

, to the`PyGraph`

and`PyDiGraph`

class. This method returns a list of edge indices for edges incident to a provided node.

Added a new method,

`incident_edge_index_map()`

, to the`PyGraph`

and`PyDiGraph`

class. This method returns a mapping of edge indices for edges incident to a provided node to the endoint and weight tuple for that edge index. For example:import retworkx graph = retworkx.PyGraph() graph.extend_from_weighted_edge_list([(0, 1, "A"), (0, 2, "B")]) print(graph.incident_edge_index_map(0))

EdgeIndexMap{1: (0, 2, B), 0: (0, 1, A)}

Added a new method,

`get_edge_data_by_index()`

, to the`PyGraph`

and`PyDiGraph`

classes. This method returns the data payload for an edge in the graph from its index.

Added a new method,

`get_edge_endpoints_by_index()`

, to the`PyGraph`

and`PyDiGraph`

classes. This method returns the edge’s endpoint tuple for an edge in the graph from its index.

Added two new methods,

`out_edges()`

and`in_edges()`

to the`PyGraph`

class. These methods are the duals of the`PyDiGraph`

methods,`out_edges()`

and`in_edges()`

and return a`WeightedEdgeList`

of the incident edges for a node.

The algorithm used for the

`steiner_tree()`

implementation has been replaced by a faster algorithm based on: https://doi.org/10.1016/0020-0190(88)90066-X. This new implementation achieves the same approximation ratio as the algorithm used previously, so there should be no change in functionality.

Added a new function,

`full_rary_tree()`

that adds support for generating a full \(r\)-ary tree of \(n\) nodes. For example:import retworkx.generators from retworkx.visualization import mpl_draw graph = retworkx.generators.full_rary_tree(3, 5) mpl_draw(graph)

Added a new function,

`lollipop_graph()`

that adds support for generating lollipop graphs. For example:import retworkx.generators from retworkx.visualization import mpl_draw graph = retworkx.generators.lollipop_graph(4, 3) mpl_draw(graph)

Added a new class,

`TopologicalSorter`

, which provides functionality to topologically sort a directed graph. It gives the ability to process nodes while they are becoming ready and then mark them as done, so more nodes can be freed.

The

`betweenness_centrality()`

(and it’s per type variants`graph_betweenness_centrality()`

and`digraph_betweenness_centrality()`

) is now multithreaded. For larger graphs this can significantly improve the runtime performance of the function. By default any graphs with < 50 nodes will still execute in a single thread, while larger graphs will be executed in parallel. The size of the graph to start running in parallel can be adjusted using the new`parallel_threshold`

kwarg. Additionally, the environment variable`RAYON_NUM_THREADS`

can be used how many threads will be used when run in parallel. By default it will use a thread for each CPU on the local system.

Added a new function,

`generalized_petersen_graph()`

that adds support for generating generalized Petersen graphs. For example:import retworkx.generators from retworkx.visualization import mpl_draw graph = retworkx.generators.generalized_petersen_graph(5, 2) layout = retworkx.shell_layout(graph, nlist=[[0, 1, 2, 3, 4], [6, 7, 8, 9, 5]]) mpl_draw(graph, pos=layout)

Added a new workspace crate, retworkx-core as part of retworkx. This is a standalone Rust library that is built on top of petgraph that provides general algorithms and graph functionality that retworkx needs. This new crate only exposes a Rust interface that is general for any petgraph graph and can be used by any downstream Rust project that wants the extra functionality that retworkx exposes, but without Python.

It’s also worth noting as this is the first release of

`retworkx-core`

there may be breaking API changes in a subsequent release. While we will attempt to follow the standard deprecation and stability policy, since we’re not necessarily fully committed to the current API and without having a user outside of retworkx, there may be gaps or issues which require breaking changes.

A new kwarg,

`keep_attributes`

, has been added to the NetworkX graph converter function`networkx_converter()`

. When this argument is set to`True`

the node attributes from the input NetworkX graph will be preserved. The data payload for the output retworkx graph will be a dictionary containing the attributes, with an extra`"__networkx_node__"`

key containing the node from NetworkX. For example:import networkx as nx import retworkx as rx g = nx.Graph() g.add_nodes_from([ ("A", {"color": "turquoise", "size": "extra large"}), ("B", {"color": "fuschia", "size": "tiny"}), ]) g.add_edge("A", "B") rx_graph = rx.networkx_converter(g, keep_attributes=True) print(rx_graph.nodes()) print(rx_graph.weighted_edge_list())

will output:

[{'color': 'turquoise', 'size': 'extra large', '__networkx_node__': 'A'}, {'color': 'fuschia', 'size': 'tiny', '__networkx_node__': 'B'}] WeightedEdgeList[(0, 1, {})]

### Upgrade Notes¶

The default behavior for how the

`unweighted_average_shortest_path_length()`

function handles disconnected graphs has been changed. Previously, disconnected pairs of nodes was assumed to have zero distance which is arguably incorrect/unexpected behavior. To make this more consistent with user expectations this has been changed to an infinite value. In addition, an extra kwarg`disconnected`

was added where, if set to`True`

, the average is taken only over connected node pairs. By default, it’s set to`False`

. If the previous behavior of treating disconnected pairs of nodes as having a distance of zero is desired, it can be reproduced using the rest of retworkx API like:import retworkx graph = retworkx.undirected_gnm_random_graph(20, 10, seed=42) n = len(graph) d_mat = retworkx.distance_matrix(graph, null_value=0.0) avg_shortest_path = d_mat.sum() / (n * (n - 1.0))

The optional dependencies for

`graphviz_draw()`

(as documented by the`graphviz`

optional extra, which can be installed via`pip install retworkx[graphviz]`

) no longer requires the`pydot`

library. Only the`pillow`

library is needed now to generate visualizations using graphviz.

### Bug Fixes¶

Fixed an issue with the

`binomial_tree_graph()`

and`directed_binomial_tree_graph()`

generator functions in`retworkx.generators`

where passing an`order`

value`>= 60`

would cause an overflow and raise a`PanicException`

caused by the internal Rust panic when overflowing or exceeding the max Vec size. Instead the function will raise an`OverflowError`

and indicate the specified order is too large. Fixed #457

Fixed an issue where

`distance_matrix()`

and`k_shortest_path_lengths()`

would previously panic if the input graph contains holes in the node indices.

Fixed the

`retworkx.PyGraph.degree()`

method when running on a node that has self-loops. Previously, the method would increment the node’s degree of a self-loop by one instead of two. Fixed #517.

Fixed the

`dfs_edges()`

function to have the`source`

argument default to`None`

as was documented. Previously, the`source`

argument was incorrectly required and had no default value. Fixed #515.

Fixed an oversight in the

`union()`

function where user-defined values for the`merge_nodes`

and`merge_edges`

arguments were being ingored.

Fixed an oversight in shortest path algorithms functions, such as:

`dijkstra_shortest_paths()`

,`dijkstra_shortest_path_lengths()`

,`all_pairs_dijkstra_path_lengths()`

,`all_pairs_dijkstra_shortest_paths()`

,`astar_shortest_path()`

, and`k_shortest_path_lengths()`

which would previously incorrectly accept edge weights with negative or`NaN`

values. Fixed #525.

## 0.10.2¶

### Prelude¶

This release is a bugfix release that fixes some issues found since the 0.10.1 release. The fixes in this release are primarily in the vf2 implementation and most importantly fixes the output of `vf2_mapping()`

with an empty input graph and the output of `vf2_mapping()`

, `is_isomorphic()`

, and `is_subgraph_isomorphic()`

with graphs that have parallel edges.

### New Features¶

Add a new function

`graph_union()`

that returns the union of two`PyGraph`

objects. This is the equivalent to`digraph_union()`

but for a`PyGraph`

instead of for a`PyDiGraph`

. A new unified function`union()`

was also added that supports both`PyDiGraph`

and`PyGraph`

. For example:import retworkx from retworkx.visualization import mpl_draw first = retworkx.generators.path_graph(3, weights=["a_0", "node", "a_1"]) second = retworkx.generators.cycle_graph(3, weights=["node", "b_0", "b_1"]) graph = retworkx.graph_union(first, second, merge_nodes=True) mpl_draw(graph)

The kwargs

`merge_nodes`

and`merge_edges`

of`digraph_union()`

are now optional and by default are set False.

Add a new

`find_node_by_weight()`

that finds the index of a node given a specific weight.

### Bug Fixes¶

Fixes the output of

`adj()`

to include neighbors that have an edge between them and the specified node, in either direction. Previously, only outbound nodes were included.

Previously,

`digraph_union()`

would incorrectly keep or delete edges if argument`merge_edges`

is set to true. This has been fixed and an edge from the second graph will be skipped if both its endpoints were merged to nodes from the first graph and these nodes already share an edge with equal weight data. Fixed #432

Fixes the output of

`is_subgraph_isomorphic()`

if the input graphs have parallel edges. Fixed #429

Fixes the output of

`is_isomorphic()`

if the input graphs have parallel edges and an edge_matcher is specified. Fixed #429

Reduces the memory requirements of VF2 graph isomorphism algorithm by making use of a hash map with number of entries scaling as the number of edges in the graph rather than building the full adjacency matrix. Fixed #367

Previously,

`vf2_mapping()`

function when comparing 2 empty graph objects would incorrectly return an empty iterator. This has been fixed and now returns an iterator over the single valid mapping, i.e the empty mapping.

## 0.10.1¶

### Prelude¶

This is a bugfix release that fixes a regression introduced in the previous 0.10.0 release. In 0.10.0 the `is_isomorphic()`

function when comparing 2 empty graph objects would incorrectly return `False`

.

## 0.10.0¶

### Prelude¶

This release includes many new features and bug fixes. The highlights of this
release are a slew of new algorithm functions including
`steiner_tree()`

and `betweenness_centrality()`

,
improvements to the isomorphism functions including the addition of
`vf2_mapping()`

to get an isomorphic mapping between two
graphs, and improvements to working with graph objects such as
`retworkx.PyDiGraph.substitute_node_with_subgraph()`

for replacing a
node with a subgraph.

### New Features¶

Added a new algorithm function,

`retworkx.unweighted_average_shortest_path_length()`

for computing the average shortest path length of a`PyDiGraph`

or`PyGraph`

object. The average shortest path length is defined as\[a =\sum_{s,t \in V} \frac{d(s, t)}{n(n-1)}\]where \(V\) is the set of nodes in the graph, \(d(s, t)\) is the shortest path length from \(s\) to \(t\), and \(n\) is the number of nodes in graph.

Added a new function,

`betweenness_centrality()`

to compute betweenness centrality of all nodes in a`PyGraph`

or`PyDiGraph`

object. The algorithm used in this function is based on:Ulrik Brandes, “A Faster Algorithm for Betweenness Centrality”. Journal of Mathematical Sociology 25(2):163-177, 2001. DOI: 10.1080/0022250X.2001.9990249

The betweenness centrality of a node \(v\) is the sum of the fraction of all-pairs shortest paths that pass through \(v\)

\[c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}\]where \(V\) is the set of nodes, \(\sigma(s, t)\) is the number of shortest \((s, t)\) paths, and \(\sigma(s, t|v)\) is the number of those paths passing through some node \(v\) other than \(s, t\). If \(s = t\), \(\sigma(s, t) = 1\), and if \(v \in {s, t}\), \(\sigma(s, t|v) = 0\)

For example, computing the betweenness centrality for all nodes in a 5x5 grid graph and using that to color the nodes in a graph visualization:

import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.grid_graph(5, 5) btw = retworkx.betweenness_centrality(graph) # Color nodes in graph visualization with betweenness centrality colors = [] for i in range(len(graph)): colors.append(btw[i]) mpl_draw(graph, node_color=colors)

Added two new algorithm functions,

`dag_weighted_longest_path_length()`

and`dag_weighted_longest_path()`

, to find the longest path and the length of the longest path in a`PyDiGraph`

object without any cycles. These new functions are basically equivalent to`dag_longest_path()`

and`dag_longest_path_length()`

except for two key differences. First the`weight_fn`

parameter is required for`dag_weighted_longest_path_length()`

and`dag_weighted_longest_path_length()`

while it is optional in`dag_longest_path()`

and`dag_longest_path_length()`

. Secondly,`dag_weighted_longest_path()`

and`dag_weighted_longest_path_length()`

work with`float`

weights (`dag_weighted_longest_path_length()`

returns a float and the`weight_fn`

callback for both is expected to return a`float`

) while`dag_longest_path()`

and`dag_longest_path_length()`

works with an unsigned`int`

.

Added a new method,

`edge_subgraph()`

, to the`PyDiGraph`

and`PyGraph`

(`edge_subgraph()`

) to get an edge induced subgraph from a given graph object.

Added new generator functions,

`retworkx.generators.heavy_hex_graph()`

and`retworkx.generators.directed_heavy_hex_graph()`

, for constructing a heavy hex graphs from: https://journals.aps.org/prx/abstract/10.1103/PhysRevX.10.011022 For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.directed_heavy_hex_graph(3) mpl_draw(graph)

Added new generator functions,

`retworkx.generators.heavy_square_graph()`

and`retworkx.generators.directed_heavy_square_graph()`

, for generating heavy square graphs from: https://journals.aps.org/prx/abstract/10.1103/PhysRevX.10.011022 For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.directed_heavy_square_graph(3) mpl_draw(graph)

A new kwarg,

`labels`

, has been added to the`retworkx.PyDiGraph.read_edge_list()`

and`retworkx.PyGraph.read_edge_list()`

constructor methods. When this kwarg is set to`True`

the first 2 elements on a line in an edge list file are treated as string labels uniquely identifying a node instead of integer node indices. For example:import tempfile import retworkx from retworkx.visualization import mpl_draw with tempfile.NamedTemporaryFile("wt") as fd: fd.write('a b first_edge\n') fd.write('b c second_edge\n') fd.flush() graph = retworkx.PyDiGraph.read_edge_list(fd.name, labels=True) mpl_draw(graph, with_labels=True, labels=str, edge_labels=str)

The

`adjacency_matrix()`

function has a new kwarg`null_value`

which is used to adjust the value used in the output matrix representing the absence of an edge. This can be set to any float value and if not specified the default value of 0.0 is still used. For example:import numpy as np import retworkx graph = retworkx.generators.cycle_graph(4) distance_matrix = retworkx.adjacency_matrix(graph, null_value=np.inf) print(distance_matrix)

[[inf 1. inf 1.] [ 1. inf 1. inf] [inf 1. inf 1.] [ 1. inf 1. inf]]

The

`distance_matrix()`

function has a new kwarg`null_value`

which is used to adjust the value used in the output matrix representing the absence of a path. This can be set to any float value and if not specified the default value of 0.0 is still used. For example:import numpy as np import retworkx graph = retworkx.generators.cycle_graph(4) graph.add_node(None) graph.add_node(None) distance_matrix = retworkx.distance_matrix(graph, null_value=np.inf) print(distance_matrix)

[[ 0. 1. 2. 1. inf inf] [ 1. 0. 1. 2. inf inf] [ 2. 1. 0. 1. inf inf] [ 1. 2. 1. 0. inf inf] [inf inf inf inf 0. inf] [inf inf inf inf inf 0.]]

A new method,

`substitute_node_with_subgraph()`

, to the`PyDiGraph`

class. This method is used to replace a node in a`PyDiGraph`

object with another`PyDiGraph`

object. For example, first creating a new graph:import retworkx from retworkx.visualization import mpl_draw original_graph = retworkx.generators.directed_path_graph(5) mpl_draw(original_graph, with_labels=True)

then create another graph to use in place of a node:

other_graph = retworkx.generators.directed_star_graph(25) mpl_draw(other_graph)

finally replace a node in the original graph with the second graph:

def edge_map_fn(_source, _target, _weight): return 0 node_mapping = original_graph.substitute_node_with_subgraph(2, other_graph, edge_map_fn) print(node_mapping) mpl_draw(original_graph, with_labels=True)

NodeMap{0: 5, 1: 6, 2: 7, 3: 8, 4: 9, 5: 10, 6: 11, 7: 12, 8: 13, 9: 14, 10: 15, 11: 16, 12: 17, 13: 18, 14: 19, 15: 20, 16: 21, 17: 22, 18: 23, 19: 24, 20: 25, 21: 26, 22: 27, 23: 28, 24: 29}

Added a new method,

`to_directed()`

, to the`PyGraph`

class. This method is used to generate a new`retworkx.PyDiGraph`

directed graph object from an undirected`PyGraph`

object. The output`retworkx.PyDiGraph`

object will have a bidirectional edge pair for each edge in the original`PyGraph`

object.

Added a new kwarg,

`null_value`

to the`retworkx.PyDiGraph.from_adjacency_matrix()`

and`retworkx.PyGraph.from_adjacency_matrix()`

which is used to optionally change the null value in the matrix treated as the absence of an edge. By default`0.0`

is used. For example:import numpy as np import retworkx from retworkx.visualization import mpl_draw matrix = np.array([[np.nan, 1, 1], [1, np.nan, 1], [1, 1, 0]], dtype=np.float64) graph = retworkx.PyDiGraph.from_adjacency_matrix(matrix, null_value=np.nan) mpl_draw(graph, with_labels=True, edge_labels=str)

The

`floyd_warshall()`

function has been completely reworked and now works with a`PyGraph`

object in addition to the`PyDiGraph`

objects already supported. It has a new kwarg`weight_fn`

which is used to support custom edge weighting, and also now executes in parallel.

Added two new functions,

`graph_floyd_warshall()`

and`digraph_floyd_warshall()`

, which are typed versions of the existing`floyd_warshall()`

.

Two new kwargs,

`multigraph`

and`weight_combo_fn`

, were added to`retworkx.PyDiGraph.to_undirected()`

method. These two options can be used to condense parallel edges into a single edge in the output graph. By setting`multigraph`

to`True`

any parallel edges will be condensed into a single edge in the output`PyGraph`

. The`weight_combo_fn`

kwarg is used to control how the parallel edges are condensed. If it’s not specified the weight/data payload of the edge with the largest edge index will be used. If`weight_combo_fn`

is specified it will be passed the weight objects for any parallel edges in the graph and the returned object will be used as the weight for the condensed edge. For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.PyDiGraph() graph.extend_from_weighted_edge_list([ (0, 1, 25), (1, 0, 10), (1, 2, 10), (2, 1, 100), (2, 3, 50), (3, 2, 40), ]) undirected_graph = graph.to_undirected( multigraph=False, weight_combo_fn=max ) mpl_draw(undirected_graph, with_labels=True, edge_labels=str)

A new kwarg,

`induced`

, was added to`is_subgraph_isomorphic()`

. If set to`True`

the function will check if the second graph is isomorphic to a node-induced subgraph of the first. If set to`False`

it will check if the second graph is isomorphic to a subgraph of the first. By default this is set to`True`

.

Added a new function,

`num_shortest_paths_unweighted()`

(and it’s per type variants`digraph_num_shortest_paths_unweighted()`

and`graph_num_shortest_paths_unweighted()`

), which is used to get a count of unweighted shortest paths from a given node to all other nodes (where path exists) in the graph.

Added a new method,

`has_parallel_edges()`

, to the`PyDiGraph`

and`PyGraph`

(`has_parallel_edges()`

) classes. This method returns`True`

if there are parallel edges in the graph and`False`

otherwise.

Added a new function,

`metric_closure()`

, which is used to generate the metric closure of a given graph. This function is used in the computation for calculating the Steiner Tree using the algorithm from Kou, Markowsky & Berman (1981). “A fast algorithm for Steiner trees”. https://link.springer.com/article/10.1007/BF00288961

Added a new function,

`steiner_tree()`

, which is used to generate an approximation of the minimum Steiner tree using the algorithm from: Kou, Markowsky & Berman (1981). “A fast algorithm for Steiner trees”. https://link.springer.com/article/10.1007/BF00288961

Added a new function,

`retworkx.vf2_mapping()`

, which will use the vf2 isomorphism algorithm (which is also used for`retworkx.is_isomorphic()`

and`retworkx.is_subgraph_isomorphic()`

) to return an iterator over all valid isomorphic mappings between two graphs. For example:import retworkx graph = retworkx.generators.directed_grid_graph(10, 10) other_graph = retworkx.generators.directed_grid_graph(4, 4) vf2 = retworkx.vf2_mapping(graph, other_graph, subgraph=True) try: mapping = next(vf2) print(mapping) except StopIteration: pass

NodeMap{0: 0, 1: 1, 2: 2, 3: 3, 10: 4, 11: 5, 12: 6, 13: 7, 20: 8, 21: 9, 22: 10, 23: 11, 30: 12, 31: 13, 32: 14, 33: 15}

Added a new kwarg,

`call_limit`

to`retworkx.is_isomorphic()`

and`retworkx.is_subgraph_isomorphic()`

which is used to set an upper bound on the number of states that VF2 algorithm visits while searching for a solution. If it exceeds this limit, the algorithm will stop and return false.

Added a new kwarg,

`weight_fn`

, to the`retworkx.dag_longest_path()`

and`retworkx.dag_longest_path_length()`

functions. These kwargs are used to set a weight function callable that will be called as the function traverses the graph to dynamically adjust the weight of an edge. For example:import retwork as rx dag = rx.PyDiGraph() dag.extend_from_weighted_edge_list( [ (0, 1, 1), (0, 3, 1), (3, 4, 1), (4, 5, 1), (1, 2, 1), (0, 1, 3), ] ) longest_path = rx.dag_longest_path(dag, lambda _, __, weight: weight) path_length = rx.dag_longest_path_length(dag, lambda_, __, weight: weight) assert [0, 1, 2] == longest_path assert 4 == weight

### Upgrade Notes¶

The

`floyd_warshall()`

function no longer returns a`dict`

and instead will return a`retworkx.AllPairsPathLengthMapping`

object. This new return type is much faster to build and it implements the Python mapping protocol in a read-only fashion. This change should mostly be compatible unless explicit type checking or mutating the output was done.

### Bug Fixes¶

Support for negative weights in the

`retworkx.PyDiGraph.from_adjacency_matrix()`

and`retworkx.PyGraph.from_adjacency_matrix()`

methods has been fixed. Previously, if a negative weight were used it would be incorrectly treated as a null value and no edge was added to the graph. This has been corrected so that a negative value in the input matrix is now treated as an edge with a negative weight. For example:import numpy as np import retworkx from retworkx.visualization import mpl_draw matrix = np.array([[0, -1, -1], [1, 0, -1], [1, 1, 0]], dtype=np.float64) graph = retworkx.PyDiGraph.from_adjacency_matrix(matrix) mpl_draw(graph, with_labels=True, edge_labels=str)

Fixed #408

Fixed an issue with the Dijkstra path functions:

where the returned paths could be incorrect in cases where there were multiple paths between nodes and an edge weight callback function was specified. Fixed #387

Fixes the output of

`number_weakly_connected_components()`

in case of holes in the graph node indices.

Previously, the graphs created by

`retworkx.generators.directed_hexagonal_lattice_graph()`

and`retworkx.generators.hexagonal_lattice_graph()`

contained holes in the node indices. This has been fixed by generating graphs with consecutive node indexes. Fixed #373

The iteration order of the output

`dict`

returned by`graph_greedy_color()`

was previously not deterministic and multiple executions with the same input would return identical dictionaries that had different insertion orders which would result in different iteration order. This has been fixed so that the iteration order of the output dictionary is now deterministic. Fixed #347

## 0.9.0¶

### Prelude¶

This release is a new feature release that includes a plethora of new
features and bug fixes. The highlights of this release are the introduction
of the `retwork.visualization`

module, which includes a
matplotlib based drawer
(`mpl_draw()`

) and a
graphviz based drawer
(`graphviz_draw()`

), and layout functions such
as `spring_layout()`

for generating a layout in
visualization. Additionally, the generator functions in
`retworkx.generators`

have been expanded to include new graph
generators, and many new algorithm functions have been added.

### New Features¶

Added new generator functions,

`retworkx.generators.binomial_tree_graph()`

and`retworkx.generators.directed_binomial_tree_graph()`

, for constructing a binomial tree graph. For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.binomial_tree_graph(4) mpl_draw(graph)

import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.directed_binomial_tree_graph(4) mpl_draw(graph)

A new method,

`copy()`

, has been added to the`PyDiGraph`

and`PyGraph`

(`copy()`

) classes. This method will return a shallow copy of a graph object.

Add a new function,

`core_number()`

for computing the core number of each node in a`PyGraph`

or a`PyDiGraph`

, where for directed graphs the degrees are calculated as in_degree + out_degree.

Added a new method,

`edge_indices()`

, to the`PyDiGraph`

and`PyGraph`

(`edge_indices()`

) that will return a list of edge indices for every edge in the graph object.

Added a new custom return type

`EdgeIndices`

which is returned by`retworkx.PyDiGraph.edge_indices`

and`retworkx.PyGraph.edge_indices`

. It is equivalent to a read-only list of integers that represent a list of edge indices.

Added a new method,

`num_nodes()`

, to the`PyDiGraph`

and`PyGraph`

(`num_nodes()`

) for returning the number of nodes in the graph.

Added a new method,

`num_edges()`

, to the`PyDiGraph`

and`PyGraph`

(`num_edges()`

) for returning the number of edges in the graph.

A new function

`retworkx.networkx_converter()`

has been added. This function takes in a networkx`Graph`

object and will generate an equivalent`PyGraph`

or`PyDiGraph`

object. While this function is provided as a convience for users of both retworkx and networkx, networkx will**not**be added as a dependency of retworkx (which precludes a retworkx->networkx converter, see Converting from a networkx graph for example code on how to build this yourself).

Added new function

`random_geometric_graph()`

which can be used to generate random geometric graphs. For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.random_geometric_graph(8, .95, 5) mpl_draw(graph)

Added a new layout function,

`retworkx.random_layout()`

(and it’s equivalent per type variants`retworkx.graph_random_layout()`

and`retworkx.diraph_random_layout()`

) to generate a random layout which can be used for visualizations. For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.directed_grid_graph(5, 5) layout = retworkx.random_layout(graph) mpl_draw(graph, pos=layout)

or with the

`graphviz_draw()`

function:import retworkx from retworkx.visualization import graphviz_draw graph = retworkx.generators.directed_grid_graph(5, 5) layout = retworkx.random_layout(graph) for i in range(25): graph[i] = i def node_attr_fn(node): point = layout[node] return { "shape": "circle", "pos": '"%s,%s!"' % (point[0], point[1]), "fillcolor": "yellow", "style": "filled", "fixedsize": "true" } graphviz_draw(graph, node_attr_fn=node_attr_fn, method='fdp')

A new custom return class,

`retworkx.Pos2DMapping`

, has been added. This class will be returned by layout functions and is a drop in replacement for an immutable read-only dictionary of the form:{1: [0.1, 0.5]}

where the keys are node indices and the values are a 2 element sequence that represents the position for the node.

Added a new function,

`is_subgraph_isomorphic()`

, to determine if two graphs of the same type (either`PyGraph`

or`PyDiGraph`

) are induced subgraph isomorphic.

A new function,

`transitivity()`

, was added to calculate the transitivity coefficient of a`PyGraph`

or a`PyDiGraph`

object.

Added a new function

`complement()`

to calculate the graph complement of a`PyGraph`

or`PyDiGraph`

.

Two new return types

`PathMapping`

and`PathLengthMapping`

. These classes are returned from functions that previously returned a dictionary of paths or a dictionary of path lengths. They both implement the Python mapping protocol and can be used inplace as a read-only dict.

New functions have been added to compute the shortest path and shortest path lengths for all nodes in a graph object:

Added a new method,

`edge_index_map()`

, to the`PyDiGraph`

and`PyGraph`

(`edge_index_map()`

) that will return a read-only mapping of edge indices to a tuple of the form`(source_node_index, target_node_index, weight/data payload)`

for every edge in the graph object.

Added a new custom return type

`EdgeIndexMap`

which is returned by`retworkx.PyDiGraph.edge_index_map()`

and`retworkx.PyGraph.edge_index_map()`

. It is equivalent to a read-only dict/mapping that represent a mapping of edge indices to the edge tuple.

The

`is_isomorphic()`

function has been expanded so it can now also take in a`PyGraph`

in addition to the the`PyDiGraph`

already supported.

The

`is_isomorphic()`

function now has two new optional kwargs`node_matcher`

and`edge_matcher`

which can be used to specify functions to use for comparing node and edge data payloads.

The

`is_isomorphic_node_match()`

function has been expanded so it can take in a`PyGraph`

in addition to the`PyDiGraph`

it already supported.

Added new generator functions,

`retworkx.generators.directed_hexagonal_lattice_graph()`

and`retworkx.generators.hexagonal_lattice_graph()`

, for constructing a hexagonal lattice graph. For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.directed_hexagonal_lattice_graph(3, 3) mpl_draw(graph)

import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.hexagonal_lattice_graph(3, 3) mpl_draw(graph)

Added two new methods,

`find_successors_by_edge()`

and`find_predecessors_by_edge()`

, to`PyDiGraph`

. These methods efficiently retrieve the neighbors in the graph which are connected to a node with edges matching a filter function.

The

`is_isomorphic()`

and`is_isomorphic_node_match()`

functions have a new kwarg,`id_order`

which is used to adjust the node matching order used. If you set`id_order=False`

then the matching order used is the heuristic matching order proposed in the VF2++ paper. If you want to retain use the order based on node ids, you can set`id_order=True`

which is the default behavior.

Added new function,

`minimum_spanning_tree()`

, to calculate the minimum spanning tree of a`PyGraph`

object and return the MST as a new`PyGraph`

object.

Added a new function,

`minimum_spanning_edges()`

, to calculate the minimum spanning tree of a`PyGraph`

object and return the`WeightedEdgeList`

for the weighted edge list of the MST of a graph.

A new module,

`retworkx.visualization`

has been added. This module will contain various functions used for visualizing retworkx graphs.

A new visualization function,

`retworkx.visualization.mpl_drawer()`

, for visualizing graphs with Matplotlib has been added. This function requires that matplotlib, which is not a dependency of retworkx, to be installed. To install matplotlib you can either use`pip install matplotlib`

or when you install retworkx`pip install 'retworkx[mpl]'`

. This function can take any retworkx graph object, a`PyGraph`

or`PyDiGraph`

and visualize them with various options to tweak the output. For example, a basic graph without any labels is:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.grid_graph(4, 6) mpl_draw(graph)

or to change the colors:

import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.grid_graph(4, 6) mpl_draw(graph, node_color='r', edge_color='#00FFFF')

Refer to the function documentation for a full list of options.

A new kwarg,

`multigraph`

was added to the`PyDiGraph`

generator functions:This can be used to set whether the generated

`PyDiGraph`

objects are multi graphs or not (to set whether parallel edges can be added or not). By default this is set to`True`

.

Added a new Graphviz based drawer function,

`graphviz_draw()`

, to the`retworkx.visualization`

module. This function requires that Graphviz is installed locally and adds two new optional dependencies, pydot which is used to call Graphviz and Pillow to interact with the generated image files. The optional dependencies can be installed either with`pip install pydot pillow` or when installing retworkx with ``pip install 'retworkx[graphviz]'`

. This function wraps the`to_dot()`

method to generate a dot representation of the graph and will call Graphviz to generate a visualization of the graph. For example:import retworkx from retworkx.visualization import graphviz_draw def node_attr(node): if node == 0: return {'color': 'yellow', 'fillcolor': 'yellow', 'style': 'filled'} if node % 2: return {'color': 'blue', 'fillcolor': 'blue', 'style': 'filled'} else: return {'color': 'red', 'fillcolor': 'red', 'style': 'filled'} graph = retworkx.generators.directed_star_graph(weights=list(range(32))) graphviz_draw(graph, node_attr_fn=node_attr, method='sfdp')

Four simple layout functions were added:

These can be used to adjust the layout used in visualizations, for example:

import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.path_graph(weights=list(range(24))) layout = retworkx.bipartite_layout(graph, set(range(12))) mpl_draw(graph, pos=layout)

import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.path_graph(weights=list(range(24))) layout = retworkx.circular_layout(graph) mpl_draw(graph, pos=layout)

import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.star_graph(25) layout = retworkx.shell_layout(graph) mpl_draw(graph, pos=layout)

import retworkx from retworkx.visualization import mpl_draw graph = retworkx.generators.path_graph(weights=list(range(24))) layout = retworkx.spiral_layout(graph) mpl_draw(graph, pos=layout)

Or with the

`graphviz_drawer()`

function:import retworkx from retworkx.visualization import graphviz_draw graph = retworkx.generators.path_graph(weights=list(range(24))) layout = retworkx.spiral_layout(graph) def node_attr_fn(node): point = layout[node] return { "shape": "circle", "pos": '"%s,%s!"' % (point[0], point[1]), "fillcolor": "yellow", "style": "filled", } graphviz_draw(graph, node_attr_fn=node_attr_fn, method='fdp')

Added a new function,

`spring_layout()`

to generate layouts for`PyGraph`

and`PyDiGraph`

using the Fruchterman-Reingold force-directed algorithm. This layout method is used by default for the`mpl_drawer()`

visualization function. You can also explicitly use it when calling`mpl_drawer()`

and`graphviz_drawer()`

. For example:import retworkx from retworkx.visualization import mpl_draw graph = retworkx.random_geometric_graph(15, 1.42) layout = retworkx.spring_layout(graph, adaptive_cooling=False) mpl_draw(graph, pos=layout)

and with the graphviz drawer:

import retworkx from retworkx.visualization import graphviz_draw graph = retworkx.random_geometric_graph(15, 1.42) layout = retworkx.spring_layout(graph, adaptive_cooling=False) for i in range(15): graph[i] = i def node_attr_fn(node): point = layout[node] return { "shape": "circle", "pos": '"%s,%s!"' % (point[0], point[1]), "fillcolor": "yellow", "style": "filled", "fixedsize": "true" } graphviz_draw(graph, node_attr_fn=node_attr_fn, method='fdp')

A new method,

`write_edge_list()`

, has been added to the`PyDiGraph`

and`PyGraph`

(`write_edge_list()`

) classes. This method is used to write an edge list file representing the graph object. The output format is such that it can be used as an input to`retworkx.PyDiGraph.read_edge_list()`

and`retworkx.PyGraph.read_edge_list()`

.

### Upgrade Notes¶

The functions:

no longer are returning a

`dict`

and instead are returning`retworkx.PathLengthMapping`

objects. This new return type is much faster to build and it implements the python mapping protocol in a read-only fashion and should not be noticeable unless explicit type checking or mutating the result were done.

The functions:

no longer are returning a

`dict`

and instead are returning`retworkx.PathMapping`

objects. This new return type is much faster to build and it implements the python mapping protocol in a read-only fashion and should not be noticeable unless explicit type checking or mutating the result were done.

### Bug Fixes¶

Fixed an issue where calling

`retworkx.PyDiGraph.successor_indices()`

or`retworkx.PyDiGraph.predecessor_indices()`

would raise a`RuntimeError`

exception if they were called in a context where retworkx is already working with a reference to a`PyDiGraph`

(primarily if it were called in a callback function for another`PyDiGraph`

method).

Fix bug in

`floyd_warshall_numpy()`

in which the dispatcher mistakenly called`adjacency_matrix()`

instead of`graph_floyd_warshall_numpy()`

and`digraph_floyd_warshall_numpy()`

.

## 0.8.0¶

### Prelude¶

This release includes several new features and bug fixes. The main features for this release are some usability improvements including the introduction of new methods for interacting with edges, constructing graphs from adjacency matrices, and universal functions that are not strictly typed and will work with either a `PyGraph`

or `PyDiGraph`

object. It also includes new algorithm functions around matchings for a `PyGraph`

, including a function to find the maximum weight matching.
This is also the first release to include support and publishing of precompiled binaries for Apple Arm CPUs on MacOS.

### New Features¶

A new constructor method

`from_adjacency_matrix()`

has been added to the`PyDiGraph`

and`PyGraph`

(`from_adjacency_matrix()`

) classes. It enables creating a new graph from an input adjacency_matrix. For example:import os import tempfile import numpy as np import pydot from PIL import Image import retworkx # Adjacency matrix for directed outward star graph: adjacency_matrix = np.array([ [0., 1., 1., 1., 1.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.]]) # Create a graph from the adjacency_matrix: graph = retworkx.PyDiGraph.from_adjacency_matrix(adjacency_matrix) # Draw graph dot_str = graph.to_dot( lambda node: dict( color='black', fillcolor='lightblue', style='filled')) dot = pydot.graph_from_dot_data(dot_str)[0] with tempfile.TemporaryDirectory() as tmpdirname: tmp_path = os.path.join(tmpdirname, 'dag.png') dot.write_png(tmp_path) image = Image.open(tmp_path) os.remove(tmp_path) image

A new algorithm function,

`is_matching()`

, was added to check if a matching set is valid for given`PyGraph`

object.

A new algorithm function,

`is_maxmimal_matching()`

, was added to check if a matching set is valid and maximal for a given`PyGraph`

object.

Add a new function,

`max_weight_matching()`

for computing the maximum-weighted matching for a`PyGraph`

object.

The

`PyGraph`

and`PyDiGraph`

constructors now have a new kwarg`multigraph`

which can optionally be set to`False`

to disallow adding parallel edges to the graph. With`multigraph=False`

if an edge is attempted to be added where one already exists it will update the weight for the edge with the new value. For example:import os import tempfile import pydot from PIL import Image import retworkx as rx graph = rx.PyGraph(multigraph=False) graph.extend_from_weighted_edge_list([(0, 1, -1), (1, 2, 0), (2, 0, 1)]) dot = pydot.graph_from_dot_data( graph.to_dot(edge_attr=lambda e:{'label': str(e)}))[0] with tempfile.TemporaryDirectory() as tmpdirname: tmp_path = os.path.join(tmpdirname, 'dag.png') dot.write_png(tmp_path) image = Image.open(tmp_path) os.remove(tmp_path) image

Then trying to add an edge between

`0`

and`1`

again will update its weight/payload.graph.add_edge(0, 1, 42) dot = pydot.graph_from_dot_data( graph.to_dot(edge_attr=lambda e:{'label': str(e)}))[0] with tempfile.TemporaryDirectory() as tmpdirname: tmp_path = os.path.join(tmpdirname, 'dag.png') dot.write_png(tmp_path) image = Image.open(tmp_path) os.remove(tmp_path) image

You can query whether a PyGraph allows multigraphs with the boolean attribute

`multigraph`

. The attribute can not be set outside of the constructor.

The

`retworkx.generators`

module’s functions`cycle_graph()`

,`path_graph()`

,`star_graph()`

,`mesh_graph()`

, and`grid_graph()`

now have a new kwarg`multigraph`

which takes a boolean and defaults to`True`

. When it is set to`False`

the generated`PyGraph`

object will have the`multigraph`

attribute set to`False`

meaning it will disallow adding parallel edges.

New universal functions that can take in a

`PyGraph`

or`PyDiGraph`

instead of being class specific have been to the retworkx API. These new functions are:

Starting with this release wheels will be published for macOS arm64. Only Python 3.9 is supported at first, because it is the only version of Python with native support for arm64 macOS.

The custom return types

`BFSSuccessors`

,`NodeIndices`

,`EdgeList`

, and`WeightedEdgeList`

now implement`__str__`

so that running`str()`

(for example when calling`print()`

on the object) it will return a human readable string with the contents of the custom return type.

The custom return types

`BFSSuccessors`

,`NodeIndices`

,`EdgeList`

, and`WeightedEdgeList`

now implement`__hash__`

so that running`hash()`

(for example when insert them into a`dict`

) will return a valid hash for the object. The only exception to this is for`BFSSuccessors`

and`WeightedEdgeList`

if they contain a Python object that is not hashable, in those cases calling`hash()`

will raise a`TypeError`

, just like as you called`hash()`

on the inner unhashable object.

Two new methods,

`update_edge()`

and`update_edge_by_index()`

were added to the`retworkx.PyDiGraph`

and`retworkx.PyGraph`

(`update_edge()`

and`update_edge_by_index()`

) classes. These methods are used to update the data payload/weight of an edge in the graph either by the nodes of an edge or by edge index.

### Upgrade Notes¶

The minimum supported Rust version has increased to 1.41.1, you will need rustc >=1.41.1 now to build retworkx. The previous minimum supported Rust version 1.39.0 will no longer be able to compile retworkx. This is due to a changes in in the new versions of the pyo3 and rust-numpy libraries.

### Bug Fixes¶

In previous releases the Python garbage collector did not know how to interact with

`PyDiGraph`

or`PyGraph`

objects and as a result they may never have been freed until Python exited. To fix this issue, the`PyDiGraph`

and`PyGraph`

classes now are integrated with Python’s garbage collector so they’ll properly be cleared when there are no more references to a graph object.

The output from

`retworkx.PyDiGraph.neighbors()`

and`retworkx.PyGraph.neighbors()`

methods will no longer include duplicate entries in case of parallel edges between nodes. See #250 for more details.

In previous releases the Python garbage collector did not know how to interact with the custom return types

`BFSSuccessors`

,`NodeIndices`

,`EdgeList`

, and`WeightedEdgeList`

and as a result they may never have been freed until Python exited. To fix this issue the custom return type classes now are integrated with Python’s garbage collector so they’ll properly be cleared when there are no more Python references to an object.

## 0.7.2¶

### Bug Fixes¶

Fixed a potential segfault that could occur when calling

`is_directed_acyclic_graph()`

with a a very deep`PyDiGraph`

object as reported in Qiskit/qiskit-terra#5502.

## 0.7.1¶

This release includes a fix for an oversight in the previous 0.7.0 and
0.6.0 releases. Those releases both added custom return types
`BFSSuccessors`

, `NodeIndices`

,
`EdgeList`

, and `WeightedEdgeList`

that
implemented the Python sequence protocol which were used in place of
lists for certain functions and methods. However, none of those classes
had support for being pickled, which was causing compatibility issues
for users that were using the return in a context where it would be
pickled (for example as an argument to or return of a function called
with multiprocessing). This release has a single change over 0.7.0 which
is to add the missing support for pickling `BFSSuccessors`

,
`NodeIndices`

, `EdgeList`

, and
`WeightedEdgeList`

which fixes that issue.

## 0.7.0¶

This release includes several new features and bug fixes.

This release also dropped support for Python 3.5. If you want to use retworkx with Python 3.5 that last version which supports Python 3.5 is 0.6.0.

### New Features¶

New generator functions for two new generator types, mesh and grid were added to

`retworkx.generators`

for generating all to all and grid graphs respectively. These functions are:`mesh_graph()`

,`directed_mesh_graph()`

,`grid_graph()`

, and`directed_grid_graph()`

A new function,

`retworkx.digraph_union()`

, for taking the union between two`PyDiGraph`

objects has been added.A new

`PyDiGraph`

method`merge_nodes()`

has been added. This method can be used to merge 2 nodes in a graph if they have the same weight/data payload.A new

`PyDiGraph`

method`find_node_by_weight()`

which can be used to lookup a node index by a given weight/data payload.A new return type

`NodeIndices`

has been added. This class is returned by functions and methods that return a list of node indices. It implements the Python sequence protocol and can be used as list.Two new return types

`EdgeList`

and`WeightedEdgeList`

. These classes are returned from functions and methods that return a list of edge tuples and a list of edge tuples with weights. They both implement the Python sequence protocol and can be used as a listA new function

`collect_runs()`

has been added. This function is used to find linear paths of nodes that match a given condition.

### Upgrade Notes¶

Support for running retworkx on Python 3.5 has been dropped. The last release with support for Python 3.5 is 0.6.0.

The

`retworkx.PyDiGraph.node_indexes()`

,`retworkx.PyDiGraph.neighbors()`

,`retworkx.PyDiGraph.successor_indices()`

,`retworkx.PyDiGraph.predecessor_indices()`

,`retworkx.PyDiGraph.add_nodes_from()`

,`retworkx.PyGraph.node_indexes()`

,`retworkx.PyGraph.add_nodes_from()`

, and`retworkx.PyGraph.neighbors()`

methods and the`dag_longest_path()`

,`topological_sort()`

,`graph_astar_shortest_path()`

, and`digraph_astar_shortest_path()`

functions now return a`NodeIndices`

object instead of a list of integers. This should not require any changes unless explicit type checking for a list was used.The

`retworkx.PyDiGraph.edge_list()`

, and`retworkx.PyGraph.edge_list()`

methods and`digraph_dfs_edges()`

,`graph_dfs_edges()`

, and`digraph_find_cycle()`

functions now return an`EdgeList`

object instead of a list of integers. This should not require any changes unless explicit type checking for a list was used.The

`retworkx.PyDiGraph.weighted_edge_list()`

,`retworkx.PyDiGraph.in_edges()`

,`retworkx.PyDiGraph.out_edges()`

, and retworkx.PyGraph.weighted_edge_list methods now return a`WeightedEdgeList`

object instead of a list of integers. This should not require any changes unless explicit type checking for a list was used.

### Fixes¶

`BFSSuccessors`

objects now can be compared with`==`

and`!=`

to any other Python sequence type.The built and published sdist packages for retworkx were previously not including the Cargo.lock file. This meant that the reproducible build versions of the rust dependencies were not passed through to source. This has been fixed so building from sdist will always use known working versions that we use for testing in CI.

## 0.6.0¶

This release includes a number of new features and bug fixes. The main focus of this release was to expand the retworkx API functionality to include some commonly needed functions that were missing.

This release is also the first release to provide full support for running with Python 3.9. On previous releases Python 3.9 would likely work, but it would require building retworkx from source. Also this will likely be the final release that supports Python 3.5.

### New Features¶

Two new functions,

`digraph_k_shortest_path_lengths()`

and`graph_k_shortest_path_lengths()`

, for finding the k shortest path lengths from a node in a`PyDiGraph`

and`PyGraph`

.A new method,

`is_symmetric()`

, to the`PyDiGraph`

class. This method will check whether the graph is symmetric or notA new kwarg,

`as_undirected`

, was added to the`digraph_floyd_warshall_numpy()`

function. This can be used to treat the input`PyDiGraph`

object as if it was undirected for the generated output matrix.A new function,

`digraph_find_cycle()`

, which will return the first cycle during a depth first search of a`PyDiGraph`

object.Two new functions,

`directed_gnm_random_graph()`

and`undirected_gnm_random_graph()`

, for generating random \(G(n, m)\) graphs.A new method,

`remove_edges_from()`

, was added to`PyDiGraph`

and`PyGraph`

(`removed_edges_from()`

). This can be used to remove multiple edges from a graph object in a single call.A new method,

`subgraph()`

, was added to`PyDiGraph`

and`PyGraph`

(`subgraph()`

) which takes in a list of node indices and will return a new object of the same type representing a subgraph containing the node indices in that list.Support for running with Python 3.9

A new method,

`to_undirected()`

, was added to`PyDiGraph`

. This method will generate an undirected`PyGraph`

object from the`PyDiGraph`

object.A new kwarg,

`bidirectional`

, was added to the directed generator functions`directed_cycle_graph()`

,`directed_path_graph()`

, and`directed_star_graph()`

. When set to`True`

the directed graphs generated by these functions will add edges in both directions.Added two new functions,

`is_weakly_connected()`

and`weakly_connected_components()`

, which will either check if a`PyDiGraph`

object is weakly connected or return the list of the weakly connected components of an input`PyDiGraph`

.The

`weight_fn`

kwarg for`graph_adjacency_matrix()`

,`digraph_adjacency_matrix()`

,`graph_floyd_warshall_numpy()`

, and`digraph_floyd_warshall_numpy()`

is now optional. Previously, it always had to be specified when calling these function. But, instead you can now rely on a default weight float (which defaults to`1.0`

) to be used for all the edges in the graph.Add a

`neighbors()`

method to`PyGraph`

and`PyDiGraph`

(`neighbors()`

). This function will return the node indices of the neighbor nodes for a given input node.Two new methods,

`successor_indices()`

and`predecessor_indices()`

, were added to`PyDiGraph`

. These methods will return the node indices for the successor and predecessor nodes of a given input node.Two new functions,

`graph_distance_matrix()`

and`digraph_distance_matrix()`

, were added for generating a distance matrix from an input`PyGraph`

and`PyDiGraph`

.Two new functions,

`digraph_dijkstra_shortest_paths()`

and`graph_dijkstra_shortest_path()`

, were added for returning the shortest paths from a node in a`PyDiGraph`

and a`PyGraph`

object.Four new methods,

`insert_node_on_in_edges()`

,`insert_node_on_out_edges()`

,`insert_node_on_in_edges_multiple()`

, and`insert_node_on_out_edges_multiple()`

were added to`PyDiGraph`

. These functions are used to insert an existing node in between an reference node(s) and all it’s predecessors or successors.Two new functions,

`graph_dfs_edges()`

and`digraph_dfs_edges()`

, were added to get an edge list in depth first order from a`PyGraph`

and`PyDiGraph`

.

### Upgrade Notes¶

The numpy arrays returned by

`graph_floyd_warshall_numpy()`

,`digraph_floyd_warshall_numpy()`

,`digraph_adjacency_matrix()`

, and`graph_adjacency_matrix()`

will now be in a contiguous C array memory layout. Previously, they would return arrays in a column-major fortran layout. This was change was made to make it easier to interface the arrays returned by these functions with other C Python extensions. There should be no change when interacting with the numpy arrays via numpy’s API.The

`bfs_successors()`

method now returns an object of a custom type`BFSSuccessors`

instead of a list. The`BFSSuccessors`

type implements the Python sequence protocol so it can be used in place like a list (except for where explicit type checking is used). This was done to defer the type conversion between Rust and Python since doing it all at once can be a performance bottleneck especially for large graphs. The`BFSSuccessors`

class will only do the type conversion when an element is accessed.

### Fixes¶

When pickling

`PyDiGraph`

objects the original node indices will be preserved across the pickle.The random \(G(n, p)\) functions,

`directed_gnp_random_graph()`

and`undirected_gnp_random_graph()`

, will now also handle exact 0 or 1 probabilities. Previously it would fail in these cases. Fixes #172

## 0.5.0¶

This release include a number of new features and bug fixes. The main focus of the improvements of this release was to increase the ease of interacting with graph objects. This includes adding support for generating dot output which can be used with graphviz (or similar tools) for visualizing graphs adding more methods to query the state of graph, adding a generator module for easily creating graphs of certain shape, and implementing the mapping protocol so you can directly interact with graph objects.

### New Features¶

A new method,

`to_dot()`

, was added to`PyGraph`

and`PyDiGraph`

(`to_dot()`

). It will generate a dot format representation of the object which can be used with Graphivz (or similar tooling) to generate visualizations of graphs.Added a new function,

`strongly_connected_components()`

, to get the list of strongly connected components of a`PyDiGraph`

object.A new method,

`compose()`

, for composing another graph object of the same type into a graph was added to`PyGraph`

and`PyDiGraph`

(`compose()`

).The

`PyGraph`

and`PyDigraph`

classes now implement the Python mapping protocol for interacting with graph nodes. You can now access and interact with node data directly by using standard map access patterns in Python. For example, accessing a graph like`graph[1]`

will return the weight/data payload for the node at index 1.A new module,

`retworkx.generators`

, has been added. Functions in this module can be used for quickly generating graphs of certain shape. To start it includes:A new method,

`remove_node_retain_edges()`

, has been added to the`PyDiGraph`

class. This method can be used to remove a node and add edges from its predecesors to its successors.Two new methods,

`edge_list()`

and`weighted_edge_list()`

, for getting a list of tuples with the edge source and target (with or without edge weights) have been added to`PyGraph`

and`PyDiGraph`

(`edge_list()`

and`weighted_edge_list()`

)A new function,

`cycle_basis()`

, for getting a list of cycles which form a basis for cycles of a`PyGraph`

object.Two new functions,

`graph_floyd_warshall_numpy()`

and`digraph_floyd_warshall_numpy()`

, were added for running the Floyd Warshall algorithm and returning all the shortest path lengths as a distance matrix.A new constructor method,

`read_edge_list()`

, has been added to`PyGraph`

and`PyDigraph`

(`read_edge_list()`

). This method will take in a path to an edge list file and will read that file and generate a new object from the contents.Two new methods,

`extend_from_edge_list()`

and`extend_from_weighted_edge_list()`

has been added to`PyGraph`

and`PyDiGraph`

(`extend_from_edge_list()`

and`extend_from_weighted_edge_list()`

). This method takes in an edge list and will add both the edges and nodes (if a node index used doesn’t exist yet) in the list to the graph.

### Fixes¶

The limitation with the

`is_isomorphic()`

and`is_isomorphic_node_match()`

functions that would cause segfaults when comparing graphs with node removals has been fixed. You can now run either function with any`PyDiGraph`

/`PyDAG`

objects, even if there are node removals. Fixes #27If an invalid node index was passed as part of the

`first_layer`

argument to the`layers()`

function it would previously raise a`PanicException`

that included a Rust backtrace and no other user actionable details which was caused by an unhandled error. This has been fixed so that an`IndexError`

is raised and the problematic node index is included in the exception message.

## 0.4.0¶

This release includes many new features and fixes, including improved performance and better documentation. But, the biggest change for this release is that this is the first release of retworkx that supports compilation with a stable released version of rust. This was made possible thanks to all the hard work of the PyO3 maintainers and contributors in the PyO3 0.11.0 release.

### New Features¶

A new class for undirected graphs,

`PyGraph`

, was added.2 new functions

`graph_adjacency_matrix()`

and`digraph_adjacency_matrix()`

to get the adjacency matrix of a`PyGraph`

and`PyDiGraph`

object.A new

`PyDiGraph`

method,`find_adjacent_node_by_edge()`

, was added. This is used to locate an adjacent node given a condition based on the edge between them.New methods,

`add_nodes_from()`

,`add_edges_from()`

,`add_edges_from_no_data()`

, and`remove_nodes_from()`

were added to`PyDiGraph`

. These methods allow for the addition (and removal) of multiple nodes or edges from a graph in a single call.A new function,

`graph_greedy_color()`

, which is used to return a coloring map from a`PyGraph`

object.2 new functions,

`graph_astar_shortest_path()`

and`digraph_astar_shortest_path()`

, to find the shortest path from a node to a specified goal using the A* search algorithm.2 new functions,

`graph_all_simple_paths()`

and`digraph_all_simple_paths()`

, to return a list of all the simple paths between 2 nodes in a`PyGraph`

or a`PyDiGraph`

object.2 new functions,

`directed_gnp_random_graph()`

and`undirected_gnp_random_graph()`

, to generate \(G_{np}\) random`PyDiGraph`

and`PyGraph`

objects.2 new functions,

`graph_dijkstra_shortest_path_lengths()`

and`digraph_dijkstra_shortest_path_lengths()`

, were added for find the shortest path length between nodes in`PyGraph`

or`PyDiGraph`

object using Dijkstra’s algorithm.

### Upgrade Notes¶

The

`PyDAG`

class was renamed`PyDiGraph`

to better reflect it’s functionality. For backwards compatibility`PyDAG`

still exists as a Python subclass of`PyDiGraph`

. No changes should be required for existing users.numpy is now a dependency of retworkx. This is used for the adjacency matrix functions to return numpy arrays. The minimum version of numpy supported is 1.16.0.

### Fixes¶

The retworkx exception classes are now properly exported from the retworkx module. In prior releases it was not possible to import the exception classes (normally to catch one being raised) requiring users to catch the base Exception class. This has been fixed so a specialized retworkx exception class can be used.