1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard st, 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 <stdio.h>
26 #include <stdlib.h>
27
main()28 int main() {
29
30 igraph_t ring1, ring2;
31 igraph_vector_int_t color1, color2;
32 igraph_vector_t perm;
33 igraph_bool_t iso;
34 igraph_integer_t count;
35 long int i;
36
37 igraph_rng_seed(igraph_rng_default(), 12345);
38
39 igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/1);
40 igraph_vector_init_seq(&perm, 0, igraph_vcount(&ring1) - 1);
41 igraph_vector_shuffle(&perm);
42 igraph_permute_vertices(&ring1, &ring2, &perm);
43
44 /* Without colors */
45 igraph_isomorphic(&ring1, &ring2, &iso);
46 if (!iso) {
47 fprintf(stderr, "Without color failed.\n");
48 return 1;
49 }
50
51 /* Without colors, number of isomorphisms */
52 igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, 0, 0, &count, 0, 0, 0);
53 if (count != 200) {
54 fprintf(stderr, "Count without colors failed, expected %li, got %li.\n",
55 (long int) 200, (long int) count);
56 return 2;
57 }
58
59 /* Everything has the same colors */
60 igraph_vector_int_init(&color1, igraph_vcount(&ring1));
61 igraph_vector_int_init(&color2, igraph_vcount(&ring2));
62 igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
63 if (!iso) {
64 fprintf(stderr, "Single color failed.\n");
65 return 3;
66 }
67
68 /* Two colors, just counting */
69 for (i = 0; i < igraph_vector_int_size(&color1); i += 2) {
70 VECTOR(color1)[i] = VECTOR(color2)[(long int)VECTOR(perm)[i]] = 1;
71 }
72 igraph_count_isomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &count, 0, 0, 0);
73 if (count != 100) {
74 fprintf(stderr, "Count with two colors failed, expected %li, got %li.\n",
75 (long int) 100, (long int) count);
76 return 4;
77 }
78
79 /* Separate colors for each vertex */
80 for (i = 0; i < igraph_vector_int_size(&color1); i++) {
81 VECTOR(color1)[i] = VECTOR(color2)[(long int)VECTOR(perm)[i]] = i;
82 }
83 igraph_count_isomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &count, 0, 0, 0);
84 if (count != 1) {
85 fprintf(stderr, "Count with separate colors failed, expected %li, got %li.\n",
86 (long int) 1, (long int) count);
87 return 5;
88 }
89
90 /* Try a negative result */
91 igraph_vector_int_fill(&color1, 0);
92 igraph_vector_int_fill(&color2, 0);
93 VECTOR(color1)[0] = 1;
94 igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
95 if (iso) {
96 fprintf(stderr, "Negative test failed.\n");
97 return 6;
98 }
99
100 /* Another negative, same color distribution, different topology */
101 igraph_vector_int_fill(&color1, 0);
102 igraph_vector_int_fill(&color2, 0);
103 VECTOR(color1)[0] = 1;
104 VECTOR(color1)[1] = 1;
105 VECTOR(color2)[0] = 1;
106 VECTOR(color2)[((long int)VECTOR(perm)[1] + 1) % igraph_vcount(&ring2)] = 1;
107 igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
108 if (iso) {
109 fprintf(stderr, "Second negative test failed.\n");
110 return 7;
111 }
112
113 igraph_vector_int_destroy(&color1);
114 igraph_vector_int_destroy(&color2);
115
116 igraph_vector_destroy(&perm);
117 igraph_destroy(&ring2);
118 igraph_destroy(&ring1);
119
120 /* ---------------------------------------------------------------- */
121 /* SUBGRAPH ISOMORPHISM */
122 /* ---------------------------------------------------------------- */
123
124 igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);
125 igraph_ring(&ring2, 80, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);
126
127 /* One color */
128 igraph_vector_int_init(&color1, igraph_vcount(&ring1));
129 igraph_vector_int_init(&color2, igraph_vcount(&ring2));
130 igraph_count_subisomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0,
131 &count, 0, 0, 0);
132 if (count != 42) {
133 fprintf(stderr, "Count with one color failed, expected %li, got %li.\n",
134 (long int) 42, (long int) count);
135 return 31;
136 }
137
138 /* Two colors */
139 for (i = 0; i < igraph_vector_int_size(&color1); i += 2) {
140 VECTOR(color1)[i] = 0;
141 VECTOR(color1)[i + 1] = 1;
142 }
143 for (i = 0; i < igraph_vector_int_size(&color2); i += 2) {
144 VECTOR(color2)[i] = 0;
145 VECTOR(color2)[i + 1] = 1;
146 }
147 igraph_count_subisomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0,
148 &count, 0, 0, 0);
149 if (count != 21) {
150 fprintf(stderr, "Count with two colors failed, expected %li, got %li.\n",
151 (long int) 21, (long int) count);
152 return 32;
153 }
154
155 igraph_vector_int_destroy(&color1);
156 igraph_vector_int_destroy(&color2);
157
158 igraph_destroy(&ring1);
159 igraph_destroy(&ring2);
160
161 /* ---------------------------------------------------------------- */
162 /* EDGE COLORING, GRAPH ISOMORPHISM */
163 /* ---------------------------------------------------------------- */
164
165 igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
166 igraph_vector_init_seq(&perm, 0, igraph_ecount(&ring1) - 1);
167 igraph_vector_shuffle(&perm);
168 igraph_permute_vertices(&ring1, &ring2, &perm);
169 igraph_vector_destroy(&perm);
170
171 /* Everything has the same color */
172 igraph_vector_int_init(&color1, igraph_ecount(&ring1));
173 igraph_vector_int_init(&color2, igraph_ecount(&ring2));
174 igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0, 0, 0, 0);
175 if (!iso) {
176 fprintf(stderr, "Single edge-color failed.\n");
177 return 41;
178 }
179
180 /* Two colors, just counting */
181 for (i = 0; i < igraph_vector_int_size(&color1); i += 2) {
182 VECTOR(color1)[i] = VECTOR(color2)[i] = 0;
183 VECTOR(color1)[i + 1] = VECTOR(color2)[i] = 1;
184 }
185 igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &count, 0, 0, 0);
186 if (count != 100) {
187 fprintf(stderr, "Count with two edge colors failed, expected %li, got %li.\n",
188 (long int) 100, (long int) count);
189 return 42;
190 }
191
192 /* Separate colors for each edge */
193 for (i = 0; i < igraph_vector_int_size(&color1); i++) {
194 VECTOR(color1)[i] = VECTOR(color2)[i] = i;
195 }
196 igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &count, 0, 0, 0);
197 if (count != 1) {
198 fprintf(stderr, "Count with separate edge colors failed, expected %li, got %li.\n",
199 (long int) 1, (long int) count);
200 return 43;
201 }
202
203 /* Try a negative result */
204 igraph_vector_int_fill(&color1, 0);
205 igraph_vector_int_fill(&color2, 0);
206 VECTOR(color1)[0] = 1;
207 igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0, 0, 0, 0);
208 if (iso) {
209 fprintf(stderr, "Negative edge test failed.\n");
210 return 44;
211 }
212
213 /* Another negative, same color distribution, different topology */
214 igraph_vector_int_fill(&color1, 0);
215 igraph_vector_int_fill(&color2, 0);
216 VECTOR(color1)[0] = 1;
217 VECTOR(color1)[1] = 1;
218 VECTOR(color2)[0] = 1;
219 VECTOR(color2)[2] = 1;
220 igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0, 0, 0, 0);
221 if (iso) {
222 fprintf(stderr, "Second negative edge test failed.\n");
223 return 45;
224 }
225
226 igraph_vector_int_destroy(&color1);
227 igraph_vector_int_destroy(&color2);
228
229 igraph_destroy(&ring1);
230 igraph_destroy(&ring2);
231
232 /* ---------------------------------------------------------------- */
233 /* EDGE COLORED SUBGRAPH ISOMORPHISM */
234 /* ---------------------------------------------------------------- */
235
236 igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);
237 igraph_ring(&ring2, 80, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);
238
239 /* One color */
240 igraph_vector_int_init(&color1, igraph_ecount(&ring1));
241 igraph_vector_int_init(&color2, igraph_ecount(&ring2));
242 igraph_count_subisomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2,
243 &count, 0, 0, 0);
244 if (count != 42) {
245 fprintf(stderr, "Count with one edge color failed, expected %li, got %li.\n",
246 (long int) 42, (long int) count);
247 return 51;
248 }
249
250 /* Two colors */
251 for (i = 0; i < igraph_vector_int_size(&color1) - 1; i += 2) {
252 VECTOR(color1)[i] = 0;
253 VECTOR(color1)[i + 1] = 1;
254 }
255 for (i = 0; i < igraph_vector_int_size(&color2) - 1; i += 2) {
256 VECTOR(color2)[i] = 0;
257 VECTOR(color2)[i + 1] = 1;
258 }
259 igraph_count_subisomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2,
260 &count, 0, 0, 0);
261 if (count != 22) {
262 fprintf(stderr, "Count with two edge colors failed, expected %li, got %li.\n",
263 (long int) 22, (long int) count);
264 return 52;
265 }
266
267 igraph_vector_int_destroy(&color1);
268 igraph_vector_int_destroy(&color2);
269
270 igraph_destroy(&ring1);
271 igraph_destroy(&ring2);
272
273 return 0;
274 }
275