Weighted Directed Acyclic Graphs: algorithm to find edge weights such that they define a distance function? -


i have technical problem can formuated directed acyclic graph (dag). nodes represent events (with unknown timing), directed edges encoding relation ship: "i'm younger you/i happened before you".

i need estimate edge weights (i.e. "dynamic weights") such weighted dag (wdag) implies distance function on dag. in other words sum of weights paths between nodes , b should equal paths.

this undetermined problem, if weights integers (same underlying reason topological sorting not unique, suppose). in generality, edge weights, represent timeintervals between nodes/events, real numbers. therefore i'm introducing preset objective function c=j(wdag) on weighted dag, here unspecified.

my question is: there algorithm distributes positive definite weights on wdag, subject constraint 1) weights form distance function of dag , 2) minimizing objective function cost c.

this seems unrelated shortest-path or minimum-spanning-tree problems classically associated wdag's. ideas formal or heuristic solution above problem?

regards,

stephane

i think need topological sorting.

  1. sort nodes according topological sort.
  2. distribute them in [0,1] interval in order got.
  3. now distance of node-pairs on [0,1] line give weight of edge connecting them.

this 1 possible solution. if have more constraints on weights describe in question, problem might more difficult.


Comments

Post a Comment

Popular posts from this blog

c# - SharpSVN - How to get the previous revision? -

i trying find efficient way previous revision of file text comparison using sharpsvn. using (svnclient c = new svnclient()) { c.authentication.defaultcredentials = new networkcredential( configurationmanager.appsettings.get("svnserviceusername") , configurationmanager.appsettings.get("svnservicepassword") , configurationmanager.appsettings.get("svnservicedomain") ); c.authentication.sslservertrusthandlers += new eventhandler<svnsslservertrusteventargs>(authentication_sslservertrusthandlers); collection<svnfileversioneventargs> fileversioncollection = new collection<svnfileversioneventargs>(); svnrevisionrange range = new svnrevisionrange(0, this.hooks.revision); svnfileversionsargs args = new svnfileversionsargs(); args.retrieveproperties = true; args.range = range; foreach (svnchangeitem item in log.changedpaths) { string path = this.repositorypath + it...
Read more

c++ - Is it possible to compile a VST on linux? -

for class project i'm attempting write vst plugin backed cuda. current cuda workflow on linux box, i'd prefer compile , link there. according wikipedia , should possible (i couldn't find steinberg documentation relevant linux) can't find makefile or instructions on how build if aren't using xcode or visual studio. i'm vst 3 sdk doesn't support linux. when try compile plugin under linux, error: ./base/source/fatomic.cpp:39:30: fatal error: libkern/osatomic.h: no such file or directory this issue caused following code in "vst3 sdk/base/source/fatomic.cpp" #if mac #include <libkern/osatomic.h> #if mac_os_x_version_min_required > mac_os_x_version_10_4 #define native_atomic_type (volatile int32_t*) #else #define native_atomic_type (int32_t*) #endif #elif windows #include <windows.h> #endif but hope compiling under linux work vst sdk 2.4. reading. jvstwrapper seems run on lin...
Read more

url - Querystring manipulation of email Address in PHP -

i using third party application (email2http) send me emailid, body , message. unable retrieve email id due name appended on , enclosed < , >. here querystring getting. test.php?from=ajay+reddy &subject=cx&body=somebody when print variable in php returns name , not email id. $from = $_get['from']; echo $from; //output ajay reddy please suggest me how can emailid also. i dont want use post method due testing , debugging. it's working fine. forgot use htmlentities() in debugging.
Read more