Graphs

Hiperwalk gives support to three different types of graphs: simples graphs, multigraphs and weighted graphs. There is a class for each of these types of graph: hiperwalk.Graph, hiperwalk.Multigraph, and hiperwalk.WeightedGraph, respectively.

Simple Graphs

The hiperwalk.Graph class is used for handling simple graphs with self-loops.

You can create any graph by passing the adjacency matrix to the hiperwalk.Graph constructor. You can obtain the adjacency matrix using NetworkX’s networkx.adjacency_matrix() function. For instance, to generate the adjacency matrix of a ladder graph, you would execute the following commands:

>>> import networkx as nx
>>> nx_ladder = nx.ladder_graph(10)
>>> adj = nx.adjacency_matrix(nx_ladder)
>>> adj 
<20x20 sparse array of type '<class 'numpy.int64'>'
    with 56 stored elements in Compressed Sparse Row format>

Once you have the adjacency matrix, you can then create a Hiperwalk graph.

>>> import hiperwalk as hpw
>>> hpw_ladder = hpw.Graph(adj)
>>> hpw_ladder 
<hiperwalk.graph.graph.Graph object at 0x7f3bd0627eb0>

Alternativaly, you can create a Hiperwalk graph by passing an instance of networkx.Graph.

>>> hpw_ladder2 = hpw.Graph(nx_ladder)
>>> hpw_ladder2 
<hiperwalk.graph.graph.Graph object at 0x74f25e41d4e0>
>>> # checking if the adjacency matrices are equal
>>> nx_adj = nx.adjacency_matrix(nx_ladder)
>>> hpw_adj1 = hpw_ladder.adjacency_matrix()
>>> hpw_adj2 = hpw_ladder2.adjacency_matrix()
>>> (nx_adj - hpw_adj1).nnz == 0
True
>>> (hpw_adj1 - hpw_adj2).nnz == 0
True

After instantiating a Hiperwalk graph, it’s advisable to delete the NetworkX graph. This step is particularly important when dealing with large graphs, as it helps to prevent memory overload.

>>> del nx_ladder

Following this, you can use hpw_ladder to simulate any quantum walk, regardless of the model.

Order of Neighbors

By default, the neighbors of a vertex are listed in ascending order.

>>> hpw_ladder.neighbors(1)
array([ 0,  2, 11])

Depending on the graph, you may wish to specify a different order of neighbors. This is particularly useful for the coined quantum walk model (hiperwalk.Coined). To specify an order of neighbors, create the adjacency matrix using scipy.sparse.csr_array such that scipy.sparse.csr_array.has_sorted_indices is False. This can be done by expliciting scipy.sparse.csr_array’s indices. Then, the neighbors of u are listed in the order indices[indptr[u]:indptr[u+1]]. For example, the following commands create a complete graph with self-loops where the neighbors of u are listed in the order [u, u+1, ..., u-1].

>>> import scipy.sparse
>>> # creating the csr_array
>>> num_vert = 5
>>> data = np.ones(num_vert**2)
>>> indices = [(u + shift) % num_vert
...            for u in range(num_vert)
...            for shift in range(num_vert)]
>>> indptr = np.arange(0, num_vert**2 + 1, num_vert)
>>> adj_matrix = scipy.sparse.csr_array((data, indices, indptr))
>>> # creating graph with non-default order of neighbors
>>> g = hpw.Graph(adj_matrix)
>>> # testing the order of neighbors
>>> for u in range(num_vert):
...     print(g.neighbors(u))
[0 1 2 3 4]
[1 2 3 4 0]
[2 3 4 0 1]
[3 4 0 1 2]
[4 0 1 2 3]

Multigraphs

You can create a multigraph by passing its adjacency matrix. The adjacency matrix entries are the number of edges simultaneously incident to pairs of vertices.

>>> # creating the adjacency matrix of a complete multigraph
>>> num_vert = 5
>>> adj_matrix = np.zeros((num_vert, num_vert))
>>> for i in range(num_vert):
...     for j in range(num_vert):
...         adj_matrix[i, j] = i + j + 1
...
>>> # creating multigraph
>>> g = hpw.Multigraph(adj_matrix)
>>> # checking if multigraph was created properly
>>> np.all(np.array(
...         [g.number_of_edges(u, v) == u + v + 1
...         for u in range(num_vert)
...         for v in range(num_vert)]) == True)
True

Multigraphs are used to create coined quantum walks (hiperwalk.Coined).

Order of Neighbors

To specify a non-default order of neighbors, you can follow the same steps used for simple graphs. But be aware that the values of data must be rearranged with respect to indices.

>>> # creating data with the appropriate values
>>> data = [u + v + 1 for u in range(num_vert)
...         for v in indices[indptr[u]:indptr[u+1]]]
>>> adj_matrix = scipy.sparse.csr_array((data, indices, indptr))
>>> # create multigraph with desired order of neighbors
>>> g = hpw.Multigraph(adj_matrix)
>>> for u in range(num_vert):
...     print(g.neighbors(u))
[0 1 2 3 4]
[1 2 3 4 0]
[2 3 4 0 1]
[3 4 0 1 2]
[4 0 1 2 3]
>>> # checking if multigraph was created properly
>>> np.all(np.array(
...         [g.number_of_edges(u, v) == u + v + 1
...         for u in range(num_vert)
...         for v in range(num_vert)]) == True)
True

Weighted Graphs

You can create a weighted graph by passing its adjacency matrix. The adjacency matrix entries are real values that represent the edge weights.

>>> # creating the adjacency matrix of a complete weighted graph
>>> num_vert = 5
>>> adj_matrix = np.zeros((num_vert, num_vert))
>>> for i in range(num_vert):
...     for j in range(num_vert):
...         adj_matrix[i, j] = (i + j)/10
...
>>> # creating weighted
>>> g = hpw.WeightedGraph(adj_matrix)
>>> adj_matrix2 = g.adjacency_matrix().todense()
>>> np.all(np.isclose(adj_matrix, adj_matrix2))
True

Weighted graphs are used to create continuous-time quantum walks (hiperwalk.ContinuousTime).

Order of Neighbors

The order of neighbors does not play a crucial role in the continuous-time quantum walk. Even so, you can specify the order of neighbors in weighted graphs using commands akin to those used for multigraphs.