search

israelst / Algorithms-Book--Python

Python implementations of the book "Algorithms - Dasgupta, Papadimitriou and Vazurani"
42 stars 26 forks source link

Kruskal algorithm #1

Open hannonq opened 9 years ago

hannonq commented 9 years ago

Hi, I'm trying to run your Kruskal code with a big graph: 10000 nodes for a complete graph. I get a Segmentation Fault, which seems to come from a memory leak(?). I have 8GB of RAM and the program execution uses all of it, crashing the execution. Any ideas whether this is an implementation bug or is Python failing to free any allocated memory?

Thanks, Hannon.

israelst commented 9 years ago

Hi, I've never tried to run this code using an graph this big. Could you send it to me?

You may consider using a more efficient algorithms to special cases.

hannonq commented 9 years ago

That's how I generated the graph. I hope I didn't screw it up. The rest of the code is unchanged.

NUM_V = 10000
vertices = [x for x in range(NUM_V)]
edges = []
for i in range(NUM_V):
    for j in range(NUM_V):
        if i != j:
            edges.append((random.randint(10,300), i, j))

graph = {'vertices' : vertices, 'edges' : list(edges)}

minimum_spanning_tree = kruskal(graph)
print minimum_spanning_tree

I can't use other algorithms because my purpose is to do a statistical comparison between Kruskal's and Prim's algorithm.