Wilson-Propp Cycle-Popping Algorithm for Random Tree Generation.

Namespace:  QuickGraph.Algorithms.RandomWalks
Assembly:  QuickGraph.Algorithms (in QuickGraph.Algorithms.dll) Version: 2.4.2.1514 (2.4.2.1514)

Syntax

C#
public class CyclePoppingRandomTreeAlgorithm : IAlgorithm
Visual Basic (Declaration)
Public Class CyclePoppingRandomTreeAlgorithm _
	Implements IAlgorithm

Remarks

This class implements cycle-popping algorithms extracted from Section 6 and 7 of How to Get Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph., by James Gary Propp and David Bruce Wilson. If you want a deepter understanding of the article, it is suggested to you have a look at this excellent paper.

The class implements two algorithms, namely RandomTreeWithRoot and RandomTree.

These algorithms apply to general digraphs. No strong connectivity is needed.

It must be emphasized that this algorithms generates trees where the edges are directe towards the root.

Inheritance Hierarchy

System..::.Object
  QuickGraph.Algorithms.RandomWalks..::.CyclePoppingRandomTreeAlgorithm

See Also