Algorithm for constructing a numbering reflecting the order of activities

Question

I'm following a book about graphs and they introduce a concept called 'activity network'. In an activity network, each vertex represents an activity in a project (like building a house for example) that needs to be done. An arc between two activities $uv$ means $u$ needs to be done before $v$ and the weight of the arc represents the duration it takes to complete $u$.

A given activity network could look like this:

• $A$: Foundation, duration: 7 days
• $B$: Door frames, duration 2 days
• $C$: Put in walls, 10 days, depends on $A$, $B$
• ...

Based on this, we can draw the graph of the activity network, satisfying the precendence relations.

The book introduces a way to number the vertices in the network in such a way that the precedence relations are satisfied.

A good numbering in this case would be $A \mapsto 1, B \mapsto 2, C \mapsto 3$. What would not be possible is to number $C$ as $1$, since $C$ depends on $A, B$.

The book uses the following algorithm:

• Represent each activity as a vertex. For each vertex, create a shadow vertex.
• Construct a bipartite graph in which one set of vertices consists of the original vertices and the other set cosnstis of the shadow vertices.
• If an activity $Y$ depends on $X$, then draw an edge joining $Y$ to the shadow vertex of $X$.
• Number all the original vertices without edges.
• Delete all numbered vertices and their corresponding shadow vertices.
• Continue until all vertices are numbered.

---

Besides the description and some examples, the book doesn't contain any more details.

1. Is there a name for this algorithm, so that I can look up more information?
2. In particular, why does the usage of a bipartite graph necessarily result in a good numbering?

The book remarks that this algorithm was developed by Fulkerson. Tried to search for it, but mainly his network flow algorithms came up.

Answer 1

This is called topological sorting.

There are many algorithms for topological sorting. The one you list isn't the first I would recommend studying, to learn about this topic. There's no fundamental need for shadow vertices or a bipartite graph. See, e.g., https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm. I've always heard this attributed to Kahn, not Fulkerson.

Without context on the specific book you are reading and a quote of the relevant section, I have no way of clearing up why the book presented it that way.