1
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, I think that's good enough for me now to continue getting deeper into the topic. $\endgroup$
    – BMBM
    Nov 20, 2023 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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