Insert edge into graph

Question

I’m trying to insert an edge into a graph. The problem is to represent a metro line, considering the existing information in csv files. I created the classes Vertex, Edge, Station(Vertex), Edge_Line(Edge) and the GraphList.

Com este método, consigo inserir os vértices do grafo:
def create_stations(filename='lisbon.stations.csv'):
    stations = []
    with open(filename, 'r', newline='') as stations_info:
        station_info = csv.reader(stations_info, delimiter=',')
        # skip first line, which is just attribute names
        next(station_info)
        # empty list to hold stations

        # parse all the lines and create stations
        for row in station_info:
            #print(row[3],row[2])
            id = row[0]
            latitude = row[1]
            longitude = row[2]
            nome = row[3]
            # assign each attribute of Station based on line in file
            #(id, latitude, longitude, nome) = tuple(row)
            #create Station instance with those attributes
            newstation = Station(id, latitude, longitude, nome)
            #print(newstation)
            stations.append(newstation)
    return stations

map = GraphList()

def station_network():
    for station in create_stations():
        map.insert_vertex(station)
    return map

I created this method to try to get links:

def create_connections(filename = 'lisbon.connections.csv'):
    connections = []
    with open(filename, 'r', newline='') as conections_info:
        conection_info = csv.reader(conections_info, delimiter=',')
        next(conection_info)

        for row in conection_info:
            (origem, destino, linha) = tuple(row)
            connections.append(Edge_Line(origem, destino, linha))
    return connections

However, when I try to create the edges, I get the error:

Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "C:/Users/sandr/PycharmProjects/teste6/main.py", line 282, in station_network
    map.insert_egde(connection._origem, connection.destination)
  File "C:/Users/sandr/PycharmProjects/teste6/main.py", line 217, in insert_egde
    self._outgoing[u].append(edge)
KeyError: '1'

How can I solve this problem?

Answer 1

Based on the description of the CSV you have passed and considering that I do not know what will be done after edges and vertices are defined, I opted for an approach with a smaller number of classes:

from dataclasses import dataclass, field
from enum import Enum

class Line(Enum):
    AMARELA = 1
    AZUL = 2
    VERDE = 3
    VERMELHA = 4

@dataclass
class Edge:
    station: str
    lattitude: float
    longitude: float

    def __str__(self):
        return f"{self.station}"

@dataclass
class Vertex:
    source: Edge
    destination: Edge
    line: Line

    def __str__(self):
        return f"{self.source} -> {self.destination} (Linha {self.line.name})"

The first class, Line, is a enumeration and serves to make it easier to identify lines and also reset them to the values that are in the CSV. Classes Edge and Vertex use Data Classes to make the example short (makes sure to create the __init__() for me).

So I created a class to join edges and vertices:

class Graph:
    edges = {}
    vertices = []

    def __init__(self, stations, connections):

        for station in stations:
            station_id, name, lattitude, longitude = station
            self.edges[station_id] = Edge(name, lattitude, longitude)

        for connection in connections:
            source, destination, line = connection
            self.vertices.append(
                Vertex(self.edges[source], self.edges[destination], line)
            )

It receives the list of stations (following the CSV model with "id", "name", "latitude" and "longitude") and creates a dictionary where the key is the id station and the value an instance of the class Edge.

In a second moment the vertices are added (also following the model of the CSV with "origin", "destination" and "line"). As the key of the dictionary is the id from the station I create Vertex passing the instances of origin, destination (as Python works by reference there is no replication) and the line itself.

And of course, the important part! (I narrowed down the list of stations so it wouldn’t get too long)

stations = (
    (30, "Marquês de Pombal", 0.0, 0.0),
    (38, "Parque", 0.0, 0.0),
    (39, "Picoas", 0.0, 0.0),
    (41, "Praça de Espanha", 0.0, 0.0),
    (43, "Rato", 0.0, 0.0),
    (48, "S. Sebastião", 0.0, 0.0),
    (50, "Saldanha", 0.0, 0.0),
)

connections = (
    (41, 48, Line.AZUL),
    (48, 50, Line.VERMELHA),
    (48, 38, Line.AZUL),
    (38, 30, Line.AZUL),
    (30, 43, Line.AMARELA),
    (39, 30, Line.AMARELA),
)

my_graph = Graph(stations, connections)

for vertex in my_graph.vertices:
    print(vertex)

And the result:

Praça de Espanha -> S. Sebastião (Linha AZUL)
S. Sebastião -> Saldanha (Linha VERMELHA)
S. Sebastião -> Parque (Linha AZUL)
Parque -> Marquês de Pombal (Linha AZUL)
Marquês de Pombal -> Rato (Linha AMARELA)
Picoas -> Marquês de Pombal (Linha AMARELA)

The methods __str__() in the classes Edge and Vertex care to format their output to the print().

Oh yes, you can replace "stations" and "Connections" with your CSV.