title: writing DFS iterator for graph
body: <p>I am stucked with implementing C++ <code>iterator</code> for graph, which is represented by adjacency list. 
  So, the idea is that my iterator should go through the graph by using <em>DFS algorithm</em>. 
  As an example, for ++ iterator goes to the next unvisited vertex for current vertex (like in simple DFS). </p>
  
  <p>My templates for graph vertex and iterator are simple:</p>
  
  <pre><code>template &lt; typename VType, typename EType &gt;
  struct vertex {
      typedef vertex &lt; VType, EType &gt; graph_vertex;
      vertex (string _name, VType _v_data): name(_name), v_data(_v_data) { }
      typedef pair &lt; graph_vertex* , EType &gt; ve;  
  
      vector &lt;ve&gt; adj; //adjacency list [ graph_vertex, edge_value ]
      string name;    
      VType v_data;
      bool marked;  // for DFS
  };
  
  template &lt; typename VType, typename EType &gt;
  class dfs_iterator {
      public:
          dfs_iterator();
          dfs_iterator( graph_vertex* start );
          ~dfs_iterator();
          dfs_iterator(const dfs_iterator&amp; that);
  
          dfs_iterator&amp; operator = (const dfs_iterator&amp; that) {
              val = that.val;
          }
          dfs_iterator&amp; operator ++ () { } // read down
          dfs_iterator&amp; operator -- () { } // read down
          VType operator * () { return val-&gt;v_data; };
  
          bool operator == (const dfs_iterator&amp; that) const { return val == that.val; }
          bool operator != (const dfs_iterator&amp; that) const { return !(*this == that); }
      private:
          graph_vertex* val;
      };
  </code></pre>
  
  <p>Things that I suppose:</p>
  
  <p>In <code>struct vertex</code> should be:</p>
  
  <ul>
  <li><p>pointer <code>graph_vertex*</code> to the vertex, which was iterated (++'ed) to<br>
  this (current) vertex (to return back from current vertex).
  I will name it <code>graph_vertex* predecessor_vertex;</code></p></li>
  <li><p>successor() and predecessor() functions, which will return
        pointers <code>graph_vertex*</code> to the next / previous ( for DF-search ) vertices .</p>
  
  <pre><code>pseudocode successor(CURR_VERT):
      for every graph_vertex VERT in CURR_VERT-&gt;ADJ LIST do {
             if ( VERT not marked )
                  return VERT;
             return successor (predecessor_vertex);
      }
  pseudocode predecessor(CURR_VERT):
       return CURR_VERT-&gt;predecessor_vertex;
  </code></pre>
  
  <p>If I think in a correct way, now I got a <code>++</code> and <code>--</code> for my dfs_iterator ( overloaded functions of ++/-- shall return successor() / predecessor() for current vertex stored in iterator (and of course, change <code>marked</code> flag for current vertex )</p></li>
  </ul>
  
  <p>But I  don't understand how to deal with situation, when user creates a lot of iterators for one graph, then <code>graph_vertex</code> info will corrupt because <code>marked</code> flags will not respond correctly (one iterator can change it, then second is unable to iterate through this vertex). Should I store a special <code>vector</code> of <code>marked</code> flags in each iterator, and not in vertex? Or duplicate this information somehow to <code>graph_vertex</code> flag ? 
  Should I overload some other operators for this iterator ?</p>
  
  <p>Please, give me some tips about my code and such implementation. Do I think in a right way? </p>
  
  <p><em>// Actually, I can't find any information about such graph iterator, and I am new in C++.</em></p>