# graph_tools¶

Filename: graph_tools.py

Author: Daisuke Oyama

Tools for dealing with a directed graph.

class quantecon.graph_tools.DiGraph(adj_matrix, weighted=False)[source]

Bases: object

Class for a directed graph. It stores useful information about the graph structure such as strong connectivity [R3] and periodicity [R4].

Parameters: adj_matrix : array_like(ndim=2) Adjacency matrix representing a directed graph. Must be of shape n x n. weighted : bool, optional(default=False) Whether to treat adj_matrix as a weighted adjacency matrix.

References

 [R3] (1, 2) Strongly connected component, Wikipedia.
 [R4] (1, 2) Aperiodic graph, Wikipedia.

Attributes

 csgraph (scipy.sparse.csr_matrix) Compressed sparse representation of the digraph. is_strongly_connected (bool) Indicate whether the digraph is strongly connected. num_strongly_connected_components (int) The number of the strongly connected components. strongly_connected_components (list(ndarray(int))) List of numpy arrays containing the strongly connected components. num_sink_strongly_connected_components (int) The number of the sink strongly connected components. sink_strongly_connected_components (list(ndarray(int))) List of numpy arrays containing the sink strongly connected components. is_aperiodic (bool) Indicate whether the digraph is aperiodic. period (int) The period of the digraph. Defined only for a strongly connected digraph. cyclic_components (list(ndarray(int))) List of numpy arrays containing the cyclic components.

Methods

 subgraph(nodes) Return the subgraph consisting of the given nodes and edges between thses nodes.
cyclic_components
is_aperiodic
is_strongly_connected
num_sink_strongly_connected_components
num_strongly_connected_components
period
scc_proj
sink_scc_labels
sink_strongly_connected_components
strongly_connected_components
subgraph(nodes)[source]

Return the subgraph consisting of the given nodes and edges between thses nodes.

Parameters: nodes : array_like(int, ndim=1) Array of nodes. DiGraph A DiGraph representing the subgraph.