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.

PyDAG#

class PyDAG(check_cycle=False, multigraph=True, attrs=None, *, node_count_hint=None, edge_count_hint=None)[source]#

Bases: PyDiGraph

A class for creating direct acyclic graphs.

PyDAG is just an alias of the PyDiGraph class and behaves identically to the PyDiGraph class and can be used interchangeably with PyDiGraph. It currently exists solely as a backwards compatibility alias for users of rustworkx from prior to the 0.4.0 release when there was no PyDiGraph class.

The PyDAG class is used to create a directed graph. It can be a multigraph (have multiple edges between nodes). Each node and edge (although rarely used for edges) is indexed by an integer id. These ids are stable for the lifetime of the graph object and on node or edge deletions you can have holes in the list of indices for the graph. Node indices will be reused on additions after removal. For example:

import rustworkx as rx

graph = rx.PyDAG()
graph.add_nodes_from(list(range(5)))
graph.add_nodes_from(list(range(2)))
graph.remove_node(2)
print("After deletion:", graph.node_indices())
res_manual = graph.add_parent(6, None, None)
print("After adding a new node:", graph.node_indices())

After deletion: NodeIndices[0, 1, 3, 4, 5, 6]
After adding a new node: NodeIndices[0, 1, 2, 3, 4, 5, 6]

Additionally, each node and edge contains an arbitrary Python object as a weight/data payload.

You can use the index for access to the data payload as in the following example:

import rustworkx as rx

graph = rx.PyDAG()
data_payload = "An arbitrary Python object"
node_index = graph.add_node(data_payload)
print(f"Node Index: {node_index}")
print(graph[node_index])

Node Index: 0
An arbitrary Python object

The PyDAG class implements the Python mapping protocol for nodes so in addition to access you can also update the data payload with:

import rustworkx as rx

graph = rx.PyDAG()
data_payload = "An arbitrary Python object"
node_index = graph.add_node(data_payload)
graph[node_index] = "New Payload"
print(f"Node Index: {node_index}")
print(graph[node_index])

Node Index: 0
New Payload

The PyDAG class has an option for real time cycle checking which can be used to ensure any edges added to the graph does not introduce a cycle. By default the real time cycle checking feature is disabled for performance, however you can enable it by setting the check_cycle attribute to True. For example:

import rustworkx as rx
dag = rx.PyDAG()
dag.check_cycle = True

or at object creation:

import rustworkx as rx
dag = rx.PyDAG(check_cycle=True)

With check_cycle set to true any calls to PyDAG.add_edge() will ensure that no cycles are added, ensuring that the PyDAG class truly represents a directed acyclic graph. Do note that this cycle checking on add_edge(), add_edges_from(), add_edges_from_no_data(), extend_from_edge_list(), and extend_from_weighted_edge_list() comes with a performance penalty that grows as the graph does. If you’re adding a node and edge at the same time, leveraging PyDAG.add_child() or PyDAG.add_parent() will avoid this overhead.

By default a PyDAG is a multigraph (meaning there can be parallel edges between nodes) however this can be disabled by setting the multigraph kwarg to False when calling the PyDAG constructor. For example:

import rustworkx as rx
dag = rx.PyDAG(multigraph=False)

This can only be set at PyDiGraph initialization and not adjusted after creation. When multigraph is set to False if a method call is made that would add a parallel edge it will instead update the existing edge’s weight/data payload.

The maximum number of nodes and edges allowed on a PyGraph object is $2^{32} - 1$ (4,294,967,294) each. Attempting to add more nodes or edges than this will result in an exception being raised.

Parameters:

check_cycle (bool) – When this is set to True the created PyDAG has runtime cycle detection enabled.
multigraph (bool) – When this is set to False the created PyDAG object will not be a multigraph. When False if a method call is made that would add parallel edges the weight/weight from that method call will be used to update the existing edge in place.

Methods

`add_child`	Add a new child node to the graph.
`add_edge`	Add an edge between 2 nodes.
`add_edges_from`	Add new edges to the graph.
`add_edges_from_no_data`	Add new edges to the graph without python data.
`add_node`	Add a new node to the graph.
`add_nodes_from`	Add new nodes to the graph.
`add_parent`	Add a new parent node to the graph.
`adj`	Get the index and data for the neighbors of a node.
`adj_direction`	Get the index and data for either the parents or children of a node.
`clear`	Clear all nodes and edges
`clear_edges`	Clears all edges, leaves nodes intact
`compose`	Add another PyDiGraph object into this PyDiGraph
`contract_nodes`	Substitute a set of nodes with a single new node.
`copy`	Return a shallow copy of the graph
`edge_index_map`	Get an edge index map
`edge_indices`	Return a list of all edge indices.
`edge_indices_from_endpoints`	Return a list of indices of all directed edges between specified nodes
`edge_list`	Get edge list
`edge_subgraph`	Return a new PyDiGraph object for an edge induced subgraph of this graph
`edges`	Return a list of all edge data.
`extend_from_edge_list`	Extend graph from an edge list
`extend_from_weighted_edge_list`	Extend graph from a weighted edge list
`filter_edges`	Filters a graph's edges by some criteria conditioned on a edge's data payload and returns those edges' indices.
`filter_nodes`	Filters a graph's nodes by some criteria conditioned on a node's data payload and returns those nodes' indices.
`find_adjacent_node_by_edge`	Find any adjacent (successor) node connected with an edge that matches the condition
`find_node_by_weight`	Find node within this graph given a specific weight
`find_predecessor_node_by_edge`	Find any predecessor node connected with an edge that matches the condition
`find_predecessors_by_edge`	Return a list of data associated with the predecessors of the given node, where the edges connecting from those nodes satisfy the provided filter function.
`find_successor_node_by_edge`	Find any successor node connected with an edge that matches the condition
`find_successors_by_edge`	Return a list of data associated with the successors of the given node, where the edges connecting to those nodes satisfy the provided filter function.
`from_adjacency_matrix`	Create a new `PyDiGraph` object from an adjacency matrix with matrix elements of type `float`
`from_complex_adjacency_matrix`	Create a new `PyDiGraph` object from an adjacency matrix with matrix elements of type `complex`
`get_all_edge_data`	Return the edge data for all the edges between 2 nodes.
`get_edge_data`	Return the edge data for an edge between 2 nodes.
`get_edge_data_by_index`	Return the edge data for the edge by its given index
`get_edge_endpoints_by_index`	Return the edge endpoints for the edge by its given index
`get_node_data`	Return the node data for a given node index
`has_edge`	Check if there is a directed edge from `node_a` to `node_b`.
`has_node`	Check if the node exists in the graph.
`has_parallel_edges`	Detect if the graph has parallel edges or not
`in_degree`	Get the degree of a node for inbound edges.
`in_edge_indices`	Return the list of incoming edge indices to a provided node
`in_edges`	Get the index and edge data for all parents of a node.
`incident_edge_index_map`	Return the index map of edges incident to a provided node
`incident_edges`	Return the list of edge indices incident to a provided node
`insert_node_on_in_edges`	Insert a node between a reference node and all its predecessor nodes
`insert_node_on_in_edges_multiple`	Insert a node between a list of reference nodes and all their predecessors
`insert_node_on_out_edges`	Insert a node between a reference node and all its successor nodes
`insert_node_on_out_edges_multiple`	Insert a node between a list of reference nodes and all their successors
`is_symmetric`	Check if the graph is symmetric
`make_symmetric`	Make edges in graph symmetric
`merge_nodes`	Merge two nodes in the graph.
`neighbors`	Return a list of node indices of neighbors (i.e.
`neighbors_undirected`	Get the direction-agnostic neighbors (i.e.
`node_indexes`	Return a list of all node indices.
`node_indices`	Return a list of all node indices.
`nodes`	Return a list of all node data.
`num_edges`	Return the number of edges in the graph
`num_nodes`	Return the number of nodes in the graph
`out_degree`	Get the degree of a node for outbound edges.
`out_edge_indices`	Return the list of outgoing edge indices from a provided node
`out_edges`	Get the index and edge data for all children of a node.
`predecessor_indices`	Return a list of predecessor node indices in a directed graph
`predecessors`	Return a list of data of all node predecessors in a directed graph
`read_edge_list`	Read an edge list file and create a new PyDiGraph object from the contents
`remove_edge`	Remove an edge between 2 nodes.
`remove_edge_from_index`	Remove an edge identified by the provided index
`remove_edges_from`	Remove edges from the graph.
`remove_node`	Remove a node from the graph.
`remove_node_retain_edges`	Remove a node from the graph and add edges from all predecessors to all successors
`remove_node_retain_edges_by_id`	Remove a node from the graph and add edges from predecessors to successors in cases where an incoming and outgoing edge have the same weight by Python object identity.
`remove_node_retain_edges_by_key`	Remove a node from the graph and add edges from predecessors to successors in cases where an incoming and outgoing edge have the same weight by Python object equality.
`remove_nodes_from`	Remove nodes from the graph.
`reverse`	Reverse the direction of all edges in the graph, in place.
`subgraph`	Return a new PyDiGraph object for a subgraph of this graph
`substitute_node_with_subgraph`	Substitute a node with a PyDigraph object
`successor_indices`	Return a list of successor node indices in a directed graph
`successors`	Return a list of data of all node successors in a directed graph
`to_dot`	Generate a dot file from the graph
`to_undirected`	Generate a new PyGraph object from this graph
`update_edge`	Update an edge's weight/payload in place
`update_edge_by_index`	Update an edge's weight/data payload in place by the edge index
`weighted_edge_list`	Get edge list with weights
`write_edge_list`	Write an edge list file from the PyDiGraph object

Attributes

attrs#

check_cycle#

Whether cycle checking is enabled for the DiGraph/DAG.

If set to True adding new edges that would introduce a cycle will raise a DAGWouldCycle exception.

multigraph#

Whether the graph is a multigraph (allows multiple edges between nodes) or not

If set to False multiple edges between nodes are not allowed and calls that would add a parallel edge will instead update the existing edge