shortest path algorithm and file saving

Pandiani · #1 08-May-2004, 03:59

I manage to implement all pairs shortest path algorithm

CPP / C++ / C Code:

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

class Graph
{
	int** adjmatrix;
	int** costmatrix;
	int** path_matrix;
	int *niz;
	int size;
	void init_adjmatrix();
	void init_costmatrix();
	void load_adjmatrix();
	void load_costmatrix(int,int);
	void init_path_matrix();
	void show_matrix_shortest_paths();
	
public:
	Graph(int);
	~Graph();
	void setup_matrices();
	void show_path(int,int);
	int find_shortest_path_cost(int,int);
	void show_adjmatrix()
	{
		for(int i=0;i<size;i++,cout<<endl)
			for(int j=0;j<size;j++)
				cout<<" "<<adjmatrix[i][j];
	}
	
};

Graph::Graph(int siz):size(siz)
{
	niz=new int[size];
	adjmatrix=new int* [size];
	costmatrix=new int* [size];
	path_matrix=new int*[size];
	for(int i=0;i<size;i++)
	{
		adjmatrix[i]=new int[size];
		costmatrix[i]=new int[size];
		path_matrix[i]=new int[size];
		niz[i]=0;
	}	
	setup_matrices();
	
}
Graph::~Graph()
{
	for(int i=0;i<size;i++)
	{
		delete adjmatrix[i];
		delete costmatrix[i];
		delete path_matrix[i];
	}
	delete adjmatrix;
	delete costmatrix;
	delete path_matrix;
}
void Graph::setup_matrices()
{
	init_path_matrix();
	init_adjmatrix();
	load_adjmatrix();
	init_costmatrix();
	
}
void Graph::init_adjmatrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			adjmatrix[i][j]=0;
}
void Graph::init_costmatrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			costmatrix[i][j]=adjmatrix[i][j];
}
void Graph::load_adjmatrix()
{
	int i,j,cost;;
	char answer;
	
		const int infinite=999999;
		for(i=0;i<size;i++)
		{
			for(j=0;j<size;j++)
			{
			
			
				if((i!=j)&& (adjmatrix[i][j]==0)){
				//adjmatrix entered by user
				cout<<"Is there connection between "<<i<<" i node "<<j<<" ?"<<endl;
				cout<<"Your answer (y for yes,any key for no): ";
				cin>>answer;
				if((answer=='y')||(answer=='Y'))
				{
					cout<<"Enter cost: ";
					cin>>cost;
					adjmatrix[i][j]=adjmatrix[j][i]=cost;
					path_matrix[i][j]=j;path_matrix[j][i]=i;
				}
				else
					adjmatrix[i][j]=adjmatrix[j][i]=path_matrix[i][j]=path_matrix[j][i]=infinite;
			}
				
		}
		
	}

}

void Graph::load_costmatrix(int beg,int end)
{
	
	const int infinite=999999;
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<size;j++)
		{
			for(int k=0;k<size;k++)
			{
				if(costmatrix[i][k]>0)
				{
					if((!costmatrix[j][k])||
						(costmatrix[i][k]+costmatrix[j][i]
						<costmatrix[j][k]))
					{
						costmatrix[j][k]=costmatrix[i][k]+costmatrix[j][i];
						path_matrix[j][k]=path_matrix[j][i];
					}
				}
			}
		}
	}
}
int Graph::find_shortest_path_cost(int i,int j)
{
	load_costmatrix(i,j);
	return costmatrix[i][j];
}
void Graph::init_path_matrix()
{
	const int infinite=999999;
	for(int i=0;i<size;i++)
		for(int j=0;j<size;j++)
		{
			if(i==j)
				path_matrix[i][j]=i;
			else
				path_matrix[i][j]=infinite;
		}
}
void Graph::show_path(int start,int end)
{
	int k=-1;
	cout<<"Path is: "<<start;
	while(k!=end)
	{
		k=path_matrix[start][end];
		cout<<" "<<k;
		start=k;
	}
}
void Graph::show_matrix_shortest_paths()
{
for(int i=0;i<size;i++,cout<<endl)
			for(int j=0;j<size;j++)
				cout<<" "<<path_matrix[i][j];
}
int main()
{
	int node_number,source,destination,cost;

	cout<<"Enter number of nodes: ";
	cin>>node_number;
	Graph graph_obj(node_number);

	cout<<"Enter source index: ";
	cin>>source;
	if(source>node_number-1)
	{
		cout<<"Error!"<<endl;
		return -1;
	}
	cout<<"Enter destination index: ";
	cin>>destination; 
	if(destination>node_number-1)
	{
		cout<<"Error"<<endl;
		return -1;
	}
	cost =graph_obj.find_shortest_path_cost(source,destination);

	cout<<"The shortest path between "<<source<<" i node "<<destination<<
		" has cost "<<cost<<"!"<<endl;
	
	graph_obj.show_path(source,destination);
	
	return 0;
}

This implementation have some weaknees:
First this variable infinite is define as 999999 this is pretty much unfortunate.
Do you have any suggestion regarding this issue?
Second, there are weak chacking of user inputs, but I think I can manage this.
Third, every time program is started user must enter graph manualy. Idea was to make this using files. So one can eneter name of file where graph is stored. First data in file would be int that represent number of nodes vertices, and then adjmatrix elements.
I not good at working with files so I manage to screw this up with the following code:

CPP / C++ / C Code:

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

class Graph
{
	int** adjmatrix;
	int** costmatrix;
	int** path_matrix;
	int *niz;
	int size;
	void init_adjmatrix();
	void init_costmatrix();
	void load_adjmatrix();
	void load_costmatrix(int,int);
	void init_path_matrix();
	void show_matrix_shortest_paths();
	FILE *fp;
	
public:
	Graph(int,FILE*);
	~Graph();
	void setup_matrices(FILE *);
	void show_path(int,int);
	int find_shortest_path_cost(int,int);
	void show_adjmatrix()
	{
		for(int i=0;i<size;i++,cout<<endl)
			for(int j=0;j<size;j++)
				cout<<" "<<adjmatrix[i][j];
	}
	
};

Graph::Graph(int siz,FILE* f):size(siz),fp(f)
{
	niz=new int[size];
	adjmatrix=new int* [size];
	costmatrix=new int* [size];
	path_matrix=new int*[size];
	for(int i=0;i<size;i++)
	{
		adjmatrix[i]=new int[size];
		costmatrix[i]=new int[size];
		path_matrix[i]=new int[size];
		niz[i]=0;
	}	
	setup_matrices(fp);
	
}
Graph::~Graph()
{
	for(int i=0;i<size;i++)
	{
		delete adjmatrix[i];
		delete costmatrix[i];
		delete path_matrix[i];
	}
	delete adjmatrix;
	delete costmatrix;
	delete path_matrix;
}
void Graph::setup_matrices(FILE *f)
{
	fp=f;
	init_path_matrix();
	init_adjmatrix();
	load_adjmatrix();
	init_costmatrix();
	
}
void Graph::init_adjmatrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			adjmatrix[i][j]=0;
}
void Graph::init_costmatrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			costmatrix[i][j]=adjmatrix[i][j];
}
void Graph::load_adjmatrix()
{
	int i,j,cost;;
	char answer;
	char s[80];
	if(fp!=NULL)
	{
		for(int i=0;i<size;i++)
			for(j=0;j<size;j++)
				fread(&adjmatrix[i][j],sizeof(int),1,fp);
	}
	else
	{
		cout<<"File doesn't exist! Creating new..."<<endl;
		cout<<"Enter new name: ";
		cin>>s;
		fp=fopen(s,"wb");
		if(fp==NULL)
		{
			cout<<"Error!";
			exit(1);
		}
		const int infinite=999999;
		fwrite(&size,sizeof(int),1,fp);
		for(i=0;i<size;i++)
		{
			for(j=0;j<size;j++)
			{
			
			
				if((i!=j)&& (adjmatrix[i][j]==0)){
				//adjmatrix entered by user
				cout<<"Is there connection between "<<i<<" i node "<<j<<" ?"<<endl;
				cout<<"Your answer (y for yes,any key for no): ";
				cin>>answer;
				if((answer=='y')||(answer=='Y'))
				{
					cout<<"Enter cost: ";
					cin>>cost;
					adjmatrix[i][j]=adjmatrix[j][i]=cost;
					path_matrix[i][j]=j;path_matrix[j][i]=i;
				}
				else
					adjmatrix[i][j]=adjmatrix[j][i]=path_matrix[i][j]=path_matrix[j][i]=infinite;
			}
				fwrite(&adjmatrix[i][j],sizeof(int),1,fp);
		}
			fclose(fp);
	}

}
}
void Graph::load_costmatrix(int beg,int end)
{
	
	const int infinite=999999;
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<size;j++)
		{
			for(int k=0;k<size;k++)
			{
				if(costmatrix[i][k]>0)
				{
					if((!costmatrix[j][k])||
						(costmatrix[i][k]+costmatrix[j][i]
						<costmatrix[j][k]))
					{
						costmatrix[j][k]=costmatrix[i][k]+costmatrix[j][i];
						path_matrix[j][k]=path_matrix[j][i];
					}
				}
			}
		}
	}
}
int Graph::find_shortest_path_cost(int i,int j)
{
	load_costmatrix(i,j);
	return costmatrix[i][j];
}
void Graph::init_path_matrix()
{
	const int infinite=999999;
	for(int i=0;i<size;i++)
		for(int j=0;j<size;j++)
		{
			if(i==j)
				path_matrix[i][j]=i;
			else
				path_matrix[i][j]=infinite;
		}
}
void Graph::show_path(int start,int end)
{
	int k=-1;
	cout<<"Path is: "<<start;
	while(k!=end)
	{
		k=path_matrix[start][end];
		cout<<" "<<k;
		start=k;
	}
}
void Graph::show_matrix_shortest_paths()
{
for(int i=0;i<size;i++,cout<<endl)
			for(int j=0;j<size;j++)
				cout<<" "<<path_matrix[i][j];
}
int main()
{
	int node_number,source,destination,cost;

	cout<<"Enter file name  contains graph infos: ";
	cout.flush();
	char s[BUFSIZ];;
	cin.getline(s,BUFSIZ-1,'\n');
	FILE *fp=fopen(s,"rb");

	if(fp==NULL){
		cout<<"Enter number of nodes: ";
	
		cin>>node_number;Graph graph_obj(node_number,fp);
	}

	fread(&node_number,sizeof(int),1,fp);
	
	Graph graph_obj(node_number,NULL );

	

	cout<<"Enter source index: ";
	cin>>source;
	if(source>node_number-1)
	{
		cout<<"Error!"<<endl;
		return -1;
	}
	cout<<"Enter destination index: ";
	cin>>destination; 
	if(destination>node_number-1)
	{
		cout<<"Error"<<endl;
		return -1;
	}
	cost =graph_obj.find_shortest_path_cost(source,destination);

	cout<<"The shortest path between "<<source<<" i cvora "<<destination<<
		" has cost "<<cost<<"!"<<endl;
	
	graph_obj.show_path(source,destination);
	
	return 0;
}

I tried at the others forums but there was no response from anybode

I hope you will help me

Thanks in advance!!!

machinated · #2 08-May-2004, 08:17

what are the specific problems you are having reading from the file? Give output examples and specific code from your program that you think is causing the problem.

Pandiani · #3 08-May-2004, 10:06

Just compile and see for yorself.
I have VC++.net and having run time error:
in file fopen.c
...........
Expression *file !=_T( '\0' );

I'm also open for suggestion how to manage saving graph to file.
I choose to save only adjmatrix. Maybe there aare some better way
Thanks

WaltP · #4 08-May-2004, 11:02

Quote:

Originally Posted by Pandiani

Just compile and see for yorself.
I have VC++.net and having run time error:

So you want help, and we have to run out and buy VC++.net to see what your problem is? I don't think so. You'll get better help by giving a detailed explanation about what is happening, where the problem is, post the code in question (not 300 lines we have to search thru), and what you expected it to do rather than "I have a problem, run this and fix it for me."

It's not surprising there was no response at other forums.

machinated · #5 08-May-2004, 11:16

figuring this out will take me a while with all the code, and plus i don't know anything about the c method of dealing with files using FILE*. I'll first have to read up on that. i'll post the reply in a little while if you can wait.

Garth Farley · #6 08-May-2004, 11:44

Hey,
since your original code is written in C++, why resort to old C style FILE pointers? The fstream library is far better at handling it, and behaves very much similarily to iostream.

WaltP also has a very valid point (except for needing VisualC++, your original code compiles grand with gcc). You're not giving us enough to work with here. Haven't you tried practising with file reading/writing before using it properly? Many of us (myself included) are unfamiliar with this algorithm, I've barely heard of Graphs myself.

How do you wish to store the graph data? In the form of a table perhaps, as displayed www.brunel.ac.uk
Could you explain the terminology, or even just show us the bits you're having trouble with?

We can help you, but don't make us do your legwork.
GF

Pandiani · #7 08-May-2004, 12:21

Sorry guys, you're right.
That will not happen again, I promise.
I figure out what is cusing run time error. My programs crashes with error message which tells that it happened in fopen.c. That means that error occures when trying to open files in that line

CPP / C++ / C Code:

 *file !=_T('\0');

suggest that I 'm trying to open file with null character. That means that cin catches something else and not wait for user input (getline(cin,s))
consider this much simpler problem:

CPP / C++ / C Code:

#include <fstream>
#include <iostream>
#include <string>
using namespace std;
class Array
{
	int len;
	double* array;
public:
	Array(int l):len(l)
	{
		array=new double[len];
	}
	~Array(){delete [] array;}
	void load_array();
	void write_to_file();
};

void Array::load_array()
{
	cout<<"Loading array:"<<endl;
	for(int i=0;i<len;i++)
		 cin>>array[i];
	
}
void Array::write_to_file()
{
	string s;
	cout<<"Enter name for file: ";
	
	cin.ignore(80,'\n');//this line solves problem
	getline(cin,s);
	ofstream ofs(s.c_str(),ios_base::binary);
		ofs.write((char*)&len,sizeof(int));
	for(int i=0;i<len;i++)
		ofs.write((char*)&array[i],sizeof(double));
	ofs.close();
}

int main()
{
	int number;
	cout<<"Enter number of elements: ";
	cin>>number;
	Array a(number);
	a.load_array();
	a.write_to_file();

}

I'm much better with good old C when it comes to dealing with files.
I found in MSDN some infos so I use ofstream and ifstream.

I use 80 character in ignore list, but that is not long therm solution, how big number I must enter, or there is a better way like flushing stdin in C?

P.S.
Are there someone of you who is good at graphs and Dijkstra algorithm especially?
I need someone to consult with about shortest paths algorithms.

svalentina · #8 22-Jul-2005, 04:48

Hi! I have to write a C++ Code for shortest path algorithm, but I don't know this language; the code written by Pandiani woulb be perfect but he says that it doesn't work in file reading/saving...
Could anybody help me? It's very important for me!
Thanks

ctyc · #9 16-Jul-2006, 08:07

Hi ! I know this program is find shortest path so longest path can use it find out? Would you tell me how to find out longest path on this program? Thank you.

cpit · #10 17-Jul-2006, 04:40

Hi,

I have implemented the Dijkstra's shortest path with combinatoric, that is, given N nodes and L links, the program run all possible graphs and calculates the mean of hops.

regards,

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
[Tutorial] Standard I/O	aaroncohn	C Programming Language	20	27-Feb-2004 22:07

shortest path algorithm and file saving

Shortest path algorithm

Re: shortest path algorithm and file saving

Re: shortest path algorithm and file saving