Release Notes¶
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 thePyDiGraph
andPyGraph
(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 givenPyGraph
object.
A new algorithm function,
is_maxmimal_matching()
, was added to check if a matching set is valid and maximal for a givenPyGraph
object.
Add a new function,
max_weight_matching()
for computing the maximum-weighted matching for aPyGraph
object.
The
PyGraph
andPyDiGraph
constructors now have a new kwargmultigraph
which can optionally be set toFalse
to disallow adding parallel edges to the graph. Withmultigraph=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
and1
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 functionscycle_graph()
,path_graph()
,star_graph()
,mesh_graph()
, andgrid_graph()
now have a new kwargmultigraph
which takes a boolean and defaults toTrue
. When it is set toFalse
the generatedPyGraph
object will have themultigraph
attribute set toFalse
meaning it will disallow adding parallel edges.
New Universal Functions that can take in a
PyGraph
orPyDiGraph
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
, andWeightedEdgeList
now implement__str__
so that runningstr()
(for example when callingprint()
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
, andWeightedEdgeList
now implement__hash__
so that runninghash()
(for example when insert them into adict
) will return a valid hash for the object. The only exception to this is forBFSSuccessors
andWeightedEdgeList
if they contain a Python object that is not hashable, in those cases callinghash()
will raise aTypeError
, just like as you calledhash()
on the inner unhashable object.
Two new methods,
update_edge()
andupdate_edge_by_index()
were added to theretworkx.PyDiGraph
andretworkx.PyGraph
(update_edge()
andupdate_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.
Bug Fixes¶
In previous releases the Python garbage collector did not know how to interact with
PyDiGraph
orPyGraph
objects and as a result they may never have been freed until Python exited. To fix this issue, thePyDiGraph
andPyGraph
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()
andretworkx.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
, andWeightedEdgeList
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 deepPyDiGraph
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()
, anddirected_grid_graph()
A new function,
retworkx.digraph_union()
, for taking the union between twoPyDiGraph
objects has been added.A new
PyDiGraph
methodmerge_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
methodfind_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
andWeightedEdgeList
. 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()
, andretworkx.PyGraph.neighbors()
methods and thedag_longest_path()
,topological_sort()
,graph_astar_shortest_path()
, anddigraph_astar_shortest_path()
functions now return aNodeIndices
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()
, andretworkx.PyGraph.edge_list()
methods anddigraph_dfs_edges()
,graph_dfs_edges()
, anddigraph_find_cycle()
functions now return anEdgeList
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 aWeightedEdgeList
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()
andgraph_k_shortest_path_lengths()
, for finding the k shortest path lengths from a node in aPyDiGraph
andPyGraph
.A new method,
is_symmetric()
, to thePyDiGraph
class. This method will check whether the graph is symmetric or notA new kwarg,
as_undirected
, was added to thedigraph_floyd_warshall_numpy()
function. This can be used to treat the inputPyDiGraph
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 aPyDiGraph
object.Two new functions,
directed_gnm_random_graph()
andundirected_gnm_random_graph()
, for generating random \(G(n, m)\) graphs.A new method,
remove_edges_from()
, was added toPyDiGraph
andPyGraph
(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 toPyDiGraph
andPyGraph
(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 toPyDiGraph
. This method will generate an undirectedPyGraph
object from thePyDiGraph
object.A new kwarg,
bidirectional
, was added to the directed generator functionsdirected_cycle_graph()
,directed_path_graph()
, anddirected_star_graph()
. When set toTrue
the directed graphs generated by these functions will add edges in both directions.Added two new functions,
is_weakly_connected()
andweakly_connected_components()
, which will either check if aPyDiGraph
object is weakly connected or return the list of the weakly connected components of an inputPyDiGraph
.The
weight_fn
kwarg forgraph_adjacency_matrix()
,digraph_adjacency_matrix()
,graph_floyd_warshall_numpy()
, anddigraph_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 to1.0
) to be used for all the edges in the graph.Add a
neighbors()
method toPyGraph
andPyDiGraph
(neighbors()
). This function will return the node indices of the neighbor nodes for a given input node.Two new methods,
successor_indices()
andpredecessor_indices()
, were added toPyDiGraph
. These methods will return the node indices for the successor and predecessor nodes of a given input node.Two new functions,
graph_distance_matrix()
anddigraph_distance_matrix()
, were added for generating a distance matrix from an inputPyGraph
andPyDiGraph
.Two new functions,
digraph_dijkstra_shortest_paths()
andgraph_dijkstra_shortest_path()
, were added for returning the shortest paths from a node in aPyDiGraph
and aPyGraph
object.Four new methods,
insert_node_on_in_edges()
,insert_node_on_out_edges()
,insert_node_on_in_edges_multiple()
, andinsert_node_on_out_edges_multiple()
were added toPyDiGraph
. 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()
anddigraph_dfs_edges()
, were added to get an edge list in depth first order from aPyGraph
andPyDiGraph
.
Upgrade Notes¶
The numpy arrays returned by
graph_floyd_warshall_numpy()
,digraph_floyd_warshall_numpy()
,digraph_adjacency_matrix()
, andgraph_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 typeBFSSuccessors
instead of a list. TheBFSSuccessors
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. TheBFSSuccessors
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()
andundirected_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 toPyGraph
andPyDiGraph
(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 aPyDiGraph
object.A new method,
compose()
, for composing another graph object of the same type into a graph was added toPyGraph
andPyDiGraph
(compose()
).The
PyGraph
andPyDigraph
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 likegraph[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 thePyDiGraph
class. This method can be used to remove a node and add edges from its predecesors to its successors.Two new methods,
edge_list()
andweighted_edge_list()
, for getting a list of tuples with the edge source and target (with or without edge weights) have been added toPyGraph
andPyDiGraph
(edge_list()
andweighted_edge_list()
)A new function,
cycle_basis()
, for getting a list of cycles which form a basis for cycles of aPyGraph
object.Two new functions,
graph_floyd_warshall_numpy()
anddigraph_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 toPyGraph
andPyDigraph
(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()
andextend_from_weighted_edge_list()
has been added toPyGraph
andPyDiGraph
(extend_from_edge_list()
andextend_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()
andis_isomorphic_node_match()
functions that would cause segfaults when comparing graphs with node removals has been fixed. You can now run either function with anyPyDiGraph
/PyDAG
objects, even if there are node removals. Fixes #27If an invalid node index was passed as part of the
first_layer
argument to thelayers()
function it would previously raise aPanicException
that included a Rust backtrace and no other user actionable details which was caused by an unhandled error. This has been fixed so that anIndexError
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()
anddigraph_adjacency_matrix()
to get the adjacency matrix of aPyGraph
andPyDiGraph
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()
, andremove_nodes_from()
were added toPyDiGraph
. 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 aPyGraph
object.2 new functions,
graph_astar_shortest_path()
anddigraph_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()
anddigraph_all_simple_paths()
, to return a list of all the simple paths between 2 nodes in aPyGraph
or aPyDiGraph
object.2 new functions,
directed_gnp_random_graph()
andundirected_gnp_random_graph()
, to generate \(G_{np}\) randomPyDiGraph
andPyGraph
objects.2 new functions,
graph_dijkstra_shortest_path_lengths()
anddigraph_dijkstra_shortest_path_lengths()
, were added for find the shortest path length between nodes inPyGraph
orPyDiGraph
object using Dijkstra’s algorithm.
Upgrade Notes¶
The
PyDAG
class was renamedPyDiGraph
to better reflect it’s functionality. For backwards compatibilityPyDAG
still exists as a Python subclass ofPyDiGraph
. 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.