Tulip  5.7.4
Large graphs analysis and drawing
GraphMeasure.h
1 /*
2  *
3  * This file is part of Tulip (https://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
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/StaticProperty.h>
26 #include <tulip/GraphTools.h>
27 
28 namespace tlp {
29 
30 class Graph;
31 class PluginProgress;
32 /**
33  * returns the average path length of a graph, that is the sum
34  * of the shortest distances for all pair of distinct nodes in that graph
35  * divided by the number of those pairs. For a pair of non connected nodes,
36  * the shorted distance is set to 0.
37  * see http://en.wikipedia.org/wiki/Average_path_length for more details
38  */
39 TLP_SCOPE double averagePathLength(const Graph *g);
40 /*
41  * return the clustering coefficient of a graph
42  * as the average of the local clustering coefficients
43  * (see clusteringCoefficient function) of all the nodes.
44  * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details.
45  */
46 TLP_SCOPE double averageClusteringCoefficient(const Graph *);
47 /*
48  * assign to each node its local clustering coefficient
49  * that is the proportion of edges between the nodes within its neighbourhood
50  * divided by the number of edges that could possibly exist between them.
51  * This quantifies how close the node and its neighbors are close to a clique.
52  * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details or
53  * the paper: D. J. Watts and S. H. Strogatz.
54  * Collective dynamics of "small-world" networks.
55  * Nature 393, 440 (1998) doi: https://doi.org/10.1038/30918\">10.1038/30918.
56  */
57 TLP_SCOPE void clusteringCoefficient(const Graph *g, tlp::NodeStaticProperty<double> &result,
58  _DEPRECATED unsigned int maxDepth = 1);
59 /*
60  * assign to each node of a graph its (in/ou/inout) degree.
61  * The weighted degree of a node is the sum of weights of
62  * all its in/out/inout edges."
63  * If no metric is specified, using a uniform metric value of 1 for all edges
64  * it assigns the usual degree of nodes (number of neighbors).",
65  * If norm is true, the measure is normalized in the following way:
66  * unweighted case => m(n) = deg(n) / (#V - 1)
67  * weighted case => m(n) = deg_w(n) / [(sum(e_w)/#E)(#V - 1)]
68  */
69 TLP_SCOPE void degree(const Graph *graph, tlp::NodeStaticProperty<double> &deg,
70  EDGE_TYPE direction = UNDIRECTED, NumericProperty *weights = nullptr,
71  bool norm = false);
72 /*
73  * assign to each node of a Directed Acyclic Graph a level such that
74  * if the edge e(u,v) exists level(u) < level(v) the algorithm ensure that
75  * the number of level used is minimal.
76  *
77  * Warning: the graph must be acyclic (no self loops).
78  */
79 TLP_SCOPE void dagLevel(const Graph *graph, tlp::NodeStaticProperty<unsigned int> &level);
80 // return the maximum value of the degree of the graph's nodes
81 TLP_SCOPE unsigned int maxDegree(const Graph *);
82 // return the minimum value of the degree of the graph's nodes
83 TLP_SCOPE unsigned int minDegree(const Graph *);
84 /*
85  * compute the maximum distance from the n (graph->nodes[nPos]) to all the other nodes of graph
86  * and store it into distance, (stored value is UINT_MAX for non connected nodes),
87  * if direction is set to UNDIRECTED use undirected graph, DIRECTED use directed graph
88  * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed)
89  * all the edge's weight is set to 1. (it uses a bfs thus the complexity is o(m), m = |E|).
90  */
91 TLP_SCOPE unsigned int maxDistance(const Graph *graph, const unsigned int nPos,
92  tlp::NodeStaticProperty<unsigned int> &distance,
93  EDGE_TYPE direction = UNDIRECTED);
94 
95 /*
96  * compute the maximum distance from the n (graph->nodes[nPos]) to all the other nodes of graph
97  * and store it into distance, (stored value is DBL_MAX for non connected nodes),
98  * if direction is set to UNDIRECTED use undirected graph, DIRECTED use directed graph
99  * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed)
100  * Edge weights can be given, Dijkstra's algorithm is then used
101  * (the complexity is then o((m + n)log n)) otherwise
102  * all the edge's weight is set to 1. (it uses a bfs thus the complexity is o(m), m = |E|).
103  */
104 TLP_SCOPE double maxDistance(const Graph *graph, const unsigned int nPos,
105  tlp::NodeStaticProperty<double> &distance,
106  const NumericProperty *const weights,
107  EDGE_TYPE direction = UNDIRECTED);
108 } // namespace tlp
109 #endif
110 ///@endcond