On Apr 10, 2006, at 11:16 AM, Alejandro Aragón wrote:
Hello everybody,
I was wondering if anybody had to implement the SNDP problem using graphs. Is there anything in the boost library that deals with this problem? In the SNDP we have to design a graph having certain degree of redundancy (cycles in the graph) so if you remove one edge, then you can still reach every part in the graph. Stated in a different way, you should be able to have different paths between two vertices in the graph. So far I have seen only algorithms to deal with minimum spanning trees. I appreciate anything related to this problem.
This sounds like it is closely related to the problem of finding biconnected components and articulation points. If a graph has no articulation points, then it will remain connected even if a vertex is destroyed. The BGL has biconnected components and articulation points algorithms already. Doug