# Generating project network graph

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?

• I don't understand the problem. If you're given a list of edges, you already have a graph -- that is one reasonable representation of a graph (namely, adjacency list format) -- so there is nothing more to compute. How is an edge specified? As a pair of vertices (the source vertex and the target vertex)? Are you asking how to draw a 2D picture/image of a graph, given the graph? If so, read about graph layout algorithms. – D.W. Mar 4 '19 at 21:06
• @D.W.♦ No, the edges are not given as relations over vertices set. The table contains just edge's "name", edge's weight and list of other edges "names" that are adjacent to this edge. I think it doesn't looks that there is a direct relation between edge set and the table content. – Elman Mar 4 '19 at 21:20
• @D.W. ♦ Actually, I need to get a list of directed edges with weights (possibly, zero), so that the graph on these edges satisfies all dependencies given in table and condition of existence of source and sink vertices. – Elman Mar 4 '19 at 21:38

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'$$).
• Will this method cope with dependencies that are not direct, therefore represented as zero weighted edges? (like $x_{2} \rightarrow x_{3}$ and $x_{3} \rightarrow x_{4}$ on example graph) – Elman Mar 5 '19 at 8:50