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

Python Kivy ListView: How to delete selected ListItemButton? -

Image
i'm trying learn kivy building simple todo-list app suggested dusty phillips, author of book "creating apps in kivy". this code far: from kivy.app import app kivy.uix.boxlayout import boxlayout kivy.properties import objectproperty kivy.uix.listview import listitembutton class taskbutton(listitembutton): pass class todoroot(boxlayout): task_input = objectproperty() task_list = objectproperty() def add_task(self): self.task_list.adapter.data.extend([self.task_input.text]) self.task_list._trigger_reset_populate() def del_task(self): pass class todoapp(app): def build(self): return todoroot() if __name__ == '__main__': todoapp().run() and kv file: #: import main todo #: import listadapter kivy.adapters.listadapter.listadapter #: import listitembutton kivy.uix.listview.listitembutton todoroot: <todoroot>: orientation: "vertical" task_input: task_input_view t...
Read more

asp.net mvc 4 - A specified Include path is not valid. The EntityType '' does not declare a navigation property with the name '' -

i wonder if help. above error when call .include() . breaks when include tblmemberships . this.dbcontext.configuration.lazyloadingenabled = false; list<tblcustomerinfo> customers = this.dbcontext.tblcustomerinfoes.include("tblusers").include("tblmemberships").tolist(); the reason because navigation property between tblcustomerinfo , tblmemberships not exist. tblusers link between other 2 tables. customer -- 1:* -- user -- 1:* -- membership (sorry, can't include image reputataion < 10). my questions are: what need in order have tblmemberships included? is recommended way of retrieve data or should break 2 queries? or design totally rubbish? i using ef5, asp .net mvc 4 kindly advise. thank you. when write code this: db.parenttable .include("childtable") .include("childofchildtable"); you saying include entries childtable keyed parenttable , include entries childofchildtable keyed paren...
Read more