Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
28namespace tlp {
29
30class Graph;
31class 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 */
39TLP_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 */
46TLP_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 its neighbors are to being a clique.
52 * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details
53 */
54TLP_SCOPE void clusteringCoefficient(const Graph *g, tlp::NodeStaticProperty<double> &result,
55 unsigned int maxDepth = 1);
56/*
57 * assign to each node of a graph its (in/ou/inout) degree.
58 * The weighted degree of a node is the sum of weights of
59 * all its in/out/inout edges."
60 * If no metric is specified, using a uniform metric value of 1 for all edges
61 * it assigns the usual degree of nodes (number of neighbors).",
62 * If norm is true, the measure is normalized in the following way:
63 * unweighted case => m(n) = deg(n) / (#V - 1)
64 * weighted case => m(n) = deg_w(n) / [(sum(e_w)/#E)(#V - 1)]
65 */
66TLP_SCOPE void degree(const Graph *graph, tlp::NodeStaticProperty<double> &deg,
67 EDGE_TYPE direction = UNDIRECTED, NumericProperty *weights = nullptr,
68 bool norm = false);
69/*
70 * assign to each node of a Directed Acyclic Graph a level such that
71 * if the edge e(u,v) exists level(u) < level(v) the algorithm ensure that
72 * the number of level used is minimal.
73 *
74 * Warning: the graph must be acyclic (no self loops).
75 */
76TLP_SCOPE void dagLevel(const Graph *graph, tlp::NodeStaticProperty<unsigned int> &level);
77// return the maximum value of the degree of the graph's nodes
78TLP_SCOPE unsigned int maxDegree(const Graph *);
79// return the minimum value of the degree of the graph's nodes
80TLP_SCOPE unsigned int minDegree(const Graph *);
81/*
82 * compute the maximum distance from the n (graph->nodes[nPos]) to all the other nodes of graph
83 * and store it into distance, (stored value is UINT_MAX for non connected nodes),
84 * if direction is set to UNDIRECTED use undirected graph, DIRECTED use directed graph
85 * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed)
86 * all the edge's weight is set to 1. (it uses a bfs thus the complexity is o(m), m = |E|).
87 */
88TLP_SCOPE unsigned int maxDistance(const Graph *graph, const unsigned int nPos,
89 tlp::NodeStaticProperty<unsigned int> &distance,
90 EDGE_TYPE direction = UNDIRECTED);
91
92/*
93 * compute the maximum distance from the n (graph->nodes[nPos]) to all the other nodes of graph
94 * and store it into distance, (stored value is DBL_MAX for non connected nodes),
95 * if direction is set to UNDIRECTED use undirected graph, DIRECTED use directed graph
96 * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed)
97 * Edge weights can be given, Dijkstra's algorithm is then used
98 * (the complexity is then o((m + n)log n)) otherwise
99 * all the edge's weight is set to 1. (it uses a bfs thus the complexity is o(m), m = |E|).
100 */
101TLP_SCOPE double maxDistance(const Graph *graph, const unsigned int nPos,
102 tlp::NodeStaticProperty<double> &distance,
103 const NumericProperty *const weights,
104 EDGE_TYPE direction = UNDIRECTED);
105} // namespace tlp
106#endif
107///@endcond