PyDiGraph¶
- class PyDiGraph(check_cycle=False, multigraph=True, /)¶
Bases:
object
A class for creating directed graphs
The
PyDiGraph
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 retworkx graph = retworkx.PyDiGraph() graph.add_nodes_from(list(range(5))) graph.add_nodes_from(list(range(2))) graph.remove_node(2) print("After deletion:", graph.node_indexes()) res_manual = graph.add_parent(6, None, None) print("After adding a new node:", graph.node_indexes())
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 retworkx graph = retworkx.PyDiGraph() data_payload = "An arbitrary Python object" node_index = graph.add_node(data_payload) print("Node Index: %s" % node_index) print(graph[node_index])
Node Index: 0 An arbitrary Python object
The PyDiGraph implements the Python mapping protocol for nodes so in addition to access you can also update the data payload with:
import retworkx graph = retworkx.PyDiGraph() data_payload = "An arbitrary Python object" node_index = graph.add_node(data_payload) graph[node_index] = "New Payload" print("Node Index: %s" % node_index) print(graph[node_index])
Node Index: 0 New Payload
The PyDiGraph 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 retworkx dag = retworkx.PyDiGraph() dag.check_cycle = True
or at object creation:
import retworkx dag = retworkx.PyDiGraph(check_cycle=True)
With check_cycle set to true any calls to
PyDiGraph.add_edge()
will ensure that no cycles are added, ensuring that the PyDiGraph class truly represents a directed acyclic graph. Do note that this cycle checking onadd_edge()
,add_edges_from()
,add_edges_from_no_data()
,extend_from_edge_list()
, andextend_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 leveragingPyDiGraph.add_child()
orPyDiGraph.add_parent()
will avoid this overhead.By default a
PyDiGraph
is a multigraph (meaning there can be parallel edges between nodes) however this can be disabled by setting themultigraph
kwarg toFalse
when calling thePyDiGraph
constructor. For example:import retworkx graph = retworkx.PyDiGraph(multigraph=False)
This can only be set at
PyDiGraph
initialization and not adjusted after creation. Whenmultigraph
is set toFalse
if a method call is made that would add a parallel edge it will instead update the existing edge’s weight/data payload.- Parameters
check_cycle (bool) – When this is set to
True
the createdPyDiGraph
has runtime cycle detection enabled.multgraph (bool) – When this is set to
False
the createdPyDiGraph
object will not be a multigraph. WhenFalse
if a method call is made that would add parallel edges the the weight/weight from that method call will be used to update the existing edge in place.
Methods
Add a new child node to the graph.
Add an edge between 2 nodes.
Add new edges to the dag.
Add new edges to the dag without python data.
Add a new node to the graph.
Add new nodes to the graph.
Add a new parent node to the dag.
Get the index and data for the neighbors of a node.
Get the index and data for either the parent or children of a node.
Add another PyDiGraph object into this PyDiGraph
Return a shallow copy of the graph
Get an edge index map
Return a list of all edge indices.
Get edge list
Return a new PyDiGraph object for an edge induced subgraph of this graph
Return a list of all edge data.
Extend graph from an edge list
Extend graph from a weighted edge list
Find a target node with a specific edge
Find node within this graph given a specific weight
Return a filtered list of predecessor data such that each node has at least one edge data which matches the filter.
Return a filtered list of successors data such that each node has at least one edge data which matches the filter.
Create a new
PyDiGraph
object from an adjacency matrixReturn the edge data for all the edges between 2 nodes.
Return the edge data for an edge between 2 nodes.
Return the node data for a given node index
Return True if there is an edge from node_a to node_b.
Detect if the graph has parallel edges or not
Get the degree of a node for inbound edges.
Get the index and edge data for all parents of a node.
Insert a node between a reference node and all its predecessor nodes
Insert a node between a list of reference nodes and all their predecessors
Insert a node between a reference node and all its successor nodes
Insert a node between a list of reference nodes and all their successors
Check if the graph is symmetric
Merge two nodes in the graph.
Get the neighbors (i.e.
Return a list of all node indexes.
Return a list of all node data.
Return the number of edges in the graph
Return the number of nodes in the graph
Get the degree of a node for outbound edges.
Get the index and edge data for all children of a node.
Get the predecessor indices of a node.
Return a list of all the node predecessor data.
Read an edge list file and create a new PyDiGraph object from the contents
Remove an edge between 2 nodes.
Remove an edge identified by the provided index
Remove edges from the graph.
Remove a node from the graph.
Remove a node from the graph and add edges from all predecessors to all successors
Remove nodes from the graph.
Return a new PyDiGraph object for a subgraph of this graph
Substitute a node with a PyDigraph object
Get the successor indices of a node.
Return a list of all the node successor data.
Generate a dot file from the graph
Generate a new PyGraph object from this graph
Update an edge’s weight/payload inplace
Update an edge’s weight/payload by the edge index
Get edge list with weights
Write an edge list file from the PyDiGraph object
Attributes
- 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 aDAGWouldCycle
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