Population

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

    ¡¡

    ¡¡

    ¡¡