Untitled

 avatar
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