Overview     Modules     Class Hierarchy     Classes     Members  
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


Tulip Software by LaBRI Visualization Team    2001 - 2012