title: What is the best/fastest way to construct a very large markov chain from simulation data?
body: <p>I have written a C++ program that simulates a certain process I'm studying. It outputs discrete "states" each timestep of the simulation. For example:</p>
  
  <pre><code>a
  b
  c
  b
  c
  b
  </code></pre>
  
  <p>would be the output of a simulation run with a as the initial condition (set by me or randomly generated) and b &amp; c would be the states the system keeps oscillating between.</p>
  
  <p>I would like to combine many of these runs into a Markov chain, so that it turns into a graph with the following vertices and edges. (Preferably at runtime, because saving the output first takes a lot of diskspace.) The number between the parentheses indicate the number of times a certain vertex or edge was encountered, so this should also be stored.</p>
  
  <pre><code>Vertices: a(1), b(3) and c(2).
  
  Edges: a-&gt;b(1), b-&gt;c(2), c-&gt;b(2).
  </code></pre>
  
  <p>The real states contain 112 bits of information and I'm generating billions of these transitions. The problem is that I haven't found a graph library or program to generate the Markov chain efficiently and fast. I have been toying around with:</p>
  
  <ul>
  <li>Google sparse hash to construct my own graph class in C++.</li>
  <li>Neo4J (I was just getting started with this one)</li>
  <li>Lemon library</li>
  </ul>
  
  <p>I just completed the "Google sparse hash graph", but it turns out to get real slow halfway into the runs. After about a day (memory usage goes above 20 GB, not a problem in itself, because there is way more), it slows down and takes about three weeks to complete.</p>
  
  <p>I have access to computers with 12 or 16 cores and 256 or 512 GB of memory, and my feeling is they should be up for the job.</p>
  
  <p>Since I'm not a trained programmer and I code quite slowly, I'm looking for some information before I spent a lot of time working on another imperfect solution.</p>
  
  <ul>
  <li>What would be the best program/library that can quickly accept large numbers of vertices and edges to construct the Markov chain?</li>
  <li>Is the slowness a result of using the wrong tools or imperfect coding (which I suspect) or am I simply trying to do something that will always take a lot of time?</li>
  </ul>
  
  <p>I hope I was able to make my issue clear. Thanks in advance for any wisdom or answers.</p>
  
  <p>EDIT:</p>
  
  <p>Based on the questions and answers in the comments I guess my question should have been: what is a suitable fast matrix library for C++?</p>