How to convert c++ vector<vector<int>> adjacency matrix to igraph_matrix_t

Usage
1

I have a question about how to convert my adjacency matrix to igraph_matrix_t type.
The following is my adjacency matrix code:

vector<vector<int>> generateMatrix(const int v, vector<vector<int>> adjMat)
{
    int i,j;
    for(i=0; i<v; i++){
        for(j=0; j<v; j++){
            adjMat[i].push_back(rand() % 2);
        }
    }
    return adjMat;
}

vector<vector<int>> adjMat(v);

adjMat = generateMatrix(v, adjMat);

I want to call igraph_adjacency this function, how do I convert vector type to igraph_matrix_t type.

2

Dense adjacency matrices are an extremely inefficient way to represent sparse graphs. Avoid this if memory use is a concern to you (you mentioned earlier that it is).

If you want to use matrices anyway: Instead of generating the matrix in a different format and then converting to an igraph_matrix_t, generate it directly as an igraph_matrix_t. Element i, j is accessed as MATRIX(mat, i, j). There are more docs here.

If you still want to use your own format, then you need to copy to the igraph_matrix_t element-wise.

Note that a std::vector<std::vector<...>> is a poor representation for matrices, as storage is not contiguous, so access is inefficient. There are also no guarantees that the matrix is not ragged.

In the future please use code blocks for code, not quotation blocks.

1 Like
3

Thank you for your reply. You suggestions is really useful, save my lots of times.
I have a question about how to generate random sparse matrix with fixed column value (lengths) and row value (lengths).
Right now I am using the igraph_sparsemat_init_diag to generate sparse matrix, and use this sparse matrix to generate the sparse graph.

    igraph_t g_sparse;
    igraph_vector_t av;
    igraph_sparsemat_t a;
    igraph_vector_init(&av, 10000);
    igraph_sparsemat_init_diag(&a, 50000, &av, 1);
    igraph_sparsemat(&g_sparse, &a, 0);

    igraph_vector_init(&modularity, 0);
    igraph_matrix_int_init(&merges, 0, 0);

    igraph_community_walktrap(&g_sparse,
                              NULL /* no weights */,
                              4 /* steps */,
                              &merges, &modularity,
                              /* membership=*/ NULL);

By doing this, I found that my sparse matrix’s all entry are set to zero. I want to randomly set my entry between 1 or 0 (that can better simulate the similarity between each vertex). I found there is a function call igraph_sparsemat_entry can set the value for each entry, but actually its quite slow if I set the value using for loop. Is there a way can initialize the sparse matrix to set each entry a random value? That means I want to generate a sparse matrix and set all entry in a random value rather than zero.

4

What I found to generate the random sparse matrix is by using igraph_sparsemat_entry method:

    for(int i=0; i<v; i++){
        for(int j=0; j<v; j++){
            igraph_sparsemat_entry(&a,i, j, rand() % 2);
        }
    }

But its seems like time cosuming… So is there a better way to generate a random sparse matrix?

5

Why do you insist on using adjacency matrices instead of using graphs directly?

What do you mean by “column value”?

What you describe is the G(n,p) random graph model, also called a Bernoulli random graph, with p=\frac{1}{2}. You can generate such a graph using igraph_erdos_renyi_game_gnp().

igraph_sparsemat_entry() is not slow. It is amortized constant time. It essentially keeps appending to to the three arrays making up the triplet format sparse matrix, doubling the array size whenever it runs out of storage, no different from std::vector::push_back().

The workflow to creating a sparse matrix is to first add elements one by one to a triplet format, then convert to a compressed format. After this no more elements can be added.

That said, why do you insist on using matrices? This won’t be useful unless you are going to perform linear algebra operations.

1 Like
6

:joy:Thank you for your reply.
The reason I insist to using adjacency matrices because our project is based on python, and my manager told me he want to optimize the memory usage, and ask me to use ctypes to call the igraph/c function in python. Our python code is calculate the similarity first, then generate an adjacency matrices, and I need to transfer this adjacency matrices(which is numpy format) from python to cpp, and using the cpp to process the rest part. So in this case I have to use adjacency matrices to generate sparse matrix graph.
The following are our sample code for generating the adjacency matrix:

def get_simlarity_matrix(feature_vec,similar_threshold):
    simlarity_matrix_np = cosine_similarity(feature_vec)
    simlarity_matrix_np[np.where(simlarity_matrix_np<similar_threshold)]=0
    return simlarity_matrix_np

The consine_similarity function return type is ndarray, this is the reason why I insist to use the adjacency matrices. I need to use simlarity_matrix_np which is an ndarray, and passing this variable from python to cpp to generate the graph and run walktrap algorithm.

7

It seems that you are generating a full density matrix here:

so it seems you are already using a full matrix (which uses by far the most memory). It might help more to address that part than to address others later (sparse) parts.

At any rate, simply converting the resulting simlarity_matrix_np to a scipy.sparse format (COO in particular), using scipy.sparse.coo_matrix, and then passing the sparse graph to Graph.Adjacency (or its weighted counterpart) will be about as efficient as you can get.

Running the walktrap algorithm in C or Python should not make a difference (as @szhorvat already explained here). (Unless the VertexDendrogram consumes a lot of memory, perhaps you can confirm this is not the case @iosonofabio or @tamas)?

1 Like
8

Thank you for your reply. I import scipy.sparse.coo_matrix, the code is like following:

    simlarity_matrix_np = sp.coo_matrix(simlarity_matrix_np)

    g = ig.Graph.Adjacency(simlarity_matrix_np, mode='undirected', attr='sim')

But I got this error:

  File "/data/home/z/PycharmProjects/pythonProject1/walktrap_v1/run_walktrap.py", line 392, in get_adjacency_simlarity_matrix
    g = ig.Graph.Adjacency(simlarity_matrix_np, mode='undirected', attr='sim')
  File "/data/home/z/PycharmProjects/pythonProject1/venv/lib64/python3.6/site-packages/igraph/__init__.py", line 2160, in Adjacency
    return _graph_from_sparse_matrix(cls, matrix, mode=mode)
  File "/data/home/z/PycharmProjects/pythonProject1/venv/lib64/python3.6/site-packages/igraph/sparse_matrix.py", line 85, in _graph_from_sparse_matrix
    [],
  File "/data/home/z/PycharmProjects/pythonProject1/venv/lib64/python3.6/site-packages/igraph/sparse_matrix.py", line 84, in <genexpr>
    ([e] * n for e, n in nedges.items()),
TypeError: can't multiply sequence by non-int of type 'numpy.float64'

TypeError: can’t multiply sequence by non-int of type ‘numpy.float64’, how should I fix this error?

9

Now I got this error, by calling walktrap algorithm in python. My igraph version is 0.9.11. I know there is a bug very similar with my problem https://github.com/igraph/igraph/issues/2042. But I found that this problem should be fixed at version 0.9.9 right? My igraph version is 0.9.11, is it a proper version to run walktrap algorithm?

igraph._igraph.InternalError: Error at src/community/community_misc.c:111: Number of steps is greater than number of rows in merges matrix: found 498 steps, 307 rows. -- Invalid value
10

Now this problem has been fixed by set up the sp.coo_matrix function return value to int type.

    simlarity_matrix_np = sp.coo_matrix(simlarity_matrix_np, dtype=np.int32)
11

I fixed this error already by updating my igraph version. I update my igraph version from 0.9.11 to 0.10.4.

igraph._igraph.InternalError: Error at src/community/community_misc.c:111: Number of steps is greater than number of rows in merges matrix: found 498 steps, 307 rows. -- Invalid value
12

Just making sure that people looking here: this same question is also asked (and answered) in this separate topic: Python ig.Graph.Adjacency TypeError: can't multiply sequence by non-int of type 'numpy.float64' - #2 by vtraag

1 Like