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