1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 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
27 #include "test_utilities.inc"
28
29 /* ----------------------------------------------------------- */
30
31 /* Vertices/edges with the same parity match */
compat_parity(const igraph_t * graph1,const igraph_t * graph2,const igraph_integer_t g1_num,const igraph_integer_t g2_num,void * arg)32 igraph_bool_t compat_parity(const igraph_t *graph1,
33 const igraph_t *graph2,
34 const igraph_integer_t g1_num,
35 const igraph_integer_t g2_num,
36 void *arg) {
37 return (g1_num % 2) == (g2_num % 2);
38 }
39
40 /* Nothing vertex/edge 0 in graph1 */
compat_not0(const igraph_t * graph1,const igraph_t * graph2,const igraph_integer_t g1_num,const igraph_integer_t g2_num,void * arg)41 igraph_bool_t compat_not0(const igraph_t *graph1,
42 const igraph_t *graph2,
43 const igraph_integer_t g1_num,
44 const igraph_integer_t g2_num,
45 void *arg) {
46 return g1_num != 0;
47 }
48
match_rings()49 int match_rings() {
50
51 igraph_t r1, r2;
52 igraph_bool_t iso;
53 igraph_integer_t count;
54 igraph_ring(&r1, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
55 igraph_ring(&r2, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
56
57 igraph_isomorphic_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
58 &iso, /*map12=*/ 0, /*map21=*/ 0,
59 /*node_compat_fn=*/ 0, /*edge_compat_fn=*/ 0,
60 /*arg=*/ 0);
61 if (!iso) {
62 exit(1);
63 }
64
65 igraph_isomorphic_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
66 &iso, /*map12=*/ 0, /*map21=*/ 0,
67 compat_parity, /*edge_compat_fn=*/ 0, /*arg=*/ 0);
68 if (!iso) {
69 exit(2);
70 }
71
72 igraph_isomorphic_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
73 &iso, /*map12=*/ 0, /*map21=*/ 0,
74 compat_not0, /*edge_compat_fn=*/ 0, /*arg=*/ 0);
75 if (iso) {
76 exit(3);
77 }
78
79 /* ------- */
80
81 igraph_isomorphic_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
82 &iso, /*map12=*/ 0, /*map21=*/ 0,
83 /*node_compat_fn=*/ 0, compat_parity, /*arg=*/ 0);
84 if (!iso) {
85 exit(4);
86 }
87
88 igraph_isomorphic_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
89 &iso, /*map12=*/ 0, /*map21=*/ 0,
90 /*node_compat_fn=*/ 0, compat_not0, /*arg=*/ 0);
91 if (iso) {
92 exit(5);
93 }
94
95 /* ------- */
96
97 igraph_count_isomorphisms_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
98 &count, /*node_compat_fn=*/ 0,
99 /*edge_compat_fn=*/ 0, /*arg=*/ 0);
100
101 if (count != 20) {
102 exit(6);
103 }
104
105 igraph_count_isomorphisms_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
106 &count, compat_parity, /*edge_compat_fn=*/ 0,
107 /*arg=*/ 0);
108
109 if (count != 10) {
110 exit(7);
111 }
112
113 igraph_count_isomorphisms_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
114 &count, compat_not0, /*edge_compat_fn=*/ 0,
115 /*arg=*/ 0);
116
117 if (count != 0) {
118 exit(8);
119 }
120
121 /* ------- */
122
123 igraph_count_isomorphisms_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
124 &count, /*node_compat_fn=*/ 0, compat_parity,
125 /*arg=*/ 0);
126
127 if (count != 10) {
128 exit(9);
129 }
130
131 igraph_count_isomorphisms_vf2(&r1, &r2, /*colors(4x)*/ 0, 0, 0, 0,
132 &count, /*node_compat_fn=*/ 0, compat_not0,
133 /*arg=*/ 0);
134
135 if (count != 0) {
136 exit(10);
137 }
138
139 igraph_destroy(&r1);
140 igraph_destroy(&r2);
141 return 0;
142 }
143
match_rings_open_closed()144 int match_rings_open_closed() {
145 igraph_t ro, rc;
146 igraph_bool_t iso;
147 igraph_integer_t count;
148 igraph_ring(&ro, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 0);
149 igraph_ring(&rc, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
150
151 igraph_subisomorphic_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
152 &iso, /*map12=*/ 0, /*map21=*/ 0,
153 /*node_compat_fn=*/ 0, /*edge_compat_fn=*/ 0,
154 /*arg=*/ 0);
155 if (!iso) {
156 exit(31);
157 }
158
159 igraph_subisomorphic_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
160 &iso, /*map12=*/ 0, /*map21=*/ 0,
161 compat_parity, /*edge_compat_fn=*/ 0,
162 /*arg=*/ 0);
163 if (!iso) {
164 exit(32);
165 }
166
167 igraph_subisomorphic_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
168 &iso, /*map12=*/ 0, /*map21=*/ 0,
169 compat_not0, /*edge_compat_fn=*/ 0,
170 /*arg=*/ 0);
171 if (iso) {
172 exit(33);
173 }
174
175 /* ------- */
176
177 igraph_subisomorphic_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
178 &iso, /*map12=*/ 0, /*map21=*/ 0,
179 /*node_compat_fn=*/ 0, compat_parity,
180 /*arg=*/ 0);
181 if (!iso) {
182 exit(34);
183 }
184
185 igraph_subisomorphic_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
186 &iso, /*map12=*/ 0, /*map21=*/ 0,
187 /*node_compat_fn=*/ 0, compat_not0,
188 /*arg=*/ 0);
189 if (!iso) {
190 exit(35);
191 }
192
193 /* ------- */
194
195 igraph_count_subisomorphisms_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
196 &count, /*node_compat_fn=*/ 0,
197 /*edge_compat_fn=*/ 0, /*arg=*/ 0);
198
199 if (count != 20) {
200 exit(36);
201 }
202
203 igraph_count_subisomorphisms_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
204 &count, compat_parity,
205 /*edge_compat_fn=*/ 0, /*arg=*/ 0);
206
207 if (count != 10) {
208 exit(37);
209 }
210
211 igraph_count_subisomorphisms_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
212 &count, compat_not0, /*edge_compat_fn=*/ 0,
213 /*arg=*/ 0);
214
215 if (count != 0) {
216 exit(38);
217 }
218
219 /* ------- */
220
221 igraph_count_subisomorphisms_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
222 &count, /*node_compat_fn=*/ 0,
223 compat_parity, /*arg=*/ 0);
224
225 if (count != 10) {
226 exit(39);
227 }
228
229 igraph_count_subisomorphisms_vf2(&rc, &ro, /*colors(4x)*/ 0, 0, 0, 0,
230 &count, /*node_compat_fn=*/ 0, compat_not0,
231 /*arg=*/ 0);
232
233 if (count != 2) {
234 exit(40);
235 }
236
237 igraph_destroy(&ro);
238 igraph_destroy(&rc);
239 return 0;
240 }
241
242 /* ----------------------------------------------------------- */
243
main()244 int main() {
245 match_rings();
246 match_rings_open_closed();
247
248 VERIFY_FINALLY_STACK();
249
250 return 0;
251 }
252