#Slope of a graph m generator code#
Feel free to take a look at the Gist of the code on GitHub.īelow is an excerpt from the code of the random walk approach: # Create two partitions, S and T.
ImplementationĪs I was also interested in this problem, I coded Python implementations of various approaches, including the random walk approach. Here is another resource for random spanning trees and Wilson's Algorithm. This works well for a simple connected graph, however if you need an algorithm for a directed graph then read the paper further as it describes Wilson's Algorithm. This algorithm is easy to code up, has small running time constants, and has a nice proof that it generates trees with the right probabilities. When all the vertices are discovered, the marked edges form a random spanning tree. Each time a vertex is first encountered, mark the edge from which it was discovered. Start at any vertex and do a simple random walk on the graph. Below is a quote from the paper Generating Random Spanning Trees More Quickly than the Cover Time by Wilson describing simple random walk algorithm. One approach to generating a uniform spanning tree is through a random walk. However, in order to create a truly random connected graph the initial spanning tree must be picked uniformly from the set of possible spanning trees (see Wikipedia's Uniform Spanning Tree article). It turns out this kind of bias is good for generating spanning trees that are similar to real world computer networks. Example of BiasĪs an example, for a 4 node connected graph rather than generating a linear path graph, which is what 75% of the possible spanning trees are, this kind of bias will cause the star graph to be generated with greater than the 25% probability that it should be.īias isn't always a bad thing. Therefore, earlier nodes are more likely to have a high degree (number of edges) than those picked later. By randomly selecting a visited node at each iteration, nodes that are visited towards the beginning have more iterations from which they have a chance to be chosen. The partition-based answer by ypnos is a good start, but bias is introduced by always selecting a visited node for one end of a new edge. Until the requested number of edges has been reached, add an edge between any two random nodes.Generate a (uniformly chosen) random spanning tree with N nodes and N - 1 edges.
0 kommentar(er)
