Re: [graph-tool] Slow filling graph

[elastica]

Hi Alexandre and thanks for your useful response


The *add_edge_list* internally changes edges ordering to the lexicographic
one so in order to set weights, I have to sort the weighted-edge list,
adding some little overhead. On the other hand, *add_edge_list()* is much
more efficient than adding edges one by one with the add_edge method (about
7 times faster!). Unfortunately, this is still slow, even slower than
NetworkX (about 1.2 times slower and we all know that NetworkX highest
quality is not speed).

Here is the new version:

# ***********************
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):
    wedges.sort()
    g= gt.Graph(directed=False)
    edges, weights= zip(*[((a,b),w) for (a,b,w) in wedges])
    weight = g.new_edge_property("long long")
    g.add_edge_list(edges)
    for e,(_,_,w) in zip(g.edges(), wedges):
        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&lt;b:
                    edges.append([a,b-1,w])
        start=clock()
        print(solver(edges, n))
        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(&quot;----------------------------&quot;)
    print(&quot;%s : %.3f&quot; %(solver.__name__, duration), file=stderr)

# ***********************



$ python3 gt_v2.py &lt; big.in > gt.out             
kruskal_networkX : 15.851
kruskal_gt : 19.713



--
Sent from: 
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
_______________________________________________
graph-tool mailing list
graph-tool@skewed.de
https://lists.skewed.de/mailman/listinfo/graph-tool