For your first project you will be tasked with programming a DFA using a graph p

Question

For your first project you will be tasked with programming a DFA using a graph
package which you are tasked with making yourself. Actually making a DFA is
not very hard, however the point of this project is to review the requirement of
COMP 333 by building something you should have been able to build by the
end of COMP 282. You are free use the language of your choice so long as it is
object oriented. This means you can use C++, C#, or Java.(JAVA Please)
Recall from your previous section of COMP 282 that graphs are mathemat-
ical representations of entities that have connections between one another. In
computer science and in mathematics, a graph G is an ordered set consisting
two sets. A nite set V that consisting of Vertices and a nite set E consisting
of an ordered pair of vertices called Edges. Vertices are nodes or points (ex-
ample: point a and b) while Edges are the connection from one point to the
other. To emphasize that a graph G is made of two sets, we tend to represent
it as G = (V;E) or G(V;E) . The reason for that is due to the fact that we can
have different graphs with either different or subsets of V and E, for example
we could have a graph G(V;E) and a graph G(N;C).
Your DFA should read it's rules from a text le and then build a DFA that will
model the said rules. To build your DFA, you will need to be able to read them
from a le somewhere. You can build a GUI prompt to nd a text le with the
required rules for your DFA or you can simply include it in your folder. Bellow
is a lab from COMP 182 that I have included with slight modications every
semester for the class. You are more than free to use the method included there
for your project. You are also free to use two les instead of a single one for the
rules. Example : 1 les for the connections, another for for whether the state is
nal or not.
Your DFA has two main methods: Making a DFA which is handled by the
constructor, and validating a sequence. It is at this point where you should
probably identify what the type of inputs you will be accepting for your DFA.
Since we will be validating strings, you should make your weights be of type
characters, that way they can be both numbers and letters.
Do not include any print statement in your classes. The console is a
shared component, you shouldn't access it randomly. Inclusion of print
statements will result in a 10% deduction.
DO NOT MAKE YOUR GRAPHS OR YOUR GRAPH COM-
PONENTS PUBLIC. THEY SHOULD NOT BE VISILBLE OUT-
SIDE THE PACKAGE. I WILL NOT GRADE YOUR PROJECT
IF YOU FAIL TO ACCOUNT FOR THAT!
Do not make any of your elds static. I will not even grade your submis-
sions and you will receive a failing grade.
You must submit a project with multiple classes. You need a separate
and independent main class for executing your code. Submitting one class
with a main method will result in a 10% deduction.
Organize and re-factor your code, Sloppy code will result in a 10% deduc-
tion. This is not the rst week of COMP 110, you will need to structure
your code so that it is reasonable. Do not include all of the user interface
in one main method, rather call on other methods which perform a specic
task.
Control your user input so that the methods are invoked with valid inputs.
Failure to control for input will result in a 10% deduction. Exceptions are
acceptable but they are not the best.
9

Explanation / Answer

// C++ program to check if there is exist a path between two vertices

// of a graph.

#include<iostream>

#include <list>

using namespace std;

// This class represents a directed graph using adjacency list

// representation

class Graph

{

int V; // No. of vertices

list<int> *adj; // Pointer to an array containing adjacency lists

public:

Graph(int V); // Constructor

void addEdge(int v, int w); // function to add an edge to graph

bool isReachable(int s, int d);

};

Graph::Graph(int V)

{

this->V = V;

adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

adj[v].push_back(w); // Add w to v’s list.

}

// A BFS based function to check whether d is reachable from s.

bool Graph::isReachable(int s, int d)

{

// Base case

if (s == d)

return true;

// Mark all the vertices as not visited

bool *visited = new bool[V];

for (int i = 0; i < V; i++)

visited[i] = false;

// Create a queue for BFS

list<int> queue;

// Mark the current node as visited and enqueue it

visited[s] = true;

queue.push_back(s);

// it will be used to get all adjacent vertices of a vertex

list<int>::iterator i;

while (!queue.empty())

{

// Dequeue a vertex from queue and print it

s = queue.front();

queue.pop_front();

// Get all adjacent vertices of the dequeued vertex s

// If a adjacent has not been visited, then mark it visited

// and enqueue it

for (i = adj[s].begin(); i != adj[s].end(); ++i)

{

// If this adjacent node is the destination node, then

// return true

if (*i == d)

return true;

// Else, continue to do BFS

if (!visited[*i])

{

visited[*i] = true;

queue.push_back(*i);

}

}

}

// If BFS is complete without visiting d

return false;

}

// Driver program to test methods of graph class

int main()

{

// Create a graph given in the above diagram

Graph g(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

int u = 1, v = 3;

if(g.isReachable(u, v))

cout<< " There is a path from " << u << " to " << v;

else

cout<< " There is no path from " << u << " to " << v;

u = 3, v = 1;

if(g.isReachable(u, v))

cout<< " There is a path from " << u << " to " << v;

else

cout<< " There is no path from " << u << " to " << v;

return 0;

}

Output:Copy

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.