BFS.hh

Go to the documentation of this file.

#ifndef __DIADES__GRAPH__BFS_HH_
#define __DIADES__GRAPH__BFS_HH_
#include<iostream>
#include<queue>
#include<diades/graph/GraphSearch.hh>

namespace Diades
{
  namespace Graph
  {

        template<typename TIncidentEdges,
                         typename TOpposite,
                         typename TContainer,
                         typename TAccumulator,
                         typename TMark,
                         typename TSolution,
                         typename TPathCut>
        class BFS : public GraphSearch<TIncidentEdges,TOpposite,TContainer,TAccumulator,
                                                                   TMark,TSolution,TPathCut>
        {
        public:
          typedef GraphSearch<TIncidentEdges,TOpposite,TContainer,TAccumulator,
                                                  TMark,TSolution,TPathCut> Search;
          typedef typename Search::Graph Graph;
          typedef typename Search::Node  Node;
          typedef typename Search::Container Container;
          typedef typename Search::Opposite Opposite;
          typedef typename Search::Solution Solution;
          typedef typename Search::PathCut PathCut;
          typedef typename Search::Accumulator Accumulator;
          typedef typename Search::IncidentEdges IncidentEdges;
          
        private:
          std::queue<Node> _queue;


          
        public:
          BFS(Graph & graph, const Container & nodes,  const Opposite & opposite, Solution & s, PathCut & cut, Accumulator & results):
                Search(graph,nodes,opposite,s,cut,results),_queue(){}

          virtual ~BFS(){}

          virtual void initialize()
          {
                Search::initialize();
                while(!_queue.empty())
                  {
                        _queue.pop();
                  }
                for(const typename Search::Node & n : Search::_nodes)
                  {
                        _queue.push(n);
                        Search::_m.mark(n);
                  }
          }

          bool finished() const {  return _queue.empty(); }

          void next()
          {
                if(!finished())
                  {
                        
                        Node n = _queue.front();
                        //cout << "VISITED NODE: " << n << endl;
                        _queue.pop();
        
                        if(Search::_s.isSolution(n))
                          {
                                Search::_results.push_back(n);
                                Search::_updated = true;
                                //cout << "SOLUTION" << endl;
                          }
                        else
                          {
                                IncidentEdges edges(Search::_graph,n,Search::_cut);
                                //cout << "NEXT NODES (QUEUED): " << endl;
                                for(typename IncidentEdges::Iterator edgeIt = edges.begin();
                                        edgeIt != edges.end();
                                        ++edgeIt)
                                  {
                                        const Node & nextNode = Search::_opposite.next(*edgeIt,n);
                                        if(!Search::_m.isMarked(nextNode))
                                          {
                                                Search::_m.mark(nextNode);
                                                _queue.push(nextNode);
                                                //cout << '\t' << nextNode << endl;
                                          }
                                  }
                          }
                  }
          }
          
        };

  };
};

#endif