Diagram Generation Algorithm

Diagram Generation Algorithm

Overview

When I was first shown an arrow diagram I did not understand what was I looking at. I took it as a node diagram and couldn't figure out what was it about. After learning more about arrow diagrams and building a few manually I eventually faced the complexity of building large arrow diagrams.

Although, admittedly, creating node diagrams of the same project was less complex, the result was confusing and convoluted. Still, my starting point for this algorithm is the node diagram for the activity list.

The reason for that is that after many hours thinking about the problem I have a somewhat clear mapping between the two in my head and I can see how they are equivalent. For each upside of an arrow diagram you can find a downside in the node diagram and vice-versa. It just so happens, that for representing projects, arrow diagrams turn out clearer.

The Algorithm

Input

The input to the algorithm is a list of activity IDs and for each activity, also the list of predecessor IDs. For visualization purposes, each activity has some metadata like its duration and total slack.

For the purpose of this explanation, I will work on the following toy project data:

• Activity 1
• Activity 2 - Predecessors 1
• Activity 3 - Predecessors 1
• Activity 4 - Predecessors 1
• Activity 5 - Predecessors 2, 3
• Activity 6 - Predecessors 1, 5, 4
• Activity 7 - Predecessors 5, 6

Creating a Node Diagram

Converting this list to a node diagram is a straight forward operation. Each activity gets a node, each dependency gets an edge from the predecessor to the activity.

It is expected that for a valid project there would be a single node which has no in-edges and a single node which has no out-edges.

Here is how such a diagram would look like:

Reducing Complexity

For the purpose of an arrow diagram, complexity is your prime enemy. When something in the diagram does not add information, you would want to get rid of it.

My first change to the diagram was to reduce such complexity by calculating the transitive reduction of the graph. That basically means that if there is an edge connecting two nodes when there exists also an indirect path between them, the direct path is removed.

In the example presented, edges [1,6] and [5,7] should be reduced.

The transitive reduction of the above graph would be something like this:

Exploding

I call this step exploding since I create an arrow diagram by exploding every node to an activity edge with two start and end event nodes. I also maintain the dependencies by connecting each end event node of an activity to the start event node of a dependent activity with a dummy edge which in arrow diagrams represents a dependency which is not an activity.

Exploding the example would produce the above verbose graph:

Redirecting

At this step, I follow a rule which says that every group of nodes which share a group of dependencies should be pointed by these dependencies indirectly via only a single node. This sounds complex, but it basically means that I do a greedy run, trying to get less dummy arrows pointing at nodes. So, again, reducing complexity.

Let me give a simple example:

This arrow diagram shows that:

• Nodes D, E Depend on A
• Nodes D, E, F Depend on B, C

Say node B is now processed, Being greedy, it would like to "own" all the dependencies of its dependents. So in this case, we can see that its dependents D, E, F all rely on B which is obvious, but also on C.

Note that D, E, F do not depend on A together, since A is shared only by D, E.

Now, B can "own" the dependency on C by depending on it itself. This way its dependents D, E, F would "get" this dependency indirectly by node B. This trades 3 edges with one edge and in that respect reduces complexity.

Doing that, we get:

Now, all of C's dependents (B) get their dependencies via C.

Moving on to process node A, all of it's dependents D, E depend on A which is obvious but also on B. Being greedy, A would redirect the B dependency to be delivered by him like this:

Note: This step only processes end event nodes since it only redirects dummy edges. Also, we treat all the nodes as equals but this step works because of the way the arrow diagram was exploded from the corresponding node diagram. Convince yourself that it works. (If not, give me feedback!)

There are some edge cases the algorithm handles but by and large this is how the redirection step works.

Back to the main example, this is how it would look after the redirect step:

Redundant Edge Reduction

This stage is also about reducing the complexity (you guessed it). Some edges add no information to the graph, namely, edges which are dummy edges (represent dependency) and are either:

• Are the only out edge of a node - That means the node they point at is the only dependent on that node.
• Are the only in edge of a node - That means that the node they point from is the only dependency of that node.

In both cases, the edge can be removed and the nodes it connected could be merged.

One edge case here is that this could create parallel edges where multiple edges connect the same pair of nodes. Currently the algorithm does not reduce edges in those cases although this could possibly be improved.

Here, in red and blue are the nodes and edges which could be removed and merged together:

And the result after the reduction: