Write a C++ class derived from GraphicInterface, as given in Listing 20-1. Pleas
ID: 3582874 • Letter: W
Question
Write a C++ class derived from GraphicInterface, as given in Listing 20-1. Please create a program that allows the graph to be either weighted or unweighted and directed or undirected. Please use an adjacency matrix. Listing 20-1 is below. Thank you!
/** Listing 20-1 **/
// Created by Frank M. Carrano and Timothy M. Henry.
// Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
// Listing 20-1.
/** An interface for the ADT undirected, connected graph.
@file GraphInterface.h */
#ifndef GRAPH_INTERFACE_
#define GRAPH_INTERFACE_
template<class LabelType>
class GraphInterface
{
public:
/** Gets the number of vertices in this graph.
@return The number of vertices in the graph. */
virtual int getNumVertices() const = 0;
/** Gets the number of edges in this graph.
@return The number of edges in the graph. */
virtual int getNumEdges() const = 0;
/** Creates an undirected edge in this graph between two vertices
that have the given labels. If such vertices do not exist, creates
them and adds them to the graph before creating the edge.
@param start A label for the first vertex.
@param end A label for the second vertex.
@param edgeWeight The integer weight of the edge.
@return True if the edge is created, or false otherwise. */
virtual bool add(LabelType start, LabelType end, int edgeWeight) = 0;
/** Removes an edge from this graph. If a vertex is left with no other edges,
it is removed from the graph since this is a connected graph.
@param start A label for the vertex at the beginning of the edge.
@param end A label for the vertex at the end of the edge.
@return True if the edge is removed, or false otherwise. */
virtual bool remove(LabelType start, LabelType end) = 0;
/** Gets the weight of an edge in this graph.
@param start A label for the vertex at the beginning of the edge.
@param end A label for the vertex at the end of the edge.
@return The weight of the specified edge.
If no such edge exists, returns a negative integer. */
virtual int getEdgeWeight(LabelType start, LabelType end) const = 0;
/** Performs a depth-first search of this graph beginning at the given
vertex and calls a given function once for each vertex visited.
@param start A label for the beginning vertex.
@param visit A client-defined function that performs an operation on
or with each visited vertex. */
virtual void depthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;
/** Performs a breadth-first search of this graph beginning at the given
vertex and calls a given function once for each vertex visited.
@param start A label for the beginning vertex.
@param visit A client-defined function that performs an operation on
or with each visited vertex. */
virtual void breadthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;
/** Destroys this graph and frees its assigned memory. */
virtual ~GraphInterface() { }
}; // end GraphInterface
#endif
Explanation / Answer
The graph is a weighted graph that holds some number of city names with edges linking them together. Each edge will have a weight (hopefully) equivalent to the driving distance between the two places.As for functionality, the user should be able to set a starting point and a destination, and then the function should send back the shortest route between the two.
We can start by creating a graph class.
The graph can be represented using either adjacency list representation or matrix representation. The later uses more memory but allows for looking up edges connected to each vertex in O(1) time.
A vertex is dependent on the representation of the graph.
Here is an interface for a graph:
#include <iostream>
using namespace std;
typedef int vertex;
enum vertexstate{white,gray,black};
class graph
{
private: bool**adjacencymatrix;
int vertexcount;
public: graph(int vertexcount);
~graph();
void addedge(int i,int j);
void removeedge(int i,int j);
bool isedge(int i,int j);
void display();
void Dfs();
void runDfs(int u,vertexstate state[]);
};
graph::graph(char filename[],int vertexcount)
{
this->vertexcount=vertexcount;
adjacencymatrix=new bool*[vertexcount];
for(int i=0;i<vertexcount;i++)
{
adjacencymatrix[i]=new bool[vertexcount];
for(int j=0;j<vertexcount;j++)
adjacencymatrix[i][j]=false;
}
}
graph::~graph()
{
for(int i=0;i<vertexcount;i++)
delete[]adjacencymatrix[i];
delete[]adjacencymatrix;
}
void graph::addedge(int i,int j)
{
if(i>=0 && i<vertexcount && j>=0 && j<vertexcount)
{
adjacencymatrix[i][j]=true;
adjacencymatrix[i][j]=true;
}
}
void graph::removeedge(int i,int j)
{
if(i>=0 && i<vertexcount &&j>0 && j<vertexcount)
{
adjacencymatrix[i][j]=false;
adjacencymatrix[i][j]=false;
}
}
bool graph::isedge(int i,int j)
{
if(i>=0 && i<vertexcount && j>0 && j<vertexcount)
return adjacencymatrix[i][j];
else
return false;
}
void graph::display()
{
for(int u=0;u<vertexcount;u++)
{
cout<<" adj[" <<(char)(u+65)<<"]->";
for(int v=0;v<vertexcount;++v)
{
cout<<" "<<adjacencymatrix[u][v];
}
}
cout<<" ";
}
void graph::Dfs()
{
vertexstate*state=new vertexstate[vertexcount];
for(int i=0;i<vertexcount;i++)
state[i]=white;
runDfs(0,state);
delete[]state;
}
void graph::runDfs(int u,vertexstate state[])
{
state[u]=gray;
cout<<(char) (u+65)<<endl;
for(int v=0;v<vertexcount;v++)
if(isedge(u,v) && state[v]==white)
runDfs(v,state);
state[u]=black;
cout<<(char) (u+65)<<endl;
}
/*void graph::bfs(int v,vertexstate state[])
{
vertexstate*state=new vertexstate[vertexcount];
queue<int>Q;
Q.push(v);
while(Q!=null)
{
v=deque(Q)
}
}*/int main()
{
graph A(5);
A.Dfs();
A.addedge(0,3);
A.addedge(3,0);
A.addedge(3,1);
A.addedge(1,3);
A.addedge(1,4);
A.addedge(4,1);
A.addedge(2,4);
A.addedge(4,2);
A.addedge(3,4);
A.addedge(4,3);
A.display();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.