(Not too off topic I hope?) problem

[Alex Martelli]

"Duncan Smith" <buzzard at urubu.freeserve.co.uk> wrote in message
news:9bkbf6$m93$1 at news5.svr.pol.co.uk...
> I am trying to get an MCMC algorithm (based on a tree structure)
implemented
> / prototyped in Python.  I have a problem figuring out how to efficiently
> randomly select a tree edge (ie. with prob = 1/(n-1)) when the tree is a
> dictionary {node: [adjacency list], ...}.  If I randomly select a node and
> then an adjacent node, the probability of selecting the edge (defined by
the
> pair) depends heavily on the tree structure.  The solution I currently
have
> is potentially less efficient than generating all the edges from the
> dictionary and selecting one at random.  Any ideas.  Thanks in advance.

You could select a node with weighted probabilities (weights being
the lengths of adjacency lists).  Keeping the length of adjacency
lists might save some memory compared with keeping the list of edges,
if you also need the dictionary anyway for other purposes.


Alex