[Boost-users] Query re connected components in the Boost Graph Library

Subject: [Boost-users] Query re connected components in the Boost Graph Library
From: Christopher Henrich (chenrich_at_[hidden])
Date: 2010-01-27 12:54:58

The connected_components function in the BGL returns the connected  
component information in a "ComponentMap," in which the value for node  
i is the number c[i] of the component containing that node.

Is the sequence of component numbers "restricted growth" ? That is,  
can I assume that c[0] = 0 and for i > 0,  c[i] <= 1 + max(c[0], ...,  
c[i-1])? It would appear that this would be true, as a consequence of  
the easiest way to use depth-first search to find the components. And  
a brief attempt to read the source code encourages me to believe it.

But I may not have understood the source code. And I do not find it  
stated in the boost documentation, nor in /The Boost Graph Library/.

Thanks in advance for clarification on this point.
Christopher Henrich
chenrich_at_[hidden]
mathinteract.com