Assignment Overview : CookMyProjectThe Graph ADT is a data structure that is often used to represent relationships between a set of objects called verticies [or…

Assignment Overview :

CookMyProjectThe Graph ADT is a data structure that is often used to represent relationships between a set of objects called verticies [or vertexes). Graphs consist of vertexes and edges. A Vertex is a point in the Graph that stores some data. Edges are the connections between Vertices and can be directed or undirected. Graphs have applications in modeling many domains, including mapping, transportation, computer networks, and electrical engineering. There are many ways to represent graphs, in this project we will be using an adjacency list that uses a list as the underlying container. The goal of this project is to encourage you to use the concepts taught throughout the semester to solve a unique and complex problem. For this assignment you will be implementing a basic Graph ADT. Test cases will be provided for you to test your code, along with a skeleton file for you to start with where a Graph, Vertex, Path, and Edge class have already been declared for you. This project was inspired by: https://snap.stanford.eduidatakmail-Eu-core.html dataset. The data represents a network of email data at a large European research center.

Assignment Specifications:

The Edge class is fully implemented and provided for you. Do not modify this class. We have provided the init, eq, methods in the Graph class, do not modify these methods. Your task will be to complete the methods listed below in the Graph, Vertex, and Path classes. Make sure that you are adhering to the time and space complexity requirements. Do not modify function signatures in any way. The data used to construct the Graph may not necessarily result In a DAG.•••

Edge Class:

This class is provided for you, DO NOT modify it. An edge object represents an edge in the graph. It connects a source (Vertex object) with a destination [Vertex id).

Path Cast:

self.vertices represents the vertices in the path in a specific order. This class keeps track of a path through the graph. This is useful in graphs because it allows for a meaninful representation of what a path is. i.e. A route in google maps is represented by a path through a graph. • add_vertex[self, vertex):

o Add a Vertex id to the path.

o Return None o 0[1) time complexity

• remove_vertex[self):

o Remove the most recently added Vertex id from the path.

o Return None

o 0[1) time complexity • last_vertex(self):

o Return the last Vertex id added to the path

o If path is empty return None o 0[1) time complexity

• is_emptyiself): o Check if the path is empty.

o Return Boolean

o 0(1) time complexity

Vertex Glass :

• This class represents a vertex in the Graph.

o self.edges is a list of outgoing edges from the vertex

o self.ID is the id of the vertex

o self.visited is a boolean that represents if the vertex has already been visited.

o self.fake is a boolean that represents if the vertex is a ‘fake’ vertex.

o Add an edge to the Vertex given the id of the destination Vertex.

o Return None

o OD) time complexity

• degree[self):

o Return the number of outgoing edges [degree) of the Vertex

o OD) time complexity • get_edge[self,

destination):

o Returns the Edge that goes to a specified destination node.

o 0(n) time complexity

• get_edges[self):

o Returns a list of all of the edges.

o OD) time complexity

• set_fake[self):

o Set the vertex as a fake vertex.

o OD) time complexity

• visit[self):

o Set the vertex as visited.

o OD) time complexity

Graph Clam:

• An abstract class that represents a directed graph

o seltadj_list represents the adjacency list storing the graph. Structure: (vertex_id: Vertex())

o self.size is the size of the graph. Only used to construct graph, disregard if constructing graph from file. Do not modify.

o setf.connectedness represents the connectedness of the graph, value between 0 and 1. Do not modify.

o self.filename is the filename used to construct a graph, default value is None.

o self.construct_graphu is the construct graph method called when a Graph Object is instantiated.

• generate_edges(self):

o DO NOT EDIT THIS METHOD

o Generates directed edges between vertices

o Returns a generator object that returns a tuple of the form (source ID, destination ID) used to construct an edge

.get_vertex(self, id):

o Returns the vertex with the specified id.

o If the vertex is not found, return None o 0(1) time complexity

• construct_graph(self):

o Add all edges to a Graph. If a filename is provided, read from the file to construct the graph, otherwise use the generate_edges method to construct the graph. Do not accept graphs with a negative size or connectedness not in the range 10,

o If provided with bad input, raise a GraphError.

o Both forms of input retum data in the following format (source, destination)

o Uses the dictionary self.adj_list to store vertices’ IDs as keys and their objects as values.

o Do NOT insert parallel edges in your graph.

o Sample file with example input is linked below

• test construction simple.txt

o 0(E) time complexity, E is the number of edges to insert

• BFS(self, start, target):

o Breadth First Search given a start ID, find a path to the target ID.

o If the target node is not found, retum an empty Path, otherwise, return a Path of vertex id’s from the start vertex to the target vertex.

o If there are multiple paths, choose 1 path to return.

o File for simple search graph: test search simple txt Same for DFS o 0(V+E), V is the number of vertices, E is the number of edges

• DFS(self, start, target, path=Path()):

o Depth First Search with the same return specifications as BFS o Must be recursive o 0[V+E), V is the number of vertices, E is the number of edges

• The construct_graph() method should raise a GraphError when:

o Incorrect filename is provided

o If no filename and the size is less than or equal to 0 o Connectedness is not 0 < connectedness <=1

External Functions:

Using the aforementioned emails dataset, we can create a structure using the Graph ADT where the vertices represent email addresses and edges represent messages sent. We assume that if a vertex has a degree 0 then it is a likely candidate for a fake email address. This is because email messages are coming into the vertex, but no email messages are sent from it. You will be writing the the functions to identify all potential fake emails.

• fake_emails(graph, mark_false=False):

o Finds all fake vertices in the Graph, sets them to be fake, and adds their IDs to a list. A Vertex is fake if the degree of the vertex is 0 (messages coming in, no messages going out).

o If mark_false is True, set the fake flag on each fake vertex.

o You are allowed to iterate over graph.adj_list ONLY In the scope of this method.

• The picture below clarifies what this means. o Returns a list of fake vertex IDs.

o OMV+ED time complexity, V is the number of vertices, E is the number of edges

• check_fake_emails(start, emaillist(j)

o This is a nested function within fake_emallsa DO NOT move it outside of fake_emails().

o Given a start Vertex ID, find all fake email addressses that can be reached from that ID and remove the edge connecting to the fake address.

o DO NOT access graph.actlist directly, use accessors.

o Must be recursive.

o Python allows for nesting functions, this can be a powerful tool for writing clean modular code, you can read more about it here.

o O(V-FE) time complexity. V is the number of vertices, E is the number of edges