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, node_labels=None)

Bases: object

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

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

[R9]	(1, 2) Strongly connected component, Wikipedia.

[R10]

(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)

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

Parameters:

nodes : array_like(int, ndim=1)

Array of node indices.

Returns:

DiGraph

A DiGraph representing the subgraph.

quantecon.graph_tools.annotate_nodes(func)