1: // Johnson_mod.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 <list>
26: #include <functional>
27: #include <queue>
28: using namespace std;
29: struct Path;
30: struct Vertex;
31: struct Edge
32: {
33: Vertex *dest;
34: double cost;
35: Edge(Vertex *d=0,double c =0.0)
36: : dest(d),cost(c) {}
37: };
38: struct Vertex
39: {
40: string name;
41: vector<Edge> adj;
42: double dist;
43: Vertex *prev;
44: unsigned int scratch;
45: double h;
46: unsigned int hash;
47: Vertex(const string & nam):name(nam)
48: {reset();}
49: void reset()
50: {
51: dist=3000000;
52: prev=0;
53: scratch=0;
54: }
55: };
56: struct Path
57: {
58: Vertex *dest;
59: double cost;
60: Path(Vertex *d=0 ,double c=0)
61: : dest(d),cost(c){}
62: bool operator>(const Path &rhs) const
63: {return (cost > rhs.cost);}
64: bool operator<(const Path &rhs) const
65: {return (cost < rhs.cost);}
66: };
67: class Graph
68: {
69: public:
70: Graph(){};
71: ~Graph();
72: void addEdge(const string & sourceName,const string & destName,double cost);
73: void printPath(const string & destName) const;
74: void dijkastra(const string & startName);
75: bool bellmanFord(const string & startName);
76: bool jhonson();
77: void printDijkastra();
78: int getNodeCount();
79: void calcHash();
80: private:
81: Vertex * getVertex(const string & vertexName);
82: void printPath(const Vertex & dest) const;
83: void clearAll();
84: typedef map<string,Vertex *,less<string> > vmap;
85: vmap vertexMap;
86: };
87: Graph g,g1;
88: Graph::~Graph()
89: {
90: for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)
91: delete (*itr).second;
92: }
93: Vertex * Graph::getVertex(const string & vertexName)
94: {
95: vmap::iterator itr= vertexMap.find(vertexName);
96: if(itr==vertexMap.end())
97: {
98: Vertex *newv=new Vertex(vertexName);
99: vertexMap[vertexName]=newv;
100: return newv;
101: }
102: return (*itr).second;
103: }
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: void Graph::clearAll()
112: {
113: for(vmap::iterator itr= vertexMap.begin();
114: itr!=vertexMap.end();++itr)
115: (*itr).second->reset();
116: }
117: void Graph::printPath(const Vertex & dest) const
118: {
119: if(dest.prev !=0)
120: {
121: printPath(*dest.prev);
122: cout<<" --> ";
123: }
124: cout<<dest.name;
125: }
126: void Graph::printPath(const string & destName) const
127: {
128: vmap::const_iterator itr= vertexMap.find(destName);
129: if(itr==vertexMap.end())
130: {
131: cout<<"Destination not found "<<endl;
132: return ;
133: }
134: const Vertex & w =*(*itr).second;
135: if(w.dist==3000000)
136: cout<<destName<<" not reachable "<<endl;
137: else
138: {
139: cout<<"(Cost is: "<< w.dist << ")";
140: printPath(w);
141: }
142: cout<<endl;
143: }
144: void Graph::printDijkastra()
145: {
146: for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)
147: {
148: cout<<(*itr).first;
149: printPath((*itr).first);
150: }
151: }
152: int Graph::getNodeCount()
153: {
154: return vertexMap.size();
155: }
156: void Graph::calcHash()
157: {
158: unsigned int i =1;
159: for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)
160: {
161: (*itr).second->hash=i++;
162: }
163: }
164: void Graph::dijkastra(const string & startName)
165: {
166: priority_queue< Path,vector<Path>,greater<Path> > pq;
167: Path vrec;
168: vmap::iterator itr=vertexMap.find(startName);
169: if(itr==vertexMap.end())
170: {
171: cout<<"Specified node not found in graph"<<endl;
172: return ;
173: }
174: clearAll();
175: Vertex *start= (*itr).second;
176: pq.push(Path(start,0));
177: start->dist=0;
178: unsigned int nodesSeen=0;
179: for(;nodesSeen<vertexMap.size();nodesSeen++)
180: {
181: do
182: {
183: if(pq.empty())
184: return;
185: vrec=pq.top();
186: pq.pop();
187: }while(vrec.dest->scratch!=0);
188: Vertex *v =vrec.dest;
189: v->scratch=1;
190: for(unsigned int i=0;i<v->adj.size();i++)
191: {
192: Edge e=v->adj[i];
193: Vertex *w=e.dest;
194: double cvw=e.cost;
195: if(cvw<0)
196: {
197: cout<<"Negative Weight Edge seen"<<endl;
198: return;
199: }
200: if(w->dist>v->dist+cvw)
201: {
202: w->dist=v->dist+cvw;
203: w->prev=v;
204: pq.push(Path(w,w->dist));
205: }
206: }
207: }
208: }
209: bool Graph::bellmanFord(const string & startName)
210: {
211: vmap::iterator itr=vertexMap.find(startName);
212: if(itr==vertexMap.end())
213: {
214: cout<<"Specified node not found in graph"<<endl;
215: return 0;
216: }
217: clearAll();
218: Vertex *start=(*itr).second;
219: list<Vertex *> q;
220: q.push_back(start);
221: start->dist=0;
222: start->scratch++;
223: while(!q.empty())
224: {
225: Vertex *v=q.front();
226: q.pop_front();
227: if(v->scratch++>2*vertexMap.size())
228: {
229: cout<<"Negative Cycle detected"<<endl;
230: return false ;
231: }
232: for(unsigned int i=0;i<v->adj.size();i++)
233: {
234: Edge e=v->adj[i];
235: Vertex *w=e.dest;
236: double cvw=e.cost;
237: if(w->dist>v->dist+cvw)
238: {
239: w->dist=v->dist+cvw;
240: w->prev=v;
241: if(w->scratch++ % 2==0)
242: q.push_back(w);
243: else
244: w->scratch++;
245: }
246: }
247: }
248: return true ;
249: }
250: bool Graph::jhonson()
251: {
252: g.calcHash();
253: int n=g.getNodeCount();
254: vector<vector<int> > d(n+1,vector<int> (n+1));
255: for(int i=0;i<n+1;i++)
256: for(int j=0;j<n+1;j++)
257: d[i][j]=0;
258: string str;
259: g.getVertex("S");
260: for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)
261: {
262: str=(*itr).first;
263: g.addEdge("S",str,0);
264: }
265: bool t=g.bellmanFord("S");
266: if(t==false)
267: {
268: cout<<"Negative Cycle is there in Graph !!Exiting!!"<<endl;
269: return false;
270: }
271: else
272: {
273: cout<<endl<<"h-value of each node using Bellman_Ford is :->"<<endl;
274: for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)
275: {
276: (*itr).second->h=(*itr).second->dist;
277: cout<<(*itr).first<<" : "<<(*itr).second->h<<endl;
278: }
279: cout<<endl<<"Reweighted edges are :->"<<endl;
280: for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)
281: {
282: Vertex *w=(*itr).second;
283: for(unsigned int i=0;i<w->adj.size();i++)
284: {
285: w->adj[i].cost=w->adj[i].cost + w->h -w->adj[i].dest->h;
286: cout<<w->name<<" to "<<w->adj[i].dest->name<<" = "<<w->adj[i].cost<<endl;
287: }
288: cout<<endl;
289: }
290: for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)
291: {
292: if((*itr).first!="S")
293: {
294: g.dijkastra((*itr).first);
295: for(vmap::iterator itr1=vertexMap.begin();itr1!=vertexMap.end();++itr1)
296: {
297: if((*itr1).first!="S");
298: {
299: d[(*itr).second->hash][(*itr1).second->hash]= (*itr1).second->dist + (*itr1).second->h - (*itr).second->h;
300: }
301: }
302: }
303: }
304: cout<<endl<<"All pair Shortest Path Matrix is -->"<<endl;
305: printf(" A B C D E");
306: for(int i=1;i<n+1;i++)
307: {
308: cout<<endl;
309: if(i==1)
310: cout<<"A";
311: if(i==2)
312: cout<<"B";
313: if(i==3)
314: cout<<"C";
315: if(i==4)
316: cout<<"D";
317: if(i==5)
318: cout<<"E";
319: if(i==6)
320: cout<<"F";
321: for(int j=1;j<n+1;j++)
322: {
323: printf("%5d",d[i][j]);
324: }
325: }
326: return true;
327: }
328: }
329: int main(int argc, char** argv)
330: {
331: cout<<"Enter the Graph description in following format:->"<<endl;
332: cout<<"Edge_sourceName Edge_destName cost_of_Edge"<<endl;
333: cout<<"Enter the detail:-"<<endl;
334: int a,cost;
335: a=1;
336: string sName,dName;
337: while(a==1)
338: {
339: cin>>sName>>dName>>cost;
340: g.addEdge(sName,dName,cost);
341: g1.addEdge(sName,dName,cost);
342: cout<<"Wanna Continue(press 1/0):";
343: cin>>a;
344: }
345: g.jhonson();
346: return 0;
347: }
Thursday, October 21, 2010
Implementation of Jhonson's APSP in C++ Using STL
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment