# 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 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 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_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 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()
("A", {"color": "turquoise", "size": "extra large"}),
("B", {"color": "fuschia", "size": "tiny"}),
])
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, {})]


• 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 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.

## 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¶

• The kwargs merge_nodes and merge_edges of digraph_union() are now optional and by default are set False.

### 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

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

• 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()

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)
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)
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 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)
mpl_draw(graph, with_labels=True, edge_labels=str)

• 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, 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, 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


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

• 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 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.

• 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:

• 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() 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.

• 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)
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)
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')


• 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.

## 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:
[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:
# 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_maxmimal_matching(), was added to check if a matching set is valid and maximal for a given 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.

• 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 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.

## 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.

### 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.

## 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.

### 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 #27

• If 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.