1 /*
2 IGraph library.
3 Copyright (C) 2021 The igraph development team <igraph@igraph.org>
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>.
17 */
18
19 #include <igraph.h>
20 #include "test_utilities.inc"
21
22 /* 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)23 igraph_bool_t compat_parity(const igraph_t *graph1,
24 const igraph_t *graph2,
25 const igraph_integer_t g1_num,
26 const igraph_integer_t g2_num,
27 void *arg) {
28 IGRAPH_UNUSED(graph1);
29 IGRAPH_UNUSED(graph2);
30 IGRAPH_UNUSED(arg);
31 return (g1_num % 2) == (g2_num % 2);
32 }
33
compat_not_arg(const igraph_t * graph1,const igraph_t * graph2,const igraph_integer_t g1_num,const igraph_integer_t g2_num,void * arg)34 igraph_bool_t compat_not_arg(const igraph_t *graph1,
35 const igraph_t *graph2,
36 const igraph_integer_t g1_num,
37 const igraph_integer_t g2_num,
38 void *arg) {
39 IGRAPH_UNUSED(graph1);
40 IGRAPH_UNUSED(graph2);
41 IGRAPH_UNUSED(arg);
42 return g1_num != *(int*)arg + g2_num;
43 }
44
print_and_destroy_maps(igraph_vector_ptr_t * vp)45 void print_and_destroy_maps(igraph_vector_ptr_t *vp) {
46 long int i;
47 for (i = 0; i < igraph_vector_ptr_size(vp); i++) {
48 print_vector(VECTOR(*vp)[i]);
49 igraph_vector_destroy(VECTOR(*vp)[i]);
50 igraph_free(VECTOR(*vp)[i]);
51 }
52 igraph_vector_ptr_destroy(vp);
53 }
54
check_print_destroy(igraph_t * g1,igraph_t * g2,igraph_vector_int_t * vertex_color1,igraph_vector_int_t * vertex_color2,igraph_vector_int_t * edge_color1,igraph_vector_int_t * edge_color2,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg,int error)55 void check_print_destroy(igraph_t *g1,
56 igraph_t *g2,
57 igraph_vector_int_t *vertex_color1,
58 igraph_vector_int_t *vertex_color2,
59 igraph_vector_int_t *edge_color1,
60 igraph_vector_int_t *edge_color2,
61 igraph_isocompat_t *node_compat_fn,
62 igraph_isocompat_t *edge_compat_fn,
63 void *arg,
64 int error) {
65 igraph_vector_ptr_t maps;
66 igraph_vector_ptr_init(&maps, 0);
67 IGRAPH_ASSERT(igraph_get_isomorphisms_vf2(g1, g2, vertex_color1, vertex_color2, edge_color1, edge_color2, &maps, node_compat_fn, edge_compat_fn, arg) == error);
68 print_and_destroy_maps(&maps);
69 printf("\n");
70 }
71
check_print_destroy_simple(igraph_t * g1,igraph_t * g2)72 void check_print_destroy_simple(igraph_t *g1, igraph_t *g2) {
73 check_print_destroy(g1, g2, NULL, NULL, NULL, NULL, NULL, NULL, NULL, IGRAPH_SUCCESS);
74 }
75
main()76 int main() {
77 igraph_t ring, ring_dir;
78 igraph_t g_0, g_1;
79 igraph_vector_int_t coloring;
80 int three = 3;
81
82 igraph_vector_int_init_int(&coloring, 5, 0, 1, 0, 1, 0);
83 igraph_small(&g_0, 0, 0, -1);
84 igraph_small(&g_1, 1, 0, -1);
85 igraph_ring(&ring, 5, /*directed*/ 0, /*mutual*/ 0, /*circular*/ 1);
86 igraph_ring(&ring_dir, 5, /*directed*/ 1, /*mutual*/ 0, /*circular*/ 1);
87
88 printf("Two empty graphs:\n");
89 check_print_destroy_simple(&g_0, &g_0);
90
91 printf("Two singleton graphs:\n");
92 check_print_destroy_simple(&g_1, &g_1);
93
94 printf("Empty and singleton graphs:\n");
95 check_print_destroy_simple(&g_0, &g_1);
96
97 printf("Two rings:\n");
98 check_print_destroy_simple(&ring, &ring);
99
100 printf("Two directed rings:\n");
101 check_print_destroy_simple(&ring_dir, &ring_dir);
102
103 printf("Two rings where node parity should be equal:\n");
104 check_print_destroy(&ring, &ring, NULL, NULL, NULL, NULL, &compat_parity, NULL, NULL, IGRAPH_SUCCESS);
105
106 printf("Two rings where edge parity should be equal:\n");
107 check_print_destroy(&ring, &ring, NULL, NULL, NULL, NULL, NULL, &compat_parity, NULL, IGRAPH_SUCCESS);
108
109 printf("Two rings with only one vertex coloring:\n");
110 check_print_destroy(&ring, &ring, &coloring, NULL, NULL, NULL, NULL, NULL, NULL, IGRAPH_SUCCESS);
111
112 printf("Two rings with vertex coloring:\n");
113 check_print_destroy(&ring, &ring, &coloring, &coloring, NULL, NULL, NULL, NULL, NULL, IGRAPH_SUCCESS);
114
115 printf("Two rings with edge coloring:\n");
116 check_print_destroy(&ring, &ring, NULL, NULL, &coloring, &coloring, NULL, NULL, NULL, IGRAPH_SUCCESS);
117
118 printf("Two rings where node of graph 1 should not be 3 higher than node of graph 2:\n");
119 check_print_destroy(&ring, &ring, NULL, NULL, NULL, NULL, &compat_not_arg, NULL, &three, IGRAPH_SUCCESS);
120
121 VERIFY_FINALLY_STACK();
122 igraph_set_error_handler(igraph_error_handler_ignore);
123
124 printf("Two rings with different directedness.\n");
125 check_print_destroy(&ring, &ring_dir, NULL, NULL, NULL, NULL, NULL, NULL, NULL, IGRAPH_EINVAL);
126
127 igraph_destroy(&g_0);
128 igraph_destroy(&g_1);
129 igraph_destroy(&ring);
130 igraph_destroy(&ring_dir);
131 igraph_vector_int_destroy(&coloring);
132
133 VERIFY_FINALLY_STACK();
134 return 0;
135 }
136