Tulip  5.3.0
Large graphs analysis and drawing
GraphMeasure.h
1 /*
2  *
3  * This file is part of Tulip (http://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 <set>
25 
26 #include <tulip/Node.h>
27 #include <tulip/MutableContainer.h>
28 #include <tulip/DoubleProperty.h>
29 #include <tulip/StaticProperty.h>
30 
31 namespace tlp {
32 
33 class Graph;
34 class PluginProgress;
35 enum EDGE_TYPE { UNDIRECTED = 0, INV_DIRECTED = 1, DIRECTED = 2 };
36 #define IN_EDGE INV_DIRECTED
37 #define OUT_EDGE DIRECTED
38 #define INOUT_EDGE UNDIRECTED
39 /**
40  * returns the average path lengh of a graph, that is the sum
41  * of the shortest distances for all pair of distinct nodes in that graph
42  * divided by the number of those pairs. For a pair of non connected nodes,
43  * the shorted distance is set to 0.
44  * see http://en.wikipedia.org/wiki/Average_path_length for more details
45  */
46 TLP_SCOPE double averagePathLength(const Graph *g);
47 /*
48  * return the clustering coefficient of a graph
49  * as the average of the local clustering coefficients
50  * (see clusteringCoefficient function) of all the nodes.
51  * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details.
52  */
53 TLP_SCOPE double averageClusteringCoefficient(const Graph *);
54 /*
55  * assign to each node its local clustering coefficient
56  * that is the proportion of edges between the nodes within its neighbourhood
57  * divided by the number of edges that could possibly exist between them.
58  * This quantifies how close its neighbors are to being a clique.
59  * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details
60  * WARNING: this function is deprecated
61  */
62 TLP_SCOPE _DEPRECATED void clusteringCoefficient(const Graph *g, MutableContainer<double> &result,
63  unsigned int maxDepth = 1);
64 /*
65  * assign to each node its local clustering coefficient
66  * that is the proportion of edges between the nodes within its neighbourhood
67  * divided by the number of edges that could possibly exist between them.
68  * This quantifies how close its neighbors are to being a clique.
69  * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details
70  */
71 TLP_SCOPE void clusteringCoefficient(const Graph *g, tlp::NodeStaticProperty<double> &result,
72  unsigned int maxDepth = 1);
73 /*
74  * assign to each node of a Directed Acyclic Graph a level such that
75  * if the edge e(u,v) exists level(u) < level(v) the algorithm ensure that
76  * the number of level used is minimal.
77  * WARNING: this function is deprecated
78  */
79 TLP_SCOPE _DEPRECATED void dagLevel(const Graph *graph, MutableContainer<unsigned int> &level);
80 /*
81  * assign to each node of a graph its (in/ou/inout) degree.
82  * The weighted degree of a node is the sum of weights of
83  * all its in/out/inout edges."
84  * If no metric is specified, using a uniform metric value of 1 for all edges
85  * it assigns the usual degree of nodes (number of neighbors).",
86  * If norm is true, the measure is normalized in the following way:
87  * unweighted case => m(n) = deg(n) / (#V - 1)
88  * weighted case => m(n) = deg_w(n) / [(sum(e_w)/#E)(#V - 1)]
89  */
90 TLP_SCOPE void degree(const Graph *graph, tlp::NodeStaticProperty<double> &deg,
91  EDGE_TYPE direction = UNDIRECTED, NumericProperty *weights = nullptr,
92  bool norm = false);
93 /*
94  * assign to each node of a Directed Acyclic Graph a level such that
95  * if the edge e(u,v) exists level(u) < level(v) the algorithm ensure that
96  * the number of level used is minimal.
97  *
98  * Warning: the graph must be acyclic (no self loops).
99  */
100 TLP_SCOPE void dagLevel(const Graph *graph, tlp::NodeStaticProperty<unsigned int> &level);
101 // return the maximum value of the degree of the graph's nodes
102 TLP_SCOPE unsigned int maxDegree(const Graph *);
103 // return the minimum value of the degree of the graph's nodes
104 TLP_SCOPE unsigned int minDegree(const Graph *);
105 /*
106  * compute the maximum distance from n to all the other nodes of graph
107  * and store it into distance, (stored value is UINT_MAX for non connected nodes),
108  * if direction is set to UNDIRECTED use undirected graph, DIRECTED use directed graph
109  * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed)
110  * all the edge's weight is set to 1. (it uses a bfs thus the complexity is o(m), m = |E|).
111  */
112 TLP_SCOPE _DEPRECATED unsigned int maxDistance(const Graph *graph, const node n,
113  MutableContainer<unsigned int> &distance,
114  EDGE_TYPE direction = UNDIRECTED);
115 /*
116  * compute the maximum distance from the n (graph->nodes[nPos]) to all the other nodes of graph
117  * and store it into distance, (stored value is UINT_MAX for non connected nodes),
118  * if direction is set to UNDIRECTED use undirected graph, DIRECTED use directed graph
119  * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed)
120  * all the edge's weight is set to 1. (it uses a bfs thus the complexity is o(m), m = |E|).
121  */
122 TLP_SCOPE unsigned int maxDistance(const Graph *graph, const unsigned int nPos,
123  tlp::NodeStaticProperty<unsigned int> &distance,
124  EDGE_TYPE direction = UNDIRECTED);
125 /*
126  * add to a result set, all the nodes, according to direction,
127  * at distance less or equal to maxDistance of startNode.
128  * If direction is set to UNDIRECTED use undirected graph, DIRECTED use directed graph
129  * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed)
130  * WARNING: this function is deprecated use markReachableNodes instead
131  */
132 TLP_SCOPE _DEPRECATED void reachableNodes(const Graph *graph, const node startNode,
133  std::set<node> &result, unsigned int maxDistance,
134  EDGE_TYPE direction = UNDIRECTED);
135 /*
136  * mark as reachable (set value in "reachables" hash map to true),
137  * all the nodes, according to direction,
138  * at distance less or equal to maxDistance of startNode.
139  * If direction is set to UNDIRECTED use undirected graph,
140  * DIRECTED use directed graph
141  * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed)
142  */
143 TLP_SCOPE void markReachableNodes(const Graph *graph, const node startNode,
144  TLP_HASH_MAP<node, bool> &reachables, unsigned int maxDistance,
145  EDGE_TYPE direction = UNDIRECTED);
146 } // namespace tlp
147 #endif
148 ///@endcond