Shortest distance
A.Second Edition
This is second edition of fifth assignment of comp352 which is an obvious solution.
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
#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