1
$\begingroup$

I'm having a little trouble with Tarjan's Algorthm.

So here's my problem: I have a graph such that these nodes are directionally-connected as shown:

A: B C D E
B: D E
C: B D E F
D: C E
E: B
F: A B D E

My problem is Tarjan's Algorithm never revisits nodes, apparently. If the node isn't on the stack, it's not checked.

So here's what's happening:

My algorithm is going A, D, E, B. B checks D.

A(id=0, link=0), D=1, E=2, B=3
-> D is visited, D is on stack, D's id is 1, B(id=3, link=1)

Cute. B checks against E (cycle—it's a tie), which has an ID of 2, and is on the stack, no change.

B is out of neighbors, doesn't have a neighbor, returns out of the recursion so E can continue.

E, upon return from DFS of B, checks B's low-link value. It's lower, so E's low-link value becomes 1.

A(id=0, link=0)
B(id=3, link=1)
C(undefined)
D(id=1, link=1)
E(id=2, link=1)
F(undefined)    

Now return to D. D's id and low-link value are 1, so no change.

Now here's the fun part.

D proceeds to check C. C checks F. F checks A, which has been visited and is on the stack. A has an ID of 0, so D updates.

F(id=5, link=0)
C(id=4, link=0)
B(id=3, link=1)
E(id=2, link=1)
D(id=1, link=0)
A(id=0, link=0)

A proceeds to check the rest of its neighbors. B and D have higher link values and IDs and are on the stack, so A doesn't update.

Every node has been visited.

There's a path from D to E to B to D, meaning those are part of the same SCC (in fact, all of these are in the same SCC—it's one SCC).

The stack is {A, D, E, B, C, F} with F at the top.

The two SCCs are {B,E} and {A,C,D,F}.

…you can reach A from B, and you can reach B from A.

What am I missing here?

$\endgroup$
1
$\begingroup$

Answer: the low-link value is not the identifier. I eventually found this while researching during the writing of this question. Question posted because I wrote it and hey, maybe this will help someone else.

Everything up to the current node is popped off the stack when identifying an SCC. My misunderstanding was trying to pop only what has the same low-link value.

| cite | improve this answer | |
$\endgroup$

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.