[1] Write a function that reads all the files in a directory. For some ideas,

[2] For each file, build the corresponding Cost Matrix which will become your graph. Follow this strategy: read a line of the file, split it at the spaces, convert the numbers from string to integer, and now you have a row of the Cost Matrix.

[3] Write a function to reprint the graph (in cost matrix form) ands state how many vertices (the number of rows/columns), and how many edges (the number of non-zero weights divided by 2).

[4] Write a function for Depth-First Search. Keep in mind that this is a weighted graph with a cost matrix, not an adjacency matrix. So when determining neighbors, i.e. which edges exist, look for costs greater than 0.

-----------------------------------------------------------

please help me fix this

def read_graph(file_name): with open(file_name, 'r') as file: graph = [] lines = file.readlines() for line in lines: costs = line.strip().split(' ') row = [] for cost in costs: row.append(int(cost)) graph.append(row) return graph def desc_graph(graph): num_vertices = len(graph) message = '' message += 'Number of vertices = ' + str(num_vertices) + ' ' non_zero = 0 for i in range(num_vertices): for j in range(num_vertices): if graph[i][j] > 0: non_zero += 1 num_edges = int(non_zero / 2) message += 'Number of edges = ' + str(num_edges) + ' ' message += 'Symmetric = ' + str(is_symmetric(graph)) + ' ' return message def is_symmetric(graph): num_vertices = len(graph) for i in range(num_vertices): for j in range(num_vertices): if graph[i][j] != graph[j][i]: return False return True def print_graph(graph, sep=' '): str_graph = '' for row in range(len(graph)): str_graph += sep.join([str(c) for c in graph[row]]) + ' ' return str_graph def dfs_util(graph, v, visited): visited.append(v) for col in range(len(graph[v])): if graph[v][col] > 0 and col not in visited: dfs_util(graph, col, visited) def dfs(graph): visited = [] dfs_util(graph, 0, visited) return visited # https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/ def bfs(graph): visited = [] bfs_util(graph, 0) return visited def bfs_util(graph, s): v = len(graph) visited = [False] * v queue = [] queue.append(s) visited[s] = True while queue: s = queue.pop(0) print(s, end=" ") for col in range(v): if graph[v][col] > 0 and not visited[col]: queue.append(col) visited[col] = True # https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/ def printMST(graph, parent): v = len(graph) print("Edge \tWeight") for i in range(1, v): print(parent[i], "-", i, "\t", graph[i][parent[i]]) def minKey(graph, key, mstSet): v = len(graph) min = 9000000000 for v in range(v): if key[v] < min and mstSet[v] == False: min = key[v] min_index = v return min_index def primMST(graph): print('prim alge:') v = len(graph) key = [999999] * graph.v parent = [None] * v key[0] = 0 mstSet = [False] * v parent[0] = -1 for cout in range(v): u = minKey(graph, key, mstSet) mstSet[u] = True for v in range(v): if graph[u][v] > 0 and mstSet[v] == False and key[v] > graph[u][v]: key[v] = graph[u][v] parent[v] = u return parent def analyze_graph(file_name): graph = read_graph(file_name) output_file_name = file_name[0:-4 + len(file_name)] + '_report.txt' with open(output_file_name, 'w') as output_file: output_file.write('Analysis of graph: ' + file_name + ' ') str_graph = print_graph(graph) output_file.write(str_graph + ' ') graph_descrip = desc_graph(graph) output_file.write(graph_descrip + ' ') dfs_traversal = dfs(graph) bfs_traversal = bfs(graph) prim_traversal = primMST(graph) output_file.write('dfs traversal: ' + str(dfs_traversal) + ' ') output_file.write('bfs traversal: ' + str(bfs_traversal) + ' ') output_file.write('prim_traversal: ' + str(prim_traversal) + ' ') def main(): mypath = "C:\\Users\\heten\\PycharmProjects\\assignment4" files = [f for f in listdir(mypath) if isfile(join(mypath, f))] for file in files: if file[0:5] == 'graph' and file.find('_report') < 0: analyze_graph(file) if __name__ == '__main__': main() 

[5] Write a function for Breadth-First Search. The same caveat for DFS in [4] applies to BFS.

[6] Write a function for Prim's MST algorithm. Any implementation is acceptable. The output should include both the set of edges in and the total cost of the MST.