How to develop a sparse, weighted adjacency example?

Usage
1

I want to implement a graph in C with perhaps millions of vertices, but with local connectivity. A sparse matrix would be best to represent connections to an igraph constructor. I found the command “igraph_sparse_weighted_adjacency” in the igraph manual and it compiles, but then generates errors when I try to run it. I cannot find an example using this command in the manual, examples, or online. The following MRE creates an igraph_sparse_matrix and uses it to call igraph_sparse_weighted_adjacency:

#include<igraph.h>

int main(int argc, char *argv[]) {
        igraph_t g;
        igraph_sparsemat_t spA, spB;
        igraph_vector_t weights;

        int sz = 100000;
        int ns = 1000;
        int rows[ns], cols[ns];
        for ( int i=0; i<ns; i++ ) {
                rows[i] = rand() % sz;
                cols[i] = rand() % sz;
        }

        igraph_sparsemat_init( &spA, sz, sz, ns );
        igraph_vector_init( &weights, ns );
        for (int i = 0; i < ns; i++) {
                igraph_integer_t r = rows[i];
                igraph_integer_t c = cols[i];
                igraph_sparsemat_entry(&spA, r, c, 1);
                igraph_vector_set( &weights, i, 1 );
        }
        /* Compress into spB */
        igraph_sparsemat_compress(&spA, &spB);
        /* Create igraph */
        igraph_sparse_weighted_adjacency(&g, &spA, IGRAPH_ADJ_UNDIRECTED, &weights, IGRAPH_LOOPS_ONCE);
//        igraph_sparse_weighted_adjacency(&g, &spB, IGRAPH_ADJ_UNDIRECTED, &weights, IGRAPH_LOOPS_ONCE);
        /* Destroy spB */
        igraph_sparsemat_destroy(&spA);
        igraph_sparsemat_destroy(&spB);
}

This compiles, but I when I run it, I get one of two errors, depending on which form of sparse matrix I send to the function (either spA or spB):

spA: Error at src/core/sparsemat.c:784 : Cannot remove duplicates from sparse matrix - Failed.
spB: Error at src/constructors/adjacency.c:1374 : Adjacency matrix is non-square. - Non-square matrix.

What is the correct format for the input variables to this function in C?

2

First of all, you should probably not be using sparse matrices at all. Are you planning to perform linear algebra operations on the adjacency matrix? If not, do not use sparse matrices.

What you are doing here is essentially:

  • Build an edge list
  • Construct a sparse matrix from the edge list
  • Construct a graph from the sparse matrix

Why don’t you construct the graph from the edge list directly? See igraph_create().

Now for the direct answer:

Most sparse matrix operations are only possible on compressed format matrices. The documentation as well as the error messages should be improved here. So yes, you need to compress the matrix.

But your matrix is not symmetric, so it does not describe an undirected graph. Hence the error.

This again illustrates that it is much easier to work with the edge list directly than going through a sparse matrix representation and dealing with symmetrization.

Use VECTOR(weights)[i] = 1 for better performance.

3

You have described my goal well and your suggestion makes sense. I am having trouble implementing it. All of the examples I can find use explicit arrays of edges, but my graph has millions of edges. This compiles, but has a run-time error (Invalid (odd) edges vector. - Invalid edge vector):

#include<igraph.h>

int main(int argc, char *argv[]) {
        igraph_t g;
        igraph_vector_int_t v;
        igraph_integer_t *edges = (igraph_integer_t *) malloc( 2 * sizeof(igraph_integer_t) );
        edges[0] = 0;
        edges[1] = 1;

        igraph_vector_int_view(&v,edges,sizeof(edges)/sizeof(edges[0]));
        igraph_create(&g,&v,0,IGRAPH_UNDIRECTED);
}

I suppose, then, that my question is "How do I define a (possibly quite large) array of type ‘igraph_integer_t’?

4

sizeof(edges)/sizeof(edges[0]) is incorrect here. edges is not of an array type, but a pointer. The size of the buffer that it is pointing to is not known at compile time.

This construct would be appropriate if you declared edges as igraph_integer_t edges[2];, but not with igraph_integer_t *edges; In the latter case you need to keep track of the buffer size yourself; it cannot be left to the compiler.

5

Yes, of course! It was copied from the example in the manual that uses a declared array. I just wasn’t thinking. Thank you!

6

Generally, you can create a vector using igraph_vector_int_init() and fill that with your values. When you are done using it, deallocate it using igraph_vector_int_destroy().

If you already have a vector of values, of the same type as igraph_integer_t, and in the appropriate source, target format, then you can use igraph_vector_int_view() to wrap this array with a read-only igraph_vector_int_int. Otherwise, just create a new igraph vector v, and you can write in it using the syntax VECTOR(v)[i] = something.