/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2007-2012 Gabor Csardi 334 Harvard st, Cambridge, MA, 02138 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ /* The original version of this file was written by Pascal Pons The original copyright notice follows here. The FSF address was fixed by Tamas Nepusz */ // File: communities.h //----------------------------------------------------------------------------- // Walktrap v0.2 -- Finds community structure of networks using random walks // Copyright (C) 2004-2005 Pascal Pons // // This program is free software; you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation; either version 2 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA // 02110-1301 USA //----------------------------------------------------------------------------- // Author : Pascal Pons // Email : pascal.pons@gmail.com // Web page : http://www-rp.lip6.fr/~latapy/PP/walktrap.html // Location : Paris, France // Time : June 2005 //----------------------------------------------------------------------------- // see readme.txt for more details #ifndef COMMUNITIES_H #define COMMUNITIES_H #include "walktrap_graph.h" #include "walktrap_heap.h" #include "igraph_community.h" #include "config.h" namespace igraph { namespace walktrap { class Communities; class Probabilities { public: static IGRAPH_THREAD_LOCAL float* tmp_vector1; // static IGRAPH_THREAD_LOCAL float* tmp_vector2; // static IGRAPH_THREAD_LOCAL int* id; // static IGRAPH_THREAD_LOCAL int* vertices1; // static IGRAPH_THREAD_LOCAL int* vertices2; // static IGRAPH_THREAD_LOCAL int current_id; // static IGRAPH_THREAD_LOCAL Communities* C; // pointer to all the communities static IGRAPH_THREAD_LOCAL int length; // length of the random walks int size; // number of probabilities stored int* vertices; // the vertices corresponding to the stored probabilities, 0 if all the probabilities are stored float* P; // the probabilities long memory(); // the memory (in Bytes) used by the object double compute_distance(const Probabilities* P2) const; // compute the squared distance r^2 between this probability vector and P2 Probabilities(int community); // compute the probability vector of a community Probabilities(int community1, int community2); // merge the probability vectors of two communities in a new one // the two communities must have their probability vectors stored ~Probabilities(); // destructor }; class Community { public: Neighbor* first_neighbor; // first item of the list of adjacent communities Neighbor* last_neighbor; // last item of the list of adjacent communities int this_community; // number of this community int first_member; // number of the first vertex of the community int last_member; // number of the last vertex of the community int size; // number of members of the community Probabilities* P; // the probability vector, 0 if not stored. float sigma; // sigma(C) of the community float internal_weight; // sum of the weight of the internal edges float total_weight; // sum of the weight of all the edges of the community (an edge between two communities is a half-edge for each community) int sub_communities[2]; // the two sub sommunities, -1 if no sub communities; int sub_community_of; // number of the community in which this community has been merged // 0 if the community is active // -1 if the community is not used void merge(Community &C1, Community &C2); // create a new community by merging C1 an C2 void add_neighbor(Neighbor* N); void remove_neighbor(Neighbor* N); float min_delta_sigma(); // compute the minimal delta sigma among all the neighbors of this community Community(); // create an empty community ~Community(); // destructor }; class Communities { private: long max_memory; // size in Byte of maximal memory usage, -1 for no limit igraph_matrix_t *merges; long int mergeidx; igraph_vector_t *modularity; public: long memory_used; // in bytes Min_delta_sigma_heap* min_delta_sigma; // the min delta_sigma of the community with a saved probability vector (for memory management) Graph* G; // the graph int* members; // the members of each community represented as a chained list. // a community points to the first_member the array which contains // the next member (-1 = end of the community) Neighbor_heap* H; // the distances between adjacent communities. Community* communities; // array of the communities int nb_communities; // number of valid communities int nb_active_communities; // number of active communities Communities(Graph* G, int random_walks_length = 3, long max_memory = -1, igraph_matrix_t *merges = 0, igraph_vector_t *modularity = 0); // Constructor ~Communities(); // Destructor void merge_communities(Neighbor* N); // create a community by merging two existing communities double merge_nearest_communities(); double compute_delta_sigma(int c1, int c2); // compute delta_sigma(c1,c2) void remove_neighbor(Neighbor* N); void add_neighbor(Neighbor* N); void update_neighbor(Neighbor* N, float new_delta_sigma); void manage_memory(); }; } } /* end of namespaces */ #endif