Prim's Algorithm for MST: File IO Error

[r1409]

hi all
i have an assignment in which i have to use object-oriented programming to read from an input file(say: input.txt), use prim's algorithm and calculate the weight of a minimun spanning tree and then save the output to a file(output.txt).

the problem with my code is that the program closes as soon as i compile and run it, however, the output is correctly printed and saved in the output file.

can anyone please help me with this.

this is the content of input.txt :

9 13
1 2 10
1 9 60
1 3 30
2 9 50
2 3 20
3 9 40
3 4 70
4 5 110
3 5 120
3 6 100
5 6 130
6 8 90
6 7 80

and this the program that i have:

#include <memory.h>
#include <stdio.h>
#include <iostream.h>

// Create the edge type
struct Edge
{
	int from;
	int to; 
	int weight; 
	bool inTheCut; 
};
typedef Edge* pEdge; 


// adjacency list
struct ListIt
{
	int value;
	ListIt *p_next;
}; 

// typedef for the pointer type
typedef ListIt* pListIt;

pEdge edges;
pEdge edgesPr; 

int n,m; 

int *tree; 
int *ancient;
int **distanceMatrix; 
FILE *fp;

pListIt* adjacencyList; // 100000 is the maximum vertexes

void read(); 
int Prim(int at);
bool add(pListIt &dest, int val); 
int compareEdges(const void* el1, const void* el2);
int min_vag();

int main()
{
	read(); 
        cout<<"\n"; 
	cout<<"\n\n The edges and weights of the MST: \n\n"; 
	Prim(1);
	fclose(fp);
        system("PAUSE");
	return 0;
}

//Read in the data from the same folder as the code being compiled in
void read()
{	 
	fp = freopen("input.txt", "r", stdin);
	if(fp == NULL) {
        cout<<"failed to open input.txt \n";
        system("PAUSE");
    }
    
        scanf("%d", &n);
	scanf("%d", &m);
	
    fp = freopen("outfile.txt", "w", stdout);
    if(fp == NULL) {
        cout<<"failed to open out.txt \n";
        system("PAUSE");
    }
    
	tree = (int*) calloc(n+1, sizeof(int)); 
	ancient = (int*) calloc(n+1, sizeof(int)); 
	edges = (pEdge)malloc(m*sizeof(Edge)); 
	adjacencyList = (pListIt*) calloc(n+1,sizeof(pListIt));

	distanceMatrix = (int**) calloc(n+1, sizeof(int*)); 
	for (int j = 1; j <=n; ++j)
	{
		distanceMatrix[j] = (int*) calloc(n+1, sizeof(int)); 
	}


	int from,to,distance; 

	for(int i =0; i< m; ++i)
	{
		scanf("%d%d%d", &from, &to, & distance);

		add(adjacencyList[from], to);
		add(adjacencyList[to], from);

		edges[i].from = from;
		edges[i].to = to;
		edges[i].weight = distance;
	}
}

//Compare two edge types according to their weight
int compareEdges(const void* edge1, const void * edge2)
{
	pEdge first = (pEdge)edge1;
	pEdge second = (pEdge)edge2;

	return first->weight - second->weight; 
}

//Prims Algoritm to create the minimal spanning tree
int Prim(int at)
{
	int i = 0; 
	
	memset(tree, 0, (n+1)*sizeof(int)); 

	tree[at] = 1; 
	ancient[at]  = 0 ;
	
	// sort the edge list
	qsort((void*)edges,m,sizeof(Edge),compareEdges);

	// build up the tree
	for (i = 0; i < m; ++i)
	{
		distanceMatrix[edges[i].from][edges[i].to  ] = i;
		distanceMatrix[edges[i].to  ][edges[i].from] = i;

		if (edges[i].from == at || edges[i].to == at)
		{
			edges[i].inTheCut = true;
		}
		else
		{
			edges[i].inTheCut = false;
		}
	}

	int overallWeight = 0; 
	int curent = 0; 
	int addedVertex = 1; 
	int neighborVertex = 0;
	int neighborEdge = 0; 
	pListIt p = NULL; 
	int j = 0; 

	for(i = 1; i < n; ++i)
	{
		for ( j =0 ; j < m; ++j)
		{
			if (edges[j].inTheCut)
			{
				curent = j; 
				break;
			}
		}

		printf( "   %d)  %d - %d -> %d \n",i, edges[curent].from,edges[curent].to, edges[curent].weight);

		overallWeight += edges[curent].weight;

		if (tree[edges[curent].from] == 1)
		{
			addedVertex = edges[curent].to;
			ancient[addedVertex] = edges[curent].from; 
		}

		tree[addedVertex] = 1; 

		for (p = adjacencyList[addedVertex]; p != NULL; p = p -> p_next)
		{
			neighborVertex = p->value;
			neighborEdge = distanceMatrix[addedVertex][neighborVertex];

			if (tree[neighborVertex] == 1)
				edges[neighborEdge].inTheCut = false; // reset if both ends are there
			else
				edges[neighborEdge].inTheCut = true; // set if only one is there
		}
	}

	printf( "\n\n Size of the MST: %d " , overallWeight);
	cout<<"\n\n";
}

// Check for correct order
bool add(pListIt &dest, int val)
{
	//create the item
	pListIt p;
	p = (pListIt) malloc(sizeof(ListIt));
	p -> value = val;	

	if(!dest)  // first item addition 
	{
		p -> p_next = NULL;
		dest = p;	
	}
	else
	{	
		pListIt find = dest; 
		pListIt at = NULL; 

		// first find the first greater number, insert before
		while(find && find->value <= val)
		{
			if( find->value == val) // do not add a duplicate
			{
				free(p);
				return false;
			}

			at = find; 
			find = find->p_next;					
		}

		// insert at 
		if (at) // insert at a valid point
		{
			p->p_next = at->p_next;
			at->p_next = p; 				
		}
		else // insert at the start
		{
			p->p_next = dest; 
			dest = p; 
		}
	}

	return true; 
}

i know the code is very long but i would be very grateful if anyone would please help me.

[daviddoria]

First, why not change the headers to

#include <memory.h>
#include <cstdio>
#include <cstdlib> //required for system()
#include <iostream>

to use the "new" way.

Also, I think the "c++ way" is to use cout and endl instead of printf and \n.

Now to the main problem

The first output ("opened input") is displayed, but the second one ("opened out") is not. Maybe someone can help you with finding the problem now that it is narrowed down to these few lines.

std::cout<<"opened input.txt " << std::endl;
    scanf("%d", &n);
    scanf("%d", &m);
	
    fp = freopen("outfile.txt", "w", stdout);
    if(fp == NULL) 
    {
	cout<<"failed to open out.txt \n";
	system("PAUSE");
    }

cout<<"opened out.txt" << std::endl;

Something must be happening that is breaking the standard output stream. If you're just trying to write ascii files, you should use ofstream.

Dave

[r1409]

thanks Dave

the reason i am using printf is that i'm not sure of the syntax to use with cout statements when writing to output file, for instance, i don't know how to do this using cout and out statements:

printf( " %d) %d - %d -> %d \n",i, edges[curent].from,edges[curent].to, edges[curent].weight);

thanks for the help.

i tried by using:

fp = fopen("input.txt", "r");

in line 58
and this in line 67:

fp = fopen("outfile.txt", "w");

but then the program does not do anything.

[daviddoria]

Here is how you use ofstream:

http://www.java2s.com/Code/Cpp/File/Toreadorwritetoafileyouincludefstream.htm

I'd definitely stop using fopen :)

Dave