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
	tlp::SelfLoops::SelfLoops (node n1, node n2, edge e1, edge e2, edge e3, edge old)
static bool	tlp::AcyclicTest::isAcyclic (const Graph *graph)
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 bool	tlp::BiconnectedTest::isBiconnected (Graph *graph)
static void	tlp::BiconnectedTest::makeBiconnected (Graph *graph, std::vector< edge > &addedEdges)
static bool	tlp::ConnectedTest::isConnected (const Graph *const graph)
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
node	tlp::SelfLoops::n1
node	tlp::SelfLoops::n2
edge	tlp::SelfLoops::e1
edge	tlp::SelfLoops::e2
edge	tlp::SelfLoops::e3
edge	tlp::SelfLoops::old

Detailed Description

Function Documentation

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

static

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

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

static bool tlp::AcyclicTest::isAcyclic ( const Graph *  graph )

static

Returns true if the graph is acyclic, false otherwise. The result is cached (ie. the next call with the same graph is done in O(1) time)

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

static

Returns true if the graph is biconnected (ie. one must remove at least two nodes in order to disconnect the graph), false otherwise.

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

static

Returns true if the graph is connected (ie. it exists an undirected path between each pair of nodes), false otherwise.

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

static

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

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

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

Returns the number of connected components in the graph.

tlp::SelfLoops::SelfLoops ( node  n1, node  n2, edge  e1, edge  e2, edge  e3, edge  old  )

inline

Variable Documentation

edge tlp::SelfLoops::e1

edge tlp::SelfLoops::e2

edge tlp::SelfLoops::e3

node tlp::SelfLoops::n1

node tlp::SelfLoops::n2

edge tlp::SelfLoops::old