# graph_tools¶

Tools for dealing with a directed graph.

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

Bases: object

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

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. node_labels : array_like(default=None) Array_like of length n containing the labels associated with the nodes, which must be homogeneous in type. If None, the labels default to integers 0 through n-1.

References

 [1] (1, 2) Strongly connected component, Wikipedia.
 [2] (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_indices : list(ndarray(int)) List of numpy arrays containing the indices of the strongly connected components. strongly_connected_components : list(ndarray) List of numpy arrays containing the strongly connected components, where the nodes are annotated with their labels (if node_labels is not None). num_sink_strongly_connected_components : int The number of the sink strongly connected components. sink_strongly_connected_components_indices : list(ndarray(int)) List of numpy arrays containing the indices of the sink strongly connected components. sink_strongly_connected_components : list(ndarray) List of numpy arrays containing the sink strongly connected components, where the nodes are annotated with their labels (if node_labels is not None). 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_indices : list(ndarray(int)) List of numpy arrays containing the indices of the cyclic components. cyclic_components : list(ndarray) List of numpy arrays containing the cyclic components, where the nodes are annotated with their labels (if node_labels is not None).

Methods

 subgraph(nodes) Return the subgraph consisting of the given nodes and edges between thses nodes.
cyclic_components
cyclic_components_indices
is_aperiodic
is_strongly_connected
node_labels
num_sink_strongly_connected_components
num_strongly_connected_components
period
scc_proj
sink_scc_labels
sink_strongly_connected_components
sink_strongly_connected_components_indices
strongly_connected_components
strongly_connected_components_indices
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 node indices. DiGraph A DiGraph representing the subgraph.
quantecon.graph_tools.annotate_nodes(func)[source]
quantecon.graph_tools.random_tournament_graph(n, random_state=None)[source]

Return a random tournament graph [1] with n nodes.

Parameters: n : scalar(int) Number of nodes. random_state : int or np.random.RandomState, optional Random seed (integer) or np.random.RandomState instance to set the initial state of the random number generator for reproducibility. If None, a randomly initialized RandomState is used. DiGraph A DiGraph representing the tournament graph.

References

 [1] (1, 2) Tournament (graph theory), Wikipedia.