Detecting cycles in graph
Hi, I want to use the BFS to detect cycles in a graph I constructed using bundled vertex properties. I want a feature that as soon as I detect a cycle, I can do some processing on the cycle path and then go back to look for other cycles in the main graph. I am really confused with the documentation regarding BFSvisitor concepts. I would really appreciate some help regarding how to proceed with this. Thanks, Abde Ali
Abde Ali Kagalwalla wrote:
Hi,
I want to use the BFS to detect cycles in a graph I constructed using bundled vertex properties. I want a feature that as soon as I detect a cycle, I can do some processing on the cycle path and then go back to look for other cycles in the main graph.
So, you want to do something for each cycle in the graph? Not for each strongly connected component? There are algorithms for enumerate all cycles in a graph, but those algorithms are not included in BGL, and a far from easy. What are you trying to do, exactly? - Volodya
Vladimir Prus wrote:
Abde Ali Kagalwalla wrote:
Hi,
I want to use the BFS to detect cycles in a graph I constructed using bundled vertex properties. I want a feature that as soon as I detect a cycle, I can do some processing on the cycle path and then go back to look for other cycles in the main graph.
So, you want to do something for each cycle in the graph? Not for each strongly connected component? There are algorithms for enumerate all cycles in a graph, but those algorithms are not included in BGL, and a far from easy.
Maybe I'm missing something, but isn't this as easy as hooking back_edge on a DFSVisitor and using depth_first_search? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
Vladimir Prus wrote:
Abde Ali Kagalwalla wrote:
Hi,
I want to use the BFS to detect cycles in a graph I constructed using bundled vertex properties. I want a feature that as soon as I detect a cycle, I can do some processing on the cycle path and then go back to look for other cycles in the main graph. So, you want to do something for each cycle in the graph? Not for each strongly connected component? There are algorithms for enumerate all cycles in a graph, but those algorithms are not included in BGL, and a far from easy.
Maybe I'm missing something, but isn't this as easy as hooking back_edge on a DFSVisitor and using depth_first_search?
Yep, looks very simple, taking into account the complexity of DFS is linear in the respect of the edges number while the number of simple cycles in a digraph potentially can be exponential large. Ali, please describe your original problem. The tedious cycles enumeration often can be avoided :-) Dmitry
Hi,
So, basically I want to find the number of cycles in an undirected graph.
Now the vertices of the
graph are colored red or green. As soon as I locate a cycle, I want to count
the number of red and black vertices in the cycle.
I want to find all possible cycles and the number of red and black vertices
for each cycle.
I was thinking of using BFS but it is ok if I can find the solution using
DFS or some other method.
Thanks,
Abde Ali
On Fri, Jun 27, 2008 at 2:32 PM, Dmitry Bufistov
David Abrahams wrote:
Vladimir Prus wrote:
Abde Ali Kagalwalla wrote:
Hi,
I want to use the BFS to detect cycles in a graph I constructed using bundled vertex properties. I want a feature that as soon as I detect a cycle, I can do some processing on the cycle path and then go back to look for other cycles in the main graph.
So, you want to do something for each cycle in the graph? Not for each strongly connected component? There are algorithms for enumerate all cycles in a graph, but those algorithms are not included in BGL, and a far from easy.
Maybe I'm missing something, but isn't this as easy as hooking back_edge on a DFSVisitor and using depth_first_search?
Yep, looks very simple, taking into account the complexity of DFS is linear in the respect of the edges number while the number of simple cycles in a digraph potentially can be exponential large.
Ali, please describe your original problem. The tedious cycles enumeration often can be avoided :-)
Dmitry
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
I don't know how to help ( Dmitry Abde Ali Kagalwalla wrote:
Hi,
So, basically I want to find the number of cycles in an undirected graph. Now the vertices of the graph are colored red or green. As soon as I locate a cycle, I want to count the number of red and black vertices in the cycle. I want to find all possible cycles and the number of red and black vertices for each cycle.
I was thinking of using BFS but it is ok if I can find the solution using DFS or some other method.
Thanks,
Abde Ali
David Abrahams wrote:
Vladimir Prus wrote:
Abde Ali Kagalwalla wrote:
Hi,
I want to use the BFS to detect cycles in a graph I constructed using bundled vertex properties. I want a feature that as soon as I detect a cycle, I can do some processing on the cycle path and then go back to look for other cycles in the main graph.
So, you want to do something for each cycle in the graph? Not for each strongly connected component? There are algorithms for enumerate all cycles in a graph, but those algorithms are not included in BGL, and a far from easy.
Maybe I'm missing something, but isn't this as easy as hooking back_edge on a DFSVisitor and using depth_first_search?
This will allow you to identify back edges -- that is edges that are surely part of some cycle. Given that a given edge can be a part of 2^|V| cycles, knowing that a given edge is a back edge is clearly not a solution for "enumerate all cycles" problem. A brute-force algorithm is not hard to write, but the point of algorithm running in exponential time and requiring exponential memory is questionable. So, there exist algorithms that allow to iterate over all cycles, where the complexity of getting the next cycle is linear-or-something. I'd suggest to take a look of them before trying to write your own algorithm :-). - Volodya
participants (4)
-
Abde Ali Kagalwalla -
David Abrahams -
Dmitry Bufistov -
Vladimir Prus