1
$\begingroup$

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.

Activities table

Desired project network graph looks like this:

Project network graph

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 4 at 21:06
  • $\begingroup$ @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. $\endgroup$ – Elman Mar 4 at 21:20
  • $\begingroup$ @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. $\endgroup$ – Elman Mar 4 at 21:38
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Elman Mar 5 at 8:50
  • $\begingroup$ @Elman, I don't know what what it means for a dependency to be direct or not, or what the weights mean; the question says nothing about that. But yes the approach should handle edges of all weights, whether zero or non-zero. $\endgroup$ – D.W. Mar 6 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.