Shortest distance
A.First Edition
This is first edition of fifth assignment of comp352.
How to find out distance between two vertices in a simple graph without weight?
Here is the graph input file.
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