Release Notes#

0.13.1-1#

Prelude#

rustworkx 0.13.2 is a minor release, adding support for Python 3.12. Existing users of 0.13.1 should not be affected by this release, but are still encouraged to upgraded.

0.13.1#

Prelude#

rustworkx 0.13.1 is a bugfix release, addressing some issues identified since the 0.13.0 release.

Known Issues#

  • The type hint stub files included in this release (and 0.13.0) are not compatible with Python 3.7’s type hinting syntax. If you are now using mypy to partially validate the typing in your usage of rustworkx, you should not run this with Python 3.7 as it will not function correctly. The actual rustworkx code will continue to function as expected with Python 3.7 for the 0.13.x release series, it was just the typing syntax used in the stubs files which are incompatible with Python 3.7.

Upgrade Notes#

  • Support for the Linux s390x platform has changed from tier 3 to tier 4 (as documented in Platform Support). This is a result of no longer being able to run tests during the pre-compiled wheel publishing jobs due to constraints in the available CI infrastructure. There hopefully shouldn’t be any meaningful impact resulting from this change, but as there are no longer tests being run to validate the binaries prior to publishing them there are no longer guarantees that the wheels for s390x are fully functional (although the likelihood they are is still high as it works on other platforms). If any issues are encountered with s390x Linux please open an issue.

Bug Fixes#

  • Fixed a potential source of non-determinism in the output of the token_swapper() function in rustworkx-core along with its matching function in the Python rustworkx package: graph_token_swapper().

  • Fixed the rustworkx-core dependencies to loosen the constraints on the version of hashbrown and indexmap used. Previously, they were fixed to the latest version which was compatible with rustworkx’s MSRV. This has been updated so a range of versions can be used, which will enable users that don’t have as restrictive of an MSRV to use newer versions of these libraries with rustworkx-core.

0.13.0#

Prelude#

This release is major feature release of Rustworkx that adds some new features to the library. The highlights of this release are:

  • An expansion of the functions exposed by rustworkx-core to including a new graph generator module.

  • New link analysis functions such as page rank

  • Expanded centrality measure functions

  • Added partial type annotations to the library including for the PyDiGraph and PyGraph classes. This enables type checking with mypy

This is also the final rustworkx release that supports running with Python 3.7. Starting in the 0.14.0 release Python >= 3.8 will be required to use rustworkx. This release also increased the minimum suported Rust version for compiling rustworkx and rustworkx-core from source to 1.56.1.

New Features#

  • Added a new method, make_symmetric(), to the PyDiGraph class. This method is used to make all the edges in the graph symmetric (there is a reverse edge in the graph for each edge). For example:

    import rustworkx as rx
from rustworkx.visualization import graphviz_draw

graph = rx.generators.directed_path_graph(5, bidirectional=False)
graph.make_symmetric()
graphviz_draw(graph)
    _images/release_notes_0_0.png

  • Added a new function, edge_betweenness_centrality() to compute edge betweenness centrality of all edges in a PyGraph or PyDiGraph object. The algorithm used in this function is based on: Ulrik Brandes, On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2):136-145, 2008. Edge betweenness centrality of an edge \(e\) is the sum of the fraction of all-pairs shortest paths that pass through \(e\)

    \[c_B(e) =\sum_{s,t \in V} \frac{\sigma(s, t|e)}{\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|e)\) is the number of those paths passing through edge \(e\). For example, the following computes the edge betweenness centrality for all edges in a 5x5 grid graph and uses the result to color the edges in a graph visualization:

    import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.grid_graph(5, 5)
btw = rustworkx.edge_betweenness_centrality(graph)
# Color edges in graph visualization with edge betweenness centrality
colors = []
for i in graph.edge_indices():
    colors.append(btw[i])
mpl_draw(graph, edge_color=colors)
    _images/release_notes_1_0.png

  • Added a new function to rustworkx-core edge_betweenness_centrality to the rustworkx_core:centrality module which computes the edge betweenness centrality of all edges in a given graph.

  • Two new functions, find_cycle and cycle_basis, have been added to the rustworkx-core crate in the connectivity module. These functions can be used to find a cycle in a petgraph graph or to find the cycle basis of a graph.

  • Added a new function, hits() which is used to compute the hubs and authorities for all nodes in a given directed graph. For example:

    import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.directed_hexagonal_lattice_graph(2, 2)
hubs, _ = rx.hits(graph)

# Generate a color list
colors = []
for node in graph.node_indices():
    hub_score = hubs[node]
    graph[node] = hub_score
    colors.append(hub_score)
mpl_draw(
    graph,
    with_labels=True,
    node_color=colors,
    node_size=650,
    labels=lambda x: "{0:.2f}".format(x)
)
    _images/release_notes_2_0.png

  • Added a new function, katz_centrality() which is used to compute the Katz centrality for all nodes in a given graph. For example:

    import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.hexagonal_lattice_graph(4, 4)
centrality = rx.katz_centrality(graph)

# Generate a color list
colors = []
for node in graph.node_indices():
    centrality_score = centrality[node]
    graph[node] = centrality_score
    colors.append(centrality_score)
mpl_draw(
    graph,
    with_labels=True,
    node_color=colors,
    node_size=650,
    labels=lambda x: "{0:.2f}".format(x)
)
    _images/release_notes_3_0.png

  • Added a new function to rustworkx-core katz_centrality to the rustworkx_core::centrality modules which is used to compute the Katz centrality for all nodes in a given graph.

  • Added a new function, longest_simple_path() which is used to search all the simple paths between all pairs of nodes in a graph and return the longest path found. For example:

    import rustworkx as rx

graph = rx.generators.binomial_tree_graph(5)
longest_path = rx.longest_simple_path(graph)
print(longest_path)

    NodeIndices[31, 30, 28, 24, 16, 0, 8, 12, 14, 15]

    Then visualizing the nodes in the longest path found:

    from rustworkx.visualization import mpl_draw

path_set = set(longest_path)
colors = []
for index in range(len(graph)):
    if index in path_set:
      colors.append('r')
    else:
      colors.append('#1f78b4')
mpl_draw(graph, node_color=colors)
    _images/release_notes_5_0.png

  • Added a new function longest_simple_path_multiple_targets() to rustworkx-core. This function will return the longest simple path from a source node to a HashSet of target nodes.

  • Added a new function, pagerank() which is used to compute the PageRank score for all nodes in a given directed graph. For example:

    import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.directed_hexagonal_lattice_graph(2, 2)
ranks = rx.pagerank(graph)

# Generate a color list
colors = []
for node in graph.node_indices():
    pagerank_score = ranks[node]
    graph[node] = pagerank_score
    colors.append(pagerank_score)
mpl_draw(
    graph,
    with_labels=True,
    node_color=colors,
    node_size=650,
    labels=lambda x: "{0:.2f}".format(x)
)
    _images/release_notes_6_0.png

  • Three new random graph generators, gnp_random_graph, gnm_random_graph and random_geometric_graph, have been added to the rustworkx-core crate in the generators module. The gnp_random_graph takes inputs of the number of nodes and a probability for adding edges. The gnp_random_graph takes inputs of the number of nodes and number of edges. The random_geometric_graph creates a random graph within an n-dimensional cube.

  • Added a new function, bfs_predecessors(), which is used to return a list of predecessors in a reversed bread-first traversal from a specified node. This is analogous to the existing bfs_successors() method.

  • Add a method find_predecessor_node_by_edge() to get the immediate predecessor of a node which is connected by the specified edge.

  • Added a new function, graph_token_swapper(), which performs an approximately optimal token swapping algorithm based on:

    Approximation and Hardness for Token Swapping by Miltzow et al. (2016) https://arxiv.org/abs/1602.05150

    that supports partial mappings (i.e. not-permutations) for graphs with missing tokens.

  • Added a new function token_swapper() to the new rustworkx-core module rustworkx_core::token_swapper. This function performs an approximately optimal token swapping algorithm based on:

    Approximation and Hardness for Token Swapping by Miltzow et al. (2016) https://arxiv.org/abs/1602.05150

    that supports partial mappings (i.e. not-permutations) for graphs with missing tokens.

  • Added a new function, closeness_centrality() to compute the closeness centrality of all nodes in a PyGraph or PyDiGraph object.

    The closeness centrality of a node \(u\) is defined as the the reciprocal of the average shortest path distance to \(u\) over all \(n-1\) reachable nodes. In it’s general form this can be expressed as:

    \[C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},\]

    where \(d(v, u)\) is the shortest-path distance between \(v\) and \(u\), and \(n\) is the number of nodes that can reach \(u\). For example, to visualize the closeness centrality of a graph:

    import matplotlib.pyplot as plt

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.hexagonal_lattice_graph(4, 4)
centrality = rx.closeness_centrality(graph)
# Generate a color list
colors = []
for node in graph.node_indices():
    colors.append(centrality[node])
# Generate a visualization with a colorbar
plt.rcParams['figure.figsize'] = [15, 10]
ax = plt.gca()
sm = plt.cm.ScalarMappable(norm=plt.Normalize(
    vmin=min(centrality.values()),
    vmax=max(centrality.values())
))
plt.colorbar(sm, ax=ax)
plt.title("Closeness Centrality of a 4 x 4 Hexagonal Lattice Graph")
mpl_draw(graph, node_color=colors, ax=ax)
    _images/release_notes_7_0.png

  • Added new generator functions, empty_graph(), and directed_empty_graph() to the rustworkx.generators module that will generate an empty graph. For example:

    import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.empty_graph(4)
mpl_draw(graph)
    _images/release_notes_8_0.png

  • Added new generator functions, complete_graph(), and directed_complete_graph() to the rustworkx.generators module that will generate a complete graph. These functions are equivalent to calling the mesh_graph() and directed_mesh_graph() functions. For example:

    import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.complete_graph(4)
mpl_draw(graph)
    _images/release_notes_9_0.png

  • Added a new generators module to the rustworkx-core crate. This module contains functions for generating graphs. These functions are generic on the output graph type and can be used to create graph objects for any type that implement the required petgraph traits.

  • Added partial type annotations to the library, including for the PyDiGraph and PyGraph classes. This enables statically type checking with mypy.

  • Added a new function, greedy_node_color, to rustworkx-core in a new coloring module. It colors a graph using a greedy graph coloring algorithm.

  • The function core_number has been added to the rustworkx-core crate in the connectivity module. It computes the k-core number for the nodes in a graph.

Upgrade Notes#

  • Passing a negative value to the probability argument to the gnp_directed_random_graph() or the gnp_undirected_random_graph() function will now cause an OverflowError to be raised. Previously, a ValueError would be raised in this situation. This was changed to be consistent with other similar error conditions in other functions in the library.

  • The minimum supported Rust version has been increased from 1.48 to 1.56.1. This applies to both building the rustworkx package from source as well as the rustworkx-core crate. This change was made to facilitate using newer versions of our upstream dependencies as well as leveraging newer Rust language features.

Bug Fixes#

  • Fixed the check_cycle attribute not being preserved when copying PyDiGraph with copy.copy() and copy.deepcopy(). Fixed #836

  • Fixed an issue when using copy.deepcopy() on PyDiGraph and PyGraph objects when there were removed edges from the graph object. Previously, if there were any holes in the edge indices caused by the removal the output copy of the graph object would incorrectly have flatten the indices. This has been corrected so that the edge indices are recreated exactly after a deepcopy(). Fixed #585

  • Fixed a compatibility issue when building rustworkx-core with priority-queue 1.3.0. Fixed #744

  • Fixed an issue with several PyDiGraph and PyGraph methods that removed nodes where previously when calling these methods the PyDiGraph.node_removed attribute would not be updated to reflect that nodes were removed.

0.12.0#

Prelude#

This release introduces some major changes to the Rustworkx (formerly retworkx) project. The first change is the library has been renamed from retworkx to rustworkx, and the retworkx-core rust crate has been renamed rustworkx-core. This was done out of respect for a request from the maintainers of the NetworkX library. For the current release the retworkx library will still continue to work as it has without any notification, but starting in the 0.13.0 release a DeprecationWarning will be emitted when importing from retworkx and in the 1.0.0 release we will drop support for the legacy name. For the retworkx-core crate, there will no longer be any releases under that name on crates.io and all future versions of the library will be released as rustworkx-core.

Additionally this release adds support for Python 3.11 and also moves to manylinux2014 for all precompiled Linux binaries we publish to PyPI. The minimum supported Rust version for building rustworkx from source has increased to Rust 1.48.

This release also includes several new features, some highlights are:

  • Support for graph attributes under the attrs attribute

  • New serialization format support (a graphml parser, read_graphml(), and a node link JSON generator, node_link_json())

  • New algorithms functions including:

    • Eigenvector Centrality

    • Stoer–Wagner Min-Cut algorithm

    • Bellman-Ford shortest path algorithm

New Features#

  • Added a new function, eigenvector_centrality() which is used to compute the eigenvector centrality for all nodes in a given graph. For example:

    import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.hexagonal_lattice_graph(4, 4)
centrality = rx.eigenvector_centrality(graph)

# Generate a color list
colors = []
for node in graph.node_indices():
    centrality_score = centrality[node]
    graph[node] = centrality_score
    colors.append(centrality_score)
mpl_draw(
    graph,
    with_labels=True,
    node_color=colors,
    node_size=650,
    labels=lambda x: "{0:.2f}".format(x)
)
    _images/release_notes_10_0.png

  • Added a new function to rustworkx-core eigenvector_centrality to the rustworkx_core::centrality modules which is used to compute the eigenvector centrality for all nodes in a given graph.

  • Added a new keyword arguments, index_output, to the layers() function. When set to True the output of the function is a list of layers as node indices. The default output is still a list of layers of node data payloads as before.

  • Added a new function, node_link_json(), which is used to generate JSON node-link data representation of an input PyGraph or PyDiGraph object. For example, running:

    import retworkx

graph = retworkx.generators.path_graph(weights=['a', 'b', 'c'])
print(retworkx.node_link_json(graph, node_attrs=lambda n: {'label': n}))

    will output a JSON payload equivalent (identical except for whitespace) to:

    {
  "directed": false,
  "multigraph": true,
  "attrs": null,
  "nodes": [
    {
      "id": 0,
      "data": {
        "label": "a"
      }
    },
    {
      "id": 1,
      "data": {
        "label": "b"
      }
    },
    {
      "id": 2,
      "data": {
        "label": "c"
      }
    }
  ],
  "links": [
    {
      "source": 0,
      "target": 1,
      "id": 0,
      "data": null
    },
    {
      "source": 1,
      "target": 2,
      "id": 1,
      "data": null
    }
  ]
}

  • Added a new algorithm function, rustworkx.stoer_wagner_min_cut() that uses the Stoer Wagner algorithm for computing a weighted minimum cut in an undirected PyGraph. For example:

    import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.grid_graph(2, 2)
cut_val, partition = rustworkx.stoer_wagner_min_cut(graph)

colors = [
    'orange' if node in partition else 'blue' for node in graph.node_indexes()
]
mpl_draw(graph, node_color=colors)
    _images/release_notes_11_0.png

  • Add two new functions which calculates the tensor product of two graphs graph_tensor_product() for undirected graphs and digraph_tensor_product() for directed graphs. For example:

    import rustworkx
from rustworkx.visualization import mpl_draw
graph_1 = rustworkx.generators.path_graph(2)
graph_2 = rustworkx.generators.path_graph(3)
graph_product, _ = rustworkx.graph_tensor_product(graph_1, graph_2)

mpl_draw(graph_product)
    _images/release_notes_12_0.png

  • Added a new function all_pairs_all_simple_paths() which is used to return all simple paths between all pairs of nodes in a graph. It can also be used with a optional min_depth and cutoff parameters to filter the results based on path lengths. For example:

    from rustworkx.generators import grid_graph
from rustworkx import all_pairs_all_simple_paths

g = grid_graph(2, 3)
paths = all_pairs_all_simple_paths(g, min_depth=3, cutoff=3)

    will return a dictionary of dictionaries where the 2 dictionary keys are the node indices and the inner value is the list of all simple paths of length 3 between those 2 nodes.

  • The rustworkx-core rustworkx_core::connectivity module has a new function all_simple_paths_multiple_targets this is similar to the all_simple_paths() method in petgraph’s algo module but instead of returning an iterator that will yield the all the simple path from a source to the target node it instead will build a DictMap of all the simple paths from a source node to all targets in a provided HashSet of target node indices.

  • Added a concept of graph attributes to the PyDiGraph and PyGraph classes. The attributes are accessible via the attrs attribute of the graph objects and can be modified in place. Additionally, they can be set initially when creating the object via the constructor. For example:

    import rustworkx as rx

graph = rx.PyGraph(attrs=dict(day="Friday"))
graph.attrs['day'] = "Monday"

    The attributes can contain any Python object, not just a dictionary. For example:

    class Day:

    def __init__(self, day):
        self.day = day

graph = rx.PyGraph(attrs=Day("Friday"))
graph.attrs = Day("Monday")

    If attrs is not set it will default to None.

  • The PyGraph.subgraph() and PyDiGraph.subgraph() methods have a new keyword argument preserve_attributes which can be set to True to copy by reference the contents of the attrs attribute from the graph to the subgraph’s attrs attribute.

  • Implements a new function is_planar() that checks whether an undirected PyGraph is planar.

    import rustworkx as rx

graph = rx.generators.mesh_graph(5)
print('Is K_5 graph planar?', rx.is_planar(graph))

    Is K_5 graph planar? False

  • The rustworkx-core connectivity module has 3 new functions, connected_components, number_connected_components, and bfs_undirected. These functions are based on the existing connected_components(), number_connected_components(), and bfs_undirected() in rustworkx.

  • Added a new function read_graphml() that generates a rustworkx graph object (a PyGraph or a PyDiGraph) from a file written in GraphML format. GraphML is an xml serialization format for representing graph files.

Upgrade Notes#

  • The return type for the PyGraph method add_edges_from() and add_edges_from_no_data() has changed from a list of integer edge indices to an EdgeIndices object. The EdgeIndices class is a read-only sequence type of integer edge indices. For the most part this should be fully compatible except if you were mutating the output list or were explicitly type checking the return. In these cases you can simply cast the EdgeIndices object with list().

  • This release no longer provides binaries that support the manylinux2010 packaging specification. All the precompiled binaries for Linux platforms are built against manylinux2014. This change is required due to changes in the GLIBC versions supported by the latest versions of the Rust compiler in addition to the manylinux2010 platform no longer being supported. If you need to run Rustworkx on a platform only compatible with manylinux2010 starting with this release you will need to build and install from source (which includes the sdist published to PyPI, so pip install rustworkx will continue to work assuming you have a Rust compiler installed) and also use a Rust compiler with a version < 1.64.0.

  • The minimum supported Rust version for building rustworkx has been raised from 1.41 to 1.48. To compile rustworkx from source you will need to ensure you have at Rustc >=1.48 installed.

  • The minimum supported Python version for using rustworkx has been raised to Python 3.7. To use rustworkx you will need to ensure you are using Python >=3.7.

  • The retworkx package has been renamed to rustworkx. This was done out of respect for a request from the maintainers of the NetworkX library. For the time being the retworkx name will continue to work, however any package requirements or imports using retworkx should be renamed to rustworkx.

Bug Fixes#

  • The custom sequence return classes:

    now correctly handle slice inputs to __getitem__. Previously if you tried to access a slice from one of these objects it would raise a TypeError. For example, if you had a NodeIndices object named nodes containing [0, 1, 3, 4, 5] if you did something like:

    nodes[0:3]

    it would return a new NodeIndices object containing [0, 1, 3] Fixed #590

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 rustworkx-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 rustworkx 0.12.0, Python >=3.7 will be required to run rustworkx. Additionally, for users compiling rustworkx from source, this will be the last release with a minimum supported Rust version (MSRV) of 1.41. In rustworkx 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 rustworkx
from rustworkx.visualization import mpl_draw

graph_1 = rustworkx.generators.path_graph(2)
graph_2 = rustworkx.generators.path_graph(3)

graph_product, _ = rustworkx.cartesian_product(graph_1, graph_2)

mpl_draw(graph_product)
    _images/release_notes_14_0.png

  • 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 rustworkx. 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 rustworkx.generators module that will generate a barbell graph. For example:

    import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.barbell_graph(4, 3)
mpl_draw(graph)
    _images/release_notes_15_0.png

  • 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 rustworkx
from rustworkx.visit import BFSVisitor


class TreeEdgesRecorder(BFSVisitor):

    def __init__(self):
        self.edges = []

    def tree_edge(self, edge):
        self.edges.append(edge)

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([(1, 3), (0, 1), (2, 1), (0, 2)])
vis = TreeEdgesRecorder()
rustworkx.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 rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([
    (0, 1), (1, 2), (0, 2), (1, 3)
])
points = rustworkx.articulation_points(graph)

colors = ['black'] * len(graph)
for node in points:
    colors[node] = 'blue'

mpl_draw(graph, node_color=colors)
    _images/release_notes_17_0.png

  • 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 rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([
    (0, 1), (1, 2), (0, 2), (1, 3), (2, 4)
])
components = rustworkx.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)
    _images/release_notes_18_0.png

  • 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 rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([
    (0, 1), (0, 2), (1, 2), (2, 3),
    (3, 4), (3, 5), (4, 5),
])
chains = rustworkx.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))
    _images/release_notes_19_0.png

  • Added new constructor methods rustworkx.PyDiGraph.from_complex_adjacency_matrix() and rustworkx.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 rustworkx
from rustworkx.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 = rustworkx.PyDiGraph.from_complex_adjacency_matrix(adj_matrix)

mpl_draw(graph, with_labels=True, edge_labels=str)
    _images/release_notes_20_0.png

  • Added new graph methods rustworkx.PyDiGraph.contract_nodes(), and rustworkx.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. rustworkx.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 rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.directed_path_graph(5)
mpl_draw(graph, with_labels=True)
    _images/release_notes_21_0.png

    perform the contraction:

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

  • 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 rustworkx
from rustworkx.visit import DFSVisitor

class TreeEdgesRecorder(DFSVisitor):

    def __init__(self):
        self.edges = []

    def tree_edge(self, edge):
        self.edges.append(edge)

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([(1, 3), (0, 1), (2, 1), (0, 2)])
vis = TreeEdgesRecorder()
rustworkx.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 rustworkx
from rustworkx.visit import DijkstraVisitor


class DijkstraTreeEdgesRecorder(rustworkx.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 = rustworkx.PyGraph()
graph.extend_from_weighted_edge_list([(1, 3, 1), (0, 1, 10), (2, 1, 1), (0, 2, 1)])
vis = DijkstraTreeEdgesRecorder()
rustworkx.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 rustworkx
graph = rustworkx.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)}

  • 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 rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.full_rary_tree(3, 5)
mpl_draw(graph)
    _images/release_notes_26_0.png

  • Added a new function, lollipop_graph() that adds support for generating lollipop graphs. For example:

    import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.lollipop_graph(4, 3)
mpl_draw(graph)
    _images/release_notes_27_0.png

  • 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 rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.generalized_petersen_graph(5, 2)
layout = rustworkx.shell_layout(graph, nlist=[[0, 1, 2, 3, 4], [6, 7, 8, 9, 5]])
mpl_draw(graph, pos=layout)
    _images/release_notes_28_0.png

  • Added a new workspace crate, rustworkx-core as part of rustworkx. This is a standalone Rust library that is built on top of petgraph that provides general algorithms and graph functionality that rustworkx 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 rustworkx exposes, but without Python.

    It’s also worth noting as this is the first release of rustworkx-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 rustworkx, 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 rustworkx 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 rustworkx 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 rustworkx API like:

    import rustworkx

graph = rustworkx.undirected_gnm_random_graph(20, 10, seed=42)
n = len(graph)
d_mat = rustworkx.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 rustworkx[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 rustworkx.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 rustworkx.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 issue with the heavy_hex_graph(), directed_heavy_hex_graph(), heavy_square_graph(), and directed_heavy_square_graph() generator functions. When the input parameter d was set to 1 these functions would previously raise a pyo3_runtime.PanicException instead of returning the expected graph (a single node). Fixed #452

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 rustworkx
from rustworkx.visualization import mpl_draw

first = rustworkx.generators.path_graph(3, weights=["a_0", "node", "a_1"])
second = rustworkx.generators.cycle_graph(3, weights=["node", "b_0", "b_1"])
graph = rustworkx.graph_union(first, second, merge_nodes=True)
mpl_draw(graph)
    _images/release_notes_29_0.png

  • 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

  • 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 rustworkx.PyDiGraph.substitute_node_with_subgraph() for replacing a node with a subgraph.

New Features#

  • Added a new algorithm function, rustworkx.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 rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.grid_graph(5, 5)
btw = rustworkx.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)
    _images/release_notes_30_0.png

  • A new kwarg, labels, has been added to the rustworkx.PyDiGraph.read_edge_list() and rustworkx.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 rustworkx
from rustworkx.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 = rustworkx.PyDiGraph.read_edge_list(fd.name, labels=True)

mpl_draw(graph, with_labels=True, labels=str, edge_labels=str)
    _images/release_notes_33_0.png

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

graph = rustworkx.generators.cycle_graph(4)
distance_matrix = rustworkx.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 rustworkx

graph = rustworkx.generators.cycle_graph(4)
graph.add_node(None)
graph.add_node(None)
distance_matrix = rustworkx.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 rustworkx
from rustworkx.visualization import mpl_draw

original_graph = rustworkx.generators.directed_path_graph(5)
mpl_draw(original_graph, with_labels=True)
    _images/release_notes_36_0.png

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

    other_graph = rustworkx.generators.directed_star_graph(25)
mpl_draw(other_graph)
    _images/release_notes_37_0.png

    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}
    _images/release_notes_38_1.png

  • Added a new kwarg, null_value to the rustworkx.PyDiGraph.from_adjacency_matrix() and rustworkx.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 rustworkx
from rustworkx.visualization import mpl_draw

matrix = np.array([[np.nan, 1, 1], [1, np.nan, 1], [1, 1, 0]], dtype=np.float64)
graph = rustworkx.PyDiGraph.from_adjacency_matrix(matrix, null_value=np.nan)
mpl_draw(graph, with_labels=True, edge_labels=str)
    _images/release_notes_39_0.png

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

  • Two new kwargs, multigraph and weight_combo_fn, were added to rustworkx.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 rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.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)
    _images/release_notes_40_0.png

  • 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, rustworkx.vf2_mapping(), which will use the vf2 isomorphism algorithm (which is also used for rustworkx.is_isomorphic() and rustworkx.is_subgraph_isomorphic()) to return an iterator over all valid isomorphic mappings between two graphs. For example:

    import rustworkx

graph = rustworkx.generators.directed_grid_graph(10, 10)
other_graph = rustworkx.generators.directed_grid_graph(4, 4)
vf2 = rustworkx.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 rustworkx.dag_longest_path() and rustworkx.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 rustworkx.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 rustworkx.PyDiGraph.from_adjacency_matrix() and rustworkx.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 rustworkx
from rustworkx.visualization import mpl_draw

matrix = np.array([[0, -1, -1], [1, 0, -1], [1, 1, 0]], dtype=np.float64)
graph = rustworkx.PyDiGraph.from_adjacency_matrix(matrix)
mpl_draw(graph, with_labels=True, edge_labels=str)
    _images/release_notes_42_0.png

    Fixed #408

  • 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 rustworkx.generators have been expanded to include new graph generators, and many new algorithm functions have been added.

New Features#

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

  • A new function rustworkx.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 rustworkx and networkx, networkx will not be added as a dependency of rustworkx (which precludes a rustworkx->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 rustworkx
from rustworkx.visualization import mpl_draw


graph = rustworkx.random_geometric_graph(8, .95, 5)
mpl_draw(graph)
    _images/release_notes_45_0.png

  • Added a new layout function, rustworkx.random_layout() (and it’s equivalent per type variants rustworkx.graph_random_layout() and rustworkx.diraph_random_layout()) to generate a random layout which can be used for visualizations. For example:

    import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.directed_grid_graph(5, 5)
layout = rustworkx.random_layout(graph)
mpl_draw(graph, pos=layout)
    _images/release_notes_46_0.png

    or with the graphviz_draw() function:

    import rustworkx
from rustworkx.visualization import graphviz_draw

graph = rustworkx.generators.directed_grid_graph(5, 5)
layout = rustworkx.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')
    _images/release_notes_47_0.png

  • A new custom return class, rustworkx.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.

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

  • 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, rustworkx.visualization has been added. This module will contain various functions used for visualizing rustworkx graphs.

  • A new visualization function, rustworkx.visualization.mpl_drawer(), for visualizing graphs with Matplotlib has been added. This function requires that matplotlib, which is not a dependency of rustworkx, to be installed. To install matplotlib you can either use pip install matplotlib or when you install rustworkx pip install 'rustworkx[mpl]'. This function can take any rustworkx 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 rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.grid_graph(4, 6)
mpl_draw(graph)
    _images/release_notes_50_0.png

    or to change the colors:

    import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.grid_graph(4, 6)
mpl_draw(graph, node_color='r', edge_color='#00FFFF')
    _images/release_notes_51_0.png

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

  • Added a new Graphviz based drawer function, graphviz_draw(), to the rustworkx.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 rustworkx with ``pip install 'rustworkx[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 rustworkx
from rustworkx.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 = rustworkx.generators.directed_star_graph(weights=list(range(32)))
graphviz_draw(graph, node_attr_fn=node_attr, method='sfdp')
    _images/release_notes_52_0.png

  • Four simple layout functions were added:

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

    import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.path_graph(weights=list(range(24)))
layout = rustworkx.bipartite_layout(graph, set(range(12)))
mpl_draw(graph, pos=layout)
    _images/release_notes_53_0.png 
    import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.path_graph(weights=list(range(24)))
layout = rustworkx.circular_layout(graph)
mpl_draw(graph, pos=layout)
    _images/release_notes_54_0.png 
    import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.star_graph(25)
layout = rustworkx.shell_layout(graph)
mpl_draw(graph, pos=layout)
    _images/release_notes_55_0.png 
    import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.path_graph(weights=list(range(24)))
layout = rustworkx.spiral_layout(graph)
mpl_draw(graph, pos=layout)
    _images/release_notes_56_0.png

    Or with the graphviz_drawer() function:

    import rustworkx
from rustworkx.visualization import graphviz_draw

graph = rustworkx.generators.path_graph(weights=list(range(24)))
layout = rustworkx.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')
    _images/release_notes_57_0.png

  • 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 rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.random_geometric_graph(15, 1.42)
layout = rustworkx.spring_layout(graph, adaptive_cooling=False)
mpl_draw(graph, pos=layout)
    _images/release_notes_58_0.png

    and with the graphviz drawer:

    import rustworkx
from rustworkx.visualization import graphviz_draw

graph = rustworkx.random_geometric_graph(15, 1.42)
layout = rustworkx.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')
    _images/release_notes_59_0.png

Upgrade Notes#

Bug Fixes#

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 rustworkx


# 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 = rustworkx.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
    _images/release_notes_60_0.png

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

  • 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 rustworkx 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
    _images/release_notes_61_0.png

    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
    _images/release_notes_62_0.png

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

Upgrade Notes#

  • The minimum supported Rust version has increased to 1.41.1, you will need rustc >=1.41.1 now to build rustworkx. The previous minimum supported Rust version 1.39.0 will no longer be able to compile rustworkx. 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.

  • 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.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 rustworkx 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 rustworkx.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, rustworkx.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 list

  • A new function collect_runs() has been added. This function is used to find linear paths of nodes that match a given condition.

Upgrade Notes#

Fixes#

  • BFSSuccessors objects now can be compared with == and != to any other Python sequence type.

  • The built and published sdist packages for rustworkx 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 rustworkx 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 rustworkx from source. Also this will likely be the final release that supports Python 3.5.

New Features#

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#

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#

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

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 rustworkx. This is used for the adjacency matrix functions to return numpy arrays. The minimum version of numpy supported is 1.16.0.

Fixes#

  • The rustworkx exception classes are now properly exported from the rustworkx 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 rustworkx exception class can be used.