dfs.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 _DFS_H
#define _DFS_H

#include "graph.h"

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

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

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

public:                                         

  // perform the traversal
  void traverse(Node& v) 
  {     
#ifdef DEBUG
    // MyGraph::MyNodeIterator itr1 = graph.nodes();
    // cout << "\tVisited status before traversal starting at node " << v.getId()
    //      << "(" << &v << "): ";
    // while (itr1.hasNext())
    //   {
    //     MyNode &node1 = itr1.next();
    //     cout << "(" << node1.getId() << ", "
    //          << node1.getStatus("visited") << ") ";
    //   }
    // cout << endl;
#endif          
    // visit v.
    visitor.startVisit(v);
    // mark v as being visited.
    visitor.markVisited(v);
#ifdef DEBUG
    // cout << "\tIn traverse(): node " << v.getId()
    //      << " (" << &v << ")"
    //      << " has degree " << v.degree() << endl;
#endif    
    EdgeIterator inEdges = graph.incidentEdges(v);
    while (inEdges.hasNext()) 
      {                         // try all its edges
        Edge &e = *inEdges.next();
        if (!visitor.isVisited(e)) 
          {
            // mark the new edge visited
            visitor.markVisited(e);
            // get next vertex
            Node *w = e.opposite(v);
#ifdef DEBUG
             // cout << "\tDuring traversal, visited status of node " << w->getId()
             //      << " (" << &w << ")"
             //      << " is " << visitor.isVisited(*w) << endl;
#endif            
            if (!visitor.isVisited(*w)) 
              {
                // unexplored edge. discover it.
                visitor.traverseDiscovery(e, v);
                // isDone() checks whether we should visit *w or not.
                if (!visitor.isDone(e, v, *w))
                  // continue traversal
                  traverse(*w);                         
              }
            else                                                // explored
              visitor.traverseBack(e, v);                               // process back edge
          }
      }
    visitor.finishVisit(v);                                     // all done
#ifdef DEBUG
    // MyGraph::MyNodeIterator itr1 = nodes();
    // cout << "\tVisited status after traversal starting at node " << v.getId()
    //      << ": ";
    // itr1 = graph.nodes();
    // while (itr1.hasNext())
    //   {
    //     MyNode &node1 = itr1.next();
    //     cout << "(" << node1.getId() << ", "
    //          << node1.getStatus("visited") << ") ";
    //   }
    // cout << endl;
#endif          
  }
};


class  MyDefaultDFSVisitor
{
public:

  typedef MyNode            Node;
  typedef MyEdge                    Edge;
  
  MyDefaultDFSVisitor()
    {}
  virtual ~MyDefaultDFSVisitor()
    {}
  virtual void initialise()
    {}
  
  // 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) 
  {}
  // back edge e
  virtual void traverseBack(const Edge& e, const Node& from) 
  {}
  

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

  void markVisited(Node& v)
  { 
#ifdef DEBUG
//    cout << "\tMarking node " << v.getId() << " as visited." << endl;
#endif    
    v.setStatus("visited");
  }
  void markVisited(Edge& e)
  { 
#ifdef DEBUG
//      cout << "\tMarking edge connecting " << e.head().getId() << " and "
//           << e.tail().getId() << " as visited." << endl;
#endif    
    e.setStatus("visited");
  }
  void markUnvisited(Node& v)
  { 
#ifdef DEBUG
//    cout << "\tMarking node " << v.getId() << " as unvisited." << endl;
#endif    
    v.clearStatus("visited");
  }
  void markUnvisited(Edge& e)
  { 
#ifdef DEBUG
//      cout << "\tMarking edge connecting " << e.head().getId() << " and "
//           << e.tail().getId() << " as unvisited." << endl;
#endif    
    e.clearStatus("visited");
  }
  bool isVisited(Node& v)
  { 
    return v.getStatus("visited");
  }
  bool isVisited(Edge& e)
  { 
    return e.getStatus("visited");
  }
};

class  MyComponentsDFSVisitor: public MyDefaultDFSVisitor
{
private:
  //vector< MyGraph > components;
//  vector< unsigned int > componentSizes;

//  const MyEdge *lastEdge;
  MyGraph component;
  unsigned int size;
public:
  
  MyComponentsDFSVisitor()
      : //lastEdge(NULL),
        component(), size(0)
    {}
  virtual ~MyComponentsDFSVisitor()
    {}

  virtual void initialise()
    {
      component.clear();
      size = 0;
    }
  
  // what do i when i visit v first?
  virtual void startVisit(const Node& v) 
  {
    component.addNode(v);
    size++;
  }
  // finished with v
  virtual void finishVisit(const Node& v) 
  {}
  // discover edge e
  virtual void traverseDiscovery(const Edge& e, const Node& from) 
  {
    // add the new node and the new edge.
    MyNode &other = *(e.opposite(from));
    component.addNode(other);
    component.addEdge(e);
  }
  // back edge e
  virtual void traverseBack(const Edge& e, const Node& from) 
  {
    component.addEdge(e);
  }
  

  virtual MyGraph &getComponent()
    {
      return(component);
    }
  
  virtual unsigned int getSize()
    {
      return(size);
    }
  
};

#endif // _DFS_H