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