Listing 2: Implementation of algorithm for performing the depth-first search of the directed graph

template <typename PREPROCESSOR>
void dep_graph<PREPROCESSOR>::check_deps(const string& cur_dep)
{
  str_cont_t::iterator it;
  str_cont_t::iterator it_end;

  //add this dependency to the current path
  cur_path_.push_back(cur_dep);

  //check if file is in map with no dependencies,
  //insert if this file has not been checked before
  if(graph_[cur_dep].empty())
  {
    dead_end_ = true;
    return; //dead end
  }
  else
  {
    //not a dead end, look for a cycle
    it_end = cur_path_.end();
    for(it = cur_path_.begin();
        it != it_end-1;
        ++it)
    {
      if(cur_dep == *it)
      {   //this cur_dep has occurred in this path before
        dead_end_ = true;
        cycle_ = true;
        return;//found cycle
      }
    }

    //not a cycle, continue search
    it_end = graph_[cur_dep].end();
    for(it = graph_[cur_dep].begin();
        it != it_end;
        ++it)
    {
      //recursive call with next node in this node's list
      check_deps(*it);

      if(dead_end_ == true)
      {
        //add this path to the list of paths and reset
        dead_end_ = false;
        add_to_all_paths();
      }

      //backup one node (work backwards through visited nodes)
      cur_path_.erase(cur_path_.end()-1);
    }
  }
}
— End of Listing —