Dear all,
I'm trying to check the size of a component in a random graph with this code (by a component I mean a maximal connected sub graph): http://pastebin.com/SzC77HdU I'm not 100 % sure that the code is working as it should but my question is if there is a better way to design the whole thing. Basically I start with a empty graph (just a set of nodes represented as the numbers between 0 and 10 ** 6) and generate random edges as pairs of integers between 0 and 10 ** 6. Also I keep a dictionary (comps) matching nodes to component numbers. If one of the nodes of the new edge doesn't touch an existing component, I just add that node to the dictionary and give it the same component number as the other node. If no node touches a component the a new component number is generated and the new nodes are added to the dict with that number. The problem is when an edge going between two distinct components are encountered, say that edge (n, m) is generated going between component i and j. Now I need to change all values for keys in one of the components to the values of the other component so that they merge into a single component. The way I tried to do this is to have lists of length one as values in the dict and by that (hopefully) manage to update all values for a whole component just by changing a single list item (I think of them as pointers to the same list). Will this work? Is there a better way to update the values of a component (fast)? /Robert
_______________________________________________ Tutor maillist - [email protected] To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
