Efficiency issue with a complete graph

112 views Asked by At

I'm trying to implement a function to generate a complete graph. The function is ok but when I try to run it with 28k nodes, my laptop crashes. Is there a problem with my implementation?

def make_complete_graph(num_nodes):
    """
     Takes the number of nodes num_nodes and returns a dictionary corresponding
     to a complete directed graph with the specified number of nodes. A 
     complete graph contains all possible edges subject to the restriction 
     that self-loops are not allowed. The nodes of the graph should be numbered
     0 to num_nodes - 1 when num_nodes is positive. Otherwise, the function
     returns a dictionary corresponding to the empty graph.
    """

    if num_nodes<=0:
        return dict()
    else:
        return {key:set(range(num_nodes))-set([key]) for key in range(num_nodes)}

I'm using Spyder running under anaconda and my OS is ubuntu 15.04

EDIT: I've made an improvement but still crashes

def make_complete_graph(num_nodes):
    """
     Takes the number of nodes num_nodes and returns a dictionary corresponding
     to a complete directed graph with the specified number of nodes. A 
     complete graph contains all possible edges subject to the restriction 
     that self-loops are not allowed. The nodes of the graph should be numbered
     0 to num_nodes - 1 when num_nodes is positive. Otherwise, the function
     returns a dictionary corresponding to the empty graph.
    """
    nodes = set(range(num_nodes))
    if num_nodes<=0:
        return dict()
    else:
        return {key:nodes.difference(set([key])) for key in nodes}
0

There are 0 answers