4
Copyright (C) 2007 Gabor Csardi <csardi@rmki.kfki.hu>
5
MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
7
This program is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 2 of the License, or
10
(at your option) any later version.
12
This program is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
GNU General Public License for more details.
17
You should have received a copy of the GNU General Public License
18
along with this program; if not, write to the Free Software
19
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
24
/* The original version of this file was written by Pascal Pons
25
The original copyright notice follows here. The FSF address was
26
fixed by Tamas Nepusz */
29
//-----------------------------------------------------------------------------
30
// Walktrap v0.2 -- Finds community structure of networks using random walks
31
// Copyright (C) 2004-2005 Pascal Pons
33
// This program is free software; you can redistribute it and/or modify
34
// it under the terms of the GNU General Public License as published by
35
// the Free Software Foundation; either version 2 of the License, or
36
// (at your option) any later version.
38
// This program is distributed in the hope that it will be useful,
39
// but WITHOUT ANY WARRANTY; without even the implied warranty of
40
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
41
// GNU General Public License for more details.
43
// You should have received a copy of the GNU General Public License
44
// along with this program; if not, write to the Free Software
45
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
47
//-----------------------------------------------------------------------------
48
// Author : Pascal Pons
49
// Email : pons@liafa.jussieu.fr
50
// Web page : http://www.liafa.jussieu.fr/~pons/
51
// Location : Paris, France
53
//-----------------------------------------------------------------------------
54
// see readme.txt for more details
61
int community1; // the two adjacent communities
62
int community2; // community1 < community2
64
float delta_sigma; // the delta sigma between the two communities
65
float weight; // the total weight of the edges between the two communities
66
bool exact; // true if delta_sigma is exact, false if it is only a lower bound
68
Neighbor* next_community1; // pointers of two double
69
Neighbor* previous_community1; // chained lists containing
70
Neighbor* next_community2; // all the neighbors of
71
Neighbor* previous_community2; // each communities.
84
Neighbor** H; // the heap that contains a pointer to each Neighbor object stored
86
void move_up(int index);
87
void move_down(int index);
90
void add(Neighbor* N); // add a new distance
91
void update(Neighbor* N); // update a distance
92
void remove(Neighbor* N); // remove a distance
93
Neighbor* get_first(); // get the first item
97
Neighbor_heap(int max_size);
102
class Min_delta_sigma_heap {
107
int* H; // the heap that contains the number of each community
108
int* I; // the index of each community in the heap (-1 = not stored)
110
void move_up(int index);
111
void move_down(int index);
114
int get_max_community(); // return the community with the maximal delta_sigma
115
void remove_community(int community); // remove a community;
116
void update(int community); // update (or insert if necessary) the community
117
long memory(); // the memory used in Bytes.
120
float* delta_sigma; // the delta_sigma of the stored communities
122
Min_delta_sigma_heap(int max_size);
123
~Min_delta_sigma_heap();