Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

Introduction to rustworkx#

The rustworkx library is a Python library for working with graphs (or networks) and graph theory.

This guide serves as an introduction to working with rustworkx. If you’re a current or past NetworkX user who is looking at using rustworkx as a replacement for NetworkX, you can also refer to rustworkx for NetworkX users for a detailed comparison.

Installing rustworkx#

To install rustworkx you need a Python installation. Rustworkx works in any Python environment. If you already have Python, you can install rustworkx with:

pip install rustworkx

(if you’re running on a supported platform, if you’re not you will need to refer to the Installing on a platform without precompiled binaries on how to build and install)

How to import rustworkx#

To access rustworkx and its functions import it into your Python code like this:

import rustworkx as rx

We shorten the name to rx for better readability of code using Rustworkx. This is a widely adopted convention that you can follow.

Creating a Graph#

To create an empty undirected graph \(G\) with no nodes and no edges you can run the following code:

G = rx.PyGraph()

A PyGraph is comprised of nodes (vertices) and unordered pairings of nodes (called edges, links, etc). Both nodes and edges in rustworkx have an assigned data payload (also referred to as a weight in the API and documentation) which can be any Python object (e.g. a numeric value, a string, an image, an XML object, another graph, a custom node object, etc.). Nodes and edges are uniquely identified by an integer index which is stable for the lifetime of that node or edge in the graph. These indices are not guaranteed to be contiguous as removed nodes or edges will leave holes in the sequence of assigned indices, and an index can be reused after a removal.

Nodes#

The graph \(G\) can be grown in several ways. There are also graph generator functions and functions to read and write graphs in different formats.

To get started we can add a single node:

G.add_node(1)

0

The add_node() method returns an integer. This integer is the index used to uniquely identify this new node in the graph. You can use this index to identify the node as long as node remains in the graph.

It is also possible to add nodes to \(G\) from any sequence of elements such as a list or range:

indices = G.add_nodes_from(range(5))
print(indices)

NodeIndices[1, 2, 3, 4, 5]

Just as with add_node(), the add_nodes_from() method returns the indices for the nodes added as a NodeIndices object, which is a custom sequence type that contains the index of each node in the order it’s added from the input sequence.

In the above cases, we were adding nodes with a data payload of type integer (e.g. G.add_node(1)). However, rustworkx doesn’t place constraints on what the node data payload can be, so you can use more involved objects including types which are not hashable. For example, we can add a node with a data payload that’s a a dict:

G.add_node({
    "color": "green",
    "size": 42,
})

6

A discussion of how to select what to use for your data payload is in the What to use for node and edge data payload section.

Edges#

The graph \(G\) can also be grown by adding one edge at a time

G.add_edge(1, 2, None)

0

This will add an edge between node index 1 and node index 2 with a data payload of None. Similarly to add_node(), the add_edge() method returns the new edge’s unique index.

Examining elements of a graph#

We can examine the nodes and edges of a graph in rustworkx fairly easily. The first thing to do is to get a list of node and edge indices using node_indices() and edge_indices():

node_indices = G.node_indices()
edge_indices = G.edge_indices()
print(node_indices)
print(edge_indices)

NodeIndices[0, 1, 2, 3, 4, 5, 6]
EdgeIndices[0]

Since indices are the unique identifiers for nodes and edges, they’re your handle to elements in the graph. This is especially important for edges in the multigraph case, or where you have identical data payloads between multiple nodes. You can use the indices to access the data payload. For nodes, the PyGraph object behaves like a mapping with the index:

first_index_data = G[node_indices[0]]
print(first_index_data)

1

For edges, you can use the get_edge_data_by_index() method to access the data payload for a given edge and get_edge_endpoints_by_index() to get the endpoints of a given edge from its index:

first_index_data = G.get_edge_data_by_index(edge_indices[0])
first_index_edgepoints = G.get_edge_endpoints_by_index(edge_indices[0])
print(first_index_edgepoints)
print(first_index_data)

(1, 2)
None

We don’t implement the mapping protocol for edges, so there is a helper method available to get the mapping of edge indices to edge endpoints and data payloads, edge_index_map():

print(G.edge_index_map())

EdgeIndexMap{0: (1, 2, None)}

Additionally, you can access the list of node and edge data payloads directly with nodes() and edges()

print("Node data payloads")
print(G.nodes())
print("Edge data payloads")
print(G.edges())

Node data payloads
[1, 0, 1, 2, 3, 4, {'color': 'green', 'size': 42}]
Edge data payloads
[None]

Removing elements from a graph#

You can remove a node or edge from a graph in a similar manner to adding elements to the graph. There are methods remove_node(), remove_nodes_from(), remove_edge(), remove_edge_from_index(), and remove_edges_from() to remove nodes and edges from the graph. One thing to note is that removals can introduce holes in the lists of indices for nodes and edges in the graph. For example:

graph = rx.PyGraph()
graph.add_nodes_from(list(range(5)))
graph.add_nodes_from(list(range(2)))
graph.remove_node(2)
print(graph.node_indices())

NodeIndices[0, 1, 3, 4, 5, 6]

You can see here that 2 is now absent from the node indices of graph. Also, after a removal, the index of the removed node or edge will be reused on subsequent additions. For example, building off the previous example if you ran

graph.add_node("New Node")

2

this new node is assigned index 2 again.

Modifying elements of a graph#

The graph classes in rustworkx also allow for in place mutation of the payloads for elements in the graph. For nodes you can simply use the mapping protocol to change the payload via it’s node index. For example:

last_index = graph.node_indices()[-1]
graph[last_index] = "New Payload"
print(graph[last_index])

New Payload

You can update the payload of any node in the graph using this interface. For edges you can leverage the update_edge or update_edge_by_index methods to update an edge’s payload in place. For example:

edge_index = graph.add_edge(0, 1, None)
graph.update_edge_by_index(edge_index, "New Edge Payload")
print(graph.get_edge_data_by_index(edge_index))

New Edge Payload

What to use for node and edge data payload#

In the above examples for the most part we use integers, strings, and None for the data payload of nodes and edges in graphs (mostly for simplicity). However, rustworkx allows the use of any Python object as the data payload for nodes and edges. This flexibility is very powerful as it allows you to create graphs that contain other graphs, graphs that contain files, graphs with functions, etc. This means you only need to keep a reference to the integer index returned by rustworkx for the objects you use as a data payloads to find those objects in the graph. For example, one approach you can take is to store the index as an attribute on the object you add to the graph:

class GraphNode:

    def __init__(self, value):
        self.value = value
        self.index = None

graph = rx.PyGraph()
index = graph.add_node(GraphNode("A"))
graph[index].index = index

Additionally, at any time you can find the index mapping to the data payload and build a mapping or update a reference to it. For example, building on the above example you can update the index references all at once after creation:

class GraphNode:
    def __init__(self, value):
        self.index = None
        self.value = value

    def __str__(self):
        return f"GraphNode: {self.value} @ index: {self.index}"

class GraphEdge:
    def __init__(self, value):
        self.index = None
        self.value = value

    def __str__(self):
        return f"EdgeNode: {self.value} @ index: {self.index}"

graph = rx.PyGraph()
graph.add_nodes_from([GraphNode(i) for i in range(5)])
graph.add_edges_from([(i, i + 1, GraphEdge(i)) for i in range(4)])
# Populate index attribute in GraphNode objects
for index in graph.node_indices():
    graph[index].index = index
# Populate index attribute in GraphEdge objects
for index, data in graph.edge_index_map().items():
    data[2].index = index
print("Nodes:")
for node in graph.nodes():
    print(node)
print("Edges:")
for edge in graph.edges():
    print(edge)

Nodes:
GraphNode: 0 @ index: 0
GraphNode: 1 @ index: 1
GraphNode: 2 @ index: 2
GraphNode: 3 @ index: 3
GraphNode: 4 @ index: 4
Edges:
EdgeNode: 0 @ index: 0
EdgeNode: 1 @ index: 1
EdgeNode: 2 @ index: 2
EdgeNode: 3 @ index: 3

Accessing edges and neighbors#

You can access edges from a node using the incident_edges() method:

print(G.incident_edges(2))

EdgeIndices[0]

which will return the edge indices of the edges incident to node 2. You can also find the neighbor nodes using the neighbors() method:

print(G.neighbors(2))

NodeIndices[1]

which returns the node indices of any neighbors of node 2.

Graph Attributes#

Graphs in rustworkx have an attribute which can be used to assign metadata to a graph object. This can be assigned at object creation or accessed and modified after creation with the attrs attribute. This attribute can be any Python object and defaults to being None if not specified at graph object creation time. For example:

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

Or, you could use a custom class like:

class Day:

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

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

Directed Graphs#

A directed graph is a graph that is made up of a set of nodes connected by directed edges (often called arcs). Edges have a directionality which is different from undirected graphs where edges have no notion of a direction to them. In rustworkx the PyDiGraph class is used to create directed graphs. For example:

from rustworkx.visualization import mpl_draw

path_graph = rx.generators.directed_path_graph(5)
mpl_draw(path_graph)
../_images/introduction_19_0.png

In this example we created a directed path graph with 5 nodes. This shows the directionality of the edges in the graph visualization with the arrow head pointing to the target node.

Multigraphs#

By default all graphs in rustworkx are multigraphs. This means that each graph object can contain parallel edges between nodes. However, you can set the multigraph argument to False on the PyGraph and PyDiGraph constructors when creating a new graph object to prevent parallel edges from being introduced. When multigraph is set to False any method call made that would add a parallel edge will instead update the existing edge’s weight/data payload. For example:

graph = rx.PyGraph(multigraph=False)
graph.add_nodes_from(range(3))
graph.add_edges_from([(0, 1, 'A'), (0, 1, 'B'), (1, 2, 'C')])
mpl_draw(graph, with_labels=True, edge_labels=str)
../_images/introduction_20_0.png

In this example, our attempt to add a parallel edge between nodes 0 and 1 will instead result in the existing edge’s data payload being updated from 'A' to 'B'.

Graph Generators and operations#

In addition to constructing graphs one node and edge at a time, you can also create graphs using the Generators, Random Graph Generator Functions, and Graph Operations to quickly generate graphs and/or apply different operations on the graph. For example:

lolipop_graph = rx.generators.lollipop_graph(4, 3)
mesh_graph = rx.generators.mesh_graph(4)
combined_graph = rx.cartesian_product(lolipop_graph, mesh_graph)[0]
mpl_draw(combined_graph)
../_images/introduction_21_0.png

Additionally there are alternate constructors such as read_edge_list() or from_adjacency_matrix() for building graphs from files or other inputs. For example:

import tempfile

with tempfile.NamedTemporaryFile('wt') as fd:
    path = fd.name
    fd.write('0 1\n')
    fd.write('0 2\n')
    fd.write('0 3\n')
    fd.write('1 2\n')
    fd.write('2 3\n')
    fd.flush()
    graph = rx.PyGraph.read_edge_list(path)
mpl_draw(graph)
../_images/introduction_22_0.png

Analyzing graphs#

The structure of a graph \(G\) can be analyzed using the available graph algorithm functions. For example:

G = rx.PyGraph()
G.extend_from_edge_list([(0, 1), (0, 2)])
new_node = G.add_node("spam")
print(rx.connected_components(G))
degrees = {}
for node in G.node_indices():
    degrees[node] = G.degree(node)
print(degrees)

[{0, 1, 2}, {3}]
{0: 2, 1: 1, 2: 1, 3: 0}

G.remove_node(new_node)
G.extend_from_edge_list([(0, 3), (0, 4), (1, 2)])
rx.transitivity(G)

0.375

See the Algorithm Functions API documentation section for a list of the available functions and corresponding usage information.

Drawing graphs#

There are two visualization functions provided in rustworkx for visualizing graphs. The first is mpl_draw(), which uses the matplotlib library to render the visualization of the graph. The mpl_draw() function relies on the Layout Functions provided with rustworkx to generate a layout (the coordinates to draw the nodes of the graph) for the graph (by default spring_layout() is used). For example:

import matplotlib.pyplot as plt

G = rx.generators.generalized_petersen_graph(5, 2)
subax1 = plt.subplot(121)
mpl_draw(G, with_labels=True, ax=subax1)
subax2 = plt.subplot(122)
layout = rx.shell_layout(G, nlist=[[0, 1, 2, 3, 4], [6, 7, 8, 9, 5]])
mpl_draw(G, pos=layout, with_labels=True, ax=subax2)
../_images/introduction_25_0.png

The second function is graphviz_draw(), which uses Graphviz to generate visualizations. For example:

from rustworkx.visualization import graphviz_draw

G = rx.generators.heavy_hex_graph(7)
# set data payload to index
for node in G.node_indices():
    G[node] = node

def node_attr_fn(node):
    attr_dict = {
        "style": "filled",
        "shape": "circle",
        "label": str(node)
    }
    # Data nodes are yellow
    if node < 7 * 7:
        attr_dict["color"] = "yellow"
        attr_dict["fill_color"] = "yellow"
    # Syndrome nodes are black
    elif node >= 7 * 7 and node < (7 * 7) + ((7 - 1) * (7 + 1) / 2):
        attr_dict["color"] = "black"
        attr_dict["fill_color"] = "black"
        attr_dict["fontcolor"] = "white"
    # Flag quits are blue
    else:
        attr_dict["color"] = "blue"
        attr_dict["fill_color"] = "blue"
    return attr_dict

graphviz_draw(G, node_attr_fn=node_attr_fn, method="neato")
../_images/introduction_26_0.png

Generally, when deciding which visualization function to use, there are a few considerations to make. mpl_draw() is a better choice for smaller graphs or cases where you want to integrate your graph drawing as part of a larger visualization. graphviz_draw() is typically a better choice for larger graphs, because Graphviz is a dedicated tool for drawing graphs.