Shortest distance

A.First Edition
This is first edition of fifth assignment of comp352. 
B.The problem
How to find out distance between two vertices in a simple graph without weight?
Here is the graph input file.
C.The idea of program
 
1. Using BFS.
2. Using my own Matrix class as an input tool because I am too lazy to write again the same routine.
3. Re-write "createGraph" from Mr. shaffer's code because I want to steal his idea.(:
4. Abusively using "mark" as recording the distance from "starting" vertices because I want to confuse the marker. (:
5. I feel regret that I didn't use my own version of "BFS" to finish the program because I forgot to do it.
6. I kept thinking about using "Kruskal" or "Prim" algorithm to make this program even capable to search distance within a "weighted" graph.
7. I should change the code a little bit to enable to output the path. This requires that I modify the graph
class to add one more field to represent the parent of current vertex so that when finding the "end" vertex" we can "backtrack" the path by this information. I have done this in "Kruskal" algorithms because it is said by the instructor of comp239 that "the algorithm will give you the shortest length between two vertex, the shortest path is only a side effect it may give you provided you do the bookkeeping job yourself." I do miss the teacher even though he is only a part-time instructor and he usually made many mistakes. He is a purely mathematisian.
D.The major functions
C.Further improvement
1. output shortest path.
2. capable for weighted graph.
3. Using Kruskal or Prim algorithms.
 
//this is main program: shortest.cpp
/*/////////////////////////////////////////////////////////////////////////////
Author: Qingzhe Huang
Date: Nov. 26, 2003
Purpose: Use graph to search shortest distance between two vertices.
features:
	1. I changed meaning of "Mark" to be level or distance from starting vertex.
	2. I use my own "Matrix" class for input tools which requires the input of graph
	to be a adjacency matrix.
	3. After reading graph into my matrix, I iterate matrix to create graph.
	4. The BFS algorithm is straight forward as I simply check if the "other"
	vertex is "dequeued" or not. If yes, that means we find out the distance of them.
	And its mark which is the distance will be returned.
	5. All default distance is -1. So, suppose we didn't find the searching vertex, we simply
	return -1.
*/////////////////////////////////////////////////////////////////////////////


#include <iostream>
#include "Matrix.h"
#include "Grlist.h"
#include "Graph.h"
#include "Grmat.h"
#include "AQueue.h"


using namespace std;


Graph* createGraph(const char* fileName, bool edgeList=true);

void Gprint(Graph* G);

int BFS(Graph* pG, int start, int end);

int main()
{
	Graph* pG;
	pG = createGraph("c:\\graph1.txt");
	Gprint(pG);
	cout<<"the distance between :"<<BFS(pG, 0, 4)<<endl;

	return 0;
}

int BFS(Graph* pG, int start, int end)
{
	int v, w;
	int level=0;
	//set all vertex as infinite
	for (int i=0; i<pG->n(); i++)
	{
		pG->setMark(i, -1);
	}
	AQueue<int> Q;
	Q.enqueue(start);
	//the distance of start to start is 0
	pG->setMark(start, level);
	
	while (Q.length()!=0)
	{
		Q.dequeue(v);
		if (v==end)//found out the vertex
		{
			return pG->getMark(v);//the level
		}
		level = pG->getMark(v)+1; //for all his son, the level is one more
		for (w=pG->first(v); w<pG->n(); w=pG->next(v, w))
		{
			if (pG->getMark(w)==-1)
			{
				pG->setMark(w, level);
				Q.enqueue(w);
			}
		}
	}
	return -1;
}







Graph* createGraph(const char* fileName, bool edgeList)
{
	Matrix M;
	Graph* pG;
	M.readFromFile(fileName);
	M.display();
	cout<<endl;
	if (edgeList)
	{
		pG = new Graphl(M.col());
	}
	else
	{
		pG = new Graphm(M.col());
	}
	for (int r=0; r<M.row(); r++)
	{
		for (int c=0; c<M.col(); c++)
		{
			if (edgeList)
			{
				if (M.items(r, c)!=0)
				{
					pG->setEdge(r, c, M.items(r, c));
				}
			}
			else
			{
				pG->setEdge(r, c, M.items(r, c));
			}

		}
	}
	return pG;
}

void Gprint(Graph* G)
{
	int i, j;

	cout << "Number of vertices is " << G->n() << "\n";
	cout << "Number of edges is " << G->e() << "\n";

	cout << "Matrix is:\n";
	for (i=0; i<G->n(); i++) 
	{
		for(j=0; j<G->n(); j++)
		{
			cout << G->weight(i, j) << " ";
		}
		cout << "\n";
	}
}

//This is the matrix.h
#ifndef MATRIX_H
#define MATRIX_H

const int MaxRow = 10;
const int MaxCol = 10;
const double LIMIT = 0.01;


class Matrix
{
private:
	int rowNum;
	int colNum;
	double lst[MaxRow][MaxCol];
protected:
	void mul(int dest, double scalor);
	void mul(int source, int dest, double scalor);
public:
	Matrix();
	Matrix& transform(int index1, int index2);
	int row() const {return rowNum;}
	int col() const {return colNum;}
	void setRow(const int newRow) { rowNum = newRow;}
	void setCol(const int newCol) { colNum = newCol;}
	void display(bool displayNumber= false);
	double& items(int r, int c);
	void initialize();
	void readFromFile(const char* fileName);
	void assign(const Matrix& other);
	Matrix& operator = (Matrix& other);
	Matrix& transposition();	
	bool operator==(Matrix& other);
	bool operator!=(Matrix& other);
};

class MathMatrix: public Matrix
{
public:
	void echelon(int r, int c, bool reduced=true);
	//Linear Homogeneous Recurrsive Relation with Constant Coefficients
	void LHRRCC(double* roots, double* initials, int degree);
	Matrix& operator+(Matrix other);
	Matrix& operator *(double i);
	Matrix& operator *(Matrix otherMatrix);  
};

class LogicMatrix: public Matrix
{
protected:
	
public:
	Matrix& operator &&(Matrix otherMatrix);
	Matrix& operator ||(Matrix otherMatrix);
	Matrix& power(int exponent);
	bool reflexive();
	bool symmetric();
	bool antiSymmetric();
	bool transitive();
	bool equivalent();
	bool partialOrder();
	Matrix& transitiveClosure();
	Matrix& reflexiveClosure();
	Matrix& symmetricClosure();
	Matrix& warshall();
	bool isomorphic(LogicMatrix& other);
	int calcDegree(int* array);
};

#endif

//this is matrix.cpp for my matrix class used for inputting. (It will read in an matrix and
//represent that matrix. Haha...)
 
#include <iostream>
#include <cmath>
#include <fstream>
#include "Matrix.h"

using namespace std;

Matrix& LogicMatrix::warshall()
{
	int n = row(); //n is dimention of matrix
	for (int k=0; k<n; k++)
	{
		for (int r=0;r<n; r++)
		{
			for (int c=0; c<n; c++)
			{
				items(r,c) = items(r,c)|| items(r,k) && items(k,c);
			}
		}
	}
	return *this;
}



Matrix& LogicMatrix::symmetricClosure()
{
	for (int r=0; r< row(); r++)
	{
		for (int c=0; c< col(); c++)
		{
			if (items(r,c)==1)
			{
				items(c, r) = 1;
			}
		}
	}
	return *this;
}

Matrix& LogicMatrix::reflexiveClosure()
{
	for (int i=0; i<row(); i++)
	{
		items(i, i) = 1;
	}
	return *this;
}


bool LogicMatrix::partialOrder()
{
	return reflexive()&&antiSymmetric()&&transitive();
}


bool LogicMatrix::equivalent()
{
	return reflexive()&&symmetric()&&transitive();
}


Matrix& LogicMatrix::transitiveClosure()
{
	int dim = col();
	LogicMatrix N;
	N = *this;
	for (int i = 1; i<=dim; i++)
	{
		(Matrix)N = (Matrix)(N ||power(i));
	}
	*this = N;
	return *this;
}


Matrix& LogicMatrix::operator ||(Matrix otherMatrix)
{
	int dim = col();
	for (int r = 0; r< dim; r++)
	{
		for (int c=0; c< dim; c++)
		{
			items(r,c) = (int)items(r,c) ||(int)otherMatrix.items(r, c);
		}
	}
	return *this;
}


bool LogicMatrix::reflexive()
{
	bool result = true;
	for (int i =0; i<col(); i++)
	{
		result = result&&items(i, i);
	}
	return result;
}

bool LogicMatrix::symmetric()
{
	int dim = col();  //since the function will be called nxn times, better use variable.
	for (int r = 0; r< dim; r++)
	{
		for (int c = r; c< dim; c++)
		{			
			if ((int)items(r,c)^(int)items(c,r))//exclusive or
			{
				return false;
			}
		}
	}
	return true;
}

bool LogicMatrix::antiSymmetric()
{
	int dim = col();
	for (int r =0; r< dim; r++)
	{
		for (int c = r; c< dim; c++)
		{
			if (items(r,c)&&items(c,r))
			{
				if (r != c)
				{
					return false;
				}
			}
		}
	}
	return true;
}

int LogicMatrix::calcDegree(int *array)
{
	int degree=row();
	int index=0;
	for (int r=0; r<row();r++)
	{
		for (int c=0; c<col();c++)
		{
			array[r] += items(r, c);
		}
		if (array[r]<degree)
		{
			degree = array[r]; //to find the smallest degree;
			index = r;
		}
	}
	return index;//the index that have smallest degree
}

bool LogicMatrix::isomorphic(LogicMatrix& other)
{
	int ownIndex=0;
	int otherIndex=0;
	if (row()!=col()||row()!=other.row()||other.row()!=other.col())
	{
		return false;
	}
	int degree[MaxRow]={0};
	int otherDegree[MaxRow] = {0};
	ownIndex = this->calcDegree(degree);
	otherIndex = other.calcDegree(otherDegree);
	while (degree[ownIndex] == otherDegree[otherIndex])
	{

		return false;
	}



	return true;
}

bool LogicMatrix::transitive()
{
	int dim = col();
	for (int r =0; r< dim; r++)
	{
		for (int c=0; c< dim; c++)
		{
			if (items(r,c))//if find an entry which is 1's
			{
				for (int i =0; i< dim; i++) // try to find in c'th row 
				{
					if (items(c, i))
					{
						if (!items(r, i))
						{
							return false;
						}
					}
				}
			}
		}
	}
	return true;
}

Matrix& LogicMatrix::operator &&(Matrix otherMatrix)
{
	bool dummy=false;
	int dim = col();  //as this function is used so many times, better use variable, 
	for (int r =0; r<dim; r++)
	{
		for (int c =0; c<dim; c++)
		{
			for (int i=0; i<dim; i++)
			{
				dummy = dummy||(items(r,i)&&otherMatrix.items(i, c));
			}
			items(r, c) = dummy;
			dummy = false;
		}
	}
	return *this;
}

Matrix& LogicMatrix::power(int exponent)
{
	Matrix N;
	N = *this; //I have to copy a temp Matrix to keep original one
	for (int i=1; i<exponent; i++)
	{
		this->operator &&(N);
	}
	return (*this);
}

Matrix& Matrix::transposition()
{
	double hold;
	int temp;
	for (int r =0; r< rowNum; r++)
	{
		for (int c=0; c< r; c++)
		{
			hold = lst[r][c];
			lst[r][c] = lst[c][r];
			lst[c][r] = hold;
		}
	}
	temp = rowNum;
	rowNum = colNum;
	colNum = temp;
	return (*this);
}


void MathMatrix::LHRRCC(double *roots, double* initials, int degree)
{
	for (int r=0; r<degree; r++)
	{
		for (int c=0;c<degree; c++)
		{
			if (r==0)
			{
				items(r,c) = 1;
			}
			else
			{
				items(r,c) = items(r-1,c)*roots[c];
			}
		}
		items(r,c) = initials[r];
	}
	setRow(degree);
	setCol(degree+1);
}

Matrix& MathMatrix::operator +(Matrix other)
{
	if (row()!= other.row() || col()!= other.col())
	{
		cout<<"\nTwo matrix has different row or col number!\n";
		return (*this);
	}
	else
	{
		for (int r=0; r< row(); r++)
		{
			for (int c=0; c< col(); c++)
			{
				items(r, c) +=other.items(r, c);
			}
		}
		return (*this);
	}
}

Matrix& MathMatrix::operator *(Matrix other)
{
	double total =0;
	Matrix temp;
	temp.setRow(row());
	temp.setCol(other.col());

	if (col()!=other.row())
	{
		cout<<"\nrow & col are not same!\n";
	
	}
	else
	{
		for (int r =0; r< row(); r++)
		{
			for (int c=0; c<other.col(); c++)
			{
				total =0;
				for (int i=0; i<col(); i++)
				{
					total += items(r,i) * other.items(i, c);
				}
				temp.items(r, c) = total;
			}
		}
		this->assign(temp);	
	}
	return (*this);
}
	
bool Matrix::operator==(Matrix& other)
{
	if (row()!=other.row()||col()!=other.col())
	{
		return false;
	}
	for (int r=0; r<row(); r++)
	{
		for (int c=0; c<col(); c++)
		{
			if (items(r,c)!=other.items(r,c))
			{
				return false;
			}
		}
	}
	return true;
}

bool Matrix::operator !=(Matrix& other)
{
	return !(this->operator ==(other));
}
			
Matrix& Matrix::operator =(Matrix& other)
{
	setRow(other.row());
	setCol(other.col());
	for (int r=0; r< other.row(); r++)
	{
		for (int c=0; c< other.col(); c++)
		{
			lst[r][c] = other.items(r, c);
		}
	}
	
	return (*this);
}

void Matrix::assign(const Matrix& other)
{
	this->operator =((Matrix&)other);
}


void Matrix::mul(int dest, double scalor)
{
	for (int c=0; c< colNum; c++)
	{
		lst[dest][c] *= scalor;
	}
}

Matrix& MathMatrix::operator *(double i)
{
	for (int r=0; r<row(); r++)
	{
		for (int c=0; c<col(); c++)
		{
			items(r, c) *= i;
		}
	}
	return (*this);
}

void MathMatrix::echelon(int r, int c, bool reduced)
{
	if (r<row()&&c<col()&&c<row())
	{
		if (items(r, c) !=0)
		{
			mul(r, 1/items(r,c));   //make it 1 for this row
			for (int i=(!reduced?r+1:0); i< row(); i++)
			{
				if (i!=r)
				{
					mul(r, i, -items(i,c));
				}
			}	
			echelon(r+1, c+1, reduced);
		}
		else
		{
			echelon(r+1, c, reduced);
		}
	}
	else
	{
		if (c<row()&&c<col())
		{
			echelon(0, c, reduced);
		}
	}
}

void Matrix::mul(int source, int dest, double scalor)
{
	for (int c=0; c< colNum; c++)
	{
		lst[dest][c] += lst[source][c]*scalor;
	}
}


double& Matrix::items(int r, int c)
{
	return lst[r][c];
}

void Matrix::readFromFile(const char* fileName)
{
	int r=0, c=0;
	char ch;
	ifstream f;
	f.open(fileName);
	while (!f.eof())
	{
		ch = f.peek();
		
		if (ch!=10)  //return char
		{
			
			f>>lst[r][c];
			c++;
			if (c>colNum)
				colNum = c;
		}
		else
		{
			f.ignore();
			r++;
			setCol(c);
			c =0;
		}
	}
	if (r!=0)
	{
		setRow(r+1);
	}
}


void Matrix::initialize()
{
	for (int r=0; r < rowNum; r++)
	{
		for (int c=0; c< colNum; c++)
		{
			lst[r][c] = r*2+c;
		}
	}	
}

Matrix& Matrix::transform(int index1, int index2)
{
	double hold;
	if (index1<rowNum&&index2<rowNum)
	{
		for (int i=0; i<colNum; i++)
		{
			hold = lst[index1][i];
			lst[index1][i] = lst[index2][i];
			lst[index2][i] = hold;
		}
		for (i=0; i< rowNum; i++)
		{
			hold = lst[i][index1];
			lst[i][index1] = lst[i][index2];
			lst[i][index2] = hold;
		}
	}
	return *this;
}




void Matrix::display(bool displayNumber)
{
//	int temp;
	long preFlag;
	int number=0;
	preFlag = cout.flags();
//	temp = cout.precision(4);
//	cout.setf(ios::fixed);
	
	cout<<"\nrow\\col";
	for (int c=0; c< colNum; c++)
	{
		cout<<"  "<<c;
	}
	cout<<"\n\n";
	for (int r = 0; r< rowNum; r++)
	{
		cout<<r<<"\t ";
		number = 0;
		for (c = 0; c< colNum; c++)
		{
			cout<<(fabs(lst[r][c])<LIMIT?0:lst[r][c])<<"  ";
			if (fabs(lst[r][c])>=LIMIT)
			{
				number++;
			}
		}
		if (displayNumber)
		{
			cout<<number;
		}

		cout<<endl;
	}
//	cout.precision(temp);
	cout.flags(preFlag);
}

Matrix::Matrix()
{
	rowNum = 5;
	colNum = 5;
	initialize();
}
 
//this is AQueue.h
#ifndef AQUEUE_H
#define AQUEUE_H
// This is the file to include in your code if you want access to the
// complete AQueue template class

// First, get the declaration for the base stack class
#include "queue.h"

// Array-based queue implementation
template <class Elem> class AQueue: public Queue<Elem> {
private:
  int size;                  // Maximum size of queue
  int front;                 // Index of front element
  int rear;                  // Index of rear element
  Elem *listArray;           // Array holding queue elements
public:
  AQueue(int sz =DefaultListSize) { // Constructor 
    // Make list array one position larger for empty slot
    size = sz+1;
    rear = 0;  front = 1;
    listArray = new Elem[size];
  }
  ~AQueue() { delete [] listArray; } // Destructor
  void clear() { front = rear; }
  bool enqueue(const Elem& it) {
    if (((rear+2) % size) == front) return false;  // Full
    rear = (rear+1) % size; // Circular increment
    listArray[rear] = it;
    return true;
  }
  bool dequeue(Elem& it) {
    if (length() == 0) return false;  // Empty
    it = listArray[front];
    front = (front+1) % size; // Circular increment
    return true;
  }
  bool frontValue(Elem& it) const {
    if (length() == 0) return false;  // Empty
    it = listArray[front];
    return true;
  }
  virtual int length() const
   { return ((rear+size) - front + 1) % size; }
};

#endif
//this is base class Queue----Queue.h
#ifndef QUEUE_H
#define QUEUE_H

// Abstract queue class
template <class Elem> class Queue {
public:
// Reinitialize the queue. The user is responsible for
// reclaiming the storage used by the stack elements.
virtual void clear() = 0;
// Place an element at the rear of the queue. Return
// true if successful, false if not (if queue is full).
virtual bool enqueue(const Elem&) = 0;
// Remove the element at the front of the queue. Return
// true if succesful, false if queue is empty.
// The element removed is returned in the first parameter.
virtual bool dequeue(Elem&) = 0; // Remove Elem from front
// Return in first parameter a copy of the front element.
// Return true if succesful, false if queue is empty.
virtual bool frontValue(Elem&) const = 0;
// Return the number of elements in the queue.
virtual int length() const = 0;
};

#endif
//this is link.h
#ifndef LINK_H
#define LINK_H

// Singly-linked list node
template <class Elem> class Link {
public:
  Elem element;      // Value for this node
  Link *next;        // Pointer to next node in list
  Link(const Elem& elemval, Link* nextval =NULL)
    { element = elemval;  next = nextval; }
  Link(Link* nextval =NULL) { next = nextval; }
};

#endif
//this is list.h
#ifndef LIST_H
#define LIST_H

// List abstract class
template <class Elem> class List {
public:
  // Reinitialize the list.  The client is responsible for
  // reclaiming the storage used by the list elements.
  virtual void clear() = 0;
  // Insert an element at the front of the right partition.
  // Return true if successful, false if the list is full.
  virtual bool insert(const Elem&) = 0;
  // Append an element at the end of the right partition.
  // Return true if successful, false if the list is full.
  virtual bool append(const Elem&) = 0;
  // Remove the first element of right partition. Return
  // true if successful, false if right partition is empty.
  // The element removed is returned in the parameter.
  virtual bool remove(Elem&) = 0;
  // Place fence at list start, making left partition empty
  virtual void setStart() = 0;
  // Place fence at list end, making right partition empty
  virtual void setEnd() = 0;
  // Move fence one step left; no change if already at start
  virtual void prev() = 0;
  // Move fence one step right; no change if already at end
  virtual void next() = 0;
  // Return length of left partition
  virtual int leftLength() const = 0;
  // Return length of right partition
  virtual int rightLength() const = 0;
  // If pos or more elements are in the list, set the size
  // of left partition to pos and return true.  Otherwise,
  // do nothing and return false.
  virtual bool setPos(int pos) = 0;
  // Return in first parameter the first element  of the
  // right partition.  Return true if successful, false
  // if the right partition is empty.
  virtual bool getValue(Elem&) const = 0;
  // Print the contents of the list
  virtual void print() const = 0;
};

#endif
//this is llist.h (the link-list)
#ifndef LLIST_H
#define LLIST_H

// This is the file to include in your code if you want access to the
// complete LList template class

// First, get the declaration for the base list class
#include "list.h"

const int DefaultListSize=50;

// Linked list implementation
template <class Elem> class LList: public List<Elem> {
private:
  Link<Elem>* head;       // Pointer to list header
  Link<Elem>* tail;       // Pointer to last Elem in list 
  Link<Elem>* fence;      // Last element on left side
  int leftcnt;            // Size of left partition
  int rightcnt;           // Size of right partition
  void init() {           // Intialization routine
    fence = tail = head = new Link<Elem>;
    leftcnt = rightcnt = 0;
  }
  void removeall() {   // Return link nodes to free store
    while(head != NULL) {
      fence = head;
      head = head->next;
      delete fence;
    }
  }
public:
  LList(int size=DefaultListSize) { init(); }
  ~LList() { removeall(); }  // Destructor
  void clear() { removeall(); init(); }
  bool insert(const Elem&);
  bool append(const Elem&);
  bool remove(Elem&);
  void setStart()
    { fence = head; rightcnt += leftcnt; leftcnt = 0; }
  void setEnd()
    { fence = tail; leftcnt += rightcnt; rightcnt = 0; }
  void prev();
  void next() {
    if (fence != tail) // Don't move fence if right empty
      { fence = fence->next; rightcnt--; leftcnt++; }
  }
  int leftLength() const  { return leftcnt; }
  int rightLength() const { return rightcnt; }
  bool setPos(int pos);
  bool getValue(Elem& it) const {
    if(rightLength() == 0) return false;
    it = fence->next->element;
    return true;
  }
  void print() const;
};

template <class Elem> // Insert at front of right partition
bool LList<Elem>::insert(const Elem& item) {
  fence->next = new Link<Elem>(item, fence->next);  
  if (tail == fence) tail = fence->next;  // New tail
  rightcnt++;
  return true;
}

template <class Elem> // Append Elem to end of the list
bool LList<Elem>::append(const Elem& item) {
  tail = tail->next = new Link<Elem>(item, NULL);
  rightcnt++;
  return true;
}

// Remove and return first Elem in right partition
template <class Elem> bool LList<Elem>::remove(Elem& it) {
  if (fence->next == NULL) return false; // Empty right
  it = fence->next->element;       // Remember value
  Link<Elem>* ltemp = fence->next; // Remember link node
  fence->next = ltemp->next;       // Remove from list
  if (tail == ltemp) tail = fence; // Reset tail
  delete ltemp;                    // Reclaim space
  rightcnt--;
  return true;
}

// Move fence one step left; no change if left is empty
template <class Elem> void LList<Elem>::prev() {
  Link<Elem>* temp = head;
  if (fence == head) return; // No previous Elem
  while (temp->next!=fence) temp=temp->next;
  fence = temp;
  leftcnt--; rightcnt++;
}

// Set the size of left partition to pos
template <class Elem> bool LList<Elem>::setPos(int pos) {
  if ((pos < 0) || (pos > rightcnt+leftcnt)) return false;
  fence = head;
  for(int i=0; i<pos; i++) fence = fence->next;
  return true;
}

template <class Elem> void LList<Elem>::print() const {
  Link<Elem>* temp = head;
  cout << "< ";
  while (temp != fence) {
    cout << temp->next->element << " ";
    temp = temp->next;
  }
  cout << "| ";
  while (temp->next != NULL) {
    cout << temp->next->element << " ";
    temp = temp->next;
  }
  cout << ">\n";
}


#endif
 
//this is graph.h
#ifndef GRAPH_H
#define GRAPH_H

// Graph abstract class
class Graph {
public:
  // Return the number of vertices
  virtual int n() =0;
  // Return the current number of edges
  virtual int e() =0;
  // Return the index of the first neigbor of given vertex
  virtual int first(int) =0;
  // Return the index of the next neigbor of given vertex
  virtual int next(int, int) =0;
  // Store an edge defined by two vertices and weight
  virtual void setEdge(int, int, int) =0;
  // Delete edge defined by two vertices
  virtual void delEdge(int, int) =0;
  // Return weight of edge connecting two vertices
  // Return 0 if no such edge exists
  virtual int weight(int, int) =0;
  // Get mark value for a vertex
  virtual int getMark(int) =0;
  //  Set mark value for a vertex
  virtual void setMark(int, int) =0;

};

#endif
//this is grlist.h
#ifndef GRLIST_H
#define GRLIST_H
#include <iostream>

using namespace std;

// Used by the mark array
#define UNVISITED 0
#define VISITED 1

#include "link.h"
#include "llist.h"

#include "graph.h"


class Edge {
public:
  int vertex, weight;
  Edge() { vertex = -1; weight = -1; }
  Edge(int v, int w) { vertex = v; weight = w; }
};

// Overload for the Edge << operator
ostream& operator << (ostream& s, Edge e)
  { return(s << "(" << e.vertex << ", " << e.weight << ")"); }

class Graphl : public Graph { // Implement adjacency list
private:
  int numVertex, numEdge;     // Number of vertices, edges
  List<Edge>** vertex; // List headers
  int *mark;                  // Pointer to mark array
public:
  Graphl(int numVert) { // Make graph with numVert vertices
    int i;
    numVertex = numVert;  numEdge = 0;
    mark = new int[numVert]; // Initialize mark array
    for (i=0; i<numVertex; i++) mark[i] = UNVISITED;
    // Create and initialize adjacency lists
    vertex = (List<Edge>**) new List<Edge>*[numVertex];
    for (i=0; i<numVertex; i++)
      vertex[i] = new LList<Edge>();
  }

  ~Graphl() {       // Destructor
    delete [] mark; // Return dynamically allocated memory
    for (int i=0; i<numVertex; i++) delete [] vertex[i];
    delete [] vertex;
  }

  int n() { return numVertex; } // Number of vertices
  int e() { return numEdge; }   // Number of edges

  int first(int v) { // Return first neighbor of v
    Edge it;
    vertex[v]->setStart();
    if (vertex[v]->getValue(it)) return it.vertex;
    else return numVertex;  // Return n if none
  }

  int next(int v1, int v2) { // Gete v1's neighbor after v2
    Edge it;
    vertex[v1]->getValue(it);
    if (it.vertex == v2) vertex[v1]->next();
    else { // Start from beginning of list
      vertex[v1]->setStart();
      while (vertex[v1]->getValue(it) && (it.vertex <= v2))
        vertex[v1]->next();
    }
    if (vertex[v1]->getValue(it)) return it.vertex;
    else return numVertex;  // Return n if none
  }

  // Set edge (v1, v2) to wgt
  void setEdge(int v1, int v2, int wgt) {
//   Assert(wgt>0, "Illegal weight value");
    Edge it(v2, wgt);
    Edge curr;
    vertex[v1]->getValue(curr);
    if (curr.vertex != v2) // If not already there, search
      for (vertex[v1]->setStart();
           vertex[v1]->getValue(curr); vertex[v1]->next())
        if (curr.vertex >= v2) break;
    if (curr.vertex == v2)  // Clear out the current one
      vertex[v1]->remove(curr);
    else numEdge++;
    vertex[v1]->insert(it);
  }

  void delEdge(int v1, int v2) { // Delete edge (v1, v2)
    Edge curr;
    vertex[v1]->getValue(curr);
    if (curr.vertex != v2)  // If not already there, search
      for (vertex[v1]->setStart();
           vertex[v1]->getValue(curr); vertex[v1]->next())
        if (curr.vertex >= v2) break;
    if (curr.vertex == v2) {  // If not, then there is none
      vertex[v1]->remove(curr);
      numEdge--;
    }
  }

  int weight(int v1, int v2) { // Return weight of (v1, v2)
    Edge curr;
    vertex[v1]->getValue(curr);
    if (curr.vertex != v2) // If not already there, search
      for (vertex[v1]->setStart();
           vertex[v1]->getValue(curr); vertex[v1]->next())
        if (curr.vertex >= v2) break;
    if (curr.vertex == v2)
      return curr.weight;
    else
      return 0;  // No such edge
  }

  int getMark(int v) { return mark[v]; }
  void setMark(int v, int val) { mark[v] = val; }
};

#endif
//this is grmat.h
#ifndef GRMAT_H
#define GRMAT_H


// Used by the mark array
#define UNVISITED 0
#define VISITED 1

#include "graph.h"

class Graphm : public Graph { // Implement adjacency matrix
private:
  int numVertex, numEdge; // Store number of vertices, edges
  int **matrix;           // Pointer to adjacency matrix
  int *mark;              // Pointer to mark array
public:
  Graphm(int numVert) {   // Make graph w/ numVert vertices
    int i;
    numVertex = numVert;
    numEdge = 0;
    mark = new int[numVert]; // Initialize mark array
    for (i=0; i<numVertex; i++)
      mark[i] = UNVISITED;
    matrix = (int**) new int*[numVertex]; // Make matrix
    for (i=0; i<numVertex; i++)
      matrix[i] = new int[numVertex];
    for (i=0; i< numVertex; i++) // Edges start w/ 0 weight
      for (int j=0; j<numVertex; j++) matrix[i][j] = 0;
  }

  ~Graphm() {       // Destructor
    delete [] mark; // Return dynamically allocated memory
    for (int i=0; i<numVertex; i++)
      delete [] matrix[i];
    delete [] matrix;
  }

  int n() { return numVertex; } // Number of vertices
  int e() { return numEdge; }   // Number of edges

  int first(int v) {            // Return v's first neighbor
    int i;
    for (i=0; i<numVertex; i++)
      if (matrix[v][i] != 0) return i;
    return i;       // Return n if none
  }

  int next(int v1, int v2) { // Get v1's neighbor after v2
    int i;
    for(i=v2+1; i<numVertex; i++)
      if (matrix[v1][i] != 0) return i;
    return i;
  }

  // Set edge (v1, v2) to wgt
  void setEdge(int v1, int v2, int wgt) {
//    Assert(wgt>0, "Illegal weight value");
    if (matrix[v1][v2] == 0) numEdge++;
    matrix[v1][v2] = wgt;
  }

  void delEdge(int v1, int v2) { // Delete edge (v1, v2)
    if (matrix[v1][v2] != 0) numEdge--;
    matrix[v1][v2] = 0;
  }

  int weight(int v1, int v2) { return matrix[v1][v2]; }
  int getMark(int v) { return mark[v]; }
  void setMark(int v, int val) { mark[v] = val; }
};

#endif
 
Here is the graph input file. If you run into some strange problem, try to check if you put this data into txt file and 
make sure that delete all invisible character after each line, especially the last line. "Enter" character always is the 
killer. Or you can down load from here.
0 0 1 0 1 0
0 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 0 1
1 0 0 0 0 1
0 1 1 1 1 0
 
 

 



	


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)