0
\$\begingroup\$

What I have: Mainly, a graph consists of 10000 nodes and around 500000 edges.

I would like to construct a dictionary where keys are the edges and the value for each edge is an array consists of 0, 1, 2 or based on a comparison between the values of another dictionary (as detailed in the algorithm below)

Although I am working on the university server, the code is too slow and takes around two hours to construct the required dictionary distance_neighbors! Additionally, I used interning and I replaced the for loops and the if elif statements by list comprehension but there is no difference.

python3
import igraph
import networkx as nx
import sys

#read data as igraph object
graph = igraph.Graph().Read_Ncol('attempt', names=True, directed=False) 

#read data as networkx object
network = nx.read_edgelist("attempt") 

#get the list of edges as a dictionary while the keys are the order
#of edges and values are edges!

    #function to give the edge list with the names of vertices
def get_edgelist_with_names(graph):
    names = graph.vs["name"]
    result = {}
    for index, neighbors in enumerate(graph.get_edgelist()):
        result[index] = [names[nei] for nei in neighbors]
    return result

edges = get_edgelist_with_names(graph) 

#get the adjacency list for the graph
G_adj = dict(network.adjacency()) 

#get a dictionary contains a list of neighbors for each node in the graph
nbrs_dict = {node: {n for n in G_adj[node]} for node in G_adj}


##########The main PROBLEM below ###########################


#try optimizing by interning 
adjacency = {sys.intern(key):value for key,value in G_adj.items()}
nbrs_adjacency = {sys.intern(key):value for key,value in nbrs_dict.items()}

neighbor1 = {}
neighbor2 = {}
distance_neighbors = {}
for i in list(edges.values()):
  neighbor1 = tuple(graph.vs[graph.neighbors(i[0], mode="all")]["name"]) 
  neighbor2 = tuple(graph.vs[graph.neighbors(i[1], mode="all")]["name"]) 
  distance_neighbors[tuple(i)] = [0 if n1 == n2 else 1 if (n1 in adjacency[n2] or n2 in adjacency[n1]) else 2 if (len(nbrs_adjacency[n1] & nbrs_adjacency[n2]) >= 1 ) else 3 for n2 in neighbor2 for n1 in neighbor1]

The original loops before list comprehension:

G_adj = dict(network.adjacency())
nbrs_dict = {node: {n for n in G_adj[node]} for node in G_adj}
neighbor1 = {}
neighbor2 = {}
distance_neighbors = {}
for i in list(edges.values()):
  distance_list = []
  neighbor1 = tuple(graph.vs[graph.neighbors(i[0], mode="all")]["name"])
  neighbor2 = tuple(graph.vs[graph.neighbors(i[1], mode="all")]["name"])
  for n2 in neighbor2:
    for n1 in neighbor1:
       if n1 == n2:
            distance_list.append(0)
       elif (n1 in G_adj[n2] or n2 in G_adj[n1]):
            distance_list.append(1)
       elif len(nbrs_dict[n1] & nbrs_dict[n2]) >= 1:
            distance_list.append(2)
       else:
            distance_list.append(3)
  distance_neighbors[tuple(i)] = distance_list

what I can do additionally to improve this code and make it faster?

P.S: I am using Python 3.7.2.

EDIT 1: Example The graph looks like

1 2
2 3
2 4
3 4
4 5

I wrote the code to construct the following dictionary

>>> distance_neighbors
{('1', '2'): [1, 1, 1], ('2', '3'): [1, 1, 1, 2, 1, 0], ('2', '4'): [1, 1, 1, 2, 0, 1, 3, 2, 1], ('3', '4'): [0, 1, 1, 1, 2, 1], ('4', '5'): [1, 1, 1]}
\$\endgroup\$
  • \$\begingroup\$ Seems like you are missing some import statements and a bunch of code... \$\endgroup\$ – Austin Hastings Apr 24 at 15:22
  • \$\begingroup\$ @AustinHastings you are right, I didn't add the function ( get_edgelist_with_names() ) because it is not related to the problem of the efficiency. I updated the code now with the required modules :) \$\endgroup\$ – Noah16 Apr 24 at 15:40
  • \$\begingroup\$ Can you add some random example data (smaller than your full data) and/or some code to generate a sufficiently large example data set? \$\endgroup\$ – Graipher Apr 24 at 15:41
  • \$\begingroup\$ @Peilonrayz In fact yes I tested it previously. This function is used in the first loop to get the values from the dictionary edges. looping over all edges will take 28.653217 seconds \$\endgroup\$ – Noah16 Apr 24 at 15:55
  • \$\begingroup\$ 1) don´t use python. 2) use multithreading \$\endgroup\$ – juvian Apr 24 at 16:31

Your Answer

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

Browse other questions tagged or ask your own question.