Sunday, October 31, 2010

How to program for IP - resolver against a host-name

For this matter u need to have some prerequisite :-
1)Knowledge of C language
2)Unix based system on ur Box


Now here we go is the code for resolving the IP address from given hostnames:
given program in line no 40 gets the address info with help of getaddrinfo( ) function line no. 46 to 61 prints the Ip addresses. Loop from 46 to 61 is for the case if server is having multiple Ip's .User can give n numbers of hostname and corresponding IP'll be resolved.
Explanation of program is described just after the program .

1:  //   Ipresolver.c  
2:  //     
3:  //   Copyright 2010 ananya <ananya@kgeek-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 <stdio.h>  
20:  #include <string.h>  
21:  #include <sys/types.h>  
22:  #include <sys/socket.h>  
23:  #include <netdb.h>  
24:  #include <arpa/inet.h>  
25:  int main(int argc, char *argv[])  
26:  {  
27:    struct addrinfo hints, *res, *p;  
28:    int status,i;  
29:    char ipstr[INET6_ADDRSTRLEN];  
30:    if (argc == 1) {  
31:      fprintf(stderr,"usage: showip hostname[n]\n");  
32:      return 1;  
33:    }  
34:   for(i=1;i<argc;i++)  
35:   {  
36:    printf("************************************************\n");  
37:    memset(&hints, 0, sizeof hints);  
38:    hints.ai_family = AF_UNSPEC;   
39:    hints.ai_socktype = SOCK_STREAM;  
40:    if ((status = getaddrinfo(argv[i], NULL, &hints, &res)) != 0) {      //getaddrinfo() call goes here   
41:      fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(status));      //Ip and other info regarding hostname is stored in struct addrinfo res     
42:      return 2;  
43:    }  
44:    //printf("%d\n",status);  
45:    printf("IP addresses for %s:\n\n", argv[i]);  
46:    for(p = res;p != NULL; p = p->ai_next) {                  //Loop goes for different Ips if hostname has multiple Ip's  
47:      void *addr;  
48:      //in_port_t port;  
49:      char *ipver;  
50:      if (p->ai_family == AF_INET) {                    //If it is IPv4  
51:        struct sockaddr_in *ipv4 = (struct sockaddr_in *)p->ai_addr;     
52:        addr = &(ipv4->sin_addr);                     //Extracting Ip address in binary format   
53:        //port=ipv4->sin_port;  
54:        ipver = "IPv4";                            
55:      } else {                               //If it is IPv6                
56:        struct sockaddr_in6 *ipv6 = (struct sockaddr_in6 *)p->ai_addr;    
57:        addr = &(ipv6->sin6_addr);  
58:        ipver = "IPv6";  
59:      }  
60:      inet_ntop(p->ai_family, addr, ipstr, sizeof ipstr);          //convert binary Ip notation in text i.e dotted decimal form  
61:      printf(" %s: %s \n", ipver, ipstr);  
62:    }  
63:  }  
64:    freeaddrinfo(res);   
65:    return 0;  
66:  }  

Compiling Info:-

$ gcc IPresolver.c -o Ipresolver.o  


$ ./Ipresolver.o www.nitk.ac.in www.google.com www.slashdot.org

Corresponding Output:-


 ************************************************  
 IP addresses for www.nitk.ac.in:  
  IPv4: 210.212.194.8   
 ************************************************  
 IP addresses for www.google.com:  
  IPv4: 72.14.213.105   
  IPv4: 72.14.213.106   
  IPv4: 72.14.213.147   
  IPv4: 72.14.213.99   
  IPv4: 72.14.213.103   
  IPv4: 72.14.213.104   
 ************************************************  
 IP addresses for www.slashdot.org:  
  IPv4: 216.34.181.48   

so here we go:-
Socket Descriptor it is of type int.
1:   struct addrinfo {  
2:          int       ai_flags;              // AI_PASSIVE, AI_CANONNAME, etc.  
3:          int       ai_family;             //AF_INET (IPv_4),AF_INET6 (IPV_6)  
4:          int       ai_socktype;          //SOCK_STREAM,SOCK_DGRM  
5:          int       ai_protocol;           //Usually "0"  
6:          size_t     ai_addrlen;           // size of ai_addr in bytes   
7:          struct sockaddr *ai_addr;         //struct sockaddr_in or _in6          
8:          char      *ai_canonname;       //full canonical hostname  
9:          struct addrinfo *ai_next;          //next node in lineked list  
10:        };  
u can even get this struct info using konsole command :-
$ man getaddrinfo  

1:  struct sockaddr {  
2:          sa_family_t sa_family;  
3:          char    sa_data[14];  
4:        }  
the only purpose of above is to cast the structure pointer passed in addr in order to avoid compiler warnings.
u can even get this struct info using konsole command :-
$ man bind  
To deal with struct sockaddr, programmers created a parallel structure: struct sockaddr_in ("in" for "Internet") to be used with IPv4. and sockaddr_in6 for IPv6
Structure sockaddr_in6
1:  struct sockaddr_in6 {  
2:          sa_family_t   sin6_family;  /* AF_INET6 */  
3:          in_port_t    sin6_port;   /* port number */  
4:          uint32_t    sin6_flowinfo; /* IPv6 flow information */  
5:          struct in6_addr sin6_addr;   /* IPv6 address */  
6:          uint32_t    sin6_scope_id; /* Scope ID (new in 2.4) */  
7:        };  
8:        struct in6_addr {  
9:          unsigned char  s6_addr[16];  /* IPv6 address */  
10:        };  
u can even get this struct info using konsole command :-
$ man ipv6   
similarly struct sockaddr_in for IPv4 cab b viewed .
First, let's say you have a struct sockaddr_in ina, and you have an IP address "192.168.0.48" or "2001:db8:63b3:1::3490" that you want to store into it. The function you want to use, inet_pton(), converts an IP address in numbers-and-dots notation into either a struct in_addr or astruct in6_addr depending on whether you specify AF_INET or AF_INET6. ("pton" stands for "presentation to network"—you can call it "printable to network" if that's easier to remember.) The conversion can be made as follows:
1:  inet_pton(AF_INET, "192.168.0.48", &(sa.sin_addr)); // IPv4  
2:  inet_pton(AF_INET6, "2001:db8:63b3:1::3490", &(sa6.sin6_addr)); // IPv6 
u can get infomation about inet_pton() using following command in konsole:-
$ man inet_pton  
getaddrinfo()
It used to be that you would use a function called gethostbyname() to do DNS lookups. Then you'd load that information by hand into a struct sockaddr_in, and use that in your calls.
In these modern times, you now have the function getaddrinfo() that does all kinds of good stuff for you, including DNS and service name lookups, and fills out the structs you need, besides!
1:   #include <sys/types.h>  
2:   #include <sys/socket.h>  
3:   #include <netdb.h>  
4:   int getaddrinfo(const char *node, const char *service,  
5:              const struct addrinfo *hints,  
6:              struct addrinfo **res);  
7:   void freeaddrinfo(struct addrinfo *res);  
8:   const char *gai_strerror(int errcode);  
U can get hell lot of information about this function using konsole command:
$ man getaddrinfo  
                                    
                  Enjoy Rest in peace 

Monday, October 25, 2010

Solution of 8-Queen Problem

Definition of problem :- Here is a very famous problem. How many ways are there to place 8 queens on a chess board so that
no two queens attack each other? A chess board is an 8x8 grid. Queens can be placed in the cells f
the grid. Two queens are under mutual attack if they share a row, a column or a diagonal. Here is one
possible solution:
We have to endure 4-things
1)No 2 Queens share same Column
2)No 2 Queens share same Row
3)No 2 Queens share / diagonal
4)No 2 Queens share \ diagonal
No. 1 is automatic because the way we store solution
No. 2 is done with used array
for 3 and 4 we do same thing we keep two array of size 15 to keep track which diagonals are occupied.,Consider the following trick.If we take a cell with coordinate (r,c) what are the values of (r+c) and (r+c-7) (indexing is from 0-7).

Let's call (r+c) the "Slash Code" of cell and (r-c+7) the "Backslash Code" .Then two queen which share a / diagonal has same "Slash code" and those who share a \ diagonal has same "Backslash Code" .

Solution O/P :-


For more info goto : http://securityresearch.in/beta
Code :-
1:  //   8_queen.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 <vector>  
21:  using namespace std;  
22:  vector<int> row(8),used(8),slash(15),backSlash(15);  
23:  int total;  
24:  int queen(int i)  
25:  {  
26:       if(i==8)  
27:       {  
28:            return 1;  
29:       }  
30:       for(row[i]=0;row[i]<8;row[i]++)  
31:       {  
32:            if(used[row[i]]==1 || slash[row[i]+i]==1 || backSlash[row[i]-i+7]==1)  
33:                 continue;  
34:            used[row[i]]=1;  
35:            slash[row[i]+i]=1 ;  
36:            backSlash[row[i]-i+7]=1;  
37:            total=queen(i+1);  
38:            if (total==1)  
39:              return 1;  
40:            used[row[i]]=0;  
41:            slash[row[i]+i]=0 ;  
42:            backSlash[row[i]-i+7]=0;  
43:       }  
44:       return total;  
45:  }   
46:  int main(int argc, char** argv)  
47:  {  
48:       for(int i=0;i<8;i++)  
49:       {  
50:            row[i]=0;  
51:            used[i]=0;  
52:       }  
53:       for(int i=0;i<15;i++)  
54:       {  
55:            slash[i]=0;  
56:            backSlash[i]=0;  
57:       }  
58:       int k=queen(0);  
59:       k++;  
60:       /*for(int i=0;i<8;i++)  
61:       {  
62:            cout<<row[i]<<endl;  
63:       }*/  
64:    for(k=0;k<8;k++)  
65:        {  
66:        for(int l=0;l<8;l++)  
67:            cout<<" ----";  
68:        cout<<endl;  
69:        for(int j=0;j<9;j++)  
70:        {  
71:            cout<<"|  ";  
72:            if(row[k]==j)  
73:            cout<<"\b\bQ"<<k;  
74:        }  
75:        cout<<endl;  
76:     }  
77:       for(int l=0;l<8;l++)  
78:            cout<<" ----";       
79:       return 0;  
80:  }  
                                                                 Rest in Peace

Sunday, October 24, 2010

Just Because Google Exists Doesn’t Mean You Should Stop Asking People Things




 I found a pretty interesting thing :- If you spend any amount of time online you’re probably very familiar with the above website,Let Me Google That For You LMGTFY is a super smug and hilarious site built for those sick of “all those people that find it more convenient to bother you with their question rather than google it for themselves.

Also “Because of Google,” Mecurio said. “Everyone would call their friend and the friend would start Googling to get the answer. The contestant would be like, ‘Hey Joe, aspirin. A-S-P-I-R-I-N.’ We could hear them typing on their keyboard!”

Google has basically become an extension of our brain, as of Mr. Steve Jobs’ Bicycle for Our Mind
Twice this week I have asked questions that would be better suited to a human rather than an search engine algorithm and both times I’ve been met with a “just Google it”-  Clumsy response [:x].

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

Implementation of Floyd Warshall in C++ Using STL

1:  //   Floyd_Warshall.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 <vector>  
21:  #include <stdio.h>  
22:  using namespace std;  
23:  int path(int x,int y,vector<vector<int> > & par)  
24:  {  
25:       if(x!=y)  
26:       {  
27:            path(x,par[x][y],par);  
28:            cout<<"-->"<<y;  
29:       }  
30:       return 0;  
31:  }  
32:  int main(int argc, char** argv)  
33:  {  
34:       int n;  
35:       cout<<"Enter the Number of nodes : ";  
36:       cin>>n;  
37:       vector<vector<int> > g(n+1,vector<int> (n+1));  
38:       vector<vector<int> > d(n+1,vector<int> (n+1));  
39:       vector<vector<int> > p(n+1,vector<int> (n+1));  
40:  /*     vector<vector<int> > Temp(n,vector<int> (n));  
41:       vector<vector<int> > pTemp((n,vecor<int> (n));  
42:  */       
43:       cout<<"use 3000 for INFINITY"<<endl;  
44:       cout<<"Enter the graph discription in row-major fashion:"<<endl;  
45:       for(int i=1;i<n+1;i++)  
46:            {  
47:                 for(int j=1;j<n+1;j++)  
48:                      {  
49:                           cin>>g[i][j];  
50:                      }  
51:            }  
52:       for(int i=1;i<n+1;i++)  
53:            {  
54:                 for(int j=1;j<n+1;j++)  
55:                      {  
56:                           d[i][j]=g[i][j];  
57:                           if(g[i][j]==0 || g[i][j]==3000)  
58:                                p[i][j]=0;  
59:                           else   
60:                                p[i][j]=i;  
61:                      }  
62:            }  
63:       for(int k=1;k<n+1;k++)  
64:       {  
65:            for(int i=1;i<n+1;i++)  
66:                 {  
67:                      for(int j=1;j<n+1;j++)  
68:                      {  
69:                           if(d[i][j] > d[i][k]+d[k][j])  
70:                           {  
71:                                d[i][j]=d[i][k]+d[k][j];  
72:                                p[i][j]=p[k][j];  
73:                           }  
74:                      }  
75:                 }  
76:       }  
77:       cout<<"Modified ASSP MATRIX is:->";  
78:       for(int i=1;i<n+1;i++)  
79:    {  
80:            std::cout<<endl;  
81:            for(int j=1;j<n+1;j++)  
82:            {  
83:                printf("%5d",d[i][j]);  
84:            }  
85:    }  
86:    cout<<endl<<"Parent MATRIX is:->";  
87:    for(int i=1;i<n+1;i++)  
88:    {  
89:            std::cout<<endl;  
90:            for(int j=1;j<n+1;j++)  
91:            {  
92:                printf("%5d",p[i][j]);  
93:            }  
94:    }  
95:    cout<<endl<<endl;  
96:    for(int i=1;i<n+1;i++)  
97:    {  
98:            for(int j=1;j<n+1;j++)  
99:            {  
100:                 if(i!=j)  
101:                 {  
102:                      cout<<"Shortes Path from node "  
103:                        <<i <<" to node "<<j  
104:                        <<" :- cost= "<<d[i][j];  
105:                      cout<<"::path is "<<i;  
106:                      path(i,j,p);  
107:                 }  
108:                 cout<<endl;  
109:            }  
110:       }  
111:       /*cout<<endl;  
112:       cout<<"1";  
113:    path(1,2,p);*/  
114:       return 0;  
115:  }  

For Further info goto :- http://securityresearch.in/beta/

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

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