vtraag / libleidenalg Goto Github PK

View Code? Open in Web Editor NEW

12.0 12.0 7.0 2.76 MB

C++ library of Leiden algorithm

License: GNU General Public License v3.0

C 0.10% C++ 91.44% CMake 8.46%

libleidenalg's People

Contributors

Stargazers

Watchers

Forkers

theaeon szhorvat ellingtonkirby emollier wolfram77 henryhollis

libleidenalg's Issues

Graph::Graph() constructor is broken

The Graph::Graph() constructor, with no arguments, seems broken, as it only creates the igraph_t struct, but does not initialize it.

https://github.com/vtraag/libleidenalg/blob/main/src/GraphHelper.cpp#L262

Actually, I am wondering if this constructor makes sense at all. If it were to create an empty graph, one would still want to add vertices and edges to it. There are no member functions that I can find to do this. Simply getting the igraph_t pointer and adding to it may not be appropriate, as the edge and vertex weights, stored separately, would also need to be updated to make sure they match in length.

The cleanest solution here may be to just remove this constructor entirely, and let people create their own igraph_t.

On a related note, would it be better to use const igraph_t * throughout, both in constructors, for Graph::_graph and get_igraph()? The constness could be cast away in those exceptional cases when the igraph_t is managed internally. Reasoning: it is not valid to modify the graph returned by get_igraph(), as doing so may cause a mismatch between the graph and the vertex/edge weight vectors.

Weird partitioning results when using C++

I’ve been using the Leiden partitioning algorithm in both R and C++. The R partitions work fine, but am getting weird results using C++. For the following graph (in LGL):

# 0
5 0.562268614768982
7 0.446964800357819
10 0.462509661912918
14 0.393828451633453
# 1
2 1
12 0.721999883651733
# 2
7 1
9 0.641682505607605
# 3
5 0.555652022361755
10 0.50146621465683
11 0.556933224201202
17 0.492925316095352
# 4
9 0.515104532241821
10 0.511390089988708
11 0.557224869728088
14 0.445745885372162
17 0.515426933765411
# 5
6 1
8 0.803642749786377
10 1
13 0.761196434497833
# 6
8 0.928025543689728
11 1
13 0.816621780395508
14 1
16 0.873375415802002
# 7
8 0.755056202411652
# 8
12 0.785851180553436
# 9
11 0.407902479171753
12 0.611177921295166
13 0.696912944316864
# 10
11 0.985303699970245
13 0.741263210773468
16 0.748125731945038
18 0.685651421546936
# 11
15 1
18 0.979115962982178
# 13
14 0.446562558412552
17 0.537507653236389
# 14
16 0.751221001148224
# 17
18 0.883056044578552

When I partition this in R, I get:

library(igraph)
library(leiden)
library(leidenAlg)
g = read_graph( 'subgraph.lgl', format='lgl')
adjacency_matrix <- igraph::as_adjacency_matrix(g)
partition <- leiden(adjacency_matrix)
table(partition)

partition
1 2 3
7 6 6

Membership:
1: 3, 4, 10, 11, 15, 17, 18
2: 0, 5, 6, 10, 13, 14
3: 1, 2, 7, 8, 9, 12

This seems reasonable.

When I run the following MRE in C:

#include "igraph/igraph.h"
#include "libleidenalg/GraphHelper.h"
#include "libleidenalg/Optimiser.h"
#include "libleidenalg/CPMVertexPartition.h"
#include <stdio.h>
#include <map>
#include <bits/stdc++.h>

using std::cout;
using std::endl;

using namespace std;

int main(int argc, char *argv[]) {
        igraph_set_attribute_table(&igraph_cattribute_table);

        igraph_t sg;

        printf( "Reading the graph.\n" );
        FILE *in_graph = fopen( "subgraph.lgl", "rt" );
        igraph_read_graph_lgl( &sg, in_graph, true, IGRAPH_ADD_WEIGHTS_YES, false );
        fclose(in_graph);
        printf( "Graph reading done.\n" );

        Graph graph(&sg);
        CPMVertexPartition part(&graph, .05 );
        Optimiser o;

        igraph_vector_t w;
        vector<double> wt;
        int ecount = igraph_ecount(&sg);
        int vcount = igraph_vcount(&sg);
        vector<bool> const is_membership_fixed(vcount, false);

        igraph_vector_init( &w, ecount );
        vector<MutableVertexPartition*> partitions(1);
        partitions[0] = &part;
        EANV(&sg, "weight", &w);
        for ( int i=0; i<igraph_vector_size(&w); i++ )
                wt.push_back( VECTOR(w)[i] );
        // Use weights.
        o.optimise_partition(partitions, wt, is_membership_fixed);
        // Don’t use weights.
        //o.optimise_partition(&part);
        igraph_vector_destroy( &w );

        for (int i = 0; i < part.membership().size(); ++i) {
                printf( "%d\t%d\n ", i, part.membership(i) );
        }
}

… and compile with …

g++ -I$HOME/install/include -L$HOME/install/lib64 MRE_partition.c -o MRE_partition -O2 -I/ocean/projects/ibn210001p/mbower/install/include -L/ocean/projects/ibn210001p/mbower/install/lib64 -std=c++11 -llibleidenalg -ligraph

… I get the following output:

$ ./MRE_partition
Reading the graph.
Graph reading done.
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0

I don’t recall where I found the example C++ code, so I cannot tell whether I’ve copied it correctly.

Besides this MRE described here (where the error might lay with reading the graph file), I have encountered similar weird graph clusterings where a graph file was not loaded. For example, I got the following cluster IDs for a different graph:

0		0
1		3
2		4
3		0
4		0
5		1
6		2
7		5
8		0
9		6
10		2
11		1
12		7
13		0
14		1
15		8
19		0
20		1
21		0
22		9
23		0
24		1072464398
25		-536870912
26		1072610043
27		0
28		1072645266

… and so on.

Am I just reading partition memberships from the wrong address?

Example of Optimiser use in C++ code

It would be helpful to have a simple example in C++ using the Optimizer to partition a graph. In particular, it would be helpful to see how to set specific, required variables prior to initializing Optimizer. Thank you!

Freeing memory

From the example:

                Graph graph(&sg);
                CPMVertexPartition part(&graph, 0.05 /* resolution */ );
                Optimiser o;
                o.optimise_partition(&part);

How can all of these objects (graph, parth, o) be deleted? I see destructors for them in the source code, but cannot find the correct syntax for calling them.

Linking problem, undefined reference

These errors appear to be internal to the libleidenalgo code:

$ g++ -I$HOME/install/include -L$HOME/install/lib64 example_leiden.c -o example_leiden -ligraph -llibleidenalg
/jet/home/mbower/install/lib64/liblibleidenalg.a(GraphHelper.cpp.o): In function `Graph::has_self_loops()':
GraphHelper.cpp:(.text+0x1cdb): undefined reference to `igraph_has_loop'
/jet/home/mbower/install/lib64/liblibleidenalg.a(Optimiser.cpp.o): In function `Optimiser::Optimiser()':
Optimiser.cpp:(.text+0x6f): undefined reference to `igraph_rngtype_mt19937'
collect2: error: ld returned 1 exit status
$

Trying to set node attributes in C

Here is an MRE that tries to set the "name" attribute of each vertex to the digits [0,4], along with the printed output:

`#include <igraph/igraph.h>
#include

using namespace std;

int main(int argc, char *argv[]) {
igraph_vector_int_t gtypes, vtypes, etypes;
igraph_strvector_t gnames, vnames, enames;

    igraph_vector_int_init(&gtypes, 0);
    igraph_vector_int_init(&vtypes, 0);
    igraph_vector_int_init(&etypes, 0);
    igraph_strvector_init(&gnames, 0);
    igraph_strvector_init(&vnames, 0);
    igraph_strvector_init(&enames, 0);

    igraph_set_attribute_table(&igraph_cattribute_table);

    igraph_t g;
    igraph_vector_int_t v;
    igraph_vector_int_init( &v, 10 );
    VECTOR(v)[0] = 0;
    VECTOR(v)[1] = 1;
    VECTOR(v)[2] = 0;
    VECTOR(v)[3] = 2;
    VECTOR(v)[4] = 0;
    VECTOR(v)[5] = 3;
    VECTOR(v)[6] = 1;
    VECTOR(v)[7] = 3;
    VECTOR(v)[8] = 2;
    VECTOR(v)[9] = 4;

    igraph_create(&g,&v,0,IGRAPH_UNDIRECTED);

    /* Add names */
    igraph_vector_t names;
    igraph_vector_init_range(&names, 0, igraph_vcount(&g));
    for ( int i=0; i<igraph_vcount(&g); i++ ) {
            VECTOR(names)[i] = i;
    }
    printf( "%s\n", VECTOR(names)[0] );
    SETVANV( &g, "name", &names );

    /* Can you plot it? */
    igraph_matrix_t coords;
    igraph_matrix_init(&coords, 0, 0);
    igraph_layout_reingold_tilford(&g, &coords, IGRAPH_ALL, 0, 0);
    int n=igraph_vcount(&g);
    for (long i=0; i<n; i++) {
            printf("%s %6.3f %6.3f\n", VAN(&g, "name", i), MATRIX(coords, i, 0), MATRIX(coords, i, 1));
    }

    igraph_vector_int_destroy( &v );
    igraph_destroy( &g );

}

$ ./MRE_graphNamedVertices

name 0.000 0.000
name 1.000 -1.000
name 2.000 0.000
name 3.000 1.000
name 4.000 0.000
$`

How should these values be set and accessed?

vtraag / libleidenalg Goto Github PK

libleidenalg's People

Contributors

Stargazers

Watchers

Forkers

libleidenalg's Issues

Graph::Graph() constructor is broken

Weird partitioning results when using C++

Example of Optimiser use in C++ code

Freeing memory

Linking problem, undefined reference

Trying to set node attributes in C

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent