Definition
A Markov Chain is a graph G in which each edge has an associated non-negative integer weight w[e] . For every node (with at least one outgoing edge) the total weight of the outgoing edges must be positive A random walk in a Markov chain starts at some node s and then performs steps according to the following rule:
Initially, s is the current node. Suppose node v is the current node and that e_{0} , ..., e_{d-1} are the edges out of v . If v has no outgoing edge no further step can be taken. Otherwise, the walk follows edge e_{i} with probability proportional to w[e_{i}] for all i , 0 < = i < d . The target node of the chosen edge becomes the new current node.
#include < LEDA/graph/markov_chain.h >
Creation
dynamic_markov_chain | M(const graph& G, const edge_array< int> & w, node s = nil) | |
creates a Markov chain for the graph G with edge weights w . The node s is taken as the start vertex (G.first_node() if s is nil). |
Operations