Generating project network graph

Question

I had a problem of generating project network graph (like there and there) from list of activities and their dependencies.

Informal description:

Every activity is represented as edge of directed acyclic graph (DAG), so such layout of the graph is called activity-on-edge, as opposed to activity-on-node layout. If the dependency of two activities can not be represented as single vertex, the zero-weight edge (drawn as dotted line) is added to satisfy this dependency.

There is example of activities and dependencies table. In addition, the weights of activities are given.

Desired project network graph looks like this:

Formal description:

Given a list of directed edges names, their weights and list of their predecessor edges (so there is a path between head of predecessor edge and tail of listed edge), build a directed acyclic graph having exactly one vertex with no predecessor edges (source) and one vertex with no successor edges (sink).

Question:

So, the problem of generating project network graph and making some analysis of related project looks so easy if we represent activities not as the edges of DAG but nodes (e.g. activity-on-node layout). But is there an algorithm solving this generating problem? Could we use prepared activity-on-node graph to generate corresponding activity-on-edge graph?

Answer 1

You can build a graph from this by identifying a name for each vertex, and then identifying for each edge the names of the start vertex and end vertex for that edge.

I suggest you name a vertex by the set of edges that are entering that vertex. For instance, the name for vertex $x_5$ in your picture would be "$a_4,a_5,a_6$" if we assume that $a_4,a_5,a_6$ are the names of the three edges that go to $x_5$ -- and similarly. (If you like, you can use the SHA256 hash of the list of edges as the name of the vertex, instead of using the list itself as the name -- that will make the names shorter but won't change anything).

Given your table, we can easily identify the set of all vertex names. Then, for each edge $e$, you can identify the name of its start vertex (by looking at the list of direct predecessor edges of $e$) and the name of its end vertex (by looking at any successor edge $e'$ of $e$, i.e., any edge $e'$ such that $e$ is a direct predecessor of $e'$, and then finding the name of the start vertex of $e'$).

This gives you a description of the graph as a set of edges, where each edge is represented by the name of its start vertex and the name of its end vertex. From this, you can easily construct an adjacency list representation of the graph. This then gives you the output you were seeking.