1 /* -*- mode: C -*-  */
2 /* vim:set ts=4 sw=4 sts=4 et: */
3 /*
4    IGraph library.
5    Copyright (C) 2005-2012  Gabor Csardi <csardi.gabor@gmail.com>
6    334 Harvard street, Cambridge, MA 02139 USA
7 
8    This program is free software; you can redistribute it and/or modify
9    it under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 2 of the License, or
11    (at your option) any later version.
12 
13    This program is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17 
18    You should have received a copy of the GNU General Public License
19    along with this program; if not, write to the Free Software
20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21    02110-1301 USA
22 
23 */
24 
25 long int no_of_nodes = igraph_vcount(graph);
26 igraph_vit_t vit;
27 long int nodes_to_calc;
28 igraph_vector_int_t *neis1, *neis2;
29 igraph_real_t triangles;
30 long int i, j, k;
31 long int neilen1, neilen2;
32 long int *neis;
33 igraph_lazy_adjlist_t adjlist;
34 
35 IGRAPH_CHECK(igraph_vit_create(graph, vids, &vit));
36 IGRAPH_FINALLY(igraph_vit_destroy, &vit);
37 nodes_to_calc = IGRAPH_VIT_SIZE(vit);
38 
39 if (nodes_to_calc == 0) {
40     igraph_vector_clear(res);
41     igraph_vit_destroy(&vit);
42     IGRAPH_FINALLY_CLEAN(1);
43     return IGRAPH_SUCCESS;
44 }
45 
46 neis = IGRAPH_CALLOC(no_of_nodes, long int);
47 if (neis == 0) {
48     IGRAPH_ERROR("local undirected transitivity failed", IGRAPH_ENOMEM);
49 }
50 IGRAPH_FINALLY(igraph_free, neis);
51 
52 IGRAPH_CHECK(igraph_vector_resize(res, nodes_to_calc));
53 
54 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph, &adjlist, IGRAPH_ALL, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE));
55 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &adjlist);
56 
57 for (i = 0; !IGRAPH_VIT_END(vit); IGRAPH_VIT_NEXT(vit), i++) {
58     long int node = IGRAPH_VIT_GET(vit);
59 
60     IGRAPH_ALLOW_INTERRUPTION();
61 
62     neis1 = igraph_lazy_adjlist_get(&adjlist, (igraph_integer_t) node);
63     neilen1 = igraph_vector_int_size(neis1);
64     for (j = 0; j < neilen1; j++) {
65         neis[ (long int)VECTOR(*neis1)[j] ] = i + 1;
66     }
67     triangles = 0;
68 
69     for (j = 0; j < neilen1; j++) {
70         long int v = (long int) VECTOR(*neis1)[j];
71         neis2 = igraph_lazy_adjlist_get(&adjlist, (igraph_integer_t) v);
72         neilen2 = igraph_vector_int_size(neis2);
73         for (k = 0; k < neilen2; k++) {
74             long int v2 = (long int) VECTOR(*neis2)[k];
75             if (neis[v2] == i + 1) {
76                 triangles += 1.0;
77             }
78         }
79     }
80 
81 #ifdef TRANSIT
82     if (mode == IGRAPH_TRANSITIVITY_ZERO && neilen1 < 2) {
83         VECTOR(*res)[i] = 0.0;
84     } else {
85         VECTOR(*res)[i] = triangles / neilen1 / (neilen1 - 1);
86     }
87 #else
88     VECTOR(*res)[i] = triangles / 2;
89 #endif
90 }
91 
92 igraph_lazy_adjlist_destroy(&adjlist);
93 IGRAPH_FREE(neis);
94 igraph_vit_destroy(&vit);
95 IGRAPH_FINALLY_CLEAN(3);
96