#USING PYTHON WOULD BE BEST# Graphs have been broadly employed in modeling vario
ID: 3812232 • Letter: #
Question
#USING PYTHON WOULD BE BEST#Graphs have been broadly employed in modeling various kinds of applications. In this project, you apply graph algorithms to solve applications specified below. 1. Write a program that displays connected components of a graph with DFS (or BFS.) Test your program with fig, a graph in its adjacency dictionary representation. fig = {'A': set(['B', 'E', 'F']), 'B': set(['A', 'C', 'F']), 'C': set(['B', 'D', 'G']), 'D': set(['C', 'G']), 'E': set(['A', 'F', 'I']), 'F': set(['A', 'B', 'E', 'I']), 'G': set(['C', 'D', 'J']), 'H': set(['K', 'L']), 'I': set(['E', 'F', 'J', 'M']), 'J': set(['G', 'I']), 'K': set(['H', 'O', 'L']), 'L': set(['K', 'H', 'P']), 'M': set(['I', 'N']), 'N': set(['M']), 'O': set(['K']), 'P': set(['L']) } 2. Write a program that locates a path for a given graph with DFS (and BFS) for the same starting and ending nodes. Test your program with the graph above and write your findings in your project report.
3. A connected digraph can be decomposed to its strongly connected components as a ‘meta graph’ in the form of a DAG. Find the DAG of the graph provided below with an available piece of software.
3. A connected digraph can be decomposed to its strongly connected components as a ‘meta graph’ in the form of a DAG. Find the DAG of the graph provided below with an available piece of software.
4. Applying Dijkstra’s algorithm, one can find the shortest path tree for a connected weighted graph. Write a program that produces the shortest path tree for a user provided weighted graph and starting node. Test your program with the graph below. 4. Applying Dijkstra’s algorithm, one can find the shortest path tree for a connected weighted graph. Write a program that produces the shortest path tree for a user provided weighted graph and starting node. Test your program with the graph below.
Write a program that produces the minimum spanning tree for a user provided weighted graph. Test your program with the graph above. Write a program that produces the minimum spanning tree for a user provided weighted graph. Test your program with the graph above.
1. Questions related to problem #1: Do DFS and BFS find the same connected components of for a given graph? 2. Questions related to problem #2: What is the necessary condition that DFS or BFS can find a path between any two vertices? If there is a path between two given vertices, do DFS and BFS always find the same path or not? 3. Questions related to problem #3: How many strongly connected components are there in the provided digraph? Illustrate their topological order with a linearized DAG. 4. Questions related to problem #4: The test weighted graph is undirected. Can you apply Dijkstra’s algorithm to find shortest paths for a weighted digraph? The test graph is positive weighted. Can you apply Dijkstra’s algorithm to find shortest paths for a weighted digraph with negative weights? 5. Question related to problem #5: Are a shortest path tree and a minimum spanning tree the same? 1. Questions related to problem #1: Do DFS and BFS find the same connected components of for a given graph? 2. Questions related to problem #2: What is the necessary condition that DFS or BFS can find a path between any two vertices? If there is a path between two given vertices, do DFS and BFS always find the same path or not? 3. Questions related to problem #3: How many strongly connected components are there in the provided digraph? Illustrate their topological order with a linearized DAG. 4. Questions related to problem #4: The test weighted graph is undirected. Can you apply Dijkstra’s algorithm to find shortest paths for a weighted digraph? The test graph is positive weighted. Can you apply Dijkstra’s algorithm to find shortest paths for a weighted digraph with negative weights? 5. Question related to problem #5: Are a shortest path tree and a minimum spanning tree the same?
Graph for question 4 4 S 2 12 9 6 11 4: backspace o O U
Explanation / Answer
ANSWERS:
2)
DEPTH FIRST SEARCH::(MAIN CODE AND YOU CAN EXTEND TO MORE VERTICES)
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
dfs(graph, 'C')
TO GET THE DFS PATH:
def dfs_paths(graph, start, goal):
stack = [(start, [start])]
while stack:
(vertex, path) = stack.pop()
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
stack.append((next, path + [next]))
BREADTH FIRST SEARCH:
def bfs(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
bfs(graph, 'A')
TO GET THE PATH:
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
list(bfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
TO GET THE SHORTEST PATH IN BFS:
def shortest_path(graph, start, goal):
try:
return next(bfs_paths(graph, start, goal))
except StopIteration:
return None
shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']
3)
DIRECTED ACYCLIC GRAPH
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None
TO FIND ALL PATHS:
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not graph.has_key(start):
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
4)
DIJKSTRAS ALGORITHM::
def Dijkstra(G,start,end=None):
D = {}
P = {}
Q = priorityDictionary()
Q[start] = 0
for v in Q:
D[v] = Q[v]
if v == end:
break
for w in G[v]:
vwLength = D[v] + G[v][w]
if w in D:
if vwLength < D[w]:
raise ERROR
elif w not in Q or vwLength < Q[w]:
Q[w] = vwLength
P[w] = v
return (D,P)
TO GET THE SHORTEST PATH::
def shortestPath(G,start,end):
D,P = Dijkstra(G,start,end)
Path = []
while 1:
Path.append(end)
if end == start:
break
end = P[end]
Path.reverse()
return Path
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.