I have a written a program for Dijesktra algorithm;
But I encounter the run time error when the code returns "lp" value ...
Runtime check failure #2-Stack around the variable 'parent' is corrupted
please see the code
Could some one tell me that how to solve this prblem
thanks
// dijkstra.cpp : Defines the entry point for the console application.
//
#include "stdafx.h" // for console application ONLY
#include <string> // for string and substring
#include <sstream>//required for converting string into integer
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAX_NODE 100
#define MAX_PATH 50
#define MAX_ITER 100
double comrange;
int num_node;
float x[MAX_NODE];//we cannot declare it as int because, there is no overload function availble for pow(int,int) etc
float y[MAX_NODE];//as above
int cn[MAX_NODE][MAX_NODE];
int nexthop[MAX_NODE][MAX_NODE];
int numhop[MAX_NODE][MAX_NODE];
//void makenodeconf();//no need
void makecn();
void printcn();
void makertmat();
int spr(int path[MAX_PATH], int s, int d);
int findmin(int temp[MAX_PATH], int len);
int netcost(int u, int v);
void makertfile();
int main(int argc, char *argv[]) {
// FILE *fp;
fstream fp; //C++ style of declaring file stream pointer
int i;
float tn=0, tx=0, ty=0;
int c=0;
int r=0;
size_t pos_from=0,pos_to=0,pos_end;
if(argc<2) {
printf("USAGE : %s [srcfile]\n", argv[0]);
return -1;
}
fp.open(argv[1], ios::in);
//fp.open("C:\\GridTopology_Simulation.txt",ios::in); //in the code, manually addressing the file path
c=0;
char str[2000];
string coordinates;
if (fp.is_open())
{
while(!fp.eof()) {
fp.getline(str,2000); //note the the total number of characters in the file, declared as 2000
cout <<str<<endl;
string strng(str);
//r=fscanf(fp, "%d%d%d", &tn, &tx, &ty); // C style of reading
for(int i=0;i<2;i++){
if(i%2==0){//for the 1st index of the line
pos_from = strng.find("("); // position of "live" in str
pos_end = strng.find(",");
pos_to=(pos_end)-(pos_from);
coordinates = strng.substr (pos_from+1,pos_to-1); // get from "live" to the end
stringstream ss(coordinates);
ss >> tx;
}
else if(i%2==1){//for the next index
pos_from = strng.find(","); // position of "live" in str
pos_end = strng.find(")"); //it ll get the index of ")"
pos_to=(pos_end-5)-(pos_from);
// note that we have to subtract 5 from pos_end; for example the format looks like (900.0, 600.0, 0.0)...
//Now we are interested in 600.0..whereas "0.0)" is fixed for the whole file document. Subtracting 5 from positon of ")"-->we will get last comma
//and then we will read between 2 commas
coordinates = strng.substr (pos_from+1,pos_to-1); // get from "live" to the end
stringstream ss(coordinates);
ss >> ty;
}
}//end of for loop
if(!strng.empty () ) {// who knows the file has empty lines at the end; if so then we need to make sure that x[c] and x[y] dont get that empty or zero input
x[c] = tx;
y[c] = ty;
//cout <<endl<<x[c]<<"\t\t"<<y[c]<<endl;
c++;
}
}//end of file
}//end of if
else
cout << "\n\nUnable to open file"<<endl<<endl;
fp.close();
num_node = c;
//printf("num_node : %d\n", num_node);
comrange=120;
// makenodeconf();
makecn();
makertmat();
makertfile();
}
/*void makenodeconf() {
FILE *fp;
int i;
fp = fopen("nodeconf.tcl", "w");
for(i=0;i<num_node;i++) {
fprintf(fp, "$node_(%d) set X_ %lf\n", i, (double)x[i]);
fprintf(fp, "$node_(%d) set Y_ %lf\n", i, (double)y[i]);
fprintf(fp, "$node_(%d) set Z_ %lf\n", i, (double)0);
fprintf(fp, "\n");
}
fclose(fp);
}*/
void makecn() {
int i,j;
double dist;
float pow1=0,pow2=0, xcord=0, ycord=0;
for(i=0;i<num_node;i++) {
for(j=0;j<num_node;j++) {
if(i==j) {
cn[i][j] = 1;
continue;
}
xcord=(x[i]-x[j]);
ycord=(y[i]-y[j]);
pow1=pow(xcord,2);
pow2=pow(ycord,2);
dist = sqrt(pow1+pow2);
//printf("dist : %lf\n", dist);
if(dist <= comrange) {
cn[i][j] = 1;
}
else {
cn[i][j] = 0;
}
}
}
//printcn();
}
void printcn() {
int i,j;
for(i=0;i<num_node;i++) {
for(j=0;j<num_node;j++) {
printf("\n this is CN metrix \t %d \n ", cn[i][j]);
}
printf("\n");
}
}
void makertmat() {
// based cn matrix
int i,j;
int path[MAX_PATH]={0,};
int lp=0;
//path[1]=0; //its important because when the loop is 1st time run, path[1] (as its assigned in below statement) has garbage value which cause a run time error
for(i=0;i<num_node;i++) {
for(j=0;j<num_node;j++) {
if(i==j) {
continue;
}
lp = spr(path, i,j);
cout<<"OKKK\n\n";
printf("i %d, j %d, lp %d, path[0] %d, path[1] %d\n", i, j, lp, path[0], path[1]);
// nexthop
nexthop[i][j] = path[1]; // here there was a run time error
// numhop
numhop[i][j] = lp-1;
}
}
}
int spr(int path[MAX_PATH], int s, int d) {
int visited[MAX_NODE] = {0,};
int distance[MAX_NODE] = {10000,};
int parent[MAX_NODE] = {num_node+1,};
int i,j,k;
int temp[MAX_PATH];
int lt;
int lp;
int h;
int t,u,v;
int c;
for(i=0;i<MAX_NODE;i++) {
distance[i]=10000;
parent[i]=num_node+1;
}
//cout<<i<<"\t\t"<<parent[i-1];
distance[s] = 0;
//printf("spr s:%d, d:%d\n", s,d);
for(i=0;i<num_node-1;i++) {
// for(k=0;k<MAX_PATH;k++) {
// temp=0;
// }
lt=0;
for(h=0;h<num_node;h++) {
if( visited[h] == 0 ) {
//printf("h %d\n", h);
temp[lt++] = distance[h];
}
else {
temp[lt++] = 10000;
}
}
//cout<<"OKKK\n\n";
u=findmin(temp,lt);
//t=u;
if(u<0) {
printf("error\n");
}
//cout<<"OKKK\n\n";
visited[u]=1;
for(v=0;v<num_node;v++) {
if(distance[u] + netcost(u,v) < distance[v]) {
//printf("u %d, v %d\n", u, v);
distance[v] = distance[u] + netcost(u,v);
parent[v] = u;
}
}
}//outer for loop
//cout<<"OKKK\n\n";
path[0]=d;
lp=1;
c=0;
while(path[0] != s) {
c++;
//cout<<c<<"\t\t1st okkkOKKK\n\n";
if(c>MAX_ITER) {
lp=0;
//cout<<c<<"\t\tOKKK Insideeeeeee\n\n\t\tlp="<<lp<<endl;
////////////************************************************************/////
return lp; /// here error occured as run time error
///***********************************************************************////
//cout<<c<<"\t\tRETURN OCCURED\n\n";
}
cout<<c<<"\t\tOuter OKKK\n\n";
if(parent[path[0]] <= num_node) {
for(k=0;k<lp;k++) {
path[lp-k] = path[lp-k-1];
}
//printf("path[1] : %d\n", path[1]);
path[0] = parent[path[1]];
lp++;
}
}//end of while
return lp;
}
int findmin(int temp[MAX_PATH], int len) {
int i;
int m;
int mi=-1;
if(len==0) {
return -1;
}
m=10000000;
for(i=0;i<len;i++) {
if(temp[i]<=m) {
m=temp[i];
mi=i;
}
}
return mi;
}
int netcost(int u, int v) {
int i;
int r=10000;
if(cn[u][v]==1) {
// r=100-v;
r=1;
}
return r;
}
void makertfile() {
int i;
int j;
FILE *fp;
fp=fopen("routefile", "w");
for(i=0;i<num_node;i++) {
for(j=0;j<num_node;j++) {
if(i==j) {
continue;
}
fprintf(fp, "%d %d %d %d\n", i, j, nexthop[i][j], numhop[i][j]);
}
}
fclose(fp);
}
