Shortest distance

A.Second Edition
This is second edition of fifth assignment of comp352 which is an obvious solution. 
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
#include <iostream>
#include "Grlist.h"
#include "Graph.h"
#include "Grmat.h"
#include "Queue.h"
#include "AQueue.h"

using namespace std;

//returns a directed graph as specified
Graph*  getGraph1(int size);

//returns an undirected graph as specified
Graph*  getGraph2(int size);//input 2nd graph

//test two vertices without a connecting edge
Graph* getGraph3(int size);

//Shortest path returns the shortest number of edges 
//needed to cross to get to another vertex, independent of 
//what kind of graph
int shortest(Graph* G, int start, int end);

int main()
{
	Graph* G;

	G=getGraph1(6);
	cout<<"output of graph 1:" <<endl;
	cout<<"The shortest distance between A and E is:"<<shortest(G, 0, 4)<<endl;
	cout<<"The shortest distance between A and C is:"<<shortest(G, 0, 2)<<endl;
	cout<<"The shortest distance between A and D is:"<<shortest(G, 0, 3)<<endl;

	delete G;

	G=getGraph2(6);
	cout<<"output of graph 2:" <<endl;
	cout<<"The shortest distance between A and D is:"<<shortest(G, 0, 3)<<endl;
	cout<<"The shortest distance between A and F is:"<<shortest(G, 0, 5)<<endl;
	cout<<"The shortest distance between C and F is:"<<shortest(G, 2, 5)<<endl;
	delete G;

	G=getGraph3(6);
	cout<<"output of graph 3:" <<endl;
	cout<<"The shortest distance between A and E is:"<<shortest(G, 0, 4)<<endl;
	cout<<"The shortest distance between A and C is:"<<shortest(G, 0, 2)<<endl;
	cout<<"The shortest distance between A and D is:"<<shortest(G, 0, 3)<<endl;
	
	delete G;
	return 0;
}

Graph* getGraph1(int size)
{
	Graph* G=new Graphm(size);
	G->setEdge(0,2,1);
	G->setEdge(2,1,1);
	G->setEdge(1,5,1);
	G->setEdge(5,3,1);
	G->setEdge(5,4,1);

	return G;
}


//in an undirected graph an edge is defined by the vertices 
//twice(A to C, and C to A)
Graph*  getGraph2(int size)
{
	Graph* G=new Graphm(size);
	G->setEdge(0,2,1);
	G->setEdge(2,0,1);

	G->setEdge(2,3,1);
	G->setEdge(3,2,1);

	G->setEdge(1,2,1);
	G->setEdge(2,1,1);

	G->setEdge(5,2,1);
	G->setEdge(2,5,1);

	G->setEdge(1,5,1);
	G->setEdge(5,1,1);

	G->setEdge(5,3,1);
	G->setEdge(3,5,1);

	G->setEdge(0,4,1);
	G->setEdge(4,0,1);


	G->setEdge(5,4,1);
	G->setEdge(4,5,1);

	return G;
}

Graph* getGraph3(int size)
{
	//same graph as graph 1 except the edge between B and F is removed
	Graph* G=new Graphm(size);
	G->setEdge(0,2,1);
	G->setEdge(2,1,1);
	G->setEdge(5,3,1);
	G->setEdge(5,4,1);

	return G;
}


int shortest(Graph* pG, int start, int end)
{
	int p, q;
	int level=0;

	// all vertices are unchecked
	for (int i=0; i<pG->n(); i++)
	{
		pG->setMark(i, -1);
	}
	AQueue<int> Q;
	Q.enqueue(start);
	
	pG->setMark(start, level);
	
	while (Q.length()!=0)
	{
		Q.dequeue(p);
		if (p==end)
		{
			return pG->getMark(p);//the level
		}
		level = pG->getMark(p)+1; //add 1 to get the correct level
		for (q=pG->first(p); q<pG->n(); q=pG->next(p, q))
		{
			if (pG->getMark(q)==-1)
			{
				pG->setMark(q, level);
				Q.enqueue(q);
			}
		}
	}
	return -1;
}
 
//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 what the graph looks like.
 
Here is the result:
output of graph 1:
The shortest distance between A and E is:4
The shortest distance between A and C is:1
The shortest distance between A and D is:4
output of graph 2:
The shortest distance between A and D is:2
The shortest distance between A and F is:2
The shortest distance between C and F is:1
output of graph 3:
The shortest distance between A and E is:-1
The shortest distance between A and C is:1
The shortest distance between A and D is:-1
Press any key to continue
 
 

 



	


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