[graph-tool] Slow filling graph

24 Nov 2018

      Hi 

I was experimenting Kruskal performance against a data file for 100 graphs (n, m<20000) : 

# =================================================
from time import clock
from sys import stderr, stdin

import graph_tool as gt
from graph_tool.topology import min_spanning_tree  

import networkx as nx

# ------------ NetworkX Code ---------------------------

def kruskal_networkX(edges, n):
    G=nx.Graph()
    for a, b, w in edges:
        G.add_edge(a,b,weight=w)
    return sum(d['weight'] for (_,_,d) in nx.minimum_spanning_tree(G).edges(data=True))

# ------------ Graph_tool Code ---------------------------

def kruskal_gt(wedges,n):
    g= gt.Graph(directed=False)
    edges, weights= zip(*[((a,b),w) for (a,b,w) in wedges])
    weight = g.new_edge_property("long long")
    for a,b,w in wedges:
        e=g.add_edge(a,b)
        weight[e]=w
    tree=min_spanning_tree(g, weights=weight)
    return sum(b*weight[e] for (e,b) in zip(g.edges(), tree))

# ------------ Benchmark ---------------------------

def go(solver, L):
    global duration

    N=len(L)
    k=1

    while k<N:
        edges=[]
        n=L[k]
        k+=1

        for a in range(n):
            d=L[k]
            k+=1
            for j in range(d):
                b=L[k]
                k+=1
                w=L[k]
                k+=1
                if a<b:
                    edges.append([a,b-1,w])
        start=clock()
        print(solver(edges, n))
        print("----------------------------")
        duration+=clock()-start

# data
L=list(int(z) for z in stdin.read().split() if z.isdigit())

for solver in [kruskal_networkX, kruskal_gt]:
    duration=0
    go(solver, L)
    print("%s : %.3f" %(solver.__name__, duration), file=stderr)

# =================================================

Outputs are in agreement but gt execution is very slow:

$ python3 gt.py < big.in > bench.out 
kruskal_networkX : 15.721
kruskal_gt : 134.839

the bottleneck being within the following loop-filling the graph:

# --------------------------------------------
    for a,b,w in wedges:
        e=g.add_edge(a,b)
        weight[e]=w
# --------------------------------------------

Probably, i'm filling the graph in the wrong way.

You can dowload the data file here:
https://drive.google.com/file/d/1y0fX1kopgzQEWgmRHRnouWHnMkuliwfw/view?usp=s...

[graph-tool] Slow filling graph

elastica＠laposte.net