8 - Carga de grafos desde archivo

Cargar un grafo desde archivo permite reutilizar casos de prueba y datasets reales. Este tema define un formato sencillo, muestra cómo leerlo y construye una lista de adyacencia en Python.

8.1 Formato recomendado del archivo

Usamos texto plano con la siguiente estructura:

n m dirigido ponderado
u1 v1 peso1
u2 v2 peso2
...
um vm pesom

dirigido y ponderado son 0 o 1. Si el grafo no es ponderado, el peso puede omitirse o ser 1.

8.2 Lectura línea por línea

Leemos la cabecera y luego iteramos sobre las líneas restantes. Esto permite detectar líneas vacías o mal formateadas.

8.3 Parseo seguro de datos

Separar y convertir campos con control de errores ayuda a detectar registros incompletos antes de insertarlos.

8.4 Construcción del grafo a partir del archivo

Se insertan las aristas en una lista de adyacencia validando rangos y duplicados.

8.5 Errores típicos de entrada/salida

  • Líneas incompletas: menos campos de los esperados.
  • Indices fuera de rango: vértices negativos o mayores a n - 1.
  • Aristas duplicadas: repetir u v en grafos simples.
  • Lectura truncada: olvidar validar que el archivo tenga las m aristas.
def crear_grafo(n, es_dirigido, es_ponderado):
  return {
    "n": n,
    "es_dirigido": es_dirigido,
    "es_ponderado": es_ponderado,
    "listas": {i: [] for i in range(n)}
  }

def insertar_arista(g, u, v, peso):
  g["listas"][u].append((v, peso))

def existe_arista(g, u, v):
  return any(dest == v for dest, _ in g["listas"][u])

def agregar(g, u, v, peso):
  insertar_arista(g, u, v, peso)
  if not g["es_dirigido"]:
    insertar_arista(g, v, u, peso)

def imprimir(g):
  for u in range(g["n"]):
    vecinos = " ".join(f"{v}(peso={p})" for v, p in g["listas"][u])
    print(f"{u}: {vecinos}")

def cargar_desde_archivo(ruta):
  with open(ruta, "r", encoding="utf-8") as f:
    cabecera = f.readline().strip().split()
    if len(cabecera) != 4:
      raise ValueError("Cabecera invalida")
    n, m, dirigido, ponderado = map(int, cabecera)
    g = crear_grafo(n, bool(dirigido), bool(ponderado))

    linea_actual = 1
    for linea in f:
      linea_actual += 1
      if not linea.strip():
        continue
      partes = linea.split()
      esperados = 3 if ponderado else 2
      if len(partes) != esperados:
        print(f"Linea {linea_actual} invalida: {linea.strip()}")
        continue
      u, v = map(int, partes[:2])
      peso = int(partes[2]) if ponderado else 1
      if u < 0 or u >= n or v < 0 or v >= n:
        print(f"Vertices fuera de rango en linea {linea_actual}")
        continue
      if u == v:
        print(f"Se omite lazo en linea {linea_actual}")
        continue
      if existe_arista(g, u, v):
        print(f"Arista duplicada en linea {linea_actual}")
        continue
      agregar(g, u, v, peso)
      if linea_actual - 1 >= m + 1:
        break
    return g

def main():
  try:
    g = cargar_desde_archivo("grafo.txt")
  except (OSError, ValueError) as error:
    print(f"No se pudo cargar el archivo: {error}")
    return
  print("Grafo cargado:")
  imprimir(g)

if __name__ == "__main__":
  main()

Prepara un archivo grafo.txt con la cabecera y las aristas. Al ejecutar, el programa valida cada línea, reporta inconsistencias y muestra el grafo resultante.

Ejemplo de grafo.txt para un grafo no dirigido y ponderado de 4 vértices con 3 aristas:

4 3 0 1
0 1 5
1 2 1
2 3 2

Salida esperada:

Grafo cargado:
0: 1(peso=5)
1: 0(peso=5) 2(peso=1)
2: 1(peso=1) 3(peso=2) 
3: 2(peso=2)
Ejemplo de salida de grafo cargado desde archivo
Retornar