Join GitHub today
GitHub is home to over 31 million developers working together to host and review code, manage projects, and build software together.Sign up
Diagram Generation Algorithm
Diagram Generation Algorithm
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 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:
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:
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 an edge which is not an activity.
Exploding the example would produce the below verbose graph:
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:
D, EDepend on
D, E, FDepend on
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
D, E, F do not depend on
A together, since
A is shared only by
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
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:
What we got is a clearer representation of the fact that
D, E depend on
A, B, C but
F only depends on
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 or both:
- The only out-edge of a node - That means the node they point at is the only dependent on that node.
- 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:
While not strictly part of an arrow diagram structure, some extra complexity reduction steps are possible. These steps are not yet implemented and require some more thought.
There are cases where a group of activities could be consolidated onto a single edge. For example consider this example:
Assuming the duration of activities
1, 2, 3 is similar, we could lose some accuracy but draw the much simpler diagram:
Another consolidation candidate is this:
Which could simply be represented as:
Somewhat low hanging fruit, a milestone is an activity with zero duration, it represents some integration point or a common event of activities being completed. By inspecting the duration of an activity, it could be exploded into a node and not an edge on the arrow diagram, and thus reduce complexity further.
IDesign's notation for milestone nodes is: