Hi all, finding edges of cycles in a directed graph is a solved problem and done by the strong_components algorithm. Is there also any a good solution for finding the path (= the exact sequence of vertices) that encloses a strong component? (Note that in a strong component there can be also smaller subcycles that are not of interest.) With other words: I want to find the way through a strong component that visits all its edges. Thanks in advance! Stefan
Enlosing in what sense? Ary you thinking spatially? Perhaps you want an algorithm from computational geometry, like convex hull. Cheers, Jeremy On Wed, 13 Aug 2003, Stefan Slapeta wrote: yg-boo> Hi all, yg-boo> yg-boo> finding edges of cycles in a directed graph is a solved problem and done by yg-boo> the strong_components algorithm. yg-boo> yg-boo> Is there also any a good solution for finding the path (= the exact sequence yg-boo> of vertices) that encloses a strong component? (Note that in a strong yg-boo> component there can be also smaller subcycles that are not of interest.) yg-boo> With other words: I want to find the way through a strong component that yg-boo> visits all its edges. yg-boo> yg-boo> Thanks in advance! yg-boo> yg-boo> Stefan ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
On Thu, 2003-08-14 at 21:48, Jeremy Siek wrote:
Enlosing in what sense? Ary you thinking spatially? Perhaps you want an algorithm from computational geometry, like convex hull.
On Wed, 13 Aug 2003, Stefan Slapeta wrote: yg-boo> Hi all, yg-boo> yg-boo> finding edges of cycles in a directed graph is a solved problem and done by yg-boo> the strong_components algorithm. yg-boo> yg-boo> Is there also any a good solution for finding the path (= the exact sequence yg-boo> of vertices) that encloses a strong component? (Note that in a strong yg-boo> component there can be also smaller subcycles that are not of interest.) yg-boo> With other words: I want to find the way through a strong component that yg-boo> visits all its edges. yg-boo>
A strong component is a graph on it's own, so if you need to visit all the edges of a strong component, why not just use a simple DFS/BFS? Like Jeremy I don't quite understand what you're going for, try to describe the problem you are looking to solve a bit more precisely. Regards, -- Tarjei
participants (3)
-
Jeremy Siek -
Stefan Slapeta -
Tarjei Knapstad