dijkstra.h

/**************************************************************************
 * Copyright (c) 2004-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 _DIJKSTRA_H
#define _DIJKSTRA_H

#include <limits.h> //for INT_MAX
#include <map>
#include <queue>
#include <stack>

#include "graph.h"

class NodeElement { 
public: 
        friend class PrioritizeNodes; 
        NodeElement( string nid, MyNT d) 
        { 
                Distance = d; 
                NodeId = nid; 
        }
        ~NodeElement(){} 
        string getNodeId(void)
        {
                return NodeId;
        }

private: 
        MyNT Distance;
        string NodeId; 
};

class PrioritizeNodes { 
public : 
        int operator()( const NodeElement &x, const NodeElement &y )
                { 
                        return x.Distance > y.Distance; } 
};


//Default Dijkstra visitor.


class  MyDefaultDijkstraVisitor
{
public:
        
        typedef MyNode Node;
        typedef MyEdge Edge;
        
        MyDefaultDijkstraVisitor()
    {}
        
        virtual ~MyDefaultDijkstraVisitor()
    {}
  
        virtual void initVisit(const Node& v) 
        {}
        // 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 { return false; }           


        //Setting touched/untouched for nodes.
        void markTouched(Node& v)
        { 
                v.setStatus("touched");
        }
        void markUntouched(Node& v)
        { 
                v.clearStatus("touched");
        }
        //Setting visited/unvisited for nodes.
        void markVisited(Node& v)
        { 
                v.setStatus("visited");
        }
        void markUnvisited(Node& v)
        { 
                v.clearStatus("visited");
        }

        //Setting visited/unvisited for edges.
        void markVisited(Edge& e)
        { 
                e.setStatus("visited");
        }
        void markUnvisited(Edge& e)
        { 
                e.clearStatus("visited");
        }


        //Check if node or edge is visited or touched.
        bool isTouched(Node& v)
        { 
                return v.getStatus("touched");
        }
        bool isVisited(Node& v)
        { 
                return v.getStatus("visited");
        }
        bool isHidden(Node& v)
        {
                return v.isHidden();
        }
        bool isVisited(Edge& e)
        { 
                return e.getStatus("visited");
        }

};

//
//Dijkstra Visitor for the earlier algorithm (very slow)...
//

class  MyMainDijkstraVisitor: public MyDefaultDijkstraVisitor
{
private:
  
public:
        map<string,MyNT>distance;//distance to node.
        map<string, unsigned int> count;//no of shortest paths to node.
        priority_queue<NodeElement, vector<NodeElement>, PrioritizeNodes> nodesToVisit;

  
        MyMainDijkstraVisitor()
                {}
  
        virtual ~MyMainDijkstraVisitor()
                {}
        
        virtual void initVisit(const Node& v) 
        {
                distance[v.getId()] = 0;
                count[v.getId()] = 1;
                map<string, MyNT>::iterator iter = distance.begin();
                while(iter!=distance.end())
                {
                        string nodeid = (*iter).first;
                        //cout<<(*iter).first<<endl;
                        MyNT distance = (*iter).second;
                        Qpush(NodeElement(nodeid,distance));
                        iter++;
                }

        }
        // what do i when i visit v first?
        virtual void startVisit(const Node& v) 
        {
                
        }
        //set distance
        void setDistance(string nodeid, MyNT d)
        {
                distance[nodeid] = d;
        }
        //get distance
        MyNT getDistance(string nodeid)
        {
                return distance[nodeid];
        }
        //set count
        void setCount(string nodeid, unsigned int d)
        {
          count[nodeid] = d;
        }
        //get count
  unsigned int getCount(string nodeid)
        {
                return count[nodeid];
        }
        // 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 { return false; }   

        bool Qempty(){ return nodesToVisit.empty();}
        void Qpop(){ return nodesToVisit.pop();}
        const NodeElement &Qtop(){ return nodesToVisit.top();}
        void Qpush(NodeElement ne){nodesToVisit.push(ne);}

};

//
//Implementation of dijkstra for old algo.
//

template <typename Graph, typename DijkstraVisitor>
class MyDijkstra {

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;
        DijkstraVisitor &visitor;
  
public:
 
        
        MyDijkstra(Graph& g, DijkstraVisitor &v) 
                  : graph(g), visitor(v)
                {}
        
        virtual ~MyDijkstra()
                {}

        void initialise() 
        {                                       
                NodeIterator nitr = graph.nodes();
                while (nitr.hasNext())
                {
                  Node &node = nitr.next();
                  visitor.markUnvisited(node);
                  visitor.setCount(node.getId(),0);
                  visitor.setDistance(node.getId(),INT_MAX);
                  EdgeIterator eitr = graph.incidentEdges(node);
                  while (eitr.hasNext())
                    {
                      visitor.markUnvisited(*eitr.next());
                    }
                }
        }
  
 

public:                                         

        //Construct the complete shortest tree DAG rooted at node v.
        // perform the traversal
  void traverse(const Node& v) 
  {
    
        // gonna implement queue later.
        initialise();
        visitor.initVisit(v);
    while (!visitor.Qempty())
      {
        NodeElement i = visitor.Qtop();
        visitor.Qpop();
        // visit node.
        Node node = graph._getNode(i.getNodeId());
        visitor.startVisit(node);
        if(visitor.isVisited(node)) continue;
        // mark node as being visited.
        visitor.markVisited(node);
        if(visitor.isHidden(node)) continue;
        //cout<<"Visiting Node "<<node.getId()<<endl;
#ifdef DEBUG
//          cout << "\tNode " << node->getId() << " has degree "
//               << node->degree() << endl;
#endif   
        EdgeIterator 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);
                MyNT distanceTillnow = visitor.getDistance(node.getId());
                unsigned int countTillnow = visitor.getCount(node.getId());
                MyNT edgeWeight = e.getWeight();//graph.getEdgeWeight(node.getId(),(*w).getId());
                MyNT totalDistance = distanceTillnow + edgeWeight;
                /*      if (!visitor.isVisited(*w))
                  {
                  visitor.markVisited(*w);
                  visitor.setDistance((*w).getId(),totalDistance);
                  visitor.Qpush(NodeElement((*w).getId(),totalDistance));
                  visitor.setCount((*w).getId(),countTillnow);
                  }
                  else
                  {*/
                if(visitor.getDistance((*w).getId()) > totalDistance)
                  {
                    visitor.setDistance((*w).getId(),totalDistance);
                    visitor.Qpush(NodeElement((*w).getId(),totalDistance));
                    visitor.setCount((*w).getId(),countTillnow);
                  }
                else if(visitor.getDistance((*w).getId()) == totalDistance)
                  {
                    unsigned int count = visitor.getCount((*w).getId());
                    visitor.setCount((*w).getId(),countTillnow+count);
                  }
                //      }   
              }
                  }
        visitor.finishVisit(v);
          }
    
  }
};

//
//The Dijkstra visitor for the new algorithm (fast).
//

class MyBCModifiedDijkstraVisitor: public MyMainDijkstraVisitor{
        
        public:
        stack<string> desc;
        map< string,vector<string> >pred;

        public:
        
        MyBCModifiedDijkstraVisitor(){}
        virtual ~MyBCModifiedDijkstraVisitor(){}
        
        void stackPush(string s)
        {
                desc.push(s);
        }
        void addToPred(string pre, string node)
        {
                pred[node].push_back(pre);
        }
        
};

//
//Implementation of Dijkstra for new algo.
//

template <typename Graph, typename DijkstraVisitor>
class MyModifiedDijkstra {

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;
        DijkstraVisitor &visitor;
  
public:
 
        
        MyModifiedDijkstra(Graph& g, DijkstraVisitor &v) 
                  : graph(g), visitor(v)
                {}
        
        virtual ~MyModifiedDijkstra()
                {}

        void initialise() 
        {                                       
                NodeIterator nitr = graph.nodes();
                while (nitr.hasNext())
                {
                        Node &node = nitr.next();
                        visitor.markUnvisited(node);
                        visitor.setCount(node.getId(),0);
                        visitor.setDistance(node.getId(),INT_MAX);
                        EdgeIterator eitr = graph.incidentEdges(node);
                        while (eitr.hasNext())
                                {
                                visitor.markUnvisited(*eitr.next());
                                }
                        
                
                }
        }
  
 

public:                                         

        //Construct the complete shortest tree DAG rooted at node v.
        // perform the traversal
  void traverse(const Node& v) 
  {
    
        // gonna implement queue later.
        initialise();
        visitor.initVisit(v);
    while (!visitor.Qempty())
      {
        NodeElement i = visitor.Qtop();
        visitor.Qpop();
        // visit node.
        Node node = graph._getNode(i.getNodeId());
        visitor.startVisit(node);
        if(visitor.isVisited(node)) continue;
        // mark node as being visited.
        visitor.markVisited(node);
        if(visitor.isHidden(node)) continue;
        //cout<<"Visiting Node "<<node.getId()<<endl;
#ifdef DEBUG
//          cout << "\tNode " << node->getId() << " has degree "
//               << node->degree() << endl;
#endif   
        EdgeIterator 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);
                string visited_nodeid = (*w).getId();
                string nodeid = node.getId(); 
                MyNT distanceTillnow = visitor.getDistance(nodeid);
                unsigned int countTillnow = visitor.getCount(nodeid);
                MyNT edgeWeight = e.getWeight();//graph.getEdgeWeight(nodeid,visited_nodeid);
                MyNT totalDistance = distanceTillnow + edgeWeight;
                        /*      if (!visitor.isVisited(*w))
                                {
                                        visitor.markVisited(*w);
                                        visitor.setDistance((*w).getId(),totalDistance);
                                        visitor.Qpush(NodeElement((*w).getId(),totalDistance));
                                        visitor.setCount((*w).getId(),countTillnow);
                                }
                                else
                                {*/
                if(visitor.getDistance(visited_nodeid) > totalDistance)
                  {
                    visitor.setDistance(visited_nodeid,totalDistance);
                    visitor.Qpush(NodeElement(visited_nodeid,totalDistance));
                    visitor.setCount(visited_nodeid,countTillnow);
                    visitor.stackPush(visited_nodeid);
                    visitor.addToPred(nodeid,visited_nodeid);
                  }
                else if(visitor.getDistance(visited_nodeid) == totalDistance)
                  {
                    unsigned int count = visitor.getCount(visited_nodeid);
                    visitor.setCount(visited_nodeid,countTillnow+count);
                    visitor.addToPred(nodeid,visited_nodeid);
                  }
                        //      }   
              }
                  }
        visitor.finishVisit(v);
          }
    
  }
};

//
//The Dijkstra visitor for the new algorithm (fast) for finding edge betweeness.
//

class MyEdgeBetweenessDijkstraVisitor: public MyMainDijkstraVisitor{
        
        public:
        stack<string> desc;
        map< string,vector<string> >pred;
        map< string,vector<string> >succ;

        public:
        
        MyEdgeBetweenessDijkstraVisitor(){}
        virtual ~MyEdgeBetweenessDijkstraVisitor(){}
        
        void stackPush(string s)
        {
                desc.push(s);
        }
        void addToPred(string pre, string node)
        {
                pred[node].push_back(pre);
        }
        void addToSucc(string suc, string node)
        {
                succ[node].push_back(suc);
        }
        
};

//
//Implementation of Dijkstra for new algo to find edge betweeness.
//

template <typename Graph, typename DijkstraVisitor>
class MyEdgeBetweenessDijkstra {

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;
        DijkstraVisitor &visitor;
  
public:
 
        
        MyEdgeBetweenessDijkstra(Graph& g, DijkstraVisitor &v) 
                  : graph(g), visitor(v)
                {}
        
        virtual ~MyEdgeBetweenessDijkstra()
                {}

        void initialise() 
        {                                       
                NodeIterator nitr = graph.nodes();
                while (nitr.hasNext())
                {
                        Node &node = nitr.next();
                        visitor.markUnvisited(node);
                        visitor.setCount(node.getId(),0);
                        visitor.setDistance(node.getId(),INT_MAX);
                        EdgeIterator eitr = graph.incidentEdges(node);
                        while (eitr.hasNext())
                                {
                                visitor.markUnvisited(*eitr.next());
                                }
                        
                
                }
        }
  
 

public:                                         

        //Construct the complete shortest tree DAG rooted at node v.
        // perform the traversal
  void traverse(const Node& v) 
  {
    
        // gonna implement queue later.
        initialise();
        visitor.initVisit(v);
    while (!visitor.Qempty())
      {
        NodeElement i = visitor.Qtop();
        visitor.Qpop();
        // visit node.
        Node node = graph._getNode(i.getNodeId());
        visitor.startVisit(node);
        if(visitor.isVisited(node)) continue;
        // mark node as being visited.
        visitor.markVisited(node);
        if(visitor.isHidden(node)) continue;
        //cout<<"Visiting Node "<<node.getId()<<endl;
#ifdef DEBUG
//          cout << "\tNode " << node->getId() << " has degree "
//               << node->degree() << endl;
#endif   
        EdgeIterator 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);
                string visited_nodeid = (*w).getId();
                string nodeid = node.getId(); 
                MyNT distanceTillnow = visitor.getDistance(nodeid);
                unsigned int countTillnow = visitor.getCount(nodeid);
                MyNT edgeWeight = e.getWeight();//graph.getEdgeWeight(nodeid,visited_nodeid);
                MyNT totalDistance = distanceTillnow + edgeWeight;
                        /*      if (!visitor.isVisited(*w))
                                {
                                        visitor.markVisited(*w);
                                        visitor.setDistance((*w).getId(),totalDistance);
                                        visitor.Qpush(NodeElement((*w).getId(),totalDistance));
                                        visitor.setCount((*w).getId(),countTillnow);
                                }
                                else
                                {*/
                if(visitor.getDistance(visited_nodeid) > totalDistance)
                  {
                    visitor.setDistance(visited_nodeid,totalDistance);
                    visitor.Qpush(NodeElement(visited_nodeid,totalDistance));
                    visitor.setCount(visited_nodeid,countTillnow);
                    visitor.stackPush(visited_nodeid);
                    visitor.addToPred(nodeid,visited_nodeid);
                    visitor.addToSucc(visited_nodeid,nodeid);
                  }
                else if(visitor.getDistance(visited_nodeid) == totalDistance)
                  {
                    unsigned int count = visitor.getCount(visited_nodeid);
                    visitor.setCount(visited_nodeid,countTillnow+count);
                    visitor.addToPred(nodeid,visited_nodeid);
                    visitor.addToSucc(visited_nodeid,nodeid);
                  }
                //      }   
              }
          }
        visitor.finishVisit(v);
          }
    
  }
};



// class  MyPrimMSTVisitor: public MyDefaultDijkstraVisitor
// {
// private:
  
// public:
//   map<string,MyNT>distance;//edge weight.
//   priority_queue<NodeElement, vector<NodeElement>, PrioritizeNodes> nodesToVisit;

  
//   MyPrimMSTVisitor()
//     {}
  
//   virtual ~MyPrimMSTVisitor()
//     {}
        
//   virtual void initVisit(const Node& v) 
//     {
//       distance[v.getId()] = 0;
//       count[v.getId()] = 1;
//       map<string, MyNT>::iterator iter = distance.begin();
//       while(iter!=distance.end())
//         {
//           string nodeid = (*iter).first;
//           //cout<<(*iter).first<<endl;
//           MyNT distance = (*iter).second;
//           Qpush(NodeElement(nodeid,distance));
//           iter++;
//         }
      
//     }
//   // what do i when i visit v first?
//   virtual void startVisit(const Node& v) 
//     {
      
//     }
//   //set distance
//   void setDistance(string nodeid, MyNT d)
//     {
//       distance[nodeid] = d;
//     }
//   //get distance
//   MyNT getDistance(string nodeid)
//     {
//       return distance[nodeid];
//     }
//   //set count
//   void setCount(string nodeid, MyNT d)
//     {
//       count[nodeid] = d;
//     }
//   //get count
//   MyNT getCount(string nodeid)
//     {
//       return count[nodeid];
//     }
//   // 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 { return false; }      
  
//   bool Qempty(){ return nodesToVisit.empty();}
//   void Qpop(){ return nodesToVisit.pop();}
//   const NodeElement &Qtop(){ return nodesToVisit.top();}
//   void Qpush(NodeElement ne){nodesToVisit.push(ne);}
  
// };


#endif // _DIJKSTRA_H