algorithm - Linearizing a DAG with multiple sources -


i looking @ algorithms book, , see there simple algorithm linearize single source, directed acyclic graph deleting source nodes 1 one. can give me example why not work multiple sources?

i assume "linearize" mean converting graph sequence of nodes one-to-one mapping, such full graph can recovered.

a single-source dag directed forest. can linearize it, example, pre-order traversal, tree, starting each root sequentially.

for example, graph:

dag single-source

becomes (a (b c)) (e f g).

the problem general dags may have repeat same node more once:

dag multiple sources

will become (a (b c)) (e (b c) f g), , when reconstruct graph, may get:

reconstructed dag

unless handle duplicates specifically. linearize (a (b c)) (e b f g) , solve problem remembering nodes reconstructed, though.

anyway, suppose using node deletion algorithm, remove b here on first encounter, won't able reach e, , you'll (a (b c)) (e f g) wrong.


Comments

Post a Comment

Popular posts from this blog

php - Submit Form Data without Reloading page -

i know question has been asked , answered bunch of times life of me can not solution work on code. believe if redo code, work properly, , in retrospect time i've spent on issue should have redone code...but beyond deadline , have working prototype up... can advise how update multiple forms on single page without reloading page? horrible @ php , complete noob js/jquery/ajax @ best. html/php in single file , believe causing me problems/is largest obstacle @ getting ajax form processing work. basically, want users to: select teams multiple dropdowns in form group 1 (league champs) , on update update db newly selected team without reloadding page. edit team scores per match , on score submit/update, update db new scores. for each requirement there multiple forms (1 each leagues, 1 each per match) have set class on each form id. everything works via php, form submission reloads page each time submitted , not ideal. i have tried ajax code here http://scotch.io/tutoria
Read more

linux - Rails running on virtual machine in Windows -

the reason why want switch ubuntu people said gems works better on linux on windows. i don't want macbook pro rails development since love windows , cannot stand lack of apps mac. moreover, people saying ubuntu "better" mac: http://www.reddit.com/r/ubuntu/comments/1bgj1s/are_there_advantages_of_ubuntu_over_os_x_for/ does virtual box work enough doesn't have lag @ all? using i7-3517u cpu 8gb memory. need program in environment lag-free , not sluggish. or there alternatives recommend? i unsure permission settings or complicated stuffs regarding terminal. i'll using terminal develop. i'm still quite new here development in linux. please kind me >< thanks. @holyxiaoxin pretty sure should asking on superuser instead. nevertheless, suggest install ubuntu in partition instead of running virtual machine. here's guide https://help.ubuntu.com/community/windowsdualboot also, yes. developing in virtual machine accurate, @ end experiment w
Read more

php - $params->set Array between square bracket -

i'm using k2 in joomla 3.3. i'm trying set params (items ids ) module k2_content item.php file. result must between brackets, like: ["96","68"] my code is: $query = "select * #__k2_items extra_fields_search = '$myautor' , catid !=1 " ; $db->setquery($query); $losautores = $db->loadobjectlist(); $result = array(); foreach ($losautores $key => $value) { $result[] = '" '.$value->id.' "'; } $string_version = implode(',', $result); $autoresfinal = '['.$string_version.']'; if test using print, looks ok. passing var pramas, 1064 error. $params->set('items', $autoresfinal); to test tried $autoresfinal = ["96","68"]; and works fine. idea why doesn't work? thank you. if assign ["x","y"] assigning an array . here transforming array in st
Read more