![]() |
Tulip
4.6.0
Better Visualization Through Research
|
00001 /* 00002 * 00003 * This file is part of Tulip (www.tulip-software.org) 00004 * 00005 * Authors: David Auber and the Tulip development Team 00006 * from LaBRI, University of Bordeaux 00007 * 00008 * Tulip is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License 00010 * as published by the Free Software Foundation, either version 3 00011 * of the License, or (at your option) any later version. 00012 * 00013 * Tulip is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 * See the GNU General Public License for more details. 00017 * 00018 */ 00019 ///@cond DOXYGEN_HIDDEN 00020 00021 #ifndef _TLPGRAPHMEASEURE_H 00022 #define _TLPGRAPHMEASEURE_H 00023 00024 #include <tulip/Node.h> 00025 #include <tulip/MutableContainer.h> 00026 #include <tulip/DoubleProperty.h> 00027 00028 namespace tlp { 00029 00030 class Graph; 00031 class PluginProgress; 00032 enum EDGE_TYPE {DIRECTED = 0, INV_DIRECTED = 1, UNDIRECTED = 2}; 00033 /** 00034 * returns the average path lengh of a graph, that is the sum 00035 * of the shortest distances for all pair of distinct nodes in that graph 00036 * divided by the number of those pairs. For a pair of non connected nodes, 00037 * the shorted distance is set to 0. 00038 * see http://en.wikipedia.org/wiki/Average_path_length for more details 00039 */ 00040 TLP_SCOPE double averagePathLength(const Graph* g, PluginProgress* = NULL); 00041 // obsolete version for compatibility purpose 00042 inline bool averagePathLength(Graph *g, double& result, PluginProgress *pp = NULL) { 00043 result = averagePathLength(g, pp); 00044 return true; 00045 } 00046 /* 00047 * returns the clustering coefficient of a graph 00048 * as the average of the local clustering coefficients 00049 * (see clusteringCoefficient function) of all the nodes. 00050 * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details. 00051 */ 00052 TLP_SCOPE double averageClusteringCoefficient(const Graph *, PluginProgress * = NULL); 00053 // obsolete version for compatibility purpose 00054 inline bool averageCluster(Graph* g, double& result, PluginProgress* pp = NULL) { 00055 result = averageClusteringCoefficient(g, pp); 00056 return true; 00057 } 00058 /* 00059 * assigns to each node its local clustering coefficient 00060 * that is the proportion of edges between the nodes within its neighbourhood 00061 * divided by the number of edges that could possibly exist between them. 00062 * This quantifies how close its neighbors are to being a clique. 00063 * see http://en.wikipedia.org/wiki/Clustering_coefficient for more details 00064 */ 00065 TLP_SCOPE void clusteringCoefficient(const Graph *g, MutableContainer<double> &result, unsigned int maxDepth = 1, PluginProgress* = NULL); 00066 /* 00067 * assigns to each node of a Directed Acyclic Graph a level such that 00068 * if the edge e(u,v) exists level(u) < level(v) the algorithm ensure that 00069 * the number of level used is minimal. 00070 * 00071 * Warning : the graph must be acyclic (no self loops). 00072 */ 00073 TLP_SCOPE void dagLevel(const Graph *graph, MutableContainer<unsigned int> &level, PluginProgress* = NULL); 00074 // returns the maximum value of the degree of the graph's nodes 00075 TLP_SCOPE unsigned int maxDegree(const Graph *); 00076 00077 // returns the minimum value of the degree of the graph's nodes 00078 TLP_SCOPE unsigned int minDegree(const Graph *); 00079 /* 00080 * computes the maximum distance from n to all the other nodes of graph 00081 * and store it into distance, (stored value is UINT_MAX for non connected nodes), 00082 * if direction is set to UNDIRECTED use undirected graph, DIRECTED use directed graph 00083 * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed) 00084 * all the edge's weight is set to 1. (it uses a bfs thus the complexity is o(m), m = |E|). 00085 */ 00086 TLP_SCOPE unsigned int maxDistance(const Graph *graph, const node n, MutableContainer<unsigned int> &distance, EDGE_TYPE direction = UNDIRECTED); 00087 /* 00088 * adds to a result set, all the nodes, according to direction, 00089 * at distance less or equal to maxDistance of startNode. 00090 * If direction is set to UNDIRECTED use undirected graph, DIRECTED use directed graph 00091 * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed) 00092 */ 00093 TLP_SCOPE void reachableNodes(const Graph *graph, const node startNode, std::set<node> &result, unsigned int maxDistance, EDGE_TYPE direction = UNDIRECTED); 00094 } 00095 #endif 00096 ///@endcond