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