Warning
The documentation for retworkx has migrated to:
https://qiskit.org/documentation/retworkx
These docs will no longer be updated.
retworkx.PyGraph¶
- class PyGraph(multigraph=True, /)¶
A class for creating undirected graphs
The PyGraph class is used to create an undirected 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. 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.PyGraph() 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.PyGraph() 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
- Parameters
multigraph (bool) – When this is set to
False
the created PyGraph object will not be a multigraph (which is the default behavior). WhenFalse
if parallel edges are added the weight/weight from that method call will be used to update the existing edge in place.
- __init__()¶
Initialize self. See help(type(self)) for accurate signature.
Methods
__init__
()Initialize self.
add_edge
(node_a, node_b, edge, /)Add an edge between 2 nodes.
add_edges_from
(obj_list, /)Add new edges to the graph.
add_edges_from_no_data
(obj_list, /)Add new edges to the graph without python data.
add_node
(obj, /)Add a new node to the graph.
add_nodes_from
(obj_list, /)Add new nodes to the graph.
adj
(node, /)Get the index and data for the neighbors of a node.
compose
(other, node_map, /[, node_map_func, …])Add another PyGraph object into this PyGraph
degree
(node, /)Get the degree for a node
Get edge list
edges
()Return a list of all edge data.
extend_from_edge_list
(edge_list, /)Extend graph from an edge list
extend_from_weighted_edge_list
(edge_lsit, /)Extend graph from a weighted edge list
from_adjacency_matrix
(matrix, /)Create a new
PyGraph
object from an adjacency matrixget_all_edge_data
(node_a, node_b, /)Return the edge data for all the edges between 2 nodes.
get_edge_data
(node_a, node_b, /)Return the edge data for the edge between 2 nodes.
get_node_data
(node, /)Return the node data for a given node index
has_edge
(node_a, node_b, /)Return True if there is an edge between node_a to node_b.
neighbors
(node, /)Get the neighbors of a node.
Return a list of all node indexes.
nodes
()Return a list of all node data.
read_edge_list
(path, /[, comment, deliminator])Read an edge list file and create a new PyGraph object from the contents
remove_edge
(node_a, node_b, /)Remove an edge between 2 nodes.
remove_edge_from_index
(edge, /)Remove an edge identified by the provided index
remove_edges_from
(index_list, /)Remove edges from the graph.
remove_node
(node, /)Remove a node from the graph.
remove_nodes_from
(index_list, /)Remove nodes from the graph.
subgraph
(nodes, /)Return a new PyGraph object for a subgraph of this graph
to_dot
([node_attr, edge_attr, graph_attr, …])Generate a dot file from the graph
update_edge
(source, target, /, edge)Update an edge’s weight/payload in place
update_edge_by_index
(source, target, /, edge)Update an edge’s weight/data payload in place by the edge index
Get edge list with weights
Attributes
Whether the graph is a multigraph (allows multiple edges between nodes) or not
- add_edge(node_a, node_b, edge, /)¶
Add an edge between 2 nodes.
If
multigraph
isFalse
and an edge already exists betweennode_a
andnode_b
the weight/payload of that existing edge will be updated to beedge
.- Parameters
node_a (int) – Index of the parent node
node_b (int) – Index of the child node
edge – The object to set as the data for the edge. It can be any python object.
- Returns
The edge index for the newly created (or updated in the case of an existing edge with
multigraph=False
) edge.- Return type
int
- add_edges_from(obj_list, /)¶
Add new edges to the graph.
- Parameters
obj_list (list) – A list of tuples of the form
(node_a, node_b, obj)
to attach to the graph.node_a
andnode_b
are integer indexes describing where an edge should be added, andobj
is the python object for the edge data.
If
multigraph
isFalse
and an edge already exists betweennode_a
andnode_b
the weight/payload of that existing edge will be updated to beedge
. This will occur in order fromobj_list
so if there are multiple parallel edges inobj_list
the last entry will be used.- Returns
A list of int indices of the newly created edges
- Return type
list
- add_edges_from_no_data(obj_list, /)¶
Add new edges to the graph without python data.
- Parameters
obj_list (list) – A list of tuples of the form
(parent, child)
to attach to the graph.parent
andchild
are integer indexes describing where an edge should be added. Unlikeadd_edges_from()
there is no data payload and when the edge is created None will be used.
If
multigraph
isFalse
and an edge already exists betweennode_a
andnode_b
the weight/payload of that existing edge will be updated to beNone
.- Returns
A list of int indices of the newly created edges
- Return type
list
- add_node(obj, /)¶
Add a new node to the graph.
- Parameters
obj – The python object to attach to the node
- Returns
The index of the newly created node
- Return type
int
- add_nodes_from(obj_list, /)¶
Add new nodes to the graph.
- Parameters
obj_list (list) – A list of python object to attach to the graph.
- Returns indices
A list of int indices of the newly created nodes
- Return type
- adj(node, /)¶
Get the index and data for the neighbors of a node.
This will return a dictionary where the keys are the node indexes of the adjacent nodes (inbound or outbound) and the value is the edge data objects between that adjacent node and the provided node. Note, that in the case of multigraphs only a single edge data object will be returned
- Parameters
node (int) – The index of the node to get the neighbors
- Returns neighbors
A dictionary where the keys are node indexes and the value is the edge data object for all nodes that share an edge with the specified node.
- Return type
dict
- compose(other, node_map, /, node_map_func=None, edge_map_func=None)¶
Add another PyGraph object into this PyGraph
- Parameters
other (PyGraph) – The other PyGraph object to add onto this graph.
node_map (dict) –
A dictionary mapping node indexes from this PyGraph object to node indexes in the other PyGraph object. The keys are a node index in this graph and the value is a tuple of the node index in the other graph to add an edge to and the weight of that edge. For example:
{ 1: (2, "weight"), 2: (4, "weight2") }
node_map_func – An optional python callable that will take in a single node weight/data object and return a new node weight/data object that will be used when adding an node from other onto this graph.
edge_map_func – An optional python callabble that will take in a single edge weight/data object and return a new edge weight/data object that will be used when adding an edge from other onto this graph.
- Returns
new_node_ids: A dictionary mapping node index from the other PyGraph to the equivalent node index in this PyDAG after they’ve been combined
- Return type
dict
For example, start by building a graph:
import os import tempfile import pydot from PIL import Image import retworkx # Build first graph and visualize: graph = retworkx.PyGraph() node_a, node_b, node_c = graph.add_nodes_from(['A', 'B', 'C']) graph.add_edges_from_no_data([(node_a, node_b), (node_b, node_c)]) 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, 'graph.png') dot.write_png(tmp_path) image = Image.open(tmp_path) os.remove(tmp_path) image
Then build a second one:
# Build second graph and visualize: other_graph = retworkx.PyGraph() node_d, node_e = other_graph.add_nodes_from(['D', 'E']) other_graph.add_edge(node_d, node_e, None) dot_str = other_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, 'other_graph.png') dot.write_png(tmp_path) image = Image.open(tmp_path) os.remove(tmp_path) image
Finally compose the
other_graph
ontograph
node_map = {node_b: (node_d, 'B to D')} graph.compose(other_graph, node_map) 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, 'combined_graph.png') dot.write_png(tmp_path) image = Image.open(tmp_path) os.remove(tmp_path) image
- degree(node, /)¶
Get the degree for a node
- Parameters
node (int) – The index of the node to find the inbound degree of
- Returns degree
The inbound degree for the specified node
- Return type
int
- edge_list()¶
Get edge list
Returns a list of tuples of the form
(source, target)
wheresource
andtarget
are the node indices.- Returns
An edge list with weights
- Return type
- edges()¶
Return a list of all edge data.
- Returns
A list of all the edge data objects in the graph
- Return type
list
- extend_from_edge_list(edge_list, /)¶
Extend graph from an edge list
This method differs from
add_edges_from_no_data()
in that it will add nodes if a node index is not present in the edge list.If
multigraph
isFalse
and an edge already exists betweennode_a
andnode_b
the weight/payload of that existing edge will be updated to beNone
.- Parameters
edge_list (list) – A list of tuples of the form
(source, target)
where source and target are integer node indices. If the node index is not present in the graph, nodes will be added (with a node weight ofNone
) to that index.
- extend_from_weighted_edge_list(edge_lsit, /)¶
Extend graph from a weighted edge list
This method differs from
add_edges_from()
in that it will add nodes if a node index is not present in the edge list.If
multigraph
isFalse
and an edge already exists betweennode_a
andnode_b
the weight/payload of that existing edge will be updated to beedge
. This will occur in order fromobj_list
so if there are multiple parallel edges inobj_list
the last entry will be used.- Parameters
edge_list (list) – A list of tuples of the form
(source, target, weight)
where source and target are integer node indices. If the node index is not present in the graph, nodes will be added (with a node weight ofNone
) to that index.
- static from_adjacency_matrix(matrix, /)¶
Create a new
PyGraph
object from an adjacency matrixThis method can be used to construct a new
PyGraph
object from an input adjacency matrix. The node weights will be the index from the matrix. The edge weights will be a float value of the value from the matrix.
- get_all_edge_data(node_a, node_b, /)¶
Return the edge data for all the edges between 2 nodes.
- Parameters
node_a (int) – The index for the first node
node_b (int) – The index for the second node
- Returns
A list with all the data objects for the edges between nodes
- Return type
list
- Raises
NoEdgeBetweenNodes – When there is no edge between nodes
- get_edge_data(node_a, node_b, /)¶
Return the edge data for the edge between 2 nodes.
Note if there are multiple edges between the nodes only one will be returned. To get all edge data objects use
get_all_edge_data()
- Parameters
node_a (int) – The index for the first node
node_b (int) – The index for the second node
- Returns
The data object set for the edge
- Raises
NoEdgeBetweenNodes – when there is no edge between the provided nodes
- get_node_data(node, /)¶
Return the node data for a given node index
- Parameters
node (int) – The index for the node
- Returns
The data object set for that node
- Raises
IndexError – when an invalid node index is provided
- has_edge(node_a, node_b, /)¶
Return True if there is an edge between node_a to node_b.
- Parameters
node_a (int) – The node index to check for an edge between
node_b (int) – The node index to check for an edge between
- Returns
True if there is an edge false if there is no edge
- Return type
bool
- 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
- neighbors(node, /)¶
Get the neighbors of a node.
This with return a list of neighbor node indices
- Parameters
node (int) – The index of the node to get the neibhors of
- Returns
A list of the neighbor node indicies
- Return type
- node_indexes()¶
Return a list of all node indexes.
- Returns
A list of all the node indexes in the graph
- Return type
- nodes()¶
Return a list of all node data.
- Returns
A list of all the node data objects in the graph
- Return type
list
- static read_edge_list(path, /, comment=None, deliminator=None)¶
Read an edge list file and create a new PyGraph object from the contents
The expected format for the edge list file is a line seperated list of deliminated node ids. If there are more than 3 elements on a line the 3rd on will be treated as a string weight for the edge
- Parameters
path (str) – The path of the file to open
comment (str) – Optional character to use as a comment by default there are no comment characters
deliminator (str) – Optional character to use as a deliminator by default any whitespace will be used
For example:
import os import tempfile from PIL import Image import pydot import retworkx 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 = retworkx.PyGraph.read_edge_list(path) # Draw graph dot = pydot.graph_from_dot_data(graph.to_dot())[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
- remove_edge(node_a, node_b, /)¶
Remove an edge between 2 nodes.
Note if there are multiple edges between the specified nodes only one will be removed.
- Parameters
parent (int) – The index for the parent node.
child (int) – The index of the child node.
- Raises
NoEdgeBetweenNodes – If there are no edges between the nodes specified
- remove_edge_from_index(edge, /)¶
Remove an edge identified by the provided index
- Parameters
edge (int) – The index of the edge to remove
- remove_edges_from(index_list, /)¶
Remove edges from the graph.
Note if there are multiple edges between the specified nodes only one will be removed.
- Parameters
index_list (list) – A list of node index pairs to remove from the graph
- remove_node(node, /)¶
Remove a node from the graph.
- Parameters
node (int) – The index of the node to remove. If the index is not present in the graph it will be ignored and this function will have no effect.
- remove_nodes_from(index_list, /)¶
Remove nodes from the graph.
If a node index in the list is not present in the graph it will be ignored.
- Parameters
index_list (list) – A list of node indicies to remove from the the graph
- subgraph(nodes, /)¶
Return a new PyGraph object for a subgraph of this graph
- Parameters
nodes (list) – A list of node indices to generate the subgraph from. If a node index is included that is not present in the graph it will silently be ignored.
- Returns
A new PyGraph object representing a subgraph of this graph. It is worth noting that node and edge weight/data payloads are passed by reference so if you update (not replace) an object used as the weight in graph or the subgraph it will also be updated in the other.
- Return type
- to_dot(node_attr=None, edge_attr=None, graph_attr=None, filename=None)¶
Generate a dot file from the graph
- Parameters
node_attr – A callable that will take in a node data object and return a dictionary of attributes to be associated with the node in the dot file. The key and value of this dictionary must be a string. If they’re not strings retworkx will raise TypeError (unfortunately without an error message because of current limitations in the PyO3 type checking)
edge_attr – A callable that will take in an edge data object and return a dictionary of attributes to be associated with the node in the dot file. The key and value of this dictionary must be a string. If they’re not strings retworkx will raise TypeError (unfortunately without an error message because of current limitations in the PyO3 type checking)
graph_attr (dict) – An optional dictionary that specifies any graph attributes for the output dot file. The key and value of this dictionary must be a string. If they’re not strings retworkx will raise TypeError (unfortunately without an error message because of current limitations in the PyO3 type checking)
filename (str) – An optional path to write the dot file to if specified there is no return from the function
- Returns
A string with the dot file contents if filename is not specified.
- Return type
str
Using this method enables you to leverage graphviz to visualize a
retworkx.PyGraph
object. For example:import os import tempfile import pydot from PIL import Image import retworkx graph = retworkx.undirected_gnp_random_graph(15, .25) 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
- update_edge(source, target, /, edge)¶
Update an edge’s weight/payload in place
If there are parallel edges in the graph only one edge will be updated. if you need to update a specific edge or need to ensure all parallel edges get updated you should use
update_edge_by_index()
instead.- Parameters
source (int) – The index for the first node
target (int) – The index for the second node
- Raises
NoEdgeBetweenNodes – When there is no edge between nodes
- update_edge_by_index(source, target, /, edge)¶
Update an edge’s weight/data payload in place by the edge index
- Parameters
edge_index (int) – The index for the edge
edge (object) – The data payload/weight to update the edge with
- Raises
NoEdgeBetweenNodes – When there is no edge between nodes
- weighted_edge_list()¶
Get edge list with weights
Returns a list of tuples of the form
(source, target, weight)
wheresource
andtarget
are the node indices andweight
is the payload of the edge.- Returns
An edge list with weights
- Return type