Cheeky Quotes

Thursday, October 21, 2010

Implementation of Bellman_Ford in C++ Using STL

For further info goto : http://securityresearch.in/beta/

1:  //   Bellman_Ford.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 bellmanFord(const string & startName);  
60:         void printbellmanFord();  
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::printbellmanFord()  
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::bellmanFord(const string & startName)  
132:  {  
133:       vmap::iterator itr=vertexMap.find(startName);  
134:       if(itr==vertexMap.end())  
135:         {  
136:          cout<<"Specified node not found in graph"<<endl;  
137:          return 0;  
138:         }  
139:       clearAll();  
140:       Vertex *start=(*itr).second;  
141:       list<Vertex *> q;  
142:       q.push_back(start);  
143:       start->dist=0;  
144:       start->scratch++;  
145:       while(!q.empty())  
146:       {  
147:            Vertex *v=q.front();  
148:            q.pop_front();  
149:            if(v->scratch++>2*vertexMap.size())  
150:            {  
151:                 cout<<"Negative Cycle detected"<<endl;  
152:                 return false ;  
153:            }  
154:            for(unsigned int i=0;i<v->adj.size();i++)  
155:            {  
156:                 Edge e=v->adj[i];  
157:                 Vertex *w=e.dest;  
158:                 double cvw=e.cost;  
159:                 if(w->dist>v->dist+cvw)  
160:                 {  
161:                      w->dist=v->dist+cvw;  
162:                      w->prev=v;  
163:                      if(w->scratch++ % 2==0)  
164:                           q.push_back(w);  
165:                      else  
166:                           w->scratch++;  
167:                 }  
168:            }  
169:       }  
170:       return true ;  
171:  }  
172:  int main(int argc, char** argv)  
173:  {  
174:       Graph g;  
175:       cout<<"Enter the Graph description in following format:->"<<endl;  
176:       cout<<"Edge_sourceName Edge_destName cost_of_Edge"<<endl;  
177:       cout<<"Enter the detail:-"<<endl;  
178:       int a,cost;  
179:       a=1;  
180:       string sName,dName;  
181:       while(a==1)  
182:       {   
183:        cin>>sName>>dName>>cost;  
184:        g.addEdge(sName,dName,cost);  
185:        cout<<"Wanna Continue(press 1/0):";  
186:        cin>>a;   
187:    }  
188:    cout<<"Enter the source node:";  
189:    cin>>sName;  
190:    if(g.bellmanFord(sName)==true)  
191:    {  
192:       cout<<"Shortest path to Distinct nodes are :-->"<<endl;  
193:       g.printbellmanFord();  
194:    }  
195:    else  
196:    {  
197:    }   
198:    return 0;  
199:  }  

No comments:

Post a Comment