ComponentsLoop.h

Go to the documentation of this file.

#ifndef COMPLOOP_H
#define COMPLOOP_H

#include "MyTools.h"

template <typename T, typename K>
bool ForEachComponent(map <T, map <T, K> >* graph, bool (*func)(map <T, map < T, K > >* Component, void* instance), void* MyInstance)
{
  /* Get neighbors
   * The given graph is undirected, so neighbors only go in one direction */
  typename map < T, map <T, K> >::iterator it_gr;
  typename map < T, K >::iterator it_fri;
  map < T, vector < T > > neighbors;
  typename map < T, vector < T > >::iterator it_nei, it_n;
  
  for (it_gr = graph->begin(); it_gr != graph->end(); it_gr++){
    for (it_fri = (it_gr->second).begin(); it_fri != (it_gr->second).end(); it_fri++){
      if ((it_nei = neighbors.find(it_gr->first)) != neighbors.end()){
        (it_nei->second).push_back(it_fri->first);
      } else {
        vector <T> temp;
        temp.push_back(it_fri->first);
        neighbors.insert(make_pair<T, vector <T> >(it_gr->first, temp));
      }
      
      if ((it_nei = neighbors.find(it_fri->first)) != neighbors.end()){
        it_nei->second.push_back(it_gr->first);
      } else {
        vector <T> temp;
        temp.push_back(it_gr->first);
        neighbors.insert(make_pair<T, vector <T> >(it_fri->first, temp));
      }
    }
  }
  
  /*Use neighbor map to go through each connected component (each vertex can only be in one)*/
  set <T> seen;
  typename set <T>::iterator it_seen;
  set <T> consider;
  typename set <T>::iterator it_con;
  for (it_nei = neighbors.begin(); it_nei != neighbors.end(); it_nei++){
    if (seen.find(it_nei->first) != seen.end())
      continue;
    
    consider.clear();
    consider.insert(it_nei->first);
    map <T, map <T, K> > Component;
    
    while (!consider.empty()){
      T current = *(consider.begin());
      consider.erase(consider.begin());
      seen.insert(current);
      if ((it_gr = graph->find(current)) != graph->end())
        Component.insert(make_pair< T, map < T, K > > (it_gr->first, it_gr->second));
      
      if((it_n = neighbors.find(current)) == neighbors.end())
      {
        cerr << "Problem retrieving next node for component." << endl;
      }
      
      for (sui i = 0; i < it_n->second.size(); i++){
        if (seen.find((it_n->second)[i]) == seen.end())
          consider.insert((it_n->second)[i]);
      }
    }
    
    /*Call the function*/
    if (!(*func)(&Component, MyInstance))
      return false;
  }
  
  return true;
}

#endif