BFS for creating a queue without repetitions and with loops in the graph

Question

I have a pipeline with loops of filters and one input filter. The rest are splitters, transform and output.

I would like my code to go over the filters and push them into a queue (order is important). However, if I have a loop, I only want to count the end of the loop once.

Here is my working code. Please review it.

queue<string> CEngineInternal::GetFiltersListToRun()
{
 queue<string> filtersBFS;
 queue<string> filtersToRun;
 set<string> alreadyFoundFilters;
 // add input filters to the list
 for(BaseFilterMap::const_iterator it = m_Filters.begin(); it != m_Filters.end(); it++)
 {
 string FilterName = (*it).first;
 const CBaseFilter *filter = (*it).second;
 if(filter->IsInputFilter())
 {
 //push the input filter
 filtersBFS.push(FilterName);
 filtersToRun.push(FilterName);
 alreadyFoundFilters.insert(FilterName);
 }
 }
 while (!filtersBFS.empty())
 {
 string filterName = filtersBFS.front();
 filtersBFS.pop();
 //get the OutputPin connections for the next filter
 FilterConnection* filterConnection = m_Connections[filterName];
 ASSERT(filterConnection != NULL);
 PinConnectionVector& outPinConnections = filterConnection->GetOutputPinConnections();
 if (outPinConnections.size() != 0)
 {
 // find all the output pin connections
 for (size_t i = 0; i < outPinConnections.size(); ++i)
 {
 //add connected filters id's to the list
 const std::string& oFilterName = outPinConnections[i].ConnectedFilterName();
 if (oFilterName.empty())
 {
 continue;
 }
 if (alreadyFoundFilters.find(oFilterName) != alreadyFoundFilters.end())
 {
 continue;
 }
 else
 {
 filtersBFS.push(oFilterName);
 filtersToRun.push(oFilterName);
 alreadyFoundFilters.insert(oFilterName);
 }
 }
 }
 }
 return filtersToRun;
}

Answer 1

As far as I can tell, this code seems pretty easy to follow, especially with the comments. Here are several things that stood out to me:

• Since you haven't provided your own queue implementation, I assume you're using std::queue. If so, remove using namespace std and use std:: where necessary.

• This entire method should be const. You're modifying three local containers and returning one, while not modifying any class members. By making this const, data members will stay immutable (modifications will cause compiler errors) and the reader will be aware of this.

  queue<string> CEngineInternal::GetFiltersListToRun() const
  

• filtersBFS is not a very descriptive name; we know this program is about BFS. It's also not the local queue that is returned, so it is unclear what this is used for within the function.

• Your functions start with a capital letter, which is not proper naming in C++. Only user-defined types should be named this way. Your variables (except for FilterName) are named correctly, however. Both variables and functions should start with a lowercase letter.

• For this line:

  for(BaseFilterMap::const_iterator it = m_Filters.begin(); it != m_Filters.end(); it++)
  

  It may be more readable to declare the iterator type before the loop.

  In addition, it may be better to use pre-increment since you're not dealing with basic types. This could also potentially avoid an extra copy.

  BaseFilterMap::const_iterator it;
  for (it = m_Filters.begin(); it != m_Filters.end(); ++it) {}
  

  However, if you're using C++11, consider auto instead of your current iterator. The compiler will determine the correct type, and it's more readable. You may also keep it inside the loop statement.

  for (auto it = m_Filters.begin(); it != m_Filters.end(); ++it) {}
  

  Better yet, if you're using C++11, consider a range-based for-loop:

  for (auto& it : m_Filters) {}
  

• This:

  if (outPinConnections.size() != 0)
  

  should instead use !empty():

  if (!outPinConnections.empty())
  

• For here:

  for (size_t i = 0; i < outPinConnections.size(); ++i) {}
  

  If this is the size type returned by size(), make it std::size_t since this is C++. Otherwise, make sure you're using the correct size type to avoid potential loss-of-data warnings.

• These:

  (*it).first;
  (*it).second;
  

  should use the more readable -> operator:

  it->first;
  it->second;
  

• You say:

  If I have a loop, I only want to count the end of the loop once.

  But I don't see that anywhere in the code, plus there are multiple loops used here. If you're still receiving the correct output and no errors associated with them, then they should be okay.

• Yuushi: +1, although if you're using C++11, I'd highly recommend using auto for iterators - much more readable I think.