Determine the critical path

Question

In project management there's a method, called the critical path method, that is used for scheduling activities and for determining which activities' timings are crucial (i.e. critical) and for which activities the schedule offers a timing tolerance.

Your program's task is to order a set of activities chronologically and for each of those activities determine their:

• earliest possible start;
• earliest possible finish;
• latest possible start;
• latest possible finish.

Lastly, your program should mark which subsequent activities make up the longest, uninterrupted path; i.e. the critical path.

The input will be the activities by their name, with their duration (in an unspecified time unit) and with the names of the activities they depend on. For this challenge only so-called finish to start dependencies will be presented as input. In other words: any possibly provided dependencies for a given activity signify that said activity can only start when all the activities, that this activity depends on, have finished. No other forms of dependencies will be presented.

The expected input is in the form of (possibly multiples of):

[F:12;C,B]

Where:

• F signifies the activity's name; an uppercase alphabetic character;
• 12 signifies the duration as a positive integer;
• C,B signifies the optional dependencies, as a comma-separated list of activity names.

Here's an example input:

[A:15][B:7][C:9;A,B][D:3;B,C][E:5;C][F:11;D][G:4;D,E,F]

Meaning:

 name | duration | dependencies
------+----------+--------------
    A |       15 |              
    B |        7 |              
    C |        9 |          A,B 
    D |        3 |          B,C 
    E |        5 |            C 
    F |       11 |            D 
    G |        4 |        D,E,F 

Your program's output will be an ASCII table, in the exact following form, but filled with different data, depending on the input of course (here I'm using the example input, from above, as input):

 name | estart | efinish | lstart | lfinish | critical
------+--------+---------+--------+---------+----------
    A |      0 |      15 |      0 |      15 |        Y 
    B |      0 |       7 |      8 |      15 |        N 
    C |     15 |      24 |     15 |      24 |        Y 
    D |     24 |      27 |     24 |      27 |        Y 
    E |     24 |      29 |     33 |      38 |        N 
    F |     27 |      38 |     27 |      38 |        Y 
    G |     38 |      42 |     38 |      42 |        Y 

Where:

• the activities are ordered chronologically ascending by estart (and then arbitrarily);
• estart is earliest start;
• efinish is earliest finish;
• lstart is latest start;
• lfinish is latest finish;
• critical is a Y/N value, signifying whether this activity belongs to the critical path (i.e. lstart - estart = 0 and lfinish - efinish = 0).

The expected constraints for the input will be:

• The activity names will never exceed Z; i.e. the total amount of activities will never exceed 26;
• The total duration (i.e. the latest finish of the last activity) will never exceed 9999999 (the width of the lfinish column, with padding);
• The number of dependencies, for any given activity, will never exceed 6;
• The input will never be inconsistent (e.g. no non-existent dependencies, etc.).

The constraints for your program are:

• No use of existing PM/CPM APIs¹; you must create the algorithm from scratch.

This is a popularity-contest²; the most elegant solution (or at least, I hope that's what voters will vote for), by popular vote, wins. The winner will be determined 4 days after the submission time of this challenge.

---

<sup>1. If any such API even exists.
2. I want to give the more verbose languages a fair shot at this as well.</sup>

Answer 1

GolfScript

A GolfScript solution - just because it can be done.

# Parse input
'['-']'%:I{[.1<\2>';'/(~\{','/{`{\1<=}+I?I?}/}%0]}%

# Determine estart iteratively
{:A{[~{A=~@+\;\;}2$%+$-1=]}%.A=!}do

# Invert dependencies
A{~@+\;\;}%$-1=:M;
[.,,]zip{[~{\~\2=@?0<{;}*}+[A.,,]zip%\:^~;;@^3=M]}%

# Determine lfinish iteratively
{:A{[~{A=~\;\;\-\;}3$%+$0=]}%.A=!}do

# Print results

# Formats numbers (right aligned, 7 chars)
{`"       "\+-7>}:F; 

" name | estart | efinish | lstart | lfinish | critical \n"
"------+--------+---------+--------+---------+----------\n"
@{"    "\(" |"@.2=F" | "@.~;@+\;F" |"@.~\;\;\-F" | "@.3=F" |        "@~-\;+!"NY"1/=n}%

Example (online):

> [A:15][B:7][C:9;A,B][D:3;B,C][E:5;C][F:11;D][G:4;D,E,F]

 name | estart | efinish | lstart | lfinish | critical 
------+--------+---------+--------+---------+----------
    A |      0 |      15 |      0 |      15 |        Y
    B |      0 |       7 |      8 |      15 |        N
    C |     15 |      24 |     15 |      24 |        Y
    D |     24 |      27 |     24 |      27 |        Y
    E |     24 |      29 |     33 |      38 |        N
    F |     27 |      38 |     27 |      38 |        Y
    G |     38 |      42 |     38 |      42 |        Y

Answer 2

C#, many many characters.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication2
{
    class Program
    {
        static char[] COLON = { ':' };
        static char[] SEMI_COLON = { ';' };
        static char[] COMMA = { ',' };
        static char[] BRACE = { ']' };

        static void Main(string[] args)
        {
            int step = 0;

            List<Activity> i = new List<Activity>();
            Console.Write("Enter input: ");
            string s = Console.ReadLine().Replace("[", null);
            foreach (string x in s.Split(BRACE, StringSplitOptions.RemoveEmptyEntries))
            {
                string[] y = x.Split(SEMI_COLON);
                Activity n = new Activity(x.Split(COLON)[0], Int32.Parse(y[0].Split(COLON)[1]));
                n.Name = x.Split(COLON)[0];
                n.Dependencies = (y.Length > 1) ? y[1].Split(COMMA).ToList() : new List<string>();
                i.Add(n);
            }

            do
            {
                List<string> d = i.Where(x => x.Done()).Select(y => y.Name).ToList();
                foreach (Activity working in i.Where(x => x.Dependencies.Except(d).Count() == 0 && !x.Done())) working.Step(step);
                step++;
            } while (i.Count(x => !x.Done()) > 0);

            foreach (Activity a in i)
            {
                Activity next = i.OrderBy(x => x.EFinish).Where(x => x.Dependencies.Contains(a.Name)).FirstOrDefault();
                a.LFinish = (next == null) ? a.EFinish : next.EStart;
                a.LStart = a.LFinish - a.Duration;
            }

            Console.WriteLine(" name | estart | efinish | lstart | lfinish | critical");
            Console.WriteLine("------+--------+---------+--------+---------+----------");
            foreach (Activity a in i)
            {
                Console.Write(a.Name.PadLeft(5) + " |");
                Console.Write(a.EStart.ToString().PadLeft(7) + " |");
                Console.Write(a.EFinish.ToString().PadLeft(8) + " |");
                Console.Write(a.LStart.ToString().PadLeft(7) + " |");
                Console.Write(a.LFinish.ToString().PadLeft(8) + " |");
                string critical = (a.LFinish - a.EFinish == 0 && a.LStart - a.EStart == 0) ? "Y" : "N";
                Console.WriteLine(critical.PadLeft(9));
            }
            Console.WriteLine("Hit any key to exit.");
            Console.ReadKey();
        }
    }

    class Activity
    {
        public string Name {get ; set;}
        public int Duration {get ; set;}
        public List<string> Dependencies {get ; set;} 
        public int EStart {get ; set;}
        public int EFinish {get ; set;}
        public int LStart { get; set; }
        public int LFinish { get; set; }
        private int steps = 0;

        public Activity(string name, int time)
        {
            EStart = -1;
            EFinish = 0;
            LStart = 0;
            LFinish = 0;
            Name = name;
            Duration = time;
            steps = time;
        }

        public void Step(int count)
        {
            EStart = (EStart == -1) ? count : EStart;
            if (--steps == 0) EFinish = count + 1;
        }

        public bool Done()
        {
            return steps == 0;
        }
    }
}

I would hesitate to call this "the most elegant solution", but it trades the verbosity of C# for ease of parsing input and formatting output (and has Linq).

I basically just loops through all of the activities and increments a time counter if all their dependencies have been completed until all of them are done. That gives the earliest starts and earliest finishes. The latest finish for each is simply the earliest start among activities that have it as a dependency, and the latest start is the activity duration minus the latest start.

Answer 3

Haskell, 39 LoC

import Control.Exception.Base (assert)
import Data.List
import Data.Maybe (fromJust)
import Text.Printf

splitBefore x = groupBy (\_ y -> x /= y)

data Activity = Activity {aName :: Char, aLength :: Int, depNames :: [Char]}
                deriving (Eq, Ord, Show)

instance Read Activity where
  readsPrec _ ('[' : aName : ':' : rest1) = 
    let [(aLength, rest2)] = reads rest1 :: [(Int, String)]
        (rest3, ']':rest) = span (/= ']') rest2
        depNames = map (\[_,x] -> x) $ splitBefore ',' $ rest3
    in  [(Activity {aName = aName, aLength = aLength, depNames = depNames},rest)]

main = getLine >>= putStrLn . \input ->
  let activities = map read $ splitBefore '[' $ input :: [Activity]
      activityByName a = fromJust . find ((a ==) . aName) $ activities
      dependencies = map activityByName . depNames 
      dependents a = filter ((a `elem`) . dependencies) $ activities
      estart   a = case dependencies a of 
                     [] -> 0
                     ds -> maximum $ map efinish ds
      efinish  a = estart a + aLength a
      critLength = maximum $ map efinish $ activities
      lfinish  a = case dependents a of
                     [] -> critLength
                     ds -> minimum $ map lstart ds
      lstart   a = lfinish a - aLength a
      critical a = estart a == lstart a
      format   a = printf " %4c | %6d | %7d | %6d | %7d | %8c "
                     (aName a) (estart a) (efinish a) (lstart a) (lfinish a) 
                     (if critical a then 'Y' else 'N')

  in  unlines $ " name | estart | efinish | lstart | lfinish | critical " 
              : "------+--------+---------+--------+---------+----------"
              : map format activities