Tarjan's algorithm: do lowest-links have to be similar for two or more nodes to be inside the same SCC -


i'm having trouble homework question involving using tarjan's algorithm on provided graph find particular scc's graph. while (according professor) have found correct scc's using pseudo-code algorithm found here, of nodes in scc's not share same lowest-link number root node scc.

from can gather pseudo-code, because if un-referenced node i (which input node current recursive call algorithm) has arc visited node i + 1 not root node, algorithm sets is ll = min(i.lowestlink, (i + 1).index), , (i + 1).index may not equal own lowest-link value anymore.

for example (this similar part of graph problem i'm trying solve): if have nodes in n = {a, b, c, d}, , arcs in e = {a ⇒ c, c ⇒ b, c ⇒ d, b ⇒ a, d ⇒ b}, , our root node start algorithm a, then:

1.1) set a.index = 1 (using 1 rather 0), a.ll = 1, , push a onto stack; a has single arc c, check c; finding undiscovered, call algorithm on c.

2.1) set c.index = 2, c.ll = 2, , push c onto stack; c has 2 arcs, 1 b, , 1 d. assume our loop checks b first; b undiscovered, , call algorithm on b.

3.1) set b.index = 3, b.ll = 3, , push b onto stack; b has 1 arc a; checking a find on stack, , (by pseudo-code linked above) set b.ll = min(b.ll, a.index) = a.index = 1; b has no further arcs, exit our loop, , check if b.ll = b.index, not, end instance of algorithm.

2.2) recursive call on b has ended, set c.ll = min(c.ll, b.ll) = b.ll = 1. c still has arc c d remaining; checking d find undefined, call algorithm on d.

4.1) d.index set 4, d.ll set 4, , push d onto stack. d has 1 arc d b, check b; find b in stack, set d.ll = min(d.ll, b.index) = b.index = 3. d has no further arcs, exit our loop , check if d.ll = d.index; not, end instance of algorithm.

2.3) recursive call on d ended, again set c.ll = min(c.ll, d.ll) = c.ll = 1. c has no further arcs, , end our loop. check see if c.ll = c.index; not, end instance of algorithm.

1.2) recursive call on c ended, set a.ll = min(a.ll, c.ll) = 1. a has no further arcs, end our loop. check if a.ll = a.index; equal, have found root node scc; create new scc, , pop each item in stack scc until find a in stack (wich goes scc).

after these steps nodes in graph discovered, running algorithm other nodes nothing, have 1 scc = {a, b, c, d}. however, d.ll = 3 not equal rest of nodes lowest-links (which 1).

have done wrong here? or possible in situation have scc differing lowest-links among nodes?


Comments

Popular posts from this blog

database - VFP Grid + SQL server 2008 - grid not showing correctly -

jquery - Set jPicker field to empty value -

.htaccess - htaccess convert request to clean url and add slash at the end of the url -