1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
/* -*- mode: C -*- */
/* vim:set ts=2 sts=2 sw=2 et: */
/*
IGraph library.
Copyright (C) 2005-2012 Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 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
*/
long int no_of_nodes=igraph_vcount(graph);
long int node, i, j, nn;
igraph_adjlist_t allneis;
igraph_vector_int_t *neis1, *neis2;
long int neilen1, neilen2, deg1;
long int *neis;
long int maxdegree;
igraph_vector_int_t order;
igraph_vector_int_t rank;
igraph_vector_t degree;
igraph_vector_int_init(&order, no_of_nodes);
IGRAPH_FINALLY(igraph_vector_int_destroy, &order);
IGRAPH_VECTOR_INIT_FINALLY(°ree, no_of_nodes);
IGRAPH_CHECK(igraph_degree(graph, °ree, igraph_vss_all(), IGRAPH_ALL,
IGRAPH_LOOPS));
maxdegree=(long int) igraph_vector_max(°ree)+1;
igraph_vector_order1_int(°ree, &order, maxdegree);
igraph_vector_int_init(&rank, no_of_nodes);
IGRAPH_FINALLY(igraph_vector_int_destroy, &rank);
for (i=0; i<no_of_nodes; i++) {
VECTOR(rank)[ VECTOR(order)[i] ] = no_of_nodes-i-1;
}
IGRAPH_CHECK(igraph_adjlist_init(graph, &allneis, IGRAPH_ALL));
IGRAPH_FINALLY(igraph_adjlist_destroy, &allneis);
IGRAPH_CHECK(igraph_i_trans4_al_simplify(&allneis, &rank));
neis=igraph_Calloc(no_of_nodes, long int);
if (neis==0) {
IGRAPH_ERROR("undirected local transitivity failed", IGRAPH_ENOMEM);
}
IGRAPH_FINALLY(igraph_free, neis);
#ifndef TRIANGLES
IGRAPH_CHECK(igraph_vector_resize(res, no_of_nodes));
igraph_vector_null(res);
#else
igraph_vector_int_clear(res);
#endif
for (nn=no_of_nodes-1; nn>=0; nn--) {
node=VECTOR(order)[nn];
IGRAPH_ALLOW_INTERRUPTION();
neis1=igraph_adjlist_get(&allneis, node);
neilen1=igraph_vector_int_size(neis1);
deg1=(long int) VECTOR(degree)[node];
/* Mark the neighbors of the node */
for (i=0; i<neilen1; i++) {
neis[ (long int) VECTOR(*neis1)[i] ] = node+1;
}
for (i=0; i<neilen1; i++) {
long int nei=(long int) VECTOR(*neis1)[i];
neis2=igraph_adjlist_get(&allneis, nei);
neilen2=igraph_vector_int_size(neis2);
for (j=0; j<neilen2; j++) {
long int nei2=(long int) VECTOR(*neis2)[j];
if (neis[nei2] == node+1) {
#ifndef TRIANGLES
VECTOR(*res)[nei2] += 1;
VECTOR(*res)[nei] += 1;
VECTOR(*res)[node] += 1;
#else
IGRAPH_CHECK(igraph_vector_int_push_back(res, node));
IGRAPH_CHECK(igraph_vector_int_push_back(res, nei));
IGRAPH_CHECK(igraph_vector_int_push_back(res, nei2));
#endif
}
}
}
#ifdef TRANSIT
if (mode == IGRAPH_TRANSITIVITY_ZERO && deg1 < 2)
VECTOR(*res)[node] = 0.0;
else
VECTOR(*res)[node] = VECTOR(*res)[node] / deg1 / (deg1-1) * 2.0;
#endif
#ifdef TRIEDGES
VECTOR(*res)[node] += deg1;
#endif
}
igraph_free(neis);
igraph_adjlist_destroy(&allneis);
igraph_vector_int_destroy(&rank);
igraph_vector_destroy(°ree);
igraph_vector_int_destroy(&order);
IGRAPH_FINALLY_CLEAN(5);
|
