title: C++ Template Graph Class, Recursion
body: <p>I'm trying to code a graph class in C++, implemented as an adjacency list. I am trying to make this class a template, so that node and edges can contain an arbitrary payload. It is a simple idea, but I am getting confused about how the language might support this.</p>
  
  <p>I want to be able to declare a graph as follows:<br>
  <code>graph&lt;int, int&gt;</code> or<br>
  <code>graph&lt;string,double&gt;</code> et.c.<br><br>
  First Idea, working backwards from a graph declaration:</p>
  
  <pre><code>template&lt;class ntype, class etype&gt;
  class node {
  
      class edge {
      etype payload;
          node&lt;ntype, etype&gt;* to;
          node&lt;ntype, etype&gt;* from;
      }   
  
      ntype payload;
      vector&lt; edge&lt;&gt; &gt; incoming; // How to avoid recursion ???
      vector&lt; edge&lt;&gt; &gt; outgoing; // ????
  }
  
  template&lt;class ntype, class etype&gt;
  class graph {
  
      vector&lt; node&lt;ntype, etype&gt; &gt; nodes;
  }
  </code></pre>
  
  <p>I am getting terribly confused about the recursion involved, the scope of template arguments etc. I've tried looking at nested classes, typename vs. template, other questions, but it is not making it any clearer. It would seem that C and void pointers are the absolute best way to code this now. Any help or references are greatly appreciated.</p>