1
\$\begingroup\$

I'm working on graph mining, so I'm trying to find the best library to do that. I've read in here that "graph-tool" is faster, so I tried the same program who count the duplicated graphs (I call them frequent in the program) in networkx and graph-tool.

The graph are in this .txt file:

t # 0
v 0 0
v 1 3
v 2 9
e 2 1 68
e 0 1 10
e 0 2 4
t # 1
v 0 2
v 1 11
v 2 6
v 3 10
v 4 18
v 5 14
e 0 1 15
e 2 5 19
e 1 3 20
t # 2
v 0 6
v 1 11
e 0 1 13
t # 3
v 0 2
v 1 11
v 2 19
v 3 2
e 0 1 15
e 1 2 11
e 0 3 19
t # 4
v 0 1
v 1 16
v 2 14
e 0 1 8
e 1 2 5
e 0 2 19

Networkx program:

import networkx as nx 
from networkx.algorithms import isomorphism
#from collections import Counter
import time
ti=time.time()
# read graphs from file.
def readGraphFile(graphFile):
    G_list = []
    indice = []
    frequence_list = []
    frequentgraphs = []
    frequentfreqs=[]

    appearance = [] #store the appearance of the frequent pattern
    fp = open(graphFile, "r+")
    lines = [line for line in fp.read().splitlines() if line]
    for line in lines:
        data = line.split()
        if data[0] == 't':
            if (len(data) < 3):
                print 'Graph header line error...'
            else:
                g = nx.Graph()
                G_list.append(g)
                indice.append(data[2])
                #G_list[ map(int, data[4:])] = g


        elif data[0] == 'v':
            data = line.split()
            if (len(data) < 3):
                print 'Node data line error...'
            else:
                g.add_node(data[1], attrib = data[2])
                #as node graph transaction format is single value, use attrib as a common noun for all attrib
        elif data[0] == 'e':
            if (len(data) < 4):
                print 'Edge data line error...'
            else:
                g.add_edge(data[1], data[2])
        else:
            print line
            print '!!! Invalid graph data line...!!!'
    graphdic = dict(zip(G_list, indice))

    #print(graphdic)  

    print '= = = = = Finished reading {} graphs from the file'.format(len(G_list)) + '= = = = ='
    #print 'Total graphs in list: ', 
####Frequency Algorithm #####
    ta=time.time()    
    i=0
    cnt=0
    #inc=0;    
    for gr in G_list:


        for c in G_list: 
                if (nx.is_isomorphic(gr,c)): cnt+= 1
                #if (isomorphism.GraphMatcher(gr,c).subgraph_is_isomorphic):inc+= 1


        print ("graph:{} frequence:{} ".format(i,cnt))
        frequence_list.append(cnt)
        cnt=0
        i+= 1
        print("-----------------------")


    freqdic = dict(zip(G_list,frequence_list))
    print("\n=x=x=x=x=x=x=x=x=x=x=x=x=")
    #try: seuil=float(raw_input('Entrer un Sieul:'))
    #except ValueError: print ("float")
    for gr, fr in freqdic.iteritems():
        if fr >= 2: 
            frequentgraphs.append(gr)
            frequentfreqs.append(fr)

    frequentgraphsdic= dict(zip(frequentgraphs,frequentfreqs))
    print("\n=x=x=x=x=x=x=x=x=x=x=x=x=\n frequent items:{}\n".format(len(frequentgraphs)))
    #print(frequentgraphsdic)

    print("* * * * * D O N E * * * * * ")    
    print("RUNNING TIME: {}s".format(time.time()-ti))    
    print("Reading from file: {}s".format(ta-ti))    
    print("Algo: {}s".format(time.time()-ta))    

#############################    





#programme pricipale    
def  main():
    readGraphFile("5.txt")

if __name__ == '__main__': main()

Graph-tool program:

#import networkx as nx 
#from networkx.algorithms import isomorphism
from graph_tool.all import *
import graph_tool.all as gt
#from collections import Counter
import time
ti=time.time()
# read graphs from file.
def readGraphFile(graphFile):
    G_list = []
    indice = []
    v_indice = []
    e_indice=[]
    frequence_list = []
    frequentgraphs = []
    frequentfreqs=[]
    #appearance = [] #store the appearance of the frequent pattern
    fp = open(graphFile, "r+")
    lines = [line for line in fp.read().splitlines() if line]
    for line in lines:
        data = line.split()
        if data[0] == 't':
            vdic={}
            vdic.clear()
            if (len(data) < 3):
                print("Graph header line error...")
            else:
                g = Graph()
                v_label = g.new_vertex_property("int")              
                v_num = g.new_vertex_property("int")
                e_label = g.new_edge_property("int")
                G_list.append(g)
                indice.append(int(data[2]))
                #G_list[ map(int, data[4:])] = g

        elif data[0] == 'v':
            data = line.split()            
            if (len(data) < 3):
                print 'Node data line error...'
            else:
                #g.add_node(data[1], attrib = data[2])
                v=g.add_vertex()
                v_num[v]= int(data[1])               
                v_label[v] = int(data[2])
                vdic[int(data[1])]=int(data[2])
                #as node graph transaction format is single value, use attrib as a common noun for all attrib
        elif data[0] == 'e':            
            if (len(data) < 4):
                print 'Edge data line error...'
            else:
                #print(vdic)
                v1=g.add_vertex()               
                #vdic[int(data[1])]
                v_label[v1] = vdic[int(data[1])]                
                v2=g.add_vertex()
                v_label[v2] = vdic[int(data[2])]
                e1 = g.add_edge(v1,v2)
                e_label[e1]=int(data[3])               

        #else:
            #print line
            #print '!!! Invalid graph data line...!!!'
    graphdic = dict(zip(G_list, indice))

    #print(graphdic)  

    print '= = = = = Finished reading {} graphs from the file'.format(len(G_list)) + '= = = = ='

####Frequency Algorithm #####
    ta=time.time()    
    i=0
    cnt=0
    #inc=0;    

    for gr in G_list:                
        for c in G_list:
            if (gt.isomorphism(gr,c)): 
                cnt+= 1                            
                print("iso")
        print ("graph:{} frequence:{} ".format(i,cnt))        
        frequence_list.append(cnt)
        cnt=0
        i+= 1
        print("-----------------------")


    freqdic = dict(zip(G_list,frequence_list))
    print("\n=x=x=x=x=x=x=x=x=x=x=x=x=")
    #try: seuil=float(raw_input('Entrer un Sieul:'))
    #except ValueError: print ("float")
    for gr, fr in freqdic.iteritems():
        if fr >= 2: 
            frequentgraphs.append(gr)
            frequentfreqs.append(fr)

    frequentgraphsdic= dict(zip(frequentgraphs,frequentfreqs))
    print("\n=x=x=x=x=x=x=x=x=x=x=x=x=\n frequent items:{}\n".format(len(frequentgraphs)))
    #print(frequentgraphsdic)

    print("* * * * * D O N E * * * * * ")    
    print("RUNNING TIME: {}s".format(time.time()-ti))    
    print("Reading from file: {}s".format(ta-ti))    
    print("Algo: {}s".format(time.time()-ta))    

#############################    





#programme pricipale    
def  main():
    readGraphFile("5.txt")

if __name__ == '__main__': main()

Results:

Networkx >>> RUNNING TIME>>> 0.00204300880432s
graph-tool>>>RUNNING TIME>>> 0.0780489444733s

I'm not sure if my graph-tool program needs amelioration or if that is the best performance.

\$\endgroup\$
  • \$\begingroup\$ Hi. Welcome to Code Review! It would be helpful if you'd add a problem statement that explains what the code is supposed to do. I.e. something more specific than "graph mining". What's the output supposed to be? Why? \$\endgroup\$ – Brythan Feb 24 '15 at 0:10
  • \$\begingroup\$ The program count the duplicated graphs (I call them frequents) \$\endgroup\$ – Mohsenuss91 Feb 24 '15 at 8:47
1
\$\begingroup\$

Printing to the terminal is slow, and I notice the second version has a print call in an inner loop where the first version has not:

    for c in G_list:
        if (gt.isomorphism(gr,c)): 
            cnt+= 1                            
            print("iso")

For more accurate timings

  • Remove all print calls from the code you want to time
  • Use the timeit module and let it repeat the timings to reduce the impact of random effects.
\$\endgroup\$
  • \$\begingroup\$ Even without print Networkx still faster than graph-tool, I dont know why because graph-tool is based on c++ boost library. \$\endgroup\$ – Mohsenuss91 Mar 3 '15 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.