Re: Conversion to graph adjacency list

On Fri, Dec 7, 2018 at 10:51 PM <[email protected]> wrote:
>
> Hi,
>
> Scipy library provides C-implementation for some classical graph
algorithms like Kruskal or connected component finding. Nevertheless, there
is an efficiency problem: sparse graphs are usually given by list of edges
or adjacency list (and not adjacency matrix). And in order to run the Scipy
routines, we have to convert our graphs to the compressed SCR format (dense
array is not well suited for graph with a lot of vertices, say more than
20,000). And sometimes, after execution we have to convert back. This
causes the routine spending most of the execution time in conversion and
retro-conversion tasks.
>
> So my question is: does Scipy provide a C-routine for converting and back
converting to edge/adjacency list format?

How are you currently doing the conversion? The most efficient method is
probably to convert from the CSR format to COO, which provides two parallel
arrays giving the row and column indices of the edges. These can be simply
zip()ed together to get a list of edge tuples.

|30> import numpy as np

|31> Nnodes = 20000

|32> edges = []

|33> for i in range(Nnodes):
...>     js = np.random.permutation(Nnodes)[:int(np.sqrt(Nnodes))]
...>     edges.extend([(i, j) for j in js])
...>

# Construct a CSR matrix of the graph, reasonably efficiently.

|35> from scipy import sparse

|36> row_ind, col_ind = np.transpose(edges)

|37> Gcsr = sparse.csr_matrix((np.ones_like(row_ind), (row_ind, col_ind)),
shape=(Nnodes,
...>  Nnodes))

# Now convert back to a list of edge tuples.

|39> Gcoo = Gcsr.tocoo()

|40> coo_edges = zip(Gcoo.row, Gcoo.col)

|41> set(edges) == set(coo_edges)
True

--
Robert Kern

_______________________________________________
SciPy-User mailing list
[email protected]
https://mail.python.org/mailman/listinfo/scipy-user