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) |
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.
Variable Documentation
|