DFS.hh

Go to the documentation of this file.

#ifndef __DIADES__GRAPH__DFS_HH_
#define __DIADES__GRAPH__DFS_HH_
#include<iostream>
#include<stack>
#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 DFS : 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::stack<Node> _stack;


        
         
        public:

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

          virtual ~DFS(){}

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


          void next()
          {
                if(!finished())
                  {
                        
                        Node n = _stack.top();
                        //std::cout << "VISITED NODE: " << n << std::endl;
                        _stack.pop();
                        if(Search::_s.isSolution(n))
                          {
                                Search::_results.push_back(n);
                                Search::_updated = true;
                                //std::cout << "SOLUTION" << std::endl;
                          }
                        else
                          {
                                IncidentEdges edges(Search::_graph,n,Search::_cut);
                                //std::cout << "NEXT NODES (STACKED): " << std::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);
                                                //std::cout << '\t' << nextNode << std::endl;
                                                _stack.push(nextNode);
                                          }
                                  }
                          }
                  }
          }
        };

  };
};

#endif