Classe and graphs

[CPT]

As the title suggests I need to write the class of a graph object. It is required that I write a function that prints the graph determine if the graph has conex components,what are the cinex components, if the graph has cycles, and to determine the shortest and longest road between two nodes
This what i have so far:

#ifndef _GRAF_H_
#define _GRAF_H_

#include<iostream>
#include<conio.h>
using namespace std;

const int MATR_DIM=500;//constant for the size of the matrix
class CGraf
{
	int matr_adi[MATR_DIM][MATR_DIM]; //Adjacency matrix
	int nr_vertices;				 //The actual number of vertices
public:
	CGraf();
	CGraf(int _nr_vertices)// class constructor
	:nr_vertices(_nr_vertices)
	{};
	void BF(int xp);//breadth first
	void read();//reads the adjancency matrix of the graph
    void print();//prints on the screen the graph
	bool det_conex();//determines if the graph contains conex components
	void det_comp();//determines the conex components
	void cycles();//determines if graph has cycles		
	void paths();//determines the longest and the shortest path between two nodes
	~CGraf();//destructor
};

#endif

and here is my definition of the functions:

#include "graf.h"

int p,u,C[MATR_DIM],viz[MATR_DIM]; //C is a queue, viz hold the list for visited nodes "p" is the first in the queue, "u" is the last

void CGraf::BF(int xp)
{
	for(int j=1;j<=CGraf::nr_vertices;j++)
		viz[j]=0;
	C[1]=xp;
	viz[xp]=1;
	p=1;
	u=1;
	while(p<=u)
	{
		for(int i=1;i<=CGraf::nr_vertices;i++)
			if((viz[i]==0)&&(CGraf::matr_adi[C[p],i]==1))
			{
				u++;
				C[u]=i;
				viz[i]=1;
			}
		p++;
	}
};


void CGraf::read()
{
	int n=CGraf::nr_vertices;

	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
		{
			cout<<"matrix["<<i<<","<<j<<"]=";
			cin>>CGraf::matr_adi[i][j];
			CGraf::matr_adi[j][i]=CGraf::matr_adi[i][j];
		}
		cout<<"Adjacency matrix:"<<endl;
		for(int i=0;i<n;i++)
		for(int j=i+1;j<=n;j++)
			cout<<CGraf::matr_adi[i][j];
};

void CGraf::print()
{
	for(int i=1;i<=u;i++)
		cout<<C[i];
};
bool CGraf::det_conex()
{
	int i,j,k,a[MATR_DIM][MATR_DIM],n=CGraf::nr_vertices;
	bool value=true;
	
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			a[i][j]=CGraf::matr_adi[i][j];
	//Roy-Warshall algoritm to determine the chain matrix
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if((i!=k)&&(j!=k))
					if(a[i][j]==0)
						a[i][j]=a[i][k]*a[k][j];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j)
				if(a[i][j]==0)//if the chain matrix contains a 0 then the graph isn't conex
					value=false;
	if(value)
		cout<<"Graph is conex"<<endl;
	else
		cout<<"Graph isn't conex"<<endl;
	
	return value;

};

so far, I have 2 errors on this line

if((viz[i]==0)&&(CGraf::matr_adi[C[p],i]==1))

these errors are:
error C2446: '==' : no conversion from 'int' to 'int *'
error C2040: '==' : 'int [500]' differs in levels of indirection from 'int'
why do I have these errors?

[daviddoria]

Here is the fix for your error - you have to dereference the value:

if(*(CGraf::matr_adi[C[p],i])==1)

But yikes, you really really really should consider using more descriptive variable names, and COMMENT COMMENT COMMENT!

There is some personal preference involved, but here is what I would change:

matr_adi -> AdjacencyMatrix
nr_vertices -> NumberOfVertices
BF -> BreadthFirst
det_conex -> HasConnectedComponents
void cycles() -> bool HasCycle()
void paths() -> void paths(int nodeA, int nodeB, int &shortestPathLength, int &longestPathLength)
xp -> ??
u -> ??
p -> ??

See what I mean?

You want someone who reads your code to have as easy of a time understanding what is going on as possible.

Good luck,

David

[Tellalca]

Good advice from David. Even you cannot understand this code after not seeing it for a week.