Thursday, October 21, 2010

Implementation of Dijkastra in C++ Using STL

1:  //   Dykstra.cpp  
2:  //     
3:  //   Copyright 2010 Ananya <Ananya@Ananya-laptop>  
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <iostream>  
20:  #include <stdio.h>  
21:  #include <limits.h>  
22:  #include <map>  
23:  #include <vector>  
24:  #include <string>  
25:  #include <queue>  
26:  #include <functional>  
27:  using namespace std;  
28:  struct Path;  
29:  struct Vertex;  
30:  struct Edge  
31:  {  
32:                 //First is implicit   
33:       Vertex *dest;    //second vertex of Edge  
34:       double cost;    //Edge cost  
35:       Edge(Vertex *d=0,double c =0.0)  
36:        : dest(d),cost(c) {}  
37:  };  
38:  struct Vertex  
39:  {  
40:       string name;    //Vertex name   
41:       vector<Edge> adj;  //Adjacent vertices (and cost)  
42:       double dist;    //cost  
43:       Vertex *prev;    //Previoius vertex on shortest path   
44:    int scratch;    //Extra variable used in algorithm  
45:    Vertex(const string & nm):name(nm)  
46:      {reset();}  
47:    void reset()  
48:     {  
49:             dist=3000000;  
50:             prev=0;  
51:             scratch=0;  
52:        }  
53:  };  
54:  struct Path  
55:  {  
56:       Vertex *dest;  
57:       double cost;  
58:       Path(Vertex *d=0 ,double c=0)  
59:        : dest(d),cost(c){}  
60:       bool operator>(const Path &rhs) const  
61:       {return (cost > rhs.cost);}  
62:       bool operator<(const Path &rhs) const  
63:       {return (cost < rhs.cost);}  
64:  };  
65:  class Graph  
66:  {  
67:       public:  
68:         Graph(){};  
69:        ~Graph();  
70:         void addEdge(const string & sourceName,const string & destName,double cost);  
71:         void printPath(const string & destName) const;  
72:         void dijkastra(const string & startName);  
73:         void printDijkastra();  
74:    private:  
75:      Vertex * getVertex(const string & vertexName);  
76:      void printPath(const Vertex & dest) const;  
77:      void clearAll();  
78:      typedef map<string,Vertex *,less<string> > vmap;  
79:      /*Graph( const Graph & rhs) {}  
80:      const Graph & operator= ( const Graph & rhs)  
81:      {return *this;}*/   
82:      vmap vertexMap;     
83:  };  
84:  //Destructor :clean up the Vertex Object  
85:  Graph::~Graph()  
86:  {  
87:       for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)  
88:           delete (*itr).second;  
89:  }  
90:  //If vertexName is not present ,add it to the vertexMap  
91:  //return a pointer to the vertex .  
92:  Vertex * Graph::getVertex(const string & vertexName)  
93:  {  
94:       vmap::iterator itr= vertexMap.find(vertexName);  
95:       if(itr==vertexMap.end())  
96:       {  
97:            Vertex *newv=new Vertex(vertexName);  
98:            vertexMap[vertexName]=newv;  
99:            return newv;  
100:       }  
101:       return (*itr).second;  
102:  }  
103:  //Add a new edge to the graph  
104:  void Graph::addEdge(const string & sourceName,  
105:            const string & destName,double cost)  
106:  {  
107:       Vertex * v =getVertex(sourceName);  
108:       Vertex * w =getVertex(destName);  
109:       v->adj.push_back(Edge(w,cost));  
110:  }  
111:  //Initialize the vertex output prior to running dijkastra  
112:  //Initialize  
113:  void Graph::clearAll()  
114:  {  
115:       for(vmap::iterator itr= vertexMap.begin();  
116:         itr!=vertexMap.end();++itr)  
117:         (*itr).second->reset();  
118:  }  
119:  //Recursive algo to print shortest path to dest after Dijkastra  
120:  void Graph::printPath(const Vertex & dest) const  
121:  {  
122:       if(dest.prev !=0)  
123:       {  
124:            printPath(*dest.prev);  
125:            cout<<" --> ";  
126:       }  
127:       cout<<dest.name;  
128:  }  
129:  //algo to print the cost if node is reachable else print not rechable  
130:  void Graph::printPath(const string & destName) const  
131:  {  
132:       vmap::const_iterator itr= vertexMap.find(destName);  
133:       if(itr==vertexMap.end())  
134:       {  
135:            cout<<"Destination not found "<<endl;  
136:            return ;  
137:       }       
138:       const Vertex & w =*(*itr).second;  
139:       if(w.dist==3000000)  
140:         cout<<destName<<" not reachable "<<endl;  
141:       else  
142:       {  
143:            cout<<"(Cost is: "<< w.dist << ")";  
144:            printPath(w);  
145:       }  
146:       cout<<endl;  
147:  }  
148:  void Graph::printDijkastra()  
149:  {  
150:       for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)  
151:        {  
152:            cout<<(*itr).first;  
153:            printPath((*itr).first);  
154:        }  
155:  }  
156:  void Graph::dijkastra(const string & startName)  
157:  {  
158:       priority_queue< Path,vector<Path>,greater<Path> > pq;  
159:       Path vrec;  
160:       vmap::iterator itr=vertexMap.find(startName);  
161:       if(itr==vertexMap.end())  
162:         {  
163:          cout<<"Specified node not found in graph"<<endl;  
164:          return ;  
165:         }  
166:       clearAll();  
167:       Vertex *start= (*itr).second;  
168:       pq.push(Path(start,0));  
169:       start->dist=0;  
170:       unsigned int nodesSeen=0;  
171:       for(;nodesSeen<vertexMap.size();nodesSeen++)  
172:       {  
173:            do  
174:            {  
175:                 if(pq.empty())  
176:                   return;  
177:                 vrec=pq.top();  
178:                 pq.pop();  
179:            }while(vrec.dest->scratch!=0);  
180:            Vertex *v =vrec.dest;  
181:            v->scratch=1;  
182:            for(unsigned int i=0;i<v->adj.size();i++)  
183:            {  
184:                 Edge e=v->adj[i];  
185:                 Vertex *w=e.dest;  
186:                 double cvw=e.cost;  
187:                 if(cvw<0)  
188:                 {  
189:                  cout<<"Negative Weight Edge seen"<<endl;  
190:                  return;  
191:                  }  
192:                  if(w->dist>v->dist+cvw)  
193:                  {  
194:                       w->dist=v->dist+cvw;  
195:                       w->prev=v;  
196:                       pq.push(Path(w,w->dist));  
197:                 }  
198:             }  
199:        }  
200:  }  
201:  int main(int argc, char** argv)  
202:  {  
203:       Graph g;  
204:       cout<<"Enter the Graph description in following format:->"<<endl;  
205:       cout<<"sourceName destName cost_of_Edge"<<endl;  
206:       cout<<"Enter the detail"<<endl;  
207:       int a,cost;  
208:       a=1;  
209:       string sName,dName;  
210:       while(a==1)  
211:       {   
212:        cin>>sName>>dName>>cost;  
213:        if(cost<0)  
214:             cout<<"Pls enter Non-Negative Edge wieght for Dijkastra"<<endl;  
215:        else  
216:             g.addEdge(sName,dName,cost);  
217:        cout<<"Wanna Continue(press 1/0):";  
218:        cin>>a;   
219:    }  
220:    cout<<"Enter the source node:";  
221:    cin>>sName;  
222:    g.dijkastra(sName);  
223:    cout<<"Shortest path to Distinct nodes are :-->"<<endl;  
224:    g.printDijkastra();  
225:    return 0;  
226:  }  
For more info goto : http://securityresearch.in/beta/

No comments:

Post a Comment