Tulip  5.7.4
Large graphs analysis and drawing
tlp::ConnectedTest Class Reference

#include <ConnectedTest.h>

Static Public Member Functions

static void computeConnectedComponents (const Graph *graph, std::vector< std::vector< node >> &components)
 
static bool isConnected (const Graph *const graph)
 
static void makeConnected (Graph *graph, std::vector< edge > &addedEdges)
 
static unsigned int numberOfConnectedComponents (const Graph *const graph)
 

Detailed Description

Performs a test of connexity on the graph, and provides a function to make a graph connected. From Wikipedia: "A graph is said to be connected if every pair of vertices in the graph are connected." (i.e. there is a path between every pair of vertices).

Definition at line 40 of file ConnectedTest.h.

Member Function Documentation

◆ computeConnectedComponents()

static void tlp::ConnectedTest::computeConnectedComponents ( const Graph graph,
std::vector< std::vector< node >> &  components 
)
static

Computes the sets of connected components and stores the result in the components vector.

Parameters
graphThe graph on which to compute connected components.
componentsThe components that were found. It is passed as a reference to avoid copying the data when returning.
Returns
void
Note
The components parameter can be returned with c++11 thanks to move constructors without performance loss, change this function once c++11 compilers are used.

◆ isConnected()

static bool tlp::ConnectedTest::isConnected ( const Graph *const  graph)
static

Checks if a graph is connected (i.e. there is a path between every pair of vertices).

Parameters
graphThe graph to check.
Returns
bool True if the graph is connected, false otherwise.

◆ makeConnected()

static void tlp::ConnectedTest::makeConnected ( Graph graph,
std::vector< edge > &  addedEdges 
)
static

If the graph is not connected, adds edges to make it connected.

Parameters
graphThe graph to make connected.
addedEdgesThe edges that were added to make it connected.
Returns
void

◆ numberOfConnectedComponents()

static unsigned int tlp::ConnectedTest::numberOfConnectedComponents ( const Graph *const  graph)
static

Gets the number of connected components in the graph.

Parameters
graphThe graph in which to count the number of connected components.
Returns
unsigned int The number of connected componments.