bfs.h

/**************************************************************************
 * Copyright (c) 2002-2011 T. M. Murali                                   *
 * Copyright (c) 2005 Shivaram Narayanan                                  *
 *                                                                        *
 * This file is part of Biorithm.                                         *
 *                                                                        *
 * Biorithm is free software: you can redistribute it and/or modify       *
 * it under the terms of the GNU General Public License as published by   *
 * the Free Software Foundation, either version 3 of the License, or      *
 * (at your option) any later version.                                    *
 *                                                                        *
 * Biorithm is distributed in the hope that it will be useful,            *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of         *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          *
 * GNU General Public License for more details.                           *
 *                                                                        *
 * You should have received a copy of the GNU General Public License      *
 * along with Biorithm.  If not, see <http://www.gnu.org/licenses/>.      *
 *                                                                        *
 **************************************************************************/

#ifndef _BFS_H
#define _BFS_H

#include <queue>

#include "graph.h"




template <typename Graph, typename BFSVisitor>
class MyBFS {
protected:
  typedef typename Graph::Node      Node;
  typedef typename Graph::Edge              Edge;
  typedef typename Graph::NodeIterator    NodeIterator;
  typedef typename Graph::EdgeIterator      EdgeIterator;
  typedef typename Graph::IncidentEdgeIterator      IncidentEdgeIterator;
protected:                                              // member data

  // the graph to be traversed
  Graph& graph;
  BFSVisitor &visitor;
  
public:
  MyBFS(Graph& g, BFSVisitor &v) 
      : graph(g), visitor(v)
    {}

  void initialise() 
  {                                     
    NodeIterator nitr = graph.nodes();          
    while (nitr.hasNext())
      {
        Node &node = nitr.next();
        visitor.markUnvisited(node);
        visitor.markUntouched(node);
        IncidentEdgeIterator eitr = graph.incidentEdges(node);
        while (eitr.hasNext())
          visitor.markUnvisited(*eitr.next());
      }
    
//     eitr = graph.edges();
//     while (eitr.hasNext())
//       visitor.markUnvisited(eitr.next());
  }
  
  virtual ~MyBFS()
    { 
    }

public:                                         

  // perform the traversal
  void traverse(Node& v) 
  {
    queue< Node* > nodesToVisit;
    nodesToVisit.push(&v);
    visitor.markTouched(v);
    Node *node;
    
    while (!nodesToVisit.empty())
      {
        node = nodesToVisit.front();
        nodesToVisit.pop();
        // visit node.
        visitor.startVisit(*node);
    
        // mark node as being visited.
        visitor.markVisited(*node);
#ifdef DEBUG
//          cout << "\tNode " << node->getId() << " has degree "
//               << node->degree() << endl;
#endif    
        IncidentEdgeIterator inEdges = graph.incidentEdges(*node);
        while (inEdges.hasNext()) 
          {
            // try all the edges incident on *node.
            Edge &e = *inEdges.next();
            if (!visitor.isVisited(e)) 
              {
                // mark the new edge visited
                visitor.markVisited(e);
                // get next vertex
                Node *w = e.opposite(*node);
                if (!visitor.isVisited(*w) && !visitor.isTouched(*w)) 
                  {
                    if (!visitor.isDone(e, *node, *w))
                      {
#ifdef DEBUG
//                        cout << "Pushing node " << w.getId() << endl;
#endif // DEBUG
                        // unexplored edge. discover it.
                        visitor.traverseDiscovery(e, *node);
                        nodesToVisit.push(w);
                        visitor.markTouched(*w);
                      }
                  }
                else
                  // process cross edge
                  visitor.traverseCross(e, *node);
              }
          }
        visitor.finishVisit(*node);
      }
    
  }
};


class  MyDefaultBFSVisitor
{
public:

  typedef MyNode            Node;
  typedef MyEdge                    Edge;

  MyDefaultBFSVisitor()
    {}
  virtual ~MyDefaultBFSVisitor()
    {}
  

  // what do i when i visit v first?
  virtual void startVisit(const Node& v) 
  {}
  // finished with v
  virtual void finishVisit(const Node& v) 
  {}
  // discover edge e
  virtual void traverseDiscovery(const Edge& e, const Node& from) 
  {}
  // cross edge e
  virtual void traverseCross(const Edge& e, const Node& from) 
  {}
  

  // done early?  
  virtual bool isDone(const Edge& e, const Node& from, const Node &to) const
    { return false; }           

  void markTouched(Node& v)
  { 
    v.setStatus("touched");
  }
  void markUntouched(Node& v)
  { 
    v.clearStatus("touched");
  }

  void markVisited(Node& v)
  { 
    v.setStatus("visited");
  }
  void markVisited(Edge& e)
  { 
    e.setStatus("visited");
  }
  void markUnvisited(Node& v)
  { 
    v.clearStatus("visited");
  }
  void markUnvisited(Edge& e)
  { 
    e.clearStatus("visited");
  }
  bool isTouched(Node& v)
  { 
    return v.getStatus("touched");
  }
  bool isVisited(Node& v)
  { 
    return v.getStatus("visited");
  }
  bool isVisited(Edge& e)
  { 
    return e.getStatus("visited");
  }
};

class  MyComponentsBFSVisitor: public MyDefaultBFSVisitor
{
private:
  //vector< MyGraph > components;
//  vector< unsigned int > componentSizes;
  
public:
  unsigned int size;
  
  MyComponentsBFSVisitor()
    {}
  virtual ~MyComponentsBFSVisitor()
    {}
  // what do i when i visit v first?
  virtual void startVisit(const Node& v) 
  {
    size++;
  }
  // finished with v
  virtual void finishVisit(const Node& v) 
  {}
  // discovery edge e
  virtual void traverseDiscovery(const Edge& e, const Node& from) 
  {}
  // cross edge e
  virtual void traverseCross(const Edge& e, const Node& from) 
  {}
  

  // done early?  
  virtual bool isDone(const Edge& e, const Node& from, const Node &to) const
    { return false; }           

};


class  MyEndsBFSVisitor: public MyDefaultBFSVisitor
{
private:
  
public:
  unsigned int numUnvisitedNeighbours;
  vector< const Node* > endNodes;
  unsigned int componentSize;
  
  MyEndsBFSVisitor()
    {}
  virtual ~MyEndsBFSVisitor()
    {}

  // what do i when i visit v first?
  virtual void startVisit(const Node& v) 
  {
    componentSize++;
    numUnvisitedNeighbours = 0;
  }
  // finished with v
  virtual void finishVisit(const Node& v) 
  {
    if (0 == numUnvisitedNeighbours)
      endNodes.push_back(&v);
  }
  
  // discovery edge e
  virtual void traverseDiscovery(const Edge& e, const Node& from) 
  {
    numUnvisitedNeighbours++;
  }
  // cross edge e
  virtual void traverseCross(const Edge& e, const Node& from) 
  {}
  

  // done early?  
  virtual bool isDone(const Edge& e, const Node& from, const Node &to) const
    { return false; }           

};



#endif // _BFS_H