I had a problem of generating project network graph (like there and there) from list of activities and their dependencies.
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:
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).
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?