[SOLVED] (csci 323) assignment 7 “graphs and graph algorithms”

In this assignment, we implement some general infrastructure for reading, generating, representing, tabulating, and
drawing graphs. We will use this in subsequent assignments that compare different algorithms for a shared problem.Submissions:
In the Google form, please submit the following:
● Assignment7.py (source code)
● Assignment7.txt (console output)
● Assignment7-times.png (bar graph of timings)
● Assignment7-graph.png (graph of points and path)Follow the template and general guidelines for previous assignments. Wherever possible, import those assignments and
invoke their functions rather than creating and maintaining copies of the same code.[1] Define a function read_graph(file_name) that reads a graph from a text file and returns an adjacency/cost matrix.
[2] Define a function adjacency_table(matrix) that accepts a graph as an adjacency/cost matrix and returns an
adjacency/cost table.[3] Define a function edge_set(matrix) that accepts a graph as an adjacency/cost matrix and returns an edge/cost set.
[4] Define a function edge_map(matrix) that accepts a graph as an adjacency/cost matrix and returns an edge/cost set.[5] Define a function zero_to_inf(matrix) that replaces non-edges represented by a cost of zero (0) with a cost of INF,
tentatively set at 9999.[6] Define a function random_graph(size, max_cost, p=1) that generates a graph with size edges, where each edge
(except loops/self-edges) is assigned a random integer cost between 1 and max_cost. The additional parameter p
represents the probability that there should be an edge between a given pair of vertices.[7] Define functions that traverse the graph in these two standard orderings
● Breadth-First Search (BFS)
● Depth-First Search (DFS)
[8] Define a function print_graph(matrix) that prints a graph in matrix form.[9] Define a function print_graph_tabular(matrix) that prints a graph in tabular form.
[10] Define a function draw_graph(graph) that draws a graph
See https://stackoverflow.com/questions/20133479/how-to-draw-directed-graphs-using-networkx-in-python[11] Define functions for various graph-related tasks using the different models and compare them by tabulating and
plotting their runtimes..# Define a function draw_graph(graph) that draws a graph and saves it as a file.
#
https://stackoverflow.com/questions/20133479/how-to-draw-directed-graphs-using-networ
kx-in-python# https://stackoverflow.com/questions/74312314/draw-a-directed-graph-in-python
def draw_graph(edges, directed, filename):
G = nx.DiGraph()
G.add_edges_from(edges)
val_map = {‘A’: 1.0, ‘D’: 0.5714285714285714, ‘H’: 0.0}
values = [val_map.get(node, 0.25) for node in G.nodes()]
pos = nx.spring_layout(G)
cmap = plt.get_cmap(‘jet’)nx.draw_networkx_nodes(G, pos, cmap=cmap, node_color=values, node_size=500)
nx.draw_networkx_labels(G, pos, font_size=12, font_color=’white’)
if directed:
nx.draw_networkx_edges(G, pos, edgelist=edges, edge_color=’r’,
arrows=directed, arrowsize=10)
else:
nx.draw_networkx_edges(G, pos, edgelist=edges, edge_color=’r’, arrows=False)
plt.savefig(filename)
plt.show()