Tulip  4.0.0
Better Visualization Through Research
 All Classes Files Functions Variables Enumerations Enumerator Properties Groups Pages
GraphTools.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef _TLPGRAPHTOOLS_H
22 #define _TLPGRAPHTOOLS_H
23 
24 #include <set>
25 #include <list>
26 #include <tulip/tuliphash.h>
27 #include <tulip/Node.h>
28 #include <tulip/Edge.h>
29 
30 #include <tulip/PlanarConMap.h>
31 
32 namespace tlp {
33 
34 class BooleanProperty;
35 class DoubleProperty;
36 class IntegerProperty;
37 
38 
39 /**
40  * This ordering was first introduced by C. Gutwenger and P. Mutzel in \n
41  * "Grid embeddings of biconnected planar graphs", \n
42  * "Extended Abstract, Max-Planck-Institut für Informatik," \n
43  * "Saarbrücken, Germany, 1997" \n
44  * Let n be the number of nodes, the original algorithm complexity is in O(n).\n
45  * But the implementation of the canonical ordering has not been made in O(n).\n
46  */
47 TLP_SCOPE std::vector<std::vector<node> > computeCanonicalOrdering(PlanarConMap *,
48  std::vector<edge> *dummyEdges = NULL,
49  PluginProgress *pluginProgress = NULL);
50 /**
51  * Find all the graph centers, that version does not manage edge weight.
52  * complexity O(n * m). Only works on connected graphs.
53  */
54 TLP_SCOPE std::vector<node> computeGraphCenters(Graph * graph);
55 /**
56  * return a node that can be considered as the graph center.
57  * It is an heuristic, thus it is not absolutely sure that this
58  * node is a graph center. Only works on connected graphs.
59  */
60 TLP_SCOPE node graphCenterHeuristic(Graph * graph,
61  PluginProgress *pluginProgress = NULL);
62 /**
63  * return a new node connected to all previously
64  * existing nodes which had a null indegree
65  */
66 TLP_SCOPE node makeSimpleSource(Graph* graph);
67 
68 TLP_SCOPE void makeProperDag(Graph* graph,std::list<node> &addedNodes,
69  TLP_HASH_MAP<edge,edge> &replacedEdges,
70  IntegerProperty* edgeLength = NULL);
71 
72 /**
73  * Select a spanning forest of the graph,
74  * i.e for all graph elements (nodes or edges) belonging to that forest
75  * the selectionProperty associated value is true. The value is false
76  * for the other elements
77  */
78 TLP_SCOPE void selectSpanningForest(Graph* graph, BooleanProperty *selectionProperty,
79  PluginProgress *pluginProgress = NULL);
80 
81 /**
82  * Select a spanning tree of a graph assuming it is connected;
83  * i.e for all graph elements (nodes or edges) belonging to that tree
84  * the selectionProperty associated value is true. The value is false
85  * for the other elements
86  */
87 TLP_SCOPE void selectSpanningTree(Graph* graph, BooleanProperty *selection,
88  PluginProgress *pluginProgress = NULL);
89 
90 /**
91  * Select the minimum spanning tree (Kruskal algorithm) of a weighted graph,
92  * i.e for all graph elements (nodes or edges) belonging to that tree
93  * the selectionProperty associated value is true. The value is false
94  * for the other elements
95  */
96 TLP_SCOPE void selectMinimumSpanningTree(Graph* graph, BooleanProperty *selectionProperty,
97  DoubleProperty *weight = NULL,
98  PluginProgress *pluginProgress = NULL);
99 
100 }
101 #endif
102 ///@endcond