Example Markov Chains

The following program shows how a markov chain can be used. First a graph G with two nodes and four edges (including two self loops) is created. Then an edge_array weight is used to assign weights to the edges. Finally, a markov_chain M is defined for G and weight and 1000 steps of a random walk are performed.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/edge_array.h>
#include <LEDA/graph/markov_chain.h>

using namespace leda;

int main()
{
  graph G;
  node v0 = G.new_node();
  node v1 = G.new_node();
  edge e00 = G.new_edge(v0,v0); 
  edge e01 = G.new_edge(v0,v1);
  edge e10 = G.new_edge(v1,v0); 
  edge e11 = G.new_edge(v1,v1);

  edge_array<int> weight(G);
  weight[e00] = 200; weight[e01] = 1;
  weight[e10] = 1; weight[e11] = 1;

  markov_chain M(G,weight);
  M.step(1000);

  std::cout << "# of visits of v0 = " 
            << M.number_of_visits(v0) << std::endl;
  std::cout << "# of visits of v1 = " 
            << M.number_of_visits(v1) << std::endl;

  return 0;
}

See also:

Markov Chains and Dynamic Markov Chains

Graphs and Related Data Types

Edge Arrays

Manual Entries:

Manual Page Markov Chains

Manual Page Dynamic Markov Chains