wiki:soc/2007/UserFriendlyGraphs/Connectivity

Version 1 (modified by Andrew Sutton, 15 years ago) ( diff )

--

Connectivity Measures

These algorithms are used to query a graph for information about its "level" of connectivity. For example, it might be worthwhile to know if a graph is fully connected, how many connected components a graph contains, the size of each component, and even views of the components themselves. Interestingly, I managed to propose this without reading the connected_components() description too closely - apparently, it returns the number of components in the graph, which answers two of the proposed measures. Specifically, it answers a) the number of components in the graph and b) whether or not the graph is fully connected (it is if the return value equals 1). Oops.

On the other hand, we can still extend this algorithm to "auto-sort" the vertices into a container that gives the vertices in each container. This might be used as a basis for other algorithms requiring connected subrgraphs.

Also, I've been trying to use the new Boost.Parameter library, with some success. So far, I've built a new connected_components_2() function that forwards to the older implmentation, and will also perform auto-sorting if a collection parameter is given.

Note: See TracWiki for help on using the wiki.