Question

in python programming language, please include the proper identation

This homework will allow you to demonstrate understanding and engagement with the following topics:

graph representations

object oriented programming

graph processing,such as finding shortest paths and finding tree traversals

Your task is to implement a Graph class. The edges in the graph are undirected, but you must implement an Edge class. In addition, you will have a Graph class, and a Node class. You can choose to implement graphs with any of the four implementation methods.

init

insertNode(d) : takes data contained as its argument, and adds it into the graph, after putting the data element into a node

deleteNode(d): finds a node with data d in its node, and deletes it. Also deletes all edges from and into it. Prints an error message if no such node exists.

insertEdge(a, b, w, name): Inserts a new edge between node with data a and node with data b. The edge has name name, and weight w. Prints an error message if either of those nodes does not exist.

deleteEdge(a,b): Deletes the edge between a node with data a and a node with data b. Prints an error message if no such edge exists.

FindPath(a,b): Prints the shortest path from node with data a to node with data b, found by using Dijkstra's algorithm. The printing of the path includes printing the nodes which are part of the path, as well as printing the name and weight of each of the edges. Nodes and edges are printed in the order in which they are part of the path. Finally, prints the total weight of the path. Prints an error message if the path does not exist.

FindSpanningTree(n): uses Kruskal's algorithm to find a spanning tree rooted on node n. The printing of the tree includes printing the nodes which are part of the tree, as well as printing the name and weight of each of the edges. Prints an error message if the spanning tree does not exist (that is, if the algorithm runs out of edges, and there are still two or more groups of nodes that have not been merged.

Answer 1

class Graph:
# Dictionary containing keys that map to the corresponding vertex object
def __init__(own):   
own.vertices = {}

# Adds a vertex with the given key to the graph.
def addVertex(own, keyValue):   
vertex = Vertex(keyValue)
own.vertices[keyValue] = vertex

# Returns vertex object with the corresponding key value.
def getVertex(own, keyValue):   
return own.vertices[keyValue]

def __contains__(own, keyValue):
return keyValue in own.vertices

# Adds an edge from sourceKey to destinationKey with given weight in the graph.
def addEdge(own, sourceKey, destinationKey, weight = 1):   
own.vertices[sourceKey].addNeighbour(own.vertices[destinationKey], weight)

# Returns True if there is an edge from sourceKey to destinationKey in the graph
def edgeExist(own, sourceKey, destinationKey):   
return own.vertices[sourceKey].isPointToDestination(own.vertices[destinationKey])

def __iter__(own):
return iter(own.vertices.values())


class Vertex:
def __init__(own, keyValue):
own.key = keyValue
own.pointingTo = {}

# Returns key corresponding to this vertex object.
def getKey(own):   
return own.key

# Make this vertex point to destination with given edge weight.
def addNeighbour(own, destination, weight):   
own.pointingTo[destination] = weight

# Returns all vertices pointed to by this vertex.
def getNeighbours(own):   
return own.pointingTo.keys()

# Gets the weight of edge from this vertex to destination
def getWeight(own, destination):   
return own.pointingTo[destination]

# Returns True if this vertex points to destination
def isPointToDestination(own, destination):   
return destination in own.pointingTo


def dijkstraAlgorithm(graph, sourceNode):
"""Return distance where distance[v] is min distance from source to v.
This will return a dictionary distance.
graph is a Graph object.
source is a Vertex object in g."""
unvisitedNode = set(graph)
currentDistance = dict.fromkeys(graph, float('inf'))
currentDistance[sourceNode] = 0

while unvisitedNode != set():
# Search for vertex with minimum distance
closest = min(unvisitedNode, key = lambda v: currentDistance[v])

# Marks the node as visited node
unvisitedNode.remove(closest)

# Update the distances
for neighbour in closest.getNeighbours():
if neighbour in unvisitedNode:
newDistance = currentDistance[closest] + closest.getWeight(neighbour)
if currentDistance[neighbour] > newDistance:
currentDistance[neighbour] = newDistance

return currentDistance


grh = Graph()
print('Undirected Graph')
print('Menu')
print('Add vertex <key>')
print('Add edge <src> <dest> <weight>')
print('Shortest <source vertex key>')
print('Show')
print('EXIT')

while True:
do = input('Enter your choice: ').split()

choice = do[0]
if choice == 'Add':
subChoice = do[1]
if subChoice == 'vertex':
keyValue = int(do[2])
if keyValue not in grh:
grh.addVertex(keyValue)
else:
print('Vertex already exists in the graph.')
elif subChoice == 'edge':
src = int(do[2])
dest = int(do[3])
weight = int(do[4])
if src not in grh:
print('Vertex {} does not exist in the graph.'.format(src))
elif dest not in grh:
print('Vertex {} does not exist in the graph.'.format(dest))
else:
if not grh.edgeExist(src, dest):
grh.addEdge(src, dest, weight)
grh.addEdge(dest, src, weight)
else:
print('Edge already exists in the graph.')

elif choice == 'Shortest':
keyValue = int(do[1])
source = grh.getVertex(keyValue)
distance = dijkstraAlgorithm(grh, source)
print('Distances from {}: '.format(keyValue))
for v in distance:
print('Distance to {}: {}'.format(v.getKey(), distance[v]))
print()

elif choice == 'Show':
print('Vertices -> ', end='')
for v in grh:
print(v.getKey(), end=' ')
print()

print('Edges -> ')
for v in grh:
for dest in v.getNeighbours():
w = v.getWeight(dest)
print('(Source = {}, Destination = {}, Weight = {}) '.format(v.getKey(),
dest.getKey(), w))
print()

elif choice == 'EXIT':
break

Sample Output:

Undirected Graph
Menu
Add vertex <key>
Add edge <src> <dest> <weight>
Shortest <source vertex key>
Show
EXIT
Enter your choice: Add vertex 1
Enter your choice: Add vertex 2
Enter your choice: Add vertex 3
Enter your choice: Add edge 1 3 60
Enter your choice: Add edge 1 1 11
Enter your choice: Add edge 2 3 22
Enter your choice: Add edge 2 3 22
Edge already exists in the graph.
Enter your choice: Add edge 2 1 13
Enter your choice: Shortest 1
Distances from 1:
Distance to 1: 0
Distance to 2: 13
Distance to 3: 35

Enter your choice: EXIT