Untitled
unknown
python
3 months ago
2.4 kB
7
Indexable
from WeightedGraph import WeightedGraph # Reads graph data from a file and creates an adjacency list def read_adjacency_list(file_path): """ Reads a graph from a file where each line contains: vertex: neighbor1 weight1, neighbor2 weight2, ... Returns a dictionary of vertices and their weighted connections """ adjacency_list = {} with open(file_path, 'r') as file: for line in file: line = line.strip() if not line: continue animal_part, connections_part = line.split(':', 1) animal_part = animal_part.strip() connections_part = connections_part.strip() connections = [] if connections_part: neighbors = connections_part.split(',') for neighbor_info in neighbors: neighbor_info = neighbor_info.strip() parts = neighbor_info.split() neighbor_animal = parts[0] weight = int(parts[1]) connections.append((neighbor_animal, weight)) adjacency_list[animal_part] = connections return adjacency_list # Extracts vertices and edges from the adjacency list def extract_vertices_and_edges(adjacency_list): """ Converts adjacency list to separate lists of vertices and edges Returns: (vertices list, edges list with weights) """ vertices = list(adjacency_list.keys()) edges = [] for source in adjacency_list: for dest, weight in adjacency_list[source]: edges.append((source, dest, weight)) return vertices, edges # Main program adjacency_list = read_adjacency_list('graph.txt') vertices, edges = extract_vertices_and_edges(adjacency_list) # Display information graph = WeightedGraph(vertices, edges) print("The number of vertices in the graph:", graph.getSize()) print("The vertex with index 1 is", graph.getVertex(1)) print("The edges for the graph:") graph.printWeightedEdges() # Find and print minimum spanning tree mst = graph.getMinimumSpanningTree() print("Minimum spanning tree:\n") print("Total weight of the minimum spanning tree is", mst.getTotalWeight(), "\n") print("MST edges:\n") mst.printTree() # Print shortest paths print("\nShortest paths from vertex 0:\n") shortest_path = graph.getShortestPath(0) shortest_path.printAllPaths()
Editor is loading...
Leave a Comment