Graph_test

Classes

class tlp::AcyclicTest
Class for testing if the graph is acyclic. More...
class tlp::BiconnectedTest
class for testing if the graph is biconnected More...
class tlp::ConnectedTest
class for testing if the graph is connected More...
class tlp::OuterPlanarTest
class for testing the outerplanarity of a graph More...
class tlp::PlanarityTest
class for testing the planarity of a graph More...
class tlp::SimpleTest
class tlp::TreeTest
Class for testing if the graph is a tree. More...
class tlp::TriconnectedTest
class for testing if a graph is triconnected More...

Functions

static void tlp::AcyclicTest::makeAcyclic (Graph *graph, std::vector< edge > &reversed, std::vector< tlp::SelfLoops > &selfLoops)
static bool tlp::AcyclicTest::acyclicTest (const Graph *, std::vector< edge > *obstructionEdges=0)
static void tlp::BiconnectedTest::makeBiconnected (Graph *graph, std::vector< edge > &addedEdges)
static void tlp::ConnectedTest::makeConnected (Graph *graph, std::vector< edge > &addedEdges)
static unsigned int tlp::ConnectedTest::numberOfConnectedComponents (const Graph *const graph)
static void tlp::ConnectedTest::computeConnectedComponents (Graph *graph, std::vector< std::set< node > > &components)

Variables

Detailed Description

Function Documentation

static bool tlp::AcyclicTest::acyclicTest	(	const Graph *	,
		std::vector< edge > *	obstructionEdges = `0`
	)			`[static, inherited]`

Returns true if the graph is acyclic, false otherwise. If the graph is not acyclic, uses obstructionEdges variable to store all edges that create cycle.

static void tlp::ConnectedTest::computeConnectedComponents	(	Graph *	graph,
		std::vector< std::set< node > > &	components
	)			`[static, inherited]`

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

static void tlp::AcyclicTest::makeAcyclic	(	Graph *	graph,
		std::vector< edge > &	reversed,
		std::vector< tlp::SelfLoops > &	selfLoops
	)			`[static, inherited]`

Makes the graph acyclic, by reversing edge direction (feedback arc set problem). If there is self loops, a new node is added with two edges that points to it.

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

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

static void tlp::ConnectedTest::makeConnected	(	Graph *	graph,
		std::vector< edge > &	addedEdges
	)			`[static, inherited]`

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

static unsigned int tlp::ConnectedTest::numberOfConnectedComponents ( const Graph *const graph ) [static, inherited]

Returns the number of connected components in the graph.

Variable Documentation

edge tlp::SelfLoops::e1 [inherited]

edge tlp::SelfLoops::e2 [inherited]

edge tlp::SelfLoops::e3 [inherited]

node tlp::SelfLoops::n1 [inherited]

node tlp::SelfLoops::n2 [inherited]

edge tlp::SelfLoops::old [inherited]