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