# Graph Project

class Graph:
def __init__(self, n):
"""
Constructor
:param n: Number of vertices
"""
self.nodes = n

self.size = 0

self.graph = {}

#inner Dictionary
for node in self.nodes:
self.graph[node] = {}

def print_nodes(self):
return self.nodes

def insert_edge(self, u, v, w):
#first check if vertex is already in the Graph
# funciton creates a new edge
## non-directed graph
self.graph[u][v] = w

self.graph[v][u] = w

#increase size of graph
self.size += 1

def _print(self):

for node in self.nodes:
print(node, "->", self.graph[node])

def degree(self, v):

'''number of edges connected to a vertex'''

if v not in self.nodes:

print("Dude this Vertex is not in the Graph!!!")

raise IndexError

return len(self.graph[v])

def are_connected(self, u, v):
'''See if two vertices are connected!'''
'''Return Boolean (True or False)'''

if u not in self.nodes or v not in self.nodes:
print("The Vertex, Edge, or both are not in Graph")

raise IndexError

return v in self.graph[u]

def is_path_valid(self, path):

'''is path valid'''
'''Pass in a list of vertices in the order of the path'''

for i in range(len(path) - 1):
# if not connected, then it's not a path and we can return False

print(path[i])

if not self.are_connected(path[i], path[i+1]):
return False

return True

def edge_weight(self, u, v):

'''Returns the weight between vertices'''
# Check if vertices exists
if u not in self.nodes or v not in self.nodes:
raise IndexError
# ok they exist, so lets see if they're connected
if v in self.graph[u]:

return self.graph[u][v]

else:
return math.inf

return math.inf

def path_weight(self, path):
'''get the total weight of a path'''
'''Return weight of a Path'''
weight = 0

for i in range(len(path) - 1 ):
weight += self.edge_weight(path[i], path[i+1])

return weight

def does_path_exist(self, u, v):

# Vertex not in graph
if u not in self.nodes or v not in self.nodes:
raise IndexError

#Create a Queue
queue = []
# Keep track of which vertices we've visited

visited = []
visited.append(u)
queue.append(u)

# while Queue isnt empty
while queue:

vertex = queue.pop(0)

# Found path is found
if vertex == v:
return True

for neighbour in self.graph[vertex]:
if neighbour not in visited:

queue.append(neighbour)                      # if neighbour node hasnt been visited we will add to the Queue
visited.append(neighbour)                # and add it to the list of visited nodes

#  else:
#   print("Already Visited that node!")       # if the neighbour is already in our visited list we alread visited it!!

#if path doesnt exist
return False