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