← Back to branch summary

~ubuntu-branches/ubuntu/lucid/igraph/lucid

« back to all changes in this revision

Viewing changes to src/walktrap_heap.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Mathieu Malaterre
  • Date: 2009-11-16 18:12:42 UTC
  • Revision ID: james.westby@ubuntu.com-20091116181242-mzv9p5fz9uj57xd1
Tags: upstream-0.5.3
Import upstream version 0.5.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/walktrap_heap.cpp
 
1
/* -*- mode: C -*-  */
 
2
/* 
 
3
   IGraph library.
 
4
   Copyright (C) 2007  Gabor Csardi <csardi@rmki.kfki.hu>
 
5
   MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
 
6
   
 
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.
 
11
   
 
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.
 
16
   
 
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 
 
20
   02110-1301 USA
 
21
 
 
22
*/
 
23
 
 
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 */
 
27
 
 
28
// File: heap.cpp
 
29
//-----------------------------------------------------------------------------
 
30
// Walktrap v0.2 -- Finds community structure of networks using random walks
 
31
// Copyright (C) 2004-2005 Pascal Pons
 
32
//
 
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.
 
37
//
 
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.
 
42
//
 
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 
 
46
// 02110-1301 USA
 
47
//-----------------------------------------------------------------------------
 
48
// Author   : Pascal Pons 
 
49
// Email    : pons@liafa.jussieu.fr
 
50
// Web page : http://www.liafa.jussieu.fr/~pons/
 
51
// Location : Paris, France
 
52
// Time     : June 2005
 
53
//-----------------------------------------------------------------------------
 
54
// see readme.txt for more details
 
55
 
 
56
#include "walktrap_heap.h"
 
57
#include <cstdlib>
 
58
#include <iostream>
 
59
 
 
60
 
 
61
using namespace std;
 
62
 
 
63
void Neighbor_heap::move_up(int index) {
 
64
  while(H[index/2]->delta_sigma > H[index]->delta_sigma) {
 
65
    Neighbor* tmp = H[index/2];
 
66
    H[index]->heap_index = index/2;
 
67
    H[index/2] = H[index];
 
68
    tmp->heap_index = index;
 
69
    H[index] = tmp;
 
70
    index = index/2;
 
71
  }
 
72
}
 
73
 
 
74
void Neighbor_heap::move_down(int index) {
 
75
  while(true) {
 
76
    int min = index;
 
77
    if((2*index < size) && (H[2*index]->delta_sigma < H[min]->delta_sigma))
 
78
      min = 2*index;
 
79
    if(2*index+1 < size && H[2*index+1]->delta_sigma < H[min]->delta_sigma)
 
80
      min = 2*index+1;
 
81
    if(min != index) {
 
82
      Neighbor* tmp = H[min];
 
83
      H[index]->heap_index = min;
 
84
      H[min] = H[index];
 
85
      tmp->heap_index = index;
 
86
      H[index] = tmp;
 
87
      index = min;
 
88
    }
 
89
    else break;
 
90
  }
 
91
}
 
92
 
 
93
Neighbor* Neighbor_heap::get_first() {
 
94
  if(size == 0) return 0;
 
95
  else return H[0];
 
96
}
 
97
 
 
98
void Neighbor_heap::remove(Neighbor* N) {
 
99
  if(N->heap_index == -1 || size == 0) return;
 
100
  Neighbor* last_N = H[--size];
 
101
  H[N->heap_index] = last_N;
 
102
  last_N->heap_index = N->heap_index;
 
103
  move_up(last_N->heap_index);
 
104
  move_down(last_N->heap_index);  
 
105
  N->heap_index = -1;
 
106
}
 
107
 
 
108
void Neighbor_heap::add(Neighbor* N) {
 
109
  if(size >= max_size) return;
 
110
    N->heap_index = size++;
 
111
    H[N->heap_index] = N;
 
112
  move_up(N->heap_index);
 
113
}
 
114
 
 
115
void Neighbor_heap::update(Neighbor* N) {
 
116
  if(N->heap_index == -1) return;
 
117
  move_up(N->heap_index);
 
118
  move_down(N->heap_index);
 
119
}
 
120
 
 
121
long Neighbor_heap::memory() {
 
122
  return (sizeof(Neighbor_heap) + long(max_size)*sizeof(Neighbor*));
 
123
}
 
124
  
 
125
Neighbor_heap::Neighbor_heap(int max_s) {
 
126
  max_size = max_s;
 
127
  size = 0;
 
128
  H = new Neighbor*[max_s];
 
129
}
 
130
 
 
131
Neighbor_heap::~Neighbor_heap() {
 
132
  delete[] H;
 
133
}
 
134
 
 
135
bool Neighbor_heap::is_empty() {
 
136
  return (size == 0);
 
137
}
 
138
 
 
139
 
 
140
 
 
141
//#################################################################
 
142
 
 
143
void Min_delta_sigma_heap::move_up(int index) {
 
144
  while(delta_sigma[H[index/2]] < delta_sigma[H[index]]) {
 
145
    int tmp = H[index/2];
 
146
    I[H[index]] = index/2;
 
147
    H[index/2] = H[index];
 
148
    I[tmp] = index;
 
149
    H[index] = tmp;
 
150
    index = index/2;
 
151
  }
 
152
}
 
153
 
 
154
void Min_delta_sigma_heap::move_down(int index) {
 
155
  while(true) {
 
156
    int max = index;
 
157
    if(2*index < size && delta_sigma[H[2*index]] > delta_sigma[H[max]])
 
158
      max = 2*index;
 
159
    if(2*index+1 < size && delta_sigma[H[2*index+1]] > delta_sigma[H[max]])
 
160
      max = 2*index+1;
 
161
    if(max != index) {
 
162
      int tmp = H[max];
 
163
      I[H[index]] = max;
 
164
      H[max] = H[index];
 
165
      I[tmp] = index;
 
166
      H[index] = tmp;
 
167
      index = max;
 
168
    }
 
169
    else break;
 
170
  }
 
171
}
 
172
 
 
173
int Min_delta_sigma_heap::get_max_community() {
 
174
  if(size == 0) return -1;
 
175
  else return H[0];
 
176
}
 
177
 
 
178
void Min_delta_sigma_heap::remove_community(int community) {
 
179
  if(I[community] == -1 || size == 0) return;
 
180
  int last_community = H[--size];
 
181
  H[I[community]] = last_community;
 
182
  I[last_community] = I[community];
 
183
  move_up(I[last_community]);
 
184
  move_down(I[last_community]);  
 
185
  I[community] = -1;
 
186
}
 
187
 
 
188
void Min_delta_sigma_heap::update(int community) {
 
189
  if(community < 0 || community >= max_size) return;
 
190
  if(I[community] == -1) {
 
191
    I[community] = size++;
 
192
    H[I[community]] = community;
 
193
  }
 
194
  move_up(I[community]);
 
195
  move_down(I[community]);
 
196
}
 
197
 
 
198
long Min_delta_sigma_heap::memory() {
 
199
  return (sizeof(Min_delta_sigma_heap) + long(max_size)*(2*sizeof(int) + sizeof(float)));
 
200
}
 
201
  
 
202
Min_delta_sigma_heap::Min_delta_sigma_heap(int max_s) {
 
203
  max_size = max_s;
 
204
  size = 0;
 
205
  H = new int[max_s];
 
206
  I = new int[max_s];
 
207
  delta_sigma = new float[max_s];
 
208
  for(int i = 0; i < max_size; i++) {
 
209
    I[i] = -1;
 
210
    delta_sigma[i] = 1.;
 
211
  }
 
212
}
 
213
 
 
214
Min_delta_sigma_heap::~Min_delta_sigma_heap() {
 
215
  delete[] H;
 
216
  delete[] I;
 
217
  delete[] delta_sigma;
 
218
}
 
219
 
 
220
bool Min_delta_sigma_heap::is_empty() {
 
221
  return (size == 0);
 
222
}