Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/GraphMeasure.h
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
 All Classes Files Functions Variables Enumerations Enumerator Properties