tlp::BiconnectedTest Class Reference

#include <BiconnectedTest.h>

Inheritance diagram for tlp::BiconnectedTest:

Collaboration diagram for tlp::BiconnectedTest:

Static Public Member Functions
static bool	isBiconnected (const Graph *graph)
static void	makeBiconnected (Graph *graph, std::vector< edge > &addedEdges)

Detailed Description

Performs a test of biconnexity on the graph, and provides a function to make a graph biconnected. From Wikipedia: "A biconnected graph is connected and nonseparable, meaning that if any vertex were to be removed, the graph will remain connected.".

Definition at line 34 of file BiconnectedTest.h.

Member Function Documentation

static bool tlp::BiconnectedTest::isBiconnected ( const Graph *  graph )

static

Checks whether the graph is biconnected (i.e. removing one edge does not disconnect the graph, at least two must be removed).

Parameters

graph

The graph to check for biconnectivity.

Returns

bool True if the graph is biconnected, false otherwise.

static void tlp::BiconnectedTest::makeBiconnected ( Graph *  graph, std::vector< edge > &  addedEdges  )

static

Adds edges to make the graph biconnected.

If the graph is not biconnected, adds edges in order to make the graph biconnected. The new edges are added in addedEdges.

Parameters

graph	The graph to make biconnected.
addedEdges	The edges that were added in the process.

Returns

void