title: C++: How to implement sparse matrices with very large indices?
body: <p>I am trying to implement the dynamic programming presented in <a href="http://codeforces.com/blog/entry/337" rel="nofollow noreferrer">this article</a> to solve the Shortest Hamiltonian Path problem.  This solution requires storing values in a 2d array called DP of size <code>n</code>x<code>2^n</code> where <code>n</code> is the number of nodes of the graph. </p>
  
  <p>My graph has more than 100 nodes, but it is very sparse, so most of the elements of the matrix DP is +infinity. Therefore I can store it using a sparse matrix library (and see zero elements as +infinity). For example, using Eigen:</p>
  
  <pre><code>Eigen::SparseMatrix&lt;double&gt; M(n, 1 &lt;&lt; n);
  M.reserve(5e8); // reserve 4GB of RAM since I'm not able to estimate the number of non-zeros
  </code></pre>
  
  <p>However, the maximum index of this matrix is <code>2^n - 1</code> (in C++ code <code>2^n</code> is <code>1 &lt;&lt; n</code>), which is far larger than what is allowed for an index (if <code>n = 100</code> for example). The operation <code>1 &lt;&lt; n</code> is also no longer valid for very large <code>n</code> as well (I tried <code>cout&lt;&lt;(1 &lt;&lt; n)&lt;&lt;endl;</code> and got 262144 as result for n = 114).</p>
  
  <p>So, while the number of non-infinity elements of my matrix can fit into memory, I don't know how to deal with the indices.</p>
  
  <p>I would appreciate a lot if somebody can help me to solve this problem. Thank you so much in advance!</p>