Problems with remove_parallel_edges

Hi Tiago,

I'm experimenting some problems with the remove_parallel_edges function. It
seems that some edges are removed randomly. I attach some reproducible code
to test.

Let's suppose the following dot graph file:

graph G{
1--2
2--1
1--3
3--1
2--3
3--2
}

It is basically an undirected graph with a triangle shape with parallel
edges. The following code loads the graph, removes parallel edges and
calculate clustering coefficient. I repeat it ten times.

for i in range(0,10):
    aux = gt.load_graph("/tmp/sampleGraph.dot",format="dot")
    gt.remove_parallel_edges (aux)
    clust=gt.local_clustering (aux)
    gt.vertex_average (aux,clust)

This operation is supposed to generate a tuple (1.0, 0.0), the problem is
that randomly the generated output is wrong. For example:

Out[111]: (1.0, 0.0)
Out[111]: (1.0, 0.0)
Out[111]: (1.0, 0.0)
Out[111]: (1.0, 0.0)
Out[111]: (0.0, 0.0)
Out[111]: (1.0, 0.0)
Out[111]: (1.0, 0.0)
Out[111]: (1.0, 0.0)
Out[111]: (1.0, 0.0)
Out[111]: (1.0, 0.0)

I have plotted the graph and I have found, that sometimes one edge is
completely removed modifying the final result.

I attach my show_config output.

gt.show_config ()
version: 2.2.5 (commit 3ba24072, Sun Feb 21 00:46:41 2010 +0100)
gcc version: 4.4.1
compilation flags: -I/usr/include/python2.6 -I/usr/include
-I/usr/lib/python2.6/dist-packages/numpy/core/include/numpy
-I/usr/lib/python2.6/dist-packages/scipy -O3 -Wall -ftemplate-depth-150
-Wno-deprecated -O99 -fvisibility=default -fvisibility-inlines-hidden
-fopenmp -Wl,-Bsymbolic-functions -L/usr/lib/python2.6 -lpython2.6
install prefix: /usr
python dir: /usr/lib/python2.6/dist-packages
graph filtering: True
openmp: True
uname: Linux host 2.6.31-22-generic #60-Ubuntu SMP Thu May 27 02:41:03 UTC
2010 x86_64

Kind regards,

Juan

attachment.html (2.39 KB)

Hi Juan,

I'm experimenting some problems with the remove_parallel_edges
function. It seems that some edges are removed randomly. I attach
some reproducible code to test.

Indeed, this was a race condition caused when OpenMP is enabled and
undirected graphs are used. I have fixed this in the git version.

If you want a quick workaround, you can disable OpenMP by setting the
environment variable:

    export OMP_NUM_THREADS=1

Thanks for finding this stuff out! :slight_smile:

Cheers,
Tiago

Thanks your for great work Tiago.

Cheers,

Juan

attachment.html (1.43 KB)