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