On 01/23/2011 03:34 AM, Kovács Péter wrote: > Hi Tim, > > Yes, I was wrong. I'm sorry. E.g. if the dependencies are A->B, B->C, > D->C, then D->C should not be removed. > > >> LEMON does not provide a direct algorithm for your problem, but it > >> provides tools that can be combined to solve it. > >> > >> As far as I understand, you would like to keep the longest paths of > >> the dependency graph, and remove all arcs that are not part of a > >> longest path. > > > > Not quite. If there are nodes in the shorter path that are not part > > of the longer paths, those arcs most be kept (to properly reflect the > > dependency on those other nodes). As near as I can tell, this only > > happens when there are longer paths between a node and a direct > > (distance=1) ancestor. The tricky part here is I want to keep the > > longer paths, not the shorter one. > > I mean, an arc should be kept if and only if there are nodes u and v, > for which a longest u->v path contains this arc. It seems to be correct, > but the proposed method is not sufficient for making this distinction > for all arcs. > >> The reason I think I need to remove this short path is because, if I >> don't, a BFS traversal will visit that node through the short path >> before the nodes along the longer path have been visited, which won't be >> right (need to visit a node only after all its ancestors have been >> visited). > > What about using a topological ordering instead of a BFS traversal? As > far as I see, it would solve your problem. Do you need this arc removal > procedure at all? Don't you need just a topological sort? > http://en.wikipedia.org/wiki/Topological_sorting >
Yes, I think that would do it, with no need for arc removal. I don't see any mention of that algorithm in Lemon, am I missing it, or is there just not one? Doesn't seem terribly difficult to implement, so that's not a show-stopper. - tim >> Thanks for your help. >> >> - tim > > Peter > >> >>> >>> In a directed acyclic graph (DAG), you can easily determine the distance >>> layers by using a topological ordering and a simple algorithm, which is >>> described here: >>> http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_acyclic_graphs >>> >>> >>> >>> I think, you would like to keep only those arcs, that connect nodes of >>> neighboring layers. >>> >>> Once you have assigned a layer number l(u) to each node u of the graph, >>> you can easily detect which arcs are superfluous. l(v)>=l(u)+1 holds for >>> each arc (u,v). If l(v)=l(u)+1, then this arc is necessary, and if >>> l(v)>l(u)+1, then this arc is superfluous, it can be safely removed. >>> The sample code of the wikipedia page computes l(u) for each node (it is >>> denoted by length_to[u]). >>> >>> LEMON provides functions for topological sort, so you only need to >>> implement the cited simple algorithm. The whole solution will be simple >>> and it will run in linear time. >>> >>> Please correct me if I overlook something. >>> >>> Best regards, >>> Peter >>> >>> >>>> Hi all, >>>> I have a ListDigraph that represents dependencies between nodes in the >>>> graph, for this example say 3 nodes, A, B, C, >>>> and 2 arcs, A-B and A-C. Now I'd like to add a dependency B-C; after >>>> doing that, B will have ancestors A and C, and >>>> there will be two paths between A and B. Since this is a dependency >>>> graph, there's no point in keeping the A-B arc, >>>> since B always has to wait for C anyway. Is there an algorithm or >>>> combination of them in Lemon that would remove these >>>> sorts of things automatically? I'm not formally trained in graph >>>> theory, but intuitively it seems like that could be >>>> phrased in terms of some of the path and flow algorithms. >>>> >>>> BTW, great package, I've started using it in a mesh generation library >>>> I'm developing (will send a link when it's ready >>>> for release). >>>> >>>> - tim >>>> >>> >> > -- ================================================================ "You will keep in perfect peace him whose mind is steadfast, because he trusts in you." Isaiah 26:3 Tim Tautges Argonne National Laboratory ([email protected]) (telecommuting from UW-Madison) phone: (608) 263-8485 1500 Engineering Dr. fax: (608) 263-4499 Madison, WI 53706 _______________________________________________ Lemon-user mailing list [email protected] http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
