← Volver a los ejercicios

Catorce módulos

Lo mismo de los ejercicios anteriores, sobre un grafo del tamaño de un problema real: catorce módulos de un proyecto con diecinueve dependencias, y la pregunta de en qué orden compilarlos. El algoritmo es el de la clase, sin cambiar una línea; lo que cambia es que ya no se puede seguir la traza de memoria.

1. El proyecto

Entrada: los catorce módulos y sus dependencias.  Salida: un orden en que compilarlos donde cada módulo vaya después de todos los que necesita, o el aviso de que no existe.

Dependencias:

Diecinueve dependencias. Una flecha de a a b quiere decir que a se compila antes que b.

en la cola saliendo ya compilado se quedó
¿Cuántos módulos alcanza a emitir el algoritmo?

2. Ejecute

Cola: vacía
Orden: –
Paso 0 de 0
Con «Auto» se ve el frente de compilación avanzar por el dibujo.

3. Una fila por módulo que sale

PasoSaleContadores que bajanCola después

4. Qué deja libre el grafo

Sobre las diecinueve dependencias, marque las parejas cuyo orden relativo no está fijado: las que un orden topológico puede poner en cualquiera de las dos formas.

5. El último

En cualquier orden válido, app sale de último. ¿Por qué?

6. Para llevarse

Sin solución aquí. Con estas diecinueve dependencias, ¿cuántos módulos se podrían compilar al mismo tiempo en cada ronda, si en cada una se compilan todos los que ya tienen sus dependencias listas? Cuente las rondas y diga cuál es la ronda más cargada. Después: ¿qué le tendría que cambiar a kahn para que, en vez de una lista, devuelva esas rondas?