Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Network Knowhow: Partial Orderings

The dependencies among a project's tasks gives you a partial ordering of those tasks. In this article, learn how to extend that to a complete ordering so you can decide what to do first, what to do next, and how long the whole project will take.


advertisement
Have you ever tried to assemble a model, piece of furniture, or garbage disposal and run into instructions like this?

“Clamp hose A onto connector B... [30 minutes of frustration later] ... after removing connector cover C.”

The problem isn't really in the instructions (although they may be badly worded, too) but in their ordering.



In any complex endeavor, some of the tasks must come before others but usually the exact order of some tasks doesn't matter. For example, suppose you're building a house. Obviously you need do the framing work before you can put wires and pipes in the frame, but you can probably to the plumbing first and or the wiring first without causing too many problems.

A list of tasks with some dependencies is called a partial ordering. It determines the ordering of some tasks (framing comes before plumbing) but not necessarily every task (plumbing and electrical work are independent).

A complete ordering is an ordering of the tasks that satisfies all of the requirements of the partial ordering. The process of finding a complete ordering for a partial ordering is called extending the ordering.

Note that the complete ordering is not guaranteed to be unique. In the house-building example, you could do the wiring or plumbing in either order.

Note also that a complete ordering isn't always possible. If the plumbers insists that they must do their work first and the electricians also insist that their work come first, you're stuck. (You may have to fire them all and find a new crew.)

The ExtendPartialOrdering program, which is shown in Figure 1 and available in C# and Visual Basic versions in the download area, extends a partial ordering to a full ordering. Enter relationships on the left using a < sign to indicate that one task must come before another. Use the Data menu's Extend Ordering item or press F5 to make the program build a complete ordering if one is possible.

Figure 1. Task Table: Program ExtendPartialOrdering extends a partial ordering to a full ordering.

The left side of the ExtendPartialOrdering program shows one way to represent a partial ordering. You can also represent a partial ordering as a network. Make a node for each task and add a directed link from each task to every task that must come after it. Figure 2 shows the house-building data from Figure 1 in a network format.

Figure 2. Network Necessities: in this task network, arrows show which tasks must come before others.

Now you can perform all sorts of interesting tricks on the network representation. For example:
    * If the network contains a cycle (a series of links that lead in a circle), then there is no complete ordering. (The plumbers and electricians are claiming they must go first.)
    * Any node with in-degree 0 (no links lead into it), can be started immediately.
    * If the network contains more than one disconnected piece, then the pieces can be worked independently.
    * The longest path through the network tells you how long it will take to perform all of the tasks.
Extending the partial ordering to a complete ordering is equivalent to moving the network's nodes around so all of the nodes are in a line and all of the links point more or less in the same direction. The links can curve, intersect, and even pass under nodes as long as none points back to a node earlier in the list.

Figure 3 shows a complete ordering of the network shown in Figure 2. Here the downward direction indicates the passage of time so tasks higher up in the network must be performed before those lower down.

Figure 3. Ready to Run: All of these links point downward so this network shows a complete ordering.

So how do you arrange the network as shown in Figure 3 in code? You could probably bash your way through an algorithm that treats the network in a general fashion but there's an easier way to approach the problem that relies on its special structure.

Build a class that records a task's name, number of items that must be done before it, and list of items that it must be done before. The ExtendPartialOrdering program uses the following class.

// Represent a task. private class POItem {    public string Name { get; set; }    public int NumBeforeMe { get; set; }    public List<POItem> ItemsAfterMe { get; set; }    public POItem(string name)    {        Name = name;        NumBeforeMe = 0;        ItemsAfterMe = new List<POItem>();    } }

Here's the algorithm:
    1. Build the POItem objects to represent the tasks.

    2. Make a list called no_prerequisites containing the items that have NumBeforeMe = 0. Those tasks are ready to run.

    3. While no_prerequisites is not empty, take the first item in the list (call it ready_item) and:

      a. Remove ready_item from the list.

      b. Add ready_item to the output. It is ready to go.

      c. For each of the items in ready_item's ItemsAfterMe list (call one of those items after_item):

        i. Decrement after_item.NumBeforeMe.

        ii. If after_item.NumBeforeMe = 0, add after_item to no_prerequisites.

    4. Continue until no_prerequisites is empty. At that point either:

      a. If all of the items have been added to the output, then you're done.

      b. If there are still items with NumBeforeMe > 0, then the partial ordering cannot be extended to a complete ordering.

    The following code shows how the ExtendPartialOrdering program implements this algorithm. The download includes some additional debugging code that validates the results to be sure they satisfy the requirements of the partial ordering.

    // Return an array giving the items in a complete ordering. public List<string> CompleteOrdering() {    List<string> results = new List<string>();    // Find items that have no prerequisites.    var no_prereqs_query =        from POItem po_item in AllItems.Values        where po_item.NumBeforeMe == 0        select po_item;    List<POItem> no_prerequisites =        new List<POItem>(no_prereqs_query);    // Process items with no prerequisites.    while (no_prerequisites.Count > 0)    {        // Process the first item in the list.        // Remove the item.        POItem ready_item = no_prerequisites[0];        no_prerequisites.RemoveAt(0);        // Add the item to the results.        results.Add(ready_item.Name);        // Remove this item from the other        // items' prerequisite counts.        foreach (POItem after_item in ready_item.ItemsAfterMe)        {            // Remove next_item from other_item's count            // and see if the count is 0.            if (--after_item.NumBeforeMe == 0)            {                // Add other_item to the list of                // items without prerequisites.                no_prerequisites.Add(after_item);            }        }    }    // See if any items are left with prerequisites.    // If so, then there are circular dependencies.    var check_query =        from POItem po_item in AllItems.Values        where po_item.NumBeforeMe != 0        select po_item;    if (check_query.FirstOrDefault() != null)    {        // There are items remaining.        throw new Exception("There is no complete ordering " +            "for this partial ordering");    }    return results; }

    When it scans the text on the left in Figure 1, the program builds its POItems. It adds all of them to the AllItems list so they're easy to find later.

    The code shown here uses Language Integrated Query (LINQ) to select the objects with NumBeforeMe = 0 into a list named no_prerequisites.

    Next the code enters a loop that runs while no_prerequisites is not empty. In that loop, it takes ready_item from the front of the no_prerequisites list and adds it to the output. It then loops through ready_item's ItemsAfterMe list, updating those items appropriately.

    When no_prerequisites is empty. The program uses LINQ to see if any items still have NumBeforeMe > 0. If there are such items, the program throws an error.

    The figures shown so far use a very simple example so you can easily verify that the ordering makes sense but real-world projects are often much bigger. You can see a sample construction schedule for a 6,000 square foot custom home at b4ubuild.com that includes almost 200 tasks. Bigger projects such as movie production or skyscraper building might include thousands of tasks.

    To let you test some bigger problems, the ExtendPartialOrdering program's Data menu includes two addition commands: Random Ordering and Complete Ordering.

    When you invoke the Random Ordering command, a dialog lets you enter a number of tasks and a number of conditions. The program then creates some random partial ordering requirements. For item names it uses numbers and, to guarantee that a solution is possible, it creates the relationships so smaller numbers come before larger ones. Note that this does not mean the number must be in numerical order in the final ordering. The program only satisfies the random requirements not all of the requirements needed to ensure a perfect numerical ordering. Figure 4 shows the program after solving a random network with 1,000 tasks and 10,000 relationships. You can see that the results aren't in completely numeric order but, trust me, the solution satisfies the requirements.

    Figure 4. Random Relationships: The Data > Random Ordering command makes the program build random items and relationships.


Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap