FGFS.hh

Go to the documentation of this file.

#ifndef __DIADES__AUTOMATA__FGFS_HH_
#define __DIADES__AUTOMATA__FGFS_HH_

#include <utils/Random.hh>
#include <utils/GraphSearch.hh>
#include "ComposableModelSearch.hh"





namespace Diades
{
  namespace Utils
  {

        template<typename TIncidentEdges,
                         typename TOpposite,
                         typename TContainer,
                         typename TAccumulator,
                         typename TMark,
                         typename TSolution,
                         typename TPathCut>
        class GFS : 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;

        public:
          GFS(Graph & graph, const Container & nodes,
                  const Opposite & opposite, Solution & s,
                  PathCut & cut, Accumulator & results):
                Search(graph,nodes,opposite,s,cut,results),
                _atTop(true),
                _current(0),
                _vnodes(),_stack(),
                _saturated(graph),
                _visiting(graph)
          {
                _vnodes.reserve(nodes.size());
                for(const typename Search::Node & node : nodes)
                  {
                        _vnodes.push_back(node);
                  }
          }

          virtual ~GFS(){}

          virtual void initialize()
          {
                Search::initialize();
                _atTop = true;
          }



          bool saturated(const typename Search::Node & node) const
          {
                return _saturated.isMarked(node);
          }

          bool visited(const typename Search::Node & node) 
          {
                return Search::_m.isMarked(node);
          }

          void setVisited(const typename Search::Node & node)
          {
                Search::_m.mark(node);
          }
          
          void setSaturated(const typename Search::Node & node)
          {
                _saturated.mark(node);
          }



          bool isVisiting(const typename Search::Node & node) const
          {
                return _visiting.isMarked(node);
          }

          void setVisiting(const typename Search::Node & node) 
          {
                _visiting.mark(node);
          }
          
          void unsetVisiting(const typename Search::Node & node) 
          {
                _visiting.unmark(node);
          }


          
          bool finished() const
          {
                bool result = true;
                unsigned index =0;
                while(result && (index < _vnodes.size()))
                  {
                        result = result && saturated(_vnodes[index]);
                        ++index;
                  }
                return result;
          }


          
          void popStack()
          {
                while(!_stack.empty())
                  {
                        unsetVisiting(_stack.top());
                        Node n = _stack.top();
                        _stack.pop();
                        if((!_stack.empty()) && saturated(n))
                          {
                                // the node n is saturated it may be enough to saturate the node behind n in the stack
                                IncidentEdges edges(Search::_graph,_stack.top(),Search::_cut);
                                bool isSaturated = true;
                                typename IncidentEdges::Iterator edgeIt = edges.begin();
                                while(isSaturated && (edgeIt != edges.end()))
                                  {
                                        isSaturated = saturated(Search::_opposite.next(*edgeIt,_stack.top()));
                                        ++edgeIt;
                                  }
                                if(isSaturated)
                                  {
                                        setSaturated(_stack.top());
                                  }
                          }
                  }
          }
          
          void next()
          {
                if(!finished())
                  {
                        if(_atTop)
                          {
                                
                                _current = (unsigned) generateRandomValue(0,_vnodes.size()-1);
                                _stack.push(_vnodes[_current]);
                                setVisiting(_vnodes[_current]);
                                //cout << "at top: we choose " << _vnodes[_current] << endl;
                                _atTop = false;
                                
                          }

                        setVisited(_stack.top());
                        Node n = _stack.top();
                        //cout << "VISITED NODE: " << n << endl;
                        if(Search::_s.isSolution(n))
                          {
                                Search::_results.push_back(n);
                                Search::_updated = true;
                                //cout << "SOLUTION" << endl;
                                setSaturated(n);
                                popStack();
                          }
                        else
                          {
                                IncidentEdges edges(Search::_graph,n,Search::_cut);
                                bool noEdges = true;
                                vector< typename Search::Node > nodes;
                                //cout << "NEXT NODES (STACKED): " << endl;
                                for(typename IncidentEdges::Iterator edgeIt = edges.begin();
                                        edgeIt != edges.end();
                                        ++edgeIt)
                                  {
                                        noEdges=false;
                                        const Node & nextNode = Search::_opposite.next(*edgeIt,n);
                                        if(!isVisiting(nextNode))
                                          {
                                                nodes.push_back(nextNode);
                                                //cout  << '\t' << nextNode  << endl;
                                          }
                                  }
                                if(noEdges)
                                  {
                                        setSaturated(n);
                                        popStack();
                                        //cout << "NO NEXT NODE" << endl;
                                  }
                                else
                                  {
                                        if(!nodes.empty())
                                          {
                                                typename Search::Node node = pickup(nodes);
                                                if(!saturated(node))
                                                  {
                                                        _stack.push(node);
                                                        setVisiting(node);
                                                  }
                                                else
                                                  {
                                                        //cout << "next node " << node << " is already SATURATED" << endl;
                                                        setSaturated(n);
                                                        popStack();
                                                  }
                                          }
                                        else
                                          {
                                                setSaturated(n);
                                                popStack();
                                                //cout << "NO NEXT NODE" << endl;
                                          }
                                  }
                          }
                        _atTop = _stack.empty();
                  }
          }



                  
        private:
          bool _atTop;
          unsigned _current;
          vector< typename Search::Node > _vnodes;
          stack< typename Search::Node >  _stack;
          mutable TMark _saturated;
          mutable TMark _visiting;

        private:

          typename Search::Node  pickup(const vector< typename Search::Node > & nodes)
          {
                vector< typename Search::Node > visitedNodes;
                visitedNodes.reserve(nodes.size());
                vector< typename Search::Node > nonVisitedNodes;
                nonVisitedNodes.reserve(nodes.size());
                for(const typename Search::Node & node : nodes)
                  {
                        if(!saturated(node))
                          {
                                if(visited(node))
                                  {
                                        visitedNodes.push_back(node);
                                  }
                                else
                                  {
                                        nonVisitedNodes.push_back(node);
                                  }
                          }
                  }
                if(!nonVisitedNodes.empty())
                  {
                        long index = Diades::Utils::generateRandomValue(0,nonVisitedNodes.size()-1);
                        return nonVisitedNodes[(unsigned) index];
                  }
                if(!visitedNodes.empty())
                  {
                        long index = Diades::Utils::generateRandomValue(0,visitedNodes.size()-1);
                        return visitedNodes[(unsigned) index];
                  }
                long index = Diades::Utils::generateRandomValue(0,nodes.size()-1);
                return nodes[(unsigned) index];
          }

          
        };
  };

  
  namespace Automata
  {     
        typedef ComposableModelSearch<Diades::Utils::GFS<NextTransitions,TargetDiagState,list<DiagState>,list<DiagState>,VisitedDiagState,IsCandidate,IncorrectPath> > FGFS;
        
  };
};
#endif