Re: [Boost-users] BGL connected_components for directed graphs

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-03-02 15:53:40

On Feb 28, 2006, at 4:28 AM, Gavin Band wrote:

> Dear boosters,
> I am trying to compile a program which is identical to the example
>
> http://www.boost.org/libs/graph/example/connected_components.cpp
>
> given in the docs, except that in the graph typedef I changed
> undirectedS to directedS.  However, I get a compilation error:
>
> g++ -o test_c++.o -I/usr/include/boost -c test_c++.cpp
> /usr/include/boost/graph/connected_components.hpp: In function 
> `typename
> boost::property_traits<IndexMap>::value_type
> boost::connected_components(const Graph&, ComponentMap) [with Graph =
> main(int, char**)::Graph, ComponentMap = int*]':
> test_c++.cpp:45:   instantiated from here
> /usr/include/boost/graph/connected_components.hpp:87: error: incomplete
> type `boost::STATIC_ASSERTION_FAILURE< false>' used in nested name
> specifier
> /usr/include/boost/graph/connected_components.hpp:87: error: size of
> array has non-integral type `<type error>'
>
> Presumably this is some meta-program's way of telling me that my graph
> isn't undirected.

Yes, that's what it's doing. connected_components() only works on 
undirected graphs.

>   Is there any way to make this work for an directed
> graph?

You can use the facilities for incremental connected components. Those 
will work on an undirected graph.
In truth, our connected_components() should be modified to decide 
between the DFS-based algorithm for undirected graphs and the 
incremental algorithm for directed graphs.

        Doug