1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard street, Cambridge, MA 02139 USA
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 #include <igraph.h>
25 #include <stdlib.h>
26
compare_vectors(const void * p1,const void * p2)27 int compare_vectors(const void *p1, const void *p2) {
28 igraph_vector_t *v1, *v2;
29 long s1, s2, i;
30
31 v1 = *((igraph_vector_t **) p1);
32 v2 = *((igraph_vector_t **) p2);
33 s1 = igraph_vector_size(v1);
34 s2 = igraph_vector_size(v2);
35 if (s1 < s2) {
36 return -1;
37 }
38 if (s1 > s2) {
39 return 1;
40 }
41 for (i = 0; i < s1; ++i) {
42 if (VECTOR(*v1)[i] < VECTOR(*v2)[i]) {
43 return -1;
44 }
45 if (VECTOR(*v1)[i] > VECTOR(*v2)[i]) {
46 return 1;
47 }
48 }
49 return 0;
50 }
51
52 /* Takes a pointer vector of vectors. Sorts each vector, then sorts the pointer vector */
canonicalize_list(igraph_vector_ptr_t * list)53 void canonicalize_list(igraph_vector_ptr_t *list) {
54 long i, len;
55 len = igraph_vector_ptr_size(list);
56 for (i = 0; i < len; ++i) {
57 igraph_vector_sort((igraph_vector_t *) VECTOR(*list)[i]);
58 }
59 qsort(&(VECTOR(*list)[0]), len, sizeof(void *), &compare_vectors);
60 }
61
print_vector(igraph_vector_t * v)62 void print_vector(igraph_vector_t *v) {
63 long int i, n = igraph_vector_size(v);
64 for (i = 0; i < n; i++) {
65 printf(" %li", (long int) VECTOR(*v)[i]);
66 }
67 printf("\n");
68 }
69
warning_handler_ignore(const char * reason,const char * file,int line,int e)70 void warning_handler_ignore(const char* reason, const char* file, int line, int e) {
71 }
72
73
74 struct userdata {
75 int i;
76 igraph_vector_ptr_t *list;
77 };
78
handler(igraph_vector_t * clique,void * arg)79 igraph_bool_t handler(igraph_vector_t *clique, void *arg) {
80 struct userdata *ud;
81 igraph_bool_t cont;
82
83 ud = (struct userdata *) arg;
84 cont = 1; /* true */
85
86 if (compare_vectors(&clique, &(VECTOR(*(ud->list))[ud->i])) != 0) {
87 printf("igraph_cliques() and igraph_cliques_callback() give different results.\n");
88 cont = 0; /* false */
89 }
90
91 igraph_vector_destroy(clique);
92 igraph_free(clique);
93
94 ud->i += 1;
95
96 return cont;
97 }
98
test_callback(const igraph_t * graph)99 void test_callback(const igraph_t *graph) {
100 igraph_vector_ptr_t list;
101 struct userdata ud;
102
103 igraph_vector_ptr_init(&list, 0);
104 igraph_cliques(graph, &list, 0, 0);
105
106 ud.i = 0;
107 ud.list = &list;
108
109 igraph_cliques_callback(graph, 0, 0, &handler, (void *) &ud);
110
111 IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR(&list, igraph_vector_destroy);
112 igraph_vector_ptr_destroy_all(&list);
113 }
114
115
main()116 int main() {
117
118 igraph_t g;
119 igraph_vector_ptr_t result;
120 igraph_es_t es;
121 igraph_integer_t omega;
122 long int i, j, n;
123 const int params[] = {4, -1, 2, 2, 0, 0, -1, -1};
124
125 igraph_set_warning_handler(warning_handler_ignore);
126
127 igraph_vector_ptr_init(&result, 0);
128 igraph_full(&g, 6, 0, 0);
129 igraph_es_pairs_small(&es, 0, 0, 1, 0, 2, 3, 5, -1);
130 igraph_delete_edges(&g, es);
131 igraph_es_destroy(&es);
132
133 for (j = 0; j < sizeof(params) / (2 * sizeof(params[0])); j++) {
134 if (params[2 * j + 1] != 0) {
135 igraph_cliques(&g, &result, params[2 * j], params[2 * j + 1]);
136 } else {
137 igraph_largest_cliques(&g, &result);
138 }
139 n = igraph_vector_ptr_size(&result);
140 printf("%ld cliques found\n", (long)n);
141 canonicalize_list(&result);
142 for (i = 0; i < n; i++) {
143 igraph_vector_t* v = (igraph_vector_t*) igraph_vector_ptr_e(&result, i);
144 print_vector(v);
145 igraph_vector_destroy(v);
146 igraph_free(v);
147 }
148 }
149
150 igraph_clique_number(&g, &omega);
151 printf("omega=%ld\n", (long)omega);
152
153 test_callback(&g);
154
155 igraph_destroy(&g);
156
157 igraph_tree(&g, 5, 2, IGRAPH_TREE_OUT);
158 igraph_cliques(&g, &result, 5, 5);
159 if (igraph_vector_ptr_size(&result) != 0) {
160 return 1;
161 }
162
163 igraph_destroy(&g);
164 igraph_vector_ptr_destroy(&result);
165
166 return 0;
167 }
168