Cheeky Quotes

Thursday, October 21, 2010

Implementation of Jhonson's APSP in C++ Using STL

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:  }  

No comments:

Post a Comment