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