Overview     Modules     Class Hierarchy     Classes     Members  

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

  • namespace tlp

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



Tulip Software by LaBRI Visualization Team    2001 - 2007