hiperwalk.Graph

class hiperwalk.Graph(adj_matrix, copy=False)

Constructs an arbitrary simple graph with loops.

This class defines the graph structure used for implementing a quantum walk. It encapsulates all necessary properties and functionalities of the graph required for the quantum walk dynamics.

Parameters:

adj_matrix

The adjacency matrix of the graph (any integer Hermitian matrix). Two input types are accepted:

• Any matrix – for instance,

  • scipy.sparse.csr_array,

  • numpy.ndarray,

  • list of lists.

• networkx.Graph.

  • The adjacency matrix is extracted from the graph.

copybool, default=False

If True, a hard copy of adj_matrix is stored. If False, the pointer to adj_matrix is stored and the adj_matrix’s data is changed.

Raises:

TypeError

If adj_matrix is not a square matrix.

Notes

The class methods facilitate the construction of a valid quantum walk and can be provided as parameters to plotting functions. For visualizations, the default graph representation will be used. Specific classes are available for well-known graph types, such as hypercubes and lattices.

The adjacency matrix is always stored as a scipy.sparse.csr_array. If adj_matrix is sparse and copy=False, the argument will be changed for more efficient manipulation.

Each vertex has at most one loop.

Warning

To reduce memory usage, adj_matrix.data is set to None. This is possible because adj_matrix.data should be an array of ones.

If the user wishes to keep the original adj_matrix, the argument copy must be set to True.

The treatment of the graph depends on the quantum walk model.

The default order of neighbors is the ascending order. A different order of neighbors can be specified using a sparse matrix where scipy.sparse.csr_array.has_sorted_indices is False. In this case, the neighbors of u are given by adj_matrix.indices[adj_matrix.indptr[u]:adj_matrix.indptr[u+1]].

Examples

Creating a complete graph with loops and the default order of neighbors (ascending order).

>>> num_vert = 4
>>> A = scipy.sparse.csr_array([[1]*num_vert]*num_vert)
>>> g = hpw.Graph(A)
>>> g.neighbors(0)
array([0, 1, 2, 3], dtype=int32)
>>> g.neighbors(1)
array([0, 1, 2, 3], dtype=int32)

Creating a complete graph with loops and the descending order of neighbors.

>>> data = [1]*(num_vert**2)
>>> indices = list(range(num_vert - 1, -1, -1))*num_vert
>>> indptr = list(range(0, num_vert*(num_vert + 1), num_vert))
>>> A = scipy.sparse.csr_array((data, indices, indptr))
>>> g = hpw.Graph(A)
>>> g.neighbors(0)
array([3, 2, 1, 0])
>>> g.neighbors(1)
array([3, 2, 1, 0])

__init__(adj_matrix, copy=False)

Methods

adjacency_matrix()	Return the graph's adjacency matrix.
adjacent(u, v)	Return True if vertex u is adjacent to v.
degree(vertex)	Return the degree of the given vertex.
is_simple()	Return True if instance of simple graph.
laplacian_matrix()	Return the graph's Laplacian matrix.
neighbors(vertex)	Return all neighbors of the given vertex.
number_of_edges()	Determine the cardinality of the edge set.
number_of_loops()	Return the number of loops in the graph.
number_of_vertices()	Determine the cardinality of the vertex set.
vertex_number(vertex)	Return the vertex number given any vertex representation.