Um trabalho de compilação só pode começar depois que todos os seus pré-requisitos terminarem. Conte as arestas de entrada e mantenha uma fronteira de trabalhos sem pré-requisitos pendentes. Processar um trabalho remove suas dependências de saída, o que pode deixar mais trabalhos prontos. Se a fronteira esvaziar antes de todos os trabalhos serem processados, resta um ciclo.
A mesma travessia responde a várias perguntas diferentes. Escolher o menor identificador pronto gera uma ordem reproduzível. Dois trabalhos prontos revelam uma escolha, então a ordem completa não é única. Os instantes de término usam o predecessor mais lento, enquanto as contagens de cadeias somam as contribuições dos predecessores empatados. Esses valores precisam ser atualizados antes de um sucessor sair da fronteira. Comece com uma auditoria de viabilidade e depois diferencie as regras de ordem dos valores que você propaga pelo grafo.
O trabalho 2 espera até o instante 7; o trabalho 3 termina no instante 13.