GraphTools.h File Reference
#include <tulip/Node.h>
#include <tulip/Edge.h>
#include <set>
#include <list>
#include <tulip/PlanarConMap.h>
Include dependency graph for GraphTools.h:
This graph shows which files directly or indirectly include this file:
Namespaces
Functions
- TLP_SCOPE std::vector< std::vector<
node > > computeCanonicalOrdering (PlanarConMap *, std::vector< edge > *dummyEdges=0, PluginProgress *pluginProgress=0)
- TLP_SCOPE std::vector< node > computeGraphCenters (Graph *graph)
- TLP_SCOPE node graphCenterHeuristic (Graph *graph)
- TLP_SCOPE node makeSimpleSource (Graph *graph)
- TLP_SCOPE void makeProperDag (Graph *graph, std::list< node > &addedNodes, stdext::hash_map< edge, edge > &replacedEdges, IntegerProperty *edgeLength=0)
- TLP_SCOPE void selectSpanningForest (Graph *graph, BooleanProperty *selectionProperty, PluginProgress *pluginProgress=0)
- TLP_SCOPE void selectMinimumSpanningTree (Graph *graph, BooleanProperty *selectionProperty, DoubleProperty *weight=0, PluginProgress *pluginProgress=0)
- TLP_SCOPE Graph * computeTree (Graph *graph, Graph *rootGraph=0, bool isConnected=false, PluginProgress *pluginProgress=0)
- TLP_SCOPE void cleanComputedTree (Graph *graph, Graph *tree)
Function Documentation
TLP_SCOPE void tlp::cleanComputedTree |
( |
Graph * |
graph, |
|
|
Graph * |
tree |
|
) |
|
|
|
Clean the graph from a tree previously computed with the computTree function |
TLP_SCOPE std::vector<std::vector<node> > tlp::computeCanonicalOrdering |
( |
PlanarConMap * |
, |
|
|
std::vector< edge > * |
dummyEdges = 0 , |
|
|
PluginProgress * |
pluginProgress = 0 |
|
) |
|
|
|
This ordering was first introduced by C. Gutwenger and P. Mutzel in
"Grid embeddings of biconnected planar graphs",
"Extended Abstract, Max-Planck-Institut für Informatik,"
"Saarbrücken, Germany, 1997"
Let n be the number of nodes, the original algorithm complexity is in O(n).
But the implementation of the canonical ordering has not been made in O(n).
|
TLP_SCOPE std::vector<node> tlp::computeGraphCenters |
( |
Graph * |
graph |
) |
|
|
|
Find all the graph centers, that version does not manage edge weight. complexity O(n * m). Only works on connected graphs. |
TLP_SCOPE Graph* tlp::computeTree |
( |
Graph * |
graph, |
|
|
Graph * |
rootGraph = 0 , |
|
|
bool |
isConnected = false , |
|
|
PluginProgress * |
pluginProgress = 0 |
|
) |
|
|
|
Compute a directed tree from the graph. The algorithm is the following
- if the graph is a directed tree, return the graph
- if the graph is a free tree, return a directed copy
- if the graph is connected, make a copy return a directed spanning tree of that copy
- if the graph is not connected, make a copy, compute a tree for each of its connected components, add a simple source and return the copy.
|
TLP_SCOPE node tlp::graphCenterHeuristic |
( |
Graph * |
graph |
) |
|
|
|
return a node that can be considered as the graph center. It is an heuristic, thus it is not absolutely sure that this node is a graph center. Only works on connected graphs. |
TLP_SCOPE void tlp::makeProperDag |
( |
Graph * |
graph, |
|
|
std::list< node > & |
addedNodes, |
|
|
stdext::hash_map< edge, edge > & |
replacedEdges, |
|
|
IntegerProperty * |
edgeLength = 0 |
|
) |
|
|
TLP_SCOPE node tlp::makeSimpleSource |
( |
Graph * |
graph |
) |
|
|
|
return a new node connected to all previously existing nodes which had a null indegree |
TLP_SCOPE void tlp::selectMinimumSpanningTree |
( |
Graph * |
graph, |
|
|
BooleanProperty * |
selectionProperty, |
|
|
DoubleProperty * |
weight = 0 , |
|
|
PluginProgress * |
pluginProgress = 0 |
|
) |
|
|
|
Select the minimum spanning tree (Kruskal algorithm) of a weighted graph, i.e for all graph elements (nodes or edges) belonging to that tree the selectionProperty associated value is true. The value is false for the other elements |
TLP_SCOPE void tlp::selectSpanningForest |
( |
Graph * |
graph, |
|
|
BooleanProperty * |
selectionProperty, |
|
|
PluginProgress * |
pluginProgress = 0 |
|
) |
|
|
|
Select a spanning forest of the graph, i.e for all graph elements (nodes or edges) belonging to that forest the selectionProperty associated value is true. The value is false for the other elements |
|