Grafos en C - Ordenamiento topológico

El ordenamiento topológico permite listar los vértices de un digrafo respetando la dirección de cada arista. Si existe una arista u → v, entonces u debe aparecer antes que v en el orden. Se usa para planificar tareas, resolver dependencias de software, compilar módulos, orquestar pipelines y más.

17.1 DAG (Directed Acyclic Graph)

El orden topológico solo existe si el grafo es un DAG:

Directed: las aristas tienen dirección.
Acyclic (no hay ciclos dirigidos).
Graph: estructura de nodos y aristas.

Si hay un ciclo, por ejemplo A → B → C → A, no se puede linealizar porque cada vértice depende de otro que vuelve. Cualquier orden topológico es una manera de aplanar el DAG respetando sus dependencias.

17.2 Algoritmo de Kahn (por grados de entrada)

Parte de los vértices con grado de entrada 0 (sin dependencias) y los procesa en una cola.

Reunir todos los vértices con in-degree = 0 y encolarlos.
Mientras la cola no esté vacía:
- Extraer un vértice v y agregarlo al orden topológico.
- Eliminar sus aristas salientes, decrementando el in-degree de cada vecino.
- Si algún vecino queda con in-degree = 0, encolarlo.

Si se procesan todos los vértices, el grafo es un DAG; si quedan sin procesar, existe un ciclo.

Ejemplo (A → C, B → C, C → D):

In-degree: A=0, B=0, C=2, D=1.
Orden posible: A, B, C, D.

17.3 Algoritmo DFS

Otra forma es usar DFS y apilar nodos al terminar sus vecinos.

Ejecutar DFS.
Al finalizar la exploración de un nodo v, insertarlo al frente de una lista (o pushear en un stack).
Invertir la lista o leer el stack de arriba hacia abajo para obtener el orden topológico.

La intuición: un nodo entra en la lista solo cuando todas sus dependencias ya se resolvieron.

El DFS también permite detectar ciclos con un arreglo de colores: blanco (no visitado), gris (en proceso), negro (finalizado). Una arista hacia un nodo gris indica ciclo.

17.4 Detección de ciclos

Kahn: si al terminar quedan nodos con in-degree > 0, hay un ciclo.
DFS: una arista hacia un nodo gris (back-edge) revela un ciclo dirigido.
Ejemplo de ciclo: Tarea_A → Tarea_B → Tarea_C → Tarea_A; no existe orden válido.

17.5 Usos en dependencias (aplicaciones reales)

Compilación de programas: respetar headers y módulos dependientes (ej. A.h, B.h, C.h).
Sistemas de paquetes: apt, npm, pip o conda calculan el orden de instalación según dependencias.
Construcción de proyectos: Make/CMake/Gradle usan grafos de reglas; compilan y evitan recompilar lo ya actualizado.
Cursos y prerrequisitos: determinar el orden posible (Prog I → Prog II → Estructuras de datos → Algoritmos avanzados).
Planificación de tareas: flujos de trabajo y pipelines (no hay deploy sin compilar ni testear antes).
Procesamiento de imágenes y señales: cada filtro depende de la salida del anterior.
Sistemas de versiones y CI/CD: ordenar commits o integraciones en DAGs de builds.

17.6 Algoritmo de Kahn para probar en CLion

Implementación del algoritmo de Kahn sobre lista de adyacencia (grafos dirigidos). Si hay ciclo, el orden no es posible.

#include <stdio.h>
#include <stdlib.h>

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

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

Grafo crearGrafo(int n) {
  Grafo g;
  g.n = n;
  g.listas = calloc(n, sizeof(Arista *));
  return g;
}

void agregarAristaDirigida(Grafo *g, int u, int v) {
  Arista *a = malloc(sizeof(Arista));
  a->destino = v;
  a->sig = g->listas[u];
  g->listas[u] = a;
}

int ordenTopologicoKahn(const Grafo *g, int *orden) {
  int *indeg = calloc(g->n, sizeof(int));
  for (int u = 0; u < g->n; u++) {
    for (Arista *it = g->listas[u]; it; it = it->sig) {
      indeg[it->destino]++;
    }
  }

  int *cola = malloc(g->n * sizeof(int));
  int ini = 0, fin = 0;
  for (int i = 0; i < g->n; i++) {
    if (indeg[i] == 0) cola[fin++] = i;
  }

  int idx = 0;
  while (ini < fin) {
    int u = cola[ini++];
    orden[idx++] = u;
    for (Arista *it = g->listas[u]; it; it = it->sig) {
      int v = it->destino;
      if (--indeg[v] == 0) {
        cola[fin++] = v;
      }
    }
  }

  free(indeg);
  free(cola);
  return idx; /* cantidad de nodos ordenados */
}

int main(void) {
  Grafo g = crearGrafo(6);
  agregarAristaDirigida(&g, 0, 2);
  agregarAristaDirigida(&g, 0, 3);
  agregarAristaDirigida(&g, 1, 3);
  agregarAristaDirigida(&g, 1, 4);
  agregarAristaDirigida(&g, 3, 5);
  agregarAristaDirigida(&g, 2, 5);

  int *orden = malloc(g.n * sizeof(int));
  int colocados = ordenTopologicoKahn(&g, orden);

  if (colocados != g.n) {
    printf("Hay un ciclo dirigido, no existe orden topologico.\n");
  } else {
    printf("Orden topologico (Kahn):\n");
    for (int i = 0; i < g.n; i++) {
      printf("%d%s", orden[i], (i + 1 == g.n) ? "\n" : " ");
    }
  }

  free(orden);
  return 0;
}

17.7 Algoritmo DFS (aplicación en C)

Versión recursiva con detección de ciclos usando colores (0 no visitado, 1 en proceso, 2 finalizado). Si hay back-edge, no existe orden topológico.

#include <stdio.h>
#include <stdlib.h>

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

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

Grafo crearGrafo(int n) {
  Grafo g;
  g.n = n;
  g.listas = calloc(n, sizeof(Arista *));
  return g;
}

void agregarAristaDirigida(Grafo *g, int u, int v) {
  Arista *a = malloc(sizeof(Arista));
  a->destino = v;
  a->sig = g->listas[u];
  g->listas[u] = a;
}

int dfsTopo(const Grafo *g, int u, int *color, int *stack, int *top) {
  color[u] = 1; /* en proceso */
  for (Arista *it = g->listas[u]; it; it = it->sig) {
    int v = it->destino;
    if (color[v] == 0) {
      if (!dfsTopo(g, v, color, stack, top)) return 0;
    } else if (color[v] == 1) {
      return 0; /* ciclo */
    }
  }
  color[u] = 2; /* finalizado */
  stack[(*top)++] = u;
  return 1;
}

int ordenTopologicoDFS(const Grafo *g, int *orden) {
  int *color = calloc(g->n, sizeof(int));
  int *stack = malloc(g->n * sizeof(int));
  int top = 0;

  for (int u = 0; u < g->n; u++) {
    if (color[u] == 0) {
      if (!dfsTopo(g, u, color, stack, &top)) {
        free(color);
        free(stack);
        return 0; /* hay ciclo */
      }
    }
  }

  for (int i = 0; i < top; i++) {
    orden[i] = stack[top - 1 - i]; /* invertir stack */
  }

  free(color);
  free(stack);
  return 1;
}

int main(void) {
  Grafo g = crearGrafo(6);
  agregarAristaDirigida(&g, 0, 2);
  agregarAristaDirigida(&g, 0, 3);
  agregarAristaDirigida(&g, 1, 3);
  agregarAristaDirigida(&g, 1, 4);
  agregarAristaDirigida(&g, 3, 5);
  agregarAristaDirigida(&g, 2, 5);

  int *orden = malloc(g.n * sizeof(int));
  if (!ordenTopologicoDFS(&g, orden)) {
    printf("Hay un ciclo dirigido, no existe orden topologico.\n");
  } else {
    printf("Orden topologico (DFS):\n");
    for (int i = 0; i < g.n; i++) {
      printf("%d%s", orden[i], (i + 1 == g.n) ? "\n" : " ");
    }
  }

  free(orden);
  return 0;
}

Retornar