Tulip  4.2.0
Better Visualization Through Research
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Groups Pages
GraphMeasure.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 _TLPGRAPHMEASEURE_H
22 #define _TLPGRAPHMEASEURE_H
23 
24 #include <tulip/Node.h>
25 #include <tulip/MutableContainer.h>
26 #include <tulip/DoubleProperty.h>
27 
28 namespace tlp {
29 
30 class Graph;
31 class PluginProgress;
32 enum EDGE_TYPE {DIRECTED = 0, INV_DIRECTED = 1, UNDIRECTED = 2};
33 /**
34  * returns the average path lengh of a graph, that is the sum
35  * of the shortest distances for all pair of distinct nodes in that graph
36  * divided by the number of those pairs. For a pair of non connected nodes,
37  * the shorted distance is set to 0.
38  * see http://en.wikipedia.org/wiki/Average_path_length for more details
39  */
40 TLP_SCOPE double averagePathLength(const Graph* g, PluginProgress* = NULL);
41 // obsolete version for compatibility purpose
42 inline bool averagePathLength(Graph *g, double& result, PluginProgress *pp = NULL) {
43  result = averagePathLength(g, pp);
44  return true;
45 }
46 /*
47  * returns the clustering coefficient of a graph
48  * as the average of the local clustering coefficients
49  * (see clusteringCoefficient function) of all the nodes.
50  * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details.
51  */
52 TLP_SCOPE double averageClusteringCoefficient(const Graph *, PluginProgress * = NULL);
53 // obsolete version for compatibility purpose
54 inline bool averageCluster(Graph* g, double& result, PluginProgress* pp = NULL) {
55  result = averageClusteringCoefficient(g, pp);
56  return true;
57 }
58 /*
59  * assigns to each node its local clustering coefficient
60  * that is the proportion of edges between the nodes within its neighbourhood
61  * divided by the number of edges that could possibly exist between them.
62  * This quantifies how close its neighbors are to being a clique.
63  * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details
64  */
65 TLP_SCOPE void clusteringCoefficient(const Graph *g, MutableContainer<double> &result, unsigned int maxDepth = 1, PluginProgress* = NULL);
66 /*
67  * assigns to each node of a Directed Acyclic Graph a level such that
68  * if the edge e(u,v) exists level(u) < level(v) the algorithm ensure that
69  * the number of level used is minimal.
70  *
71  * Warning : the graph must be acyclic (no self loops).
72  */
73 TLP_SCOPE void dagLevel(const Graph *graph, MutableContainer<unsigned int> &level, PluginProgress* = NULL);
74 // returns the maximum value of the degree of the graph's nodes
75 TLP_SCOPE unsigned int maxDegree(const Graph *);
76 
77 // returns the minimum value of the degree of the graph's nodes
78 TLP_SCOPE unsigned int minDegree(const Graph *);
79 /*
80  * computes the shortest distance from n to all the other nodes of graph
81  * and store it into distance, (stored value is UINT_MAX for non connected nodes),
82  * if direction is set to 2 use undirected graph, 0 use directed graph
83  * and 1 use reverse directed graph (ie. all edges are reversed)
84  * all the edge's weight is set to 1. (it uses a bfs thus the complexity is o(m), m = |E|).
85  */
86 TLP_SCOPE unsigned int maxDistance(const Graph *graph, const node n, MutableContainer<unsigned int> &distance, EDGE_TYPE direction = UNDIRECTED);
87 /*
88  * adds to a result set, all the nodes, according to direction,
89  * at distance less or equal to maxDistance of startNode
90  */
91 TLP_SCOPE void reachableNodes(const Graph *graph, const node startNode, std::set<node> &result, unsigned int maxDistance, EDGE_TYPE direction = UNDIRECTED);
92 }
93 #endif
94 ///@endcond