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

Post a Comment

Popular posts from this blog

C# random value from dictionary and tuple -

-
i have following code, , need random item contains string "region_1" dictionary. public static dictionary<int, tuple<string, int, currencytype>> itemarray = new dictionary<int, tuple<string, int, currencytype>>() { { 0xb3e, new tuple<string, int, currencytype>("region_1", 1500, currencytype.fame) } }; public static int generateitemid(string shopid) { var generateditem = itemarray.elementat(new random().next(0, itemarray.count)).key; } how select this? it's not possible efficiently... first create static random @ class level... prevent non-random behaviour if run query on short period of time... (it's seeded discrete clock) static random rnd = new random(); then: var item = itemarray.values .where(t => t.item1 == shopid) .orderby(_ => rnd.next()) .firstordefault()
Read more

cgi - How do I interpret URLs without extension as files rather than missing directories in nginx? -

-
so i'm trying install zoneminder , have run under nginx, has few compiled files need run using fast-cgi. these files lack extension. if file has extension, there no issue , nginx interprets file , return 404 if can't find it. if has no extension, assume it's directory , return 404 when can't find sort of index page. here have now: # security camera domain. server { listen 888; server_name mydomain.com; root /srv/http/zm; # enable php support. include php.conf; location / { index index.html index.htm index.php; } # enable cgi support. location ~ ^/cgi-bin/(.+)$ { alias /srv/cgi-bin/zm/; fastcgi_pass unix:/run/fcgiwrap.sock; fastcgi_param script_filename $document_root/$1; include fastcgi.conf; } } the idea is, under cgi-bin directory goes through fastcgi pipe. any idea on howi can fix this? upon closer inspection, realized zoneminder has 2 cgi sc...
Read more

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

-
ok , searched more 4 days , more 20 posts here in stach or in websites without kind of success first here htaccess file rewriteengine on rewriterule ^([a-za-z0-9_]+)/?$ index.php?page=$1 [nc] rewriterule ^([a-za-z0-9_]+)\/([a-za-z0-9_]+)\/?$ index.php?page=$1&action=$2 [nc] i tried many codes 1 worked me can call request , works me www.example.com/pagename => www.example.com/index.php?page=pagename here questions , please provide me information "in detail" understand code well 1- how convert request automatically www.example.com/index.php?page=pagename www.example.com/pagename 2- if tried add slash @ end shows me page without images or styling mean www.example.com/pagename => works www.example.com/pagename/ => doesn't work that's :) for first part need 301 rule this: rewritecond %{the_request} /index\.php\?page=([^\s&]+) [nc] rewriterule ^ /%1? [r=301,l] for second part use absolute path in css, js, images files r...
Read more