[Tutor] random graph

[Robert Johansson]

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

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20100713/8b3d1116/attachment.html>