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 con fgets y sscanf, y construye una lista de adyacencia en C.

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

Empleamos fgets para leer cada línea completa y luego parsearla. Esto permite detectar líneas vacías o mal formateadas.

8.3 Manejo de fgets y sscanf

fgets toma la línea en un buffer; sscanf extrae enteros de esa línea con verificación de cantidad de campos.

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: olvidarse de verificar EOF en el bucle.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Arista {
  int destino;
  int peso;
  struct Arista *sig;
} Arista;

typedef struct {
  int n;
  int esDirigido;
  int esPonderado;
  Arista **listas;
} Grafo;

Grafo *crearGrafo(int n, int esDirigido, int esPonderado) {
  Grafo *g = malloc(sizeof(Grafo));
  if (!g) return NULL;
  g->n = n;
  g->esDirigido = esDirigido;
  g->esPonderado = esPonderado;
  g->listas = calloc(n, sizeof(Arista *));
  return g;
}

static void insertarArista(Grafo *g, int u, int v, int peso) {
  Arista *nuevo = malloc(sizeof(Arista));
  if (!nuevo) return;
  nuevo->destino = v;
  nuevo->peso = peso;
  nuevo->sig = g->listas[u];
  g->listas[u] = nuevo;
}

int existeArista(const Grafo *g, int u, int v) {
  for (Arista *it = g->listas[u]; it; it = it->sig) {
    if (it->destino == v) return 1;
  }
  return 0;
}

void agregar(Grafo *g, int u, int v, int peso) {
  insertarArista(g, u, v, peso);
  if (!g->esDirigido) insertarArista(g, v, u, peso);
}

void imprimir(const Grafo *g) {
  for (int u = 0; u < g->n; u++) {
    printf("%d:", u);
    for (Arista *it = g->listas[u]; it; it = it->sig) {
      printf(" %d(peso=%d)", it->destino, it->peso);
    }
    printf("\n");
  }
}

void liberar(Grafo *g) {
  if (!g) return;
  for (int u = 0; u < g->n; u++) {
    Arista *it = g->listas[u];
    while (it) {
      Arista *tmp = it;
      it = it->sig;
      free(tmp);
    }
  }
  free(g->listas);
  free(g);
}

int main(void) {
  FILE *f = fopen("../grafo.txt", "r");
  if (!f) {
    perror("No se pudo abrir el archivo");
    return 1;
  }

  char linea[128];
  if (!fgets(linea, sizeof(linea), f)) {
    printf("Archivo vacio\n");
    fclose(f);
    return 1;
  }

  int n, m, dirigido, ponderado;
  if (sscanf(linea, "%d %d %d %d", &n, &m, &dirigido, &ponderado) != 4) {
    printf("Cabecera invalida\n");
    fclose(f);
    return 1;
  }
  Grafo *g = crearGrafo(n, dirigido, ponderado);
  if (!g) {
    printf("No se pudo crear el grafo\n");
    fclose(f);
    return 1;
  }

  int lineaActual = 1;
  while (fgets(linea, sizeof(linea), f) && lineaActual <= m) {
    lineaActual++;
    int u, v, peso = 1;
    int leidos = ponderado ?
      sscanf(linea, "%d %d %d", &u, &v, &peso) :
      sscanf(linea, "%d %d", &u, &v);
    int esperados = ponderado ? 3 : 2;
    if (leidos != esperados) {
      printf("Linea %d invalida: %s", lineaActual, linea);
      continue;
    }
    if (u < 0 || u >= g->n || v < 0 || v >= g->n) {
      printf("Vertices fuera de rango en linea %d\n", lineaActual);
      continue;
    }
    if (u == v) {
      printf("Se omite lazo en linea %d\n", lineaActual);
      continue;
    }
    if (existeArista(g, u, v)) {
      printf("Arista duplicada en linea %d\n", lineaActual);
      continue;
    }
    agregar(g, u, v, peso);
  }

  fclose(f);
  printf("Grafo cargado:\n");
  imprimir(g);
  liberar(g);
  return 0;
}

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: 2(peso=1) 0(peso=5)
2: 3(peso=2) 1(peso=1)
3: 2(peso=2)
Ejemplo de salida de grafo cargado desde archivo
Retornar