Come migliorare la progettazione di un semplice algoritmo di gestione del progetto per un grafico non ciclico diretto

Mi è stato detto di migrare qui da SO con questa domanda. Sto lavorando a un piccolo progetto che mira a risolvere un problema di gestione del progetto. L'input sarà nel seguente formato: Un'attività ha un ID specificato, richiede un certo tempo per essere completata e conosce l'ID delle attività che devono essere completate per l'avvio di questa attività. Voglio calcolare l'orario di inizio più recente e più recente per ogni attività. Tuttavia, non sono sicuro di come progettarlo per evitare che l'algoritmo impieghi più tempo necessario, ma mantenga il codice in qualche modo organizzato ed eviti i metodi troppo lunghi e illeggibili.

Ecco la mia idea iniziale:

1. Una classe Task rappresenta ciascun vertice nel grafico. L'attività avrà una lista di bordi in uscita e in entrata; Sa quali compiti dipendono da questo e viceversa.

2. Dopo aver costruito il grafico secondo 1, ordino topologicamente, iniziando dal nodo senza bordi in entrata.

3. Scorrere la lista ordinata topologicamente e calcolare la prima ora di inizio per ciascun vertice. Questo verrà archiviato come campo dati all'interno del vertice.

4. Infine, continua dalla fine all'inizio attraverso la stessa lista ordinata topologicamente e calcola l'ultimo avvio possibile per ogni attività che non ritarda il progetto complessivo.

Il topSort iniziale verrà eseguito in O (| E | + | V |). A questo punto, potrei calcolare contemporaneamente la prima ora di inizio per ciascun vertice che viene ordinato. Ma questo renderebbe il metodo (o almeno lo rende la mia implementazione) molto meno leggibile e un po 'più complicato.

Calcolando il primo tempo di inizio al di fuori del topSort () - il metodo può essere fatto nell'ordine della stessa complessità temporale dell'ordinamento, ma questo è ancora chiaramente peggiore rispetto a farlo nel metodo topSort ().

Si sente anche un po 'ridondante per far sì che tutti i vertici memorizzino le informazioni su ogni spigolo dentro e fuori quando il grafico è diretto. Il ragionamento alla base di questo è che rende semplice iterare all'indietro attraverso la lista ordinata dalla fine verso l'inizio.

Potrei migliorare su questo? Devo entrambi ordinare la lista e calcolare la prima ora di inizio con lo stesso metodo per risparmiare tempo, o è meglio rifattarla? L'elenco dei margini interni è ridondante?