Graph value propagation algorithm -


i've got directed graph (n, a), each node n[i] has value v[i] , threshold t[i]. each arrow (n[i], n[j]), invariant v[i] <= v[j] holds. need efficiently implement following operations:

  • increasethreshold(i, x): set t[i] = max(t[i], x). that's trivial , completeness here.
  • increasevalue(i, x): set v[i] = max(v[i], x) , increase other values needed above invariant holds.
  • evaluate(i): return true if v[i] < t[i]

the straightforward implementation store v[i], t[i], , outgoing arrows each node. on increasevalue(i, x), it'd propagate value along outgoing arrows (using set of "open" nodes many other graph algorithms do). v[i] stored each node, evaluate(i) trivial.

as increasevalue more frequent other operations, eager approach seems wasteful. wonder, if lazy propagation v[i] recomputed needed more efficient. this, i'd maintain w[i] maximum of x increasevalue(i, x) , compute v[j] on fly when evaluate(j) needs it. can computed maximum of w[i] on nodes n[i] there's path n[j]. actually, once know v[j] >= t[j], exact value v[j] doesn't matter , can stop computation.

unfortunately, lazy algorithm inefficient, doesn't pay off increasevalue being orders of magnitude more frequent evaluate.

i imagine, "partially lazy" algorithm better, that's intuition , can't make progress it.

is somehow well-known problem? other idea?


Comments

Post a Comment

Popular posts from this blog

resizing Telegram inline keyboard -

telegram's inline keyboard great feature lots of different use cases. inline buttons added list of items this: inline_keyboard = [[inlinekeyboardbutton(text="button", callback_data="button"), inlinekeyboardbutton(text="reset",callback_data="reset")]] inline_keyboard_markup = inlinekeyboardmarkup(inline_keyboard) update.message.reply_text("hi", reply_markup=inline_keyboard_markup) the above code adds 2 buttons each half width of chat screen. i know the normal keyboard button there resize_keyboard parameter somehow can used. my question is there way resize inline buttons ? example make full width or quarter width. unfortunately, can't now. :( you can suggest @botsupport , might add feature next version.
Read more

javascript - How to bind ViewModel Store to View? -

i'm pretty new ext js , trying embed multiselect inside panel . the viewmodel has stores property can see here: ext.define('test.view.controls.search.searchfiltermodel', { extend: 'ext.app.viewmodel', alias: 'viewmodel.filter', data: { title: '' }, stores: { test: { fields: [ 'id', 'name' ], proxy: { type: 'ajax', url: 'api/test', reader: 'array' }, autoload: true } } }); i bind in view this: viewmodel: { type: 'filter' }, layout: 'fit', border: 1, plain: true, scrollable: 'y', layout: 'fit', bind: { title: '{title}', }, items: { xtype: 'multiselect', scrollable: false, allowblank: true, ddreorder: true, bind: { store: '{test}' }, valuefield: 'id', displayfield: 'name' } ...
Read more

c - Why does alarm() cause fgets() to stop waiting? -

i playing around signals in c. main function asks input using fgets(name, 30, stdin) , , sits there , waits. set alarm alarm(3) , , reassigned sigalrm call function myalarm calls system("say pay attention") . after alarm goes off, fgets() stops waiting input , main fn continues on. happens if change myalarm set variable , nothing it. void myalarm(int sig) { //system("say pay attention"); int x = 0; } int catch_signal(int sig, void (*handler)(int)) { // when signal comes in, "catch" , "handle it" in way want struct sigaction action; // create new sigaction action.sa_handler = handler; // set it's sa_handler attribute function specified in header sigemptyset(&action.sa_mask); // "turn signals in sa_mask off?" "set sa_mask contian no signals, i.e. nothing masked?" action.sa_flags = 0; // not sure, looks aren't using of available flags, whatever may return sigaction(sig, ...
Read more