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
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/Implementation of Directed Acyclic Graph(DAG) in C++ using STL
1: // DAG.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: using namespace std;
28: struct Vertex;
29: struct Edge
30: {
31: Vertex *dest;
32: double cost;
33: Edge(Vertex *d=0,double c=0.0)
34: : dest(d),cost(c){}
35: };
36: struct Vertex
37: {
38: string name;
39: vector<Edge> adj;
40: double dist;
41: Vertex *prev;
42: unsigned int scratch;
43: Vertex(const string &nam):name(nam)
44: {reset();}
45: void reset()
46: {
47: dist=3000000;
48: prev=0;
49: scratch=0;
50: }
51: };
52: class Graph
53: {
54: public:
55: Graph(){};
56: ~Graph();
57: void addEdge(const string & sourceName,const string & destName,double cost);
58: void printPath(const string & destName) const;
59: bool dag(const string & startName);
60: void printdag();
61: private:
62: Vertex * getVertex(const string & vertexName);
63: void printPath(const Vertex & dest) const;
64: void clearAll();
65: typedef map<string,Vertex *,less<string> > vmap;
66: vmap vertexMap;
67: };
68: Graph::~Graph()
69: {
70: for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)
71: delete (*itr).second;
72: }
73: Vertex * Graph::getVertex(const string & vertexName)
74: {
75: vmap::iterator itr=vertexMap.find(vertexName);
76: if(itr==vertexMap.end())
77: {
78: Vertex *newv=new Vertex(vertexName);
79: vertexMap[vertexName]=newv;
80: return newv;
81: }
82: return (*itr).second;
83: }
84: void Graph::addEdge(const string & sourceName,
85: const string & destName,double cost)
86: {
87: Vertex *v=getVertex(sourceName);
88: Vertex *w=getVertex(destName);
89: v->adj.push_back(Edge(w,cost));
90: }
91: void Graph::clearAll()
92: {
93: for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)
94: (*itr).second->reset();
95: }
96: void Graph::printPath(const Vertex & dest) const
97: {
98: if(dest.prev!=0)
99: {
100: printPath(*dest.prev);
101: cout<<" -->";
102: }
103: cout<<dest.name;
104: }
105: void Graph::printPath(const string &destName) const
106: {
107: vmap::const_iterator itr=vertexMap.find(destName);
108: if(itr==vertexMap.end())
109: {
110: cout<<destName<<" not Found in Graph"<<endl;
111: return;
112: }
113: Vertex & w =*(*itr).second;
114: if(w.dist==3000000)
115: cout<<destName<<" is not rechable"<<endl;
116: else
117: {
118: cout<<"(Cost is: "<<w.dist<< ")";
119: printPath(w);
120: }
121: cout<<endl;
122: }
123: void Graph::printdag()
124: {
125: for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)
126: {
127: cout<<(*itr).first;
128: printPath((*itr).first);
129: }
130: }
131: bool Graph::dag(const string & startName)
132: {
133: vmap::iterator itr=vertexMap.find(startName);
134: if(itr==vertexMap.end())
135: {
136: cout<<"Vertex not found"<<endl;
137: return false;
138: }
139: clearAll();
140: Vertex *start=(*itr).second;
141: start->dist=0;
142: list<Vertex *> q;
143: for(itr=vertexMap.begin();itr!=vertexMap.end();++itr) //Computation of
144: { //Indegree of each vertices
145: Vertex *v =(*itr).second; // from line no.143 to 150
146: for(unsigned int i=0;i<v->adj.size();i++)
147: {
148: v->adj[i].dest->scratch++;
149: }
150: }
151: for(itr=vertexMap.begin();itr!=vertexMap.end();++itr)
152: {
153: Vertex *v=(*itr).second; //Pushing the vertices in queue
154: if(v->scratch==0)
155: { //Vertices wid indegree 0 are pushed 1st
156: q.push_back(v);
157: }
158: }
159: unsigned int y;
160: for(y=0;!q.empty();y++)
161: {
162: Vertex *v=q.front();
163: q.pop_front();
164: for(unsigned int i =0;i<v->adj.size();i++)
165: {
166: Edge e=v->adj[i];
167: Vertex *w=e.dest;
168: double cvw=e.cost;
169: if(--w->scratch==0)
170: q.push_back(w);
171: if(v->dist==3000000)
172: continue;
173: if(w->dist>v->dist+cvw)
174: {
175: w->dist=v->dist+cvw;
176: w->prev=v;
177: }
178: }
179: }
180: if(y!=vertexMap.size())
181: {
182: cout<<"Cycle is there in the graph"<<endl;
183: return false;
184: }
185: else
186: return true;
187: }
188: int main(int argc, char** argv)
189: {
190: Graph g;
191: cout<<"Enter the Graph description in following format:->"<<endl;
192: cout<<"sourceName destName cost_of_Edge"<<endl;
193: cout<<"Enter the detail"<<endl;
194: int a,cost;
195: a=1;
196: string sName,dName;
197: while(a==1)
198: {
199: cin>>sName>>dName>>cost;
200: g.addEdge(sName,dName,cost);
201: cout<<"Wanna Continue(press 1/0):";
202: cin>>a;
203: }
204: cout<<"Enter the source node:";
205: cin>>sName;
206: bool flag;
207: flag=g.dag(sName);
208: if(flag==true)
209: {
210: cout<<"Shortest path to Distinct nodes are :-->"<<endl;
211: g.printdag();
212: return 0;
213: }
214: else
215: return 0;
216: }
Subscribe to:
Posts (Atom)