0
\$\begingroup\$

Hope someone can help me out in reviewing this code to make it faster.

My goal is to create a graph recursively:

  1. query for a node and its neighbors from a db (not present here)
  2. add it and its neighbours to a graph
  3. until you find a target, recurse (1, 2) for each neighbour

I also set a control maxNodes in case target is not found.

I don't want to process twice a node and tried some optimisation with node_processed and node_to_process:

if a node was already processed (node_processed) so that its children already added to the graph, then skip it and go to the next in node_to_process.

I tried to implement a second version making use of an adjacency list with lists and sets, I was able to achieve 2 order magnitude faster performance, but the resulting graphs were not exactly the same, with qualitative worse results. Because of this, the second version was considered inappropriate for the question and I remove it.

Networx has neat interface to access data, but in this case it is too slow.

Could you help in feedback how to make this function significantly faster ? Intended use is real-time sub-graph extraction.

EDITED: to abide with comments for making question on topic

I put here the function for computing a sub-graph recursively: for clarity, focus on the construct_simply_subgraph() and subgraph().

The inner function is_target_in_neighbors( parent, target) just return an edge_list in the form of [(parent, neighbor1, edge1_weight), (parent, neighbor2, edge2_weight) ... ] and a boolean is_found, that tells if the searched target node is present in the edge_list.

So let's use a mockup data here, and generate a db:

import random    

number_of_ids = 6000000
db_nodes = set(random.randrange(1, number_of_ids) for i in range(number_of_ids))

def generate_neighbors(parent, max_number_of_neighbors):
  generate_weight = lambda x : round( random.uniform(0, 1) , x)
  neighbors = set([random.choice( list(db_nodes - {parent}) ) for _ in range(0, max_number_of_neighbors)])
  return sorted( [(parent, neighbor, generate_weight(3)) for neighbor in neighbors] , key= lambda x :x[2], reverse=True)

# will take long while
db = { u : generate_neighbors( u, random.randrange(50, 500) ) for u in db_nodes}

Use:

# start node
a = random.choice(list(db.keys()))
# target
b = random.choice(list(db.keys()))
# compute a subgraph
make_subgraph(a, b)

Now, let get a subgraph of a node, attempting to reach out to a target node:

import networkx as nx

def make_subgraph(fromNode, toNode, weight = True, toComplete = False):

  #iterate
  g = nx.Graph()

  maxNodes  =10000

  nodes_processed = []
  nodes_to_process = []

  # helper function returning parents' neighbors
  # check if target node is among them
  def is_target_in_neighbors( parent, target):
     weighted_edge_list = db[parent]
     if not weight:
        return  [(u, v) for (u, v, w) in neighbors ], target in [t[1] for t in weighted_edge_list]
     else:
        return weighted_edge_list, target in [t[1] for t in weighted_edge_list]


  def construct_simple_sub_graph(startNode, g):

    edge_list, is_found = is_target_in_neighbors( startNode, toNode)

    if weight:
      g.add_weighted_edges_from( edge_list )
    else:
      g.add_edges_from( edge_list )


    nodes_processed.append( startNode )

    for node in list(g.nodes):
      # if not has not yet been processed: add it to a "TODO" list of nodes to be processed; otherwise, remove it from the TODO
      if node not in nodes_processed:
        if node not in nodes_to_process:
          nodes_to_process.append( node )
      else:
        if node in nodes_to_process:
              nodes_to_process.remove( node )  
    return g

  def subgraph(fromNode, g):
    while not ( g.has_node( fromNode) and g.has_node( toNode) ):

        for node in nodes_to_process:
          #print('Iterations has', g.number_of_nodes())

          g = construct_simple_sub_graph( node, g)

          if (g.number_of_nodes() > maxNodes) :
            return g

        return g
    else:
        return g

  g = construct_simple_sub_graph( fromNode, g) 
  g = subgraph(fromNode, g)

  # complete ?
  if toComplete:
    for node in nodes_to_process:
      if node not in nodes_processed:
        g = construct_simple_sub_graph( node, g )

  print('Found {} edges, {} nodes, {} remaining'.format( g.number_of_edges(),  g.number_of_nodes() ,  len(nodes_to_process)) )

  return g

Could you help improve performance ?

Performance Test on actual db: 26s

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! At the moment the question has several issues. The code looks incomplete and the // style comments make it strictly speaking invalid Python code. The last part of the question also seems to indicate that the code is not working as intended. All of these points make if off-topic for this site. To fix this, provide the complete working code. \$\endgroup\$ – AlexV Nov 10 at 20:49
  • \$\begingroup\$ @AlexV I used pseudo-code as // to clarify and focus on the essential part. Both the snippets works, but I the second snippet offers slightly different results, although it computes much faster. So question is about performance with networkx (first snippet) which I tried to rework out with the snippet above as a comparison. According to codereview.stackexchange.com/help/on-topic this is a performance and correctness question; for the second snippet, it is suggested SO, however since code execute and I post here asking for answer related to performance and logic. Can it be ok here? \$\endgroup\$ – user305883 Nov 10 at 21:13
  • 2
    \$\begingroup\$ As the downvotes tell you, "stubby"/pseudo code is not well received here. \$\endgroup\$ – AlexV Nov 11 at 9:48
  • \$\begingroup\$ Edited to make the question well received here. Please reconsider down-voting: first function is working correctly, to the best of my knowledge. I post question here to improve performance. The second function is an attempt to improve the performance, but I obtain slightly different results than the first. If yet not ok with the policy, I will remove it and leave only the first function. Please advice, thank you. \$\endgroup\$ – user305883 Nov 11 at 14:12
  • \$\begingroup\$ Considering the 2nd version doesn't produce the correct results, does its speed matter? Does the function matter at all, if it doesn't work? \$\endgroup\$ – Mast Nov 11 at 16:27

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.