'''
PROJECT 8 - Graphs
Name:
PID:
'''
import random
def Generate_edges(size, connectedness):
"""
DO NOT EDIT THIS FUNCTION
Generates directed edges between vertices to form a DAG
:return: A generator object that returns a tuple of the form (source ID, destination ID)
used to construct an edge
"""
assert connectedness <= 1
random.seed(10)
for i in range(size):
for j in range(i + 1, size):
if random.randrange(0, 100) <= connectedness * 100:
yield f'{i} {j}'
# Custom Graph error
class GraphError(Exception): pass
class Vertex:
"""
Class representing a Vertex in the Graph
"""
__slots__ = ['ID', 'index', 'visited']
def __init__(self, ID, index):
"""
Class representing a vertex in the graph
:param ID : Unique ID of this vertex
:param index : Index of vertex edges in adjacency matrix
"""
self.ID = ID
self.index = index # The index that this vertex is in the matrix
self.visited = False
def __repr__(self):
return f"Vertex: {self.ID}"
__str__ = __repr__
def __eq__(self, other):
"""
DO NOT EDIT THIS METHOD
:param other: Vertex to compare
:return: Bool, True if same, otherwise False
"""
return self.ID == other.ID and self.index == other.index
def out_degree(self, adj_matrix):
"""
Same as in_degree
Time: O(V) Space: O(1)
:param adj_matrix:
:return: the number of outgoing edges to its vertex
"""
pass
def in_degree(self, adj_matrix):
"""
Given an adj_matrix, type: List[List[Optional[Vertex.ID]]
adj_matrix should not be modified in this method
Time: O(V) Space: O(1)
:param adj_matrix:
:return: the number of incoming edges to its vertex
"""
pass
def visit(self):
"""
Set the visit flag to seen (true).
Time: O(1) Space: O(1)
:return:None
"""
pass
class Graph:
"""
Graph Class ADT
"""
def __init__(self, iterable=None):
"""
DO NOT EDIT THIS METHOD
Construct a random Directed Graph
:param size: Number of vertices
:param: iterable: iterable containing edges to use to construct the graph.
"""
self.id_map = {}
self.size = 0
self.matrix = []
self.iterable = iterable
self.construct_graph()
if hasattr(iterable, 'close'):
iterable.close()
def __eq__(self, other):
"""
DO NOT EDIT THIS METHOD
Determines if 2 graphs are Identical
:param other: Graph Object
:return: Bool, True if Graph objects are equal
"""
return self.id_map == other.id_map and self.matrix == other.matrix and self.size == other.size
def get_vertex(self, ID):
"""
Given an ID that is the same type as Vertex.ID,
get the corresponding Vertex object.
Time: O(1) Space: O(1)
:param ID:
:return: Vertex
If ID doesn't exist return None
"""
pass
def get_edges(self, ID):
"""
Given an ID with type: Vertex.ID,
return the set of outgoing vertex ID's from the input vertex
Time: O(V) Space: O(V)
:param ID:
:return: Set[Vertex.ID]
"""
pass
def construct_graph(self):
"""
Iterates through iterable and calls insert_edge to
create the graph representation stored in self.matrix.
Time: O(V^2) Space: O(V^2)
:return: None
"""
pass
def insert_edge(self, source, destination):
"""
Creates vertex objects, if needed, then adds edge
representation into the matrix between the given source
and destination, and updates self.id_map
source type: Vertex.ID
destination type: Vertex.ID
Time: O(V) Space: O(V)
:param source:
:param destination:
:return: None
"""
pass
def bfs(self, start, target, path=None):
"""
Does a breadth first search to generate a path from start
to target visiting a node only once.
If no such path exists return an empty list.
start type: Vertex.ID
target type: Vertex.ID
path type: Optional[List[Vertex.ID]]
Both bfs and dfs (below) are provided an optional additional
parameter 'path'. This is to support keeping state in where
you are in a recursive call stack, if you choose to implement
either recursively.
bfs and dfs (below) can return any accurate path from source to target.
Must not access self.adj_matrix
Time: O(V^2) Space: O(V)
:param start:
:param target:
:param path:
:return: List[Vertex.ID]
"""
pass
def dfs(self, start, target, path=None):
"""
Same as bfs, but doing a depth first search instead
Time: O(V^2) Space: O(V)
:param start:
:param target:
:param path:
:return:
"""
pass
def find_k_away(K, iterable, start):
"""
Given a starting ID and value K, return all vertex ID's that are K (inclusive) vertices away.
ex. ID = 100, K = 2
Graph is
100 -> 99
99 -> 98
98 -> 97
99 -> 20
result = {98, 20}
K type : int
iterable type: some iterable holding strings that represent edges
start type : Vertex.ID
K is guaranteed to be >= 0
Should not access Graph.adj_matrix, or Graph.id_map explicitly.
Time: O(V^2 Vlog(V)) Space: O(V) *
:param K:
:param iterable:
:param start:
:return: Set[VertexID]
"""
pass