[BGL] question about connected_components()
This page: http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/connected_components.htm... says "The connected_components() functions compute the connected components of an _undirected_ graph using a DFS-based approach." [emphasis mine] Looking here: http://www.boost.org/doc/libs/1_48_0/boost/graph/connected_components.hpp I see somewhat some unexpected things. o Only the first variant asserts that the graph is undirected, in the second variant the assert is commented out - why is that? o Both variants use depth_first_search() and not undirected_dfs(), which would seem to be more logical for the undirected case - why? Despite the above questions I actually want to use connected_components() [and not strong_components()] for a directed graph. Should that be possible? Does it make sense? Thank you! -- Andriy Gapon
On Thu, 19 Jan 2012, Andriy Gapon wrote:
This page: http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/connected_components.htm... says "The connected_components() functions compute the connected components of an _undirected_ graph using a DFS-based approach." [emphasis mine]
Looking here: http://www.boost.org/doc/libs/1_48_0/boost/graph/connected_components.hpp I see somewhat some unexpected things.
o Only the first variant asserts that the graph is undirected, in the second variant the assert is commented out - why is that?
I don't know for sure, but the likely reason is to allow the use of a directed graph that has each edge inserted in both directions.
o Both variants use depth_first_search() and not undirected_dfs(), which would seem to be more logical for the undirected case - why?
I don't know.
Despite the above questions I actually want to use connected_components() [and not strong_components()] for a directed graph. Should that be possible? Does it make sense?
Do you want to compute the weak components of the graph? I.e., do you want the connected components that would be present if you ignored edge directions? -- Jeremiah Willcock
on 23/01/2012 21:56 Jeremiah Willcock said the following:
On Thu, 19 Jan 2012, Andriy Gapon wrote:
This page: http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/connected_components.htm... says "The connected_components() functions compute the connected components of an _undirected_ graph using a DFS-based approach." [emphasis mine]
Looking here: http://www.boost.org/doc/libs/1_48_0/boost/graph/connected_components.hpp I see somewhat some unexpected things.
o Only the first variant asserts that the graph is undirected, in the second variant the assert is commented out - why is that?
I don't know for sure, but the likely reason is to allow the use of a directed graph that has each edge inserted in both directions.
Right. But then, IMO, either both functions should support that or neither.
o Both variants use depth_first_search() and not undirected_dfs(), which would seem to be more logical for the undirected case - why?
I don't know.
Fair enough.
Despite the above questions I actually want to use connected_components() [and not strong_components()] for a directed graph. Should that be possible? Does it make sense?
Do you want to compute the weak components of the graph? I.e., do you want the connected components that would be present if you ignored edge directions?
Yes, exactly! Thank you for your interest. -- Andriy Gapon
On Mon, 23 Jan 2012, Andriy Gapon wrote:
on 23/01/2012 21:56 Jeremiah Willcock said the following:
On Thu, 19 Jan 2012, Andriy Gapon wrote:
This page: http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/connected_components.htm... says "The connected_components() functions compute the connected components of an _undirected_ graph using a DFS-based approach." [emphasis mine]
Looking here: http://www.boost.org/doc/libs/1_48_0/boost/graph/connected_components.hpp I see somewhat some unexpected things.
o Only the first variant asserts that the graph is undirected, in the second variant the assert is commented out - why is that?
I don't know for sure, but the likely reason is to allow the use of a directed graph that has each edge inserted in both directions.
Right. But then, IMO, either both functions should support that or neither.
Yes, they probably should be the same.
o Both variants use depth_first_search() and not undirected_dfs(), which would seem to be more logical for the undirected case - why?
I don't know.
Fair enough.
Despite the above questions I actually want to use connected_components() [and not strong_components()] for a directed graph. Should that be possible? Does it make sense?
Do you want to compute the weak components of the graph? I.e., do you want the connected components that would be present if you ignored edge directions?
Yes, exactly!
In order to do that, the easiest way is to create a new undirected graph from your original graph, adding each directed edge as an undirected edge in the new graph. If you have very large graphs, there are (more complicated) ways to do that without extra memory utilization, but this approach involves the least effort and works unless your graphs are very large or you are doing this operation many times. -- Jeremiah Willcock
on 24/01/2012 23:03 Jeremiah Willcock said the following:
In order to do that, the easiest way is to create a new undirected graph from your original graph, adding each directed edge as an undirected edge in the new graph. If you have very large graphs, there are (more complicated) ways to do that without extra memory utilization, but this approach involves the least effort and works unless your graphs are very large or you are doing this operation many times.
My graph is actually a quite large (directed) adjacency_matrix. Actually, I need to run connected_components() on a filtered_graph of the said graph (based on edge weight). So I think that I found a way to achieve what I wanted, but I would like to double-check my approach with you. I arranged my filter to be such that each edge of the filtered graph has an opposite edge - for each (u, v) there is a (v, u). And then I use exactly the same approach as boost::connected_components(), but without any limitations on a directionality of a graph. That is, I also use depth_first_search(). I think that since depth_first_search() colors only the vertices, then it should work on my graph in the same way as it would work on an undirected graph. And thus it should find the weekly connected components that I want. What do you think? P.S. It seems that the connected_components documentation mentions only the first version of the connected_components function. -- Andriy Gapon
On Wed, 25 Jan 2012, Andriy Gapon wrote:
on 24/01/2012 23:03 Jeremiah Willcock said the following:
In order to do that, the easiest way is to create a new undirected graph from your original graph, adding each directed edge as an undirected edge in the new graph. If you have very large graphs, there are (more complicated) ways to do that without extra memory utilization, but this approach involves the least effort and works unless your graphs are very large or you are doing this operation many times.
My graph is actually a quite large (directed) adjacency_matrix. Actually, I need to run connected_components() on a filtered_graph of the said graph (based on edge weight). So I think that I found a way to achieve what I wanted, but I would like to double-check my approach with you.
I arranged my filter to be such that each edge of the filtered graph has an opposite edge - for each (u, v) there is a (v, u). And then I use exactly the same approach as boost::connected_components(), but without any limitations on a directionality of a graph.
If you have both directions of each edge, the normal connected_components code (possibly with the directionality check commented out) should work just fine.
That is, I also use depth_first_search(). I think that since depth_first_search() colors only the vertices, then it should work on my graph in the same way as it would work on an undirected graph.
Yes, I think so.
And thus it should find the weekly connected components that I want. What do you think?
That's the way I would recommend doing it.
P.S. It seems that the connected_components documentation mentions only the first version of the connected_components function.
Having two versions is an implementation detail; the second one implements the "= all defaults" part of the signature given in the documentation. -- Jeremiah Willcock
on 25/01/2012 23:27 Jeremiah Willcock said the following:
On Wed, 25 Jan 2012, Andriy Gapon wrote:
on 24/01/2012 23:03 Jeremiah Willcock said the following:
In order to do that, the easiest way is to create a new undirected graph from your original graph, adding each directed edge as an undirected edge in the new graph. If you have very large graphs, there are (more complicated) ways to do that without extra memory utilization, but this approach involves the least effort and works unless your graphs are very large or you are doing this operation many times.
My graph is actually a quite large (directed) adjacency_matrix. Actually, I need to run connected_components() on a filtered_graph of the said graph (based on edge weight). So I think that I found a way to achieve what I wanted, but I would like to double-check my approach with you.
I arranged my filter to be such that each edge of the filtered graph has an opposite edge - for each (u, v) there is a (v, u). And then I use exactly the same approach as boost::connected_components(), but without any limitations on a directionality of a graph.
If you have both directions of each edge, the normal connected_components code (possibly with the directionality check commented out) should work just fine.
That is, I also use depth_first_search(). I think that since depth_first_search() colors only the vertices, then it should work on my graph in the same way as it would work on an undirected graph.
Yes, I think so.
And thus it should find the weekly connected components that I want. What do you think?
That's the way I would recommend doing it.
Thank you!
P.S. It seems that the connected_components documentation mentions only the first version of the connected_components function.
Having two versions is an implementation detail; the second one implements the "= all defaults" part of the signature given in the documentation.
Oh, I see, thank you again. -- Andriy Gapon
participants (2)
-
Andriy Gapon -
Jeremiah Willcock