About a possible optimized version of Johnson's algorithm on a DAG with "elementary circuits"

Question

Recently I came upon the Johnson's algorithm to find "elementary circuits" on a directed graph, which is really cool to me. I'm just implementing it from scratch in C++ following the original Johnson's paper

I have a couple of doubts before going on.

In the paper it's clear to me what $A_k$ about adjacency, but in the pseudocode I see at a certain point $V_k$, which seems to me a TYPO, since probably the $A_k$ should be used instead.

Also, it's clear to me the mechanism to find the "s" vertex and remove it from the $A_k$ to reloop on it with the s+1 vertex.

However it's not clear to me why he needs to find the minimum s from each SCC.

In my code a SCC is represented as a unordered_setm since not in need to have them sorted.

So let's imagine to have a DAG with 50 nodes, and running the Tarjan on it to find SCCs with more than one vertex in them.

In my case this could give a couple of SCCs, let's say:

$${50, 12, 8, 40}$$ and $${4, 3, 20}$$

First of all, I'm wondering why the algo is taking into account also SCCs with 1 node only, since they cannot contain any "elementary circuits", but the self-loops, eventually.

So I was wondering if I could modifiy the algo like this: instead of using an incremental s from 1 to N, why not taking each SCC and pick the entries as they come, i.e. running:

CIRCUIT(50)

then removing 50 from the $A_k$, rebuilding a SCC subgraph from it and re-running:

CIRCUIT(12)

then removing 12 and running

CIRCUIT(8)

and so on and so forth.

Actually I'm probably understimating the problem, but it seems to me we could keep only the "meaningful" SCCs with nNodes > 1 and go linearly on the SCCs, without getting the min Vertex index from them.

Actually I'm applying this possible optimization on a DAG, but it could work for any generic directed graph indeed, I mean:

running Tarjan and keeping ONLY the SCCs with more than 1 node in it

for each SCC, pick the s linearly from the SCC as they come, without worrying about to get the Min s from each of them. Of course, the algo would still remove the s from the SCC subgraph incrementally, to exhaust each SCC as doing in the original paper.

Am I right in claiming that?

Thanks in advance

Answer 1

While implementing Johnson's algo, I think to have figure out by myself why he's exctracting the min node Id from the SCCs, during the pipeline. Basically, Johnson's algo is:

1. initing a StartIndex "s" to 1, since assuming all nodes range from 1 to N
2. extracting a subgraph from the main graph induced by node Ids (s, s+1, ..., N) this means the extracted subgraoh will have nodes Ids >=s, discarding the previous ones.
3. running Tarjan on this subgraph and finding all SCCs from this subgraph
4. finding the min Node Id between all these SCCs and assigning it to s.
5. cleaning internal data (blocked etc)
6. running the CIRCUIT on the s node
7. increasing s by 1, where s is meant to be a node Id, here

Basically, what I have understood is getting the min Id from the SCCs simply let the found circuits to come in their first node Id increasing order. There's no other reason for that, I mean in order to have a "good" enumeration in increasing order.

A possible other solution could be:

1. instead of using s as a node Id to extract the subgraph, simply loop on the internal graph nodes, one by one. So the second graph will start from the second node discarding the first one, etc.
2. build the SCCs on this subgraph as above
3. instead of finding the min Node Id among the SCCs, simply take the first node of the first SCC, assigning it to s.
4. cleaning stuff and running CIRCUIT(s)
5. loop back without the need to increase s, since point 1) is working incrementally on internal nodes, one by one.

Of course this solution will give scrambled circuits, not in increasing order. The only benefit I could see here is to avoid to find the min node Id, saving a bit of time in the algo.

However, finding the minimum between a list of Ids is not taking too much for sure, and complete in a negligible time.

So, all in all, I've decided to keep the original Johnson's approach which gives back the circuits in a elegant and visually appealing increasing order.

The only thing I've changed a bit is the usage of the blocked and blocked set, which I turned to:

1. unordered_set for the blocked nodes, instead of plain bool arrays, saving a bit of memory
2. unordered_map<nodeIdx, vector> representing the blocked chain to be used in the UNBLOCK f(), instead of plain list of vector, saving a bit of memory as well.

I will run build complete graphs up to N=10 and see if my results will match Johnson's paper in the number of found circuits, now, focusing on the performances as well.

A particular care has to be taken between internal node Idx Vs node Ids management. Node Ids are fundamental to be able to re-find the same node within the CIRCUIT to navigate the neighbors of a node in the subgraph. So you basically have to find the node Id of the node fed to the CIRCUIT and match the corresponding one in the subgraph, by the same Id. This is because the subgraph will have LESS nodes than the original graph, and so the Node idx will not make sense in the second subgraph list. However, when found a neighbor, you will have to find back the original graph node idx matching the same Id as well, of course. This is a solution where you refer the internal objects to the original graph node idx domain, no matter the subgraph you are using, and it could sound a bit trickier. However, since the original paper uses $V_k$ as vertex index set inside $A_k$, it's probably better to work directly in the subgraph subidx domain everywhere. I will probably change my current implementation and use this second approach, to avoid to do too many "Id finding" in the CIRCUIT f(). Notice, doing like that, the algo is more robust since does not assume the original graph has uniformly distributed node Ids, but could contain holes in them, like in my case (I mean the node Ids can be {1, 5, 8, 10}, without being uniform and admitting holes).

To sum up: if the circuits order is not important for you, you can use the second solution, saving a bit of time, even if it will not impact the final performances.