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_topology.h"
25 #include "igraph_memory.h"
26 #include "igraph_adjlist.h"
27 #include "igraph_interface.h"
28 #include "igraph_interrupt_internal.h"
29 #include "igraph_constructors.h"
30 #include "igraph_conversion.h"
31 #include "igraph_stack.h"
32 #include "igraph_attributes.h"
33 #include "igraph_structural.h"
34 #include "igraph_isoclasses.h"
35 #include "config.h"
36
37 const unsigned int igraph_i_isoclass_3[] = { 0, 1, 1, 3, 1, 5, 6, 7,
38 1, 6, 10, 11, 3, 7, 11, 15,
39 1, 6, 5, 7, 10, 21, 21, 23,
40 6, 25, 21, 27, 11, 27, 30, 31,
41 1, 10, 6, 11, 6, 21, 25, 27,
42 5, 21, 21, 30, 7, 23, 27, 31,
43 3, 11, 7, 15, 11, 30, 27, 31,
44 7, 27, 23, 31, 15, 31, 31, 63
45 };
46
47 const unsigned int igraph_i_isoclass_3_idx[] = { 0, 4, 16, 1, 0, 32, 2, 8, 0 };
48
49 const unsigned int igraph_i_isoclass_4[] = {
50 0, 1, 1, 3, 1, 3, 3, 7, 1, 9, 10, 11, 10,
51 11, 14, 15, 1, 10, 18, 19, 20, 21, 22, 23, 3, 11,
52 19, 27, 21, 29, 30, 31, 1, 10, 20, 21, 18, 19, 22,
53 23, 3, 11, 21, 29, 19, 27, 30, 31, 3, 14, 22, 30,
54 22, 30, 54, 55, 7, 15, 23, 31, 23, 31, 55, 63, 1,
55 10, 9, 11, 10, 14, 11, 15, 18, 73, 73, 75, 76, 77,
56 77, 79, 10, 81, 73, 83, 84, 85, 86, 87, 19, 83, 90,
57 91, 92, 93, 94, 95, 20, 84, 98, 99, 100, 101, 102, 103,
58 22, 86, 106, 107, 108, 109, 110, 111, 21, 85, 106, 115, 116,
59 117, 118, 119, 23, 87, 122, 123, 124, 125, 126, 127, 1, 18,
60 10, 19, 20, 22, 21, 23, 10, 73, 81, 83, 84, 86, 85,
61 87, 9, 73, 73, 90, 98, 106, 106, 122, 11, 75, 83, 91,
62 99, 107, 115, 123, 10, 76, 84, 92, 100, 108, 116, 124, 14,
63 77, 85, 93, 101, 109, 117, 125, 11, 77, 86, 94, 102, 110,
64 118, 126, 15, 79, 87, 95, 103, 111, 119, 127, 3, 19, 11,
65 27, 21, 30, 29, 31, 19, 90, 83, 91, 92, 94, 93, 95,
66 11, 83, 75, 91, 99, 115, 107, 123, 27, 91, 91, 219, 220,
67 221, 221, 223, 21, 92, 99, 220, 228, 229, 230, 231, 30, 94,
68 115, 221, 229, 237, 238, 239, 29, 93, 107, 221, 230, 238, 246,
69 247, 31, 95, 123, 223, 231, 239, 247, 255, 1, 20, 10, 21,
70 18, 22, 19, 23, 20, 98, 84, 99, 100, 102, 101, 103, 10,
71 84, 76, 92, 100, 116, 108, 124, 21, 99, 92, 220, 228, 230,
72 229, 231, 18, 100, 100, 228, 292, 293, 293, 295, 22, 102, 116,
73 230, 293, 301, 302, 303, 19, 101, 108, 229, 293, 302, 310, 311,
74 23, 103, 124, 231, 295, 303, 311, 319, 3, 21, 11, 29, 19,
75 30, 27, 31, 22, 106, 86, 107, 108, 110, 109, 111, 14, 85,
76 77, 93, 101, 117, 109, 125, 30, 115, 94, 221, 229, 238, 237,
77 239, 22, 116, 102, 230, 293, 302, 301, 303, 54, 118, 118, 246,
78 310, 365, 365, 367, 30, 117, 110, 238, 302, 373, 365, 375, 55,
79 119, 126, 247, 311, 375, 382, 383, 3, 22, 14, 30, 22, 54,
80 30, 55, 21, 106, 85, 115, 116, 118, 117, 119, 11, 86, 77,
81 94, 102, 118, 110, 126, 29, 107, 93, 221, 230, 246, 238, 247,
82 19, 108, 101, 229, 293, 310, 302, 311, 30, 110, 117, 238, 302,
83 365, 373, 375, 27, 109, 109, 237, 301, 365, 365, 382, 31, 111,
84 125, 239, 303, 367, 375, 383, 7, 23, 15, 31, 23, 55, 31,
85 63, 23, 122, 87, 123, 124, 126, 125, 127, 15, 87, 79, 95,
86 103, 119, 111, 127, 31, 123, 95, 223, 231, 247, 239, 255, 23,
87 124, 103, 231, 295, 311, 303, 319, 55, 126, 119, 247, 311, 382,
88 375, 383, 31, 125, 111, 239, 303, 375, 367, 383, 63, 127, 127,
89 255, 319, 383, 383, 511, 1, 10, 10, 14, 9, 11, 11, 15,
90 18, 73, 76, 77, 73, 75, 77, 79, 20, 84, 100, 101, 98,
91 99, 102, 103, 22, 86, 108, 109, 106, 107, 110, 111, 10, 81,
92 84, 85, 73, 83, 86, 87, 19, 83, 92, 93, 90, 91, 94,
93 95, 21, 85, 116, 117, 106, 115, 118, 119, 23, 87, 124, 125,
94 122, 123, 126, 127, 18, 76, 73, 77, 73, 77, 75, 79, 292,
95 585, 585, 587, 585, 587, 587, 591, 100, 593, 594, 595, 596, 597,
96 598, 599, 293, 601, 602, 603, 604, 605, 606, 607, 100, 593, 596,
97 597, 594, 595, 598, 599, 293, 601, 604, 605, 602, 603, 606, 607,
98 228, 625, 626, 627, 626, 627, 630, 631, 295, 633, 634, 635, 634,
99 635, 638, 639, 20, 100, 84, 101, 98, 102, 99, 103, 100, 594,
100 593, 595, 596, 598, 597, 599, 98, 596, 596, 659, 660, 661, 661,
101 663, 102, 598, 666, 667, 661, 669, 670, 671, 84, 593, 674, 675,
102 596, 666, 678, 679, 101, 595, 675, 683, 659, 667, 686, 687, 99,
103 597, 678, 686, 661, 670, 694, 695, 103, 599, 679, 687, 663, 671,
104 695, 703, 22, 108, 86, 109, 106, 110, 107, 111, 293, 602, 601,
105 603, 604, 606, 605, 607, 102, 666, 598, 667, 661, 670, 669, 671,
106 301, 729, 729, 731, 732, 733, 733, 735, 116, 737, 678, 739, 626,
107 741, 742, 743, 302, 745, 746, 747, 748, 749, 750, 751, 230, 753,
108 742, 755, 756, 757, 758, 759, 303, 761, 762, 763, 764, 765, 766,
109 767, 10, 84, 81, 85, 73, 86, 83, 87, 100, 596, 593, 597,
110 594, 598, 595, 599, 84, 674, 593, 675, 596, 678, 666, 679, 116,
111 678, 737, 739, 626, 742, 741, 743, 76, 593, 593, 625, 585, 601,
112 601, 633, 108, 666, 737, 753, 602, 729, 745, 761, 92, 675, 737,
113 819, 604, 746, 822, 823, 124, 679, 826, 827, 634, 762, 830, 831,
114 19, 92, 83, 93, 90, 94, 91, 95, 293, 604, 601, 605, 602,
115 606, 603, 607, 101, 675, 595, 683, 659, 686, 667, 687, 302, 746,
116 745, 747, 748, 750, 749, 751, 108, 737, 666, 753, 602, 745, 729,
117 761, 310, 822, 822, 875, 876, 877, 877, 879, 229, 819, 741, 883,
118 748, 885, 886, 887, 311, 823, 830, 891, 892, 893, 894, 895, 21,
119 116, 85, 117, 106, 118, 115, 119, 228, 626, 625, 627, 626, 630,
120 627, 631, 99, 678, 597, 686, 661, 694, 670, 695, 230, 742, 753,
121 755, 756, 758, 757, 759, 92, 737, 675, 819, 604, 822, 746, 823,
122 229, 741, 819, 883, 748, 886, 885, 887, 220, 739, 739, 947, 732,
123 949, 949, 951, 231, 743, 827, 955, 764, 957, 958, 959, 23, 124,
124 87, 125, 122, 126, 123, 127, 295, 634, 633, 635, 634, 638, 635,
125 639, 103, 679, 599, 687, 663, 695, 671, 703, 303, 762, 761, 763,
126 764, 766, 765, 767, 124, 826, 679, 827, 634, 830, 762, 831, 311,
127 830, 823, 891, 892, 894, 893, 895, 231, 827, 743, 955, 764, 958,
128 957, 959, 319, 831, 831, 1019, 1020, 1021, 1021, 1023, 1, 18, 20,
129 22, 10, 19, 21, 23, 10, 73, 84, 86, 81, 83, 85, 87,
130 10, 76, 100, 108, 84, 92, 116, 124, 14, 77, 101, 109, 85,
131 93, 117, 125, 9, 73, 98, 106, 73, 90, 106, 122, 11, 75,
132 99, 107, 83, 91, 115, 123, 11, 77, 102, 110, 86, 94, 118,
133 126, 15, 79, 103, 111, 87, 95, 119, 127, 20, 100, 98, 102,
134 84, 101, 99, 103, 100, 594, 596, 598, 593, 595, 597, 599, 84,
135 593, 596, 666, 674, 675, 678, 679, 101, 595, 659, 667, 675, 683,
136 686, 687, 98, 596, 660, 661, 596, 659, 661, 663, 102, 598, 661,
137 669, 666, 667, 670, 671, 99, 597, 661, 670, 678, 686, 694, 695,
138 103, 599, 663, 671, 679, 687, 695, 703, 18, 292, 100, 293, 100,
139 293, 228, 295, 76, 585, 593, 601, 593, 601, 625, 633, 73, 585,
140 594, 602, 596, 604, 626, 634, 77, 587, 595, 603, 597, 605, 627,
141 635, 73, 585, 596, 604, 594, 602, 626, 634, 77, 587, 597, 605,
142 595, 603, 627, 635, 75, 587, 598, 606, 598, 606, 630, 638, 79,
143 591, 599, 607, 599, 607, 631, 639, 22, 293, 102, 301, 116, 302,
144 230, 303, 108, 602, 666, 729, 737, 745, 753, 761, 86, 601, 598,
145 729, 678, 746, 742, 762, 109, 603, 667, 731, 739, 747, 755, 763,
146 106, 604, 661, 732, 626, 748, 756, 764, 110, 606, 670, 733, 741,
147 749, 757, 765, 107, 605, 669, 733, 742, 750, 758, 766, 111, 607,
148 671, 735, 743, 751, 759, 767, 10, 100, 84, 116, 76, 108, 92,
149 124, 84, 596, 674, 678, 593, 666, 675, 679, 81, 593, 593, 737,
150 593, 737, 737, 826, 85, 597, 675, 739, 625, 753, 819, 827, 73,
151 594, 596, 626, 585, 602, 604, 634, 86, 598, 678, 742, 601, 729,
152 746, 762, 83, 595, 666, 741, 601, 745, 822, 830, 87, 599, 679,
153 743, 633, 761, 823, 831, 21, 228, 99, 230, 92, 229, 220, 231,
154 116, 626, 678, 742, 737, 741, 739, 743, 85, 625, 597, 753, 675,
155 819, 739, 827, 117, 627, 686, 755, 819, 883, 947, 955, 106, 626,
156 661, 756, 604, 748, 732, 764, 118, 630, 694, 758, 822, 886, 949,
157 957, 115, 627, 670, 757, 746, 885, 949, 958, 119, 631, 695, 759,
158 823, 887, 951, 959, 19, 293, 101, 302, 108, 310, 229, 311, 92,
159 604, 675, 746, 737, 822, 819, 823, 83, 601, 595, 745, 666, 822,
160 741, 830, 93, 605, 683, 747, 753, 875, 883, 891, 90, 602, 659,
161 748, 602, 876, 748, 892, 94, 606, 686, 750, 745, 877, 885, 893,
162 91, 603, 667, 749, 729, 877, 886, 894, 95, 607, 687, 751, 761,
163 879, 887, 895, 23, 295, 103, 303, 124, 311, 231, 319, 124, 634,
164 679, 762, 826, 830, 827, 831, 87, 633, 599, 761, 679, 823, 743,
165 831, 125, 635, 687, 763, 827, 891, 955, 1019, 122, 634, 663, 764,
166 634, 892, 764, 1020, 126, 638, 695, 766, 830, 894, 958, 1021, 123,
167 635, 671, 765, 762, 893, 957, 1021, 127, 639, 703, 767, 831, 895,
168 959, 1023, 3, 19, 21, 30, 11, 27, 29, 31, 19, 90, 92,
169 94, 83, 91, 93, 95, 21, 92, 228, 229, 99, 220, 230, 231,
170 30, 94, 229, 237, 115, 221, 238, 239, 11, 83, 99, 115, 75,
171 91, 107, 123, 27, 91, 220, 221, 91, 219, 221, 223, 29, 93,
172 230, 238, 107, 221, 246, 247, 31, 95, 231, 239, 123, 223, 247,
173 255, 22, 108, 106, 110, 86, 109, 107, 111, 293, 602, 604, 606,
174 601, 603, 605, 607, 116, 737, 626, 741, 678, 739, 742, 743, 302,
175 745, 748, 749, 746, 747, 750, 751, 102, 666, 661, 670, 598, 667,
176 669, 671, 301, 729, 732, 733, 729, 731, 733, 735, 230, 753, 756,
177 757, 742, 755, 758, 759, 303, 761, 764, 765, 762, 763, 766, 767,
178 22, 293, 116, 302, 102, 301, 230, 303, 108, 602, 737, 745, 666,
179 729, 753, 761, 106, 604, 626, 748, 661, 732, 756, 764, 110, 606,
180 741, 749, 670, 733, 757, 765, 86, 601, 678, 746, 598, 729, 742,
181 762, 109, 603, 739, 747, 667, 731, 755, 763, 107, 605, 742, 750,
182 669, 733, 758, 766, 111, 607, 743, 751, 671, 735, 759, 767, 54,
183 310, 118, 365, 118, 365, 246, 367, 310, 876, 822, 877, 822, 877,
184 875, 879, 118, 822, 630, 886, 694, 949, 758, 957, 365, 877, 886,
185 1755, 949, 1757, 1758, 1759, 118, 822, 694, 949, 630, 886, 758, 957,
186 365, 877, 949, 1757, 886, 1755, 1758, 1759, 246, 875, 758, 1758, 758,
187 1758, 1782, 1783, 367, 879, 957, 1759, 957, 1759, 1783, 1791, 14, 101,
188 85, 117, 77, 109, 93, 125, 101, 659, 675, 686, 595, 667, 683,
189 687, 85, 675, 625, 819, 597, 739, 753, 827, 117, 686, 819, 947,
190 627, 755, 883, 955, 77, 595, 597, 627, 587, 603, 605, 635, 109,
191 667, 739, 755, 603, 731, 747, 763, 93, 683, 753, 883, 605, 747,
192 875, 891, 125, 687, 827, 955, 635, 763, 891, 1019, 30, 229, 115,
193 238, 94, 237, 221, 239, 302, 748, 746, 750, 745, 749, 747, 751,
194 117, 819, 627, 883, 686, 947, 755, 955, 373, 885, 885, 1883, 885,
195 1883, 1883, 1887, 110, 741, 670, 757, 606, 749, 733, 765, 365, 886,
196 949, 1758, 877, 1755, 1757, 1759, 238, 883, 757, 1907, 750, 1883, 1758,
197 1911, 375, 887, 958, 1911, 893, 1917, 1918, 1919, 30, 302, 117, 373,
198 110, 365, 238, 375, 229, 748, 819, 885, 741, 886, 883, 887, 115,
199 746, 627, 885, 670, 949, 757, 958, 238, 750, 883, 1883, 757, 1758,
200 1907, 1911, 94, 745, 686, 885, 606, 877, 750, 893, 237, 749, 947,
201 1883, 749, 1755, 1883, 1917, 221, 747, 755, 1883, 733, 1757, 1758, 1918,
202 239, 751, 955, 1887, 765, 1759, 1911, 1919, 55, 311, 119, 375, 126,
203 382, 247, 383, 311, 892, 823, 893, 830, 894, 891, 895, 119, 823,
204 631, 887, 695, 951, 759, 959, 375, 893, 887, 1917, 958, 1918, 1911,
205 1919, 126, 830, 695, 958, 638, 894, 766, 1021, 382, 894, 951, 1918,
206 894, 2029, 1918, 2031, 247, 891, 759, 1911, 766, 1918, 1783, 2039, 383,
207 895, 959, 1919, 1021, 2031, 2039, 2047, 1, 20, 18, 22, 10, 21,
208 19, 23, 20, 98, 100, 102, 84, 99, 101, 103, 18, 100, 292,
209 293, 100, 228, 293, 295, 22, 102, 293, 301, 116, 230, 302, 303,
210 10, 84, 100, 116, 76, 92, 108, 124, 21, 99, 228, 230, 92,
211 220, 229, 231, 19, 101, 293, 302, 108, 229, 310, 311, 23, 103,
212 295, 303, 124, 231, 311, 319, 10, 84, 73, 86, 81, 85, 83,
213 87, 100, 596, 594, 598, 593, 597, 595, 599, 76, 593, 585, 601,
214 593, 625, 601, 633, 108, 666, 602, 729, 737, 753, 745, 761, 84,
215 674, 596, 678, 593, 675, 666, 679, 116, 678, 626, 742, 737, 739,
216 741, 743, 92, 675, 604, 746, 737, 819, 822, 823, 124, 679, 634,
217 762, 826, 827, 830, 831, 10, 100, 76, 108, 84, 116, 92, 124,
218 84, 596, 593, 666, 674, 678, 675, 679, 73, 594, 585, 602, 596,
219 626, 604, 634, 86, 598, 601, 729, 678, 742, 746, 762, 81, 593,
220 593, 737, 593, 737, 737, 826, 85, 597, 625, 753, 675, 739, 819,
221 827, 83, 595, 601, 745, 666, 741, 822, 830, 87, 599, 633, 761,
222 679, 743, 823, 831, 14, 101, 77, 109, 85, 117, 93, 125, 101,
223 659, 595, 667, 675, 686, 683, 687, 77, 595, 587, 603, 597, 627,
224 605, 635, 109, 667, 603, 731, 739, 755, 747, 763, 85, 675, 597,
225 739, 625, 819, 753, 827, 117, 686, 627, 755, 819, 947, 883, 955,
226 93, 683, 605, 747, 753, 883, 875, 891, 125, 687, 635, 763, 827,
227 955, 891, 1019, 9, 98, 73, 106, 73, 106, 90, 122, 98, 660,
228 596, 661, 596, 661, 659, 663, 73, 596, 585, 604, 594, 626, 602,
229 634, 106, 661, 604, 732, 626, 756, 748, 764, 73, 596, 594, 626,
230 585, 604, 602, 634, 106, 661, 626, 756, 604, 732, 748, 764, 90,
231 659, 602, 748, 602, 748, 876, 892, 122, 663, 634, 764, 634, 764,
232 892, 1020, 11, 99, 75, 107, 83, 115, 91, 123, 102, 661, 598,
233 669, 666, 670, 667, 671, 77, 597, 587, 605, 595, 627, 603, 635,
234 110, 670, 606, 733, 741, 757, 749, 765, 86, 678, 598, 742, 601,
235 746, 729, 762, 118, 694, 630, 758, 822, 949, 886, 957, 94, 686,
236 606, 750, 745, 885, 877, 893, 126, 695, 638, 766, 830, 958, 894,
237 1021, 11, 102, 77, 110, 86, 118, 94, 126, 99, 661, 597, 670,
238 678, 694, 686, 695, 75, 598, 587, 606, 598, 630, 606, 638, 107,
239 669, 605, 733, 742, 758, 750, 766, 83, 666, 595, 741, 601, 822,
240 745, 830, 115, 670, 627, 757, 746, 949, 885, 958, 91, 667, 603,
241 749, 729, 886, 877, 894, 123, 671, 635, 765, 762, 957, 893, 1021,
242 15, 103, 79, 111, 87, 119, 95, 127, 103, 663, 599, 671, 679,
243 695, 687, 703, 79, 599, 591, 607, 599, 631, 607, 639, 111, 671,
244 607, 735, 743, 759, 751, 767, 87, 679, 599, 743, 633, 823, 761,
245 831, 119, 695, 631, 759, 823, 951, 887, 959, 95, 687, 607, 751,
246 761, 887, 879, 895, 127, 703, 639, 767, 831, 959, 895, 1023, 3,
247 21, 19, 30, 11, 29, 27, 31, 22, 106, 108, 110, 86, 107,
248 109, 111, 22, 116, 293, 302, 102, 230, 301, 303, 54, 118, 310,
249 365, 118, 246, 365, 367, 14, 85, 101, 117, 77, 93, 109, 125,
250 30, 115, 229, 238, 94, 221, 237, 239, 30, 117, 302, 373, 110,
251 238, 365, 375, 55, 119, 311, 375, 126, 247, 382, 383, 19, 92,
252 90, 94, 83, 93, 91, 95, 293, 604, 602, 606, 601, 605, 603,
253 607, 108, 737, 602, 745, 666, 753, 729, 761, 310, 822, 876, 877,
254 822, 875, 877, 879, 101, 675, 659, 686, 595, 683, 667, 687, 302,
255 746, 748, 750, 745, 747, 749, 751, 229, 819, 748, 885, 741, 883,
256 886, 887, 311, 823, 892, 893, 830, 891, 894, 895, 21, 228, 92,
257 229, 99, 230, 220, 231, 116, 626, 737, 741, 678, 742, 739, 743,
258 106, 626, 604, 748, 661, 756, 732, 764, 118, 630, 822, 886, 694,
259 758, 949, 957, 85, 625, 675, 819, 597, 753, 739, 827, 117, 627,
260 819, 883, 686, 755, 947, 955, 115, 627, 746, 885, 670, 757, 949,
261 958, 119, 631, 823, 887, 695, 759, 951, 959, 30, 229, 94, 237,
262 115, 238, 221, 239, 302, 748, 745, 749, 746, 750, 747, 751, 110,
263 741, 606, 749, 670, 757, 733, 765, 365, 886, 877, 1755, 949, 1758,
264 1757, 1759, 117, 819, 686, 947, 627, 883, 755, 955, 373, 885, 885,
265 1883, 885, 1883, 1883, 1887, 238, 883, 750, 1883, 757, 1907, 1758, 1911,
266 375, 887, 893, 1917, 958, 1911, 1918, 1919, 11, 99, 83, 115, 75,
267 107, 91, 123, 102, 661, 666, 670, 598, 669, 667, 671, 86, 678,
268 601, 746, 598, 742, 729, 762, 118, 694, 822, 949, 630, 758, 886,
269 957, 77, 597, 595, 627, 587, 605, 603, 635, 110, 670, 741, 757,
270 606, 733, 749, 765, 94, 686, 745, 885, 606, 750, 877, 893, 126,
271 695, 830, 958, 638, 766, 894, 1021, 27, 220, 91, 221, 91, 221,
272 219, 223, 301, 732, 729, 733, 729, 733, 731, 735, 109, 739, 603,
273 747, 667, 755, 731, 763, 365, 949, 877, 1757, 886, 1758, 1755, 1759,
274 109, 739, 667, 755, 603, 747, 731, 763, 365, 949, 886, 1758, 877,
275 1757, 1755, 1759, 237, 947, 749, 1883, 749, 1883, 1755, 1917, 382, 951,
276 894, 1918, 894, 1918, 2029, 2031, 29, 230, 93, 238, 107, 246, 221,
277 247, 230, 756, 753, 757, 742, 758, 755, 759, 107, 742, 605, 750,
278 669, 758, 733, 766, 246, 758, 875, 1758, 758, 1782, 1758, 1783, 93,
279 753, 683, 883, 605, 875, 747, 891, 238, 757, 883, 1907, 750, 1758,
280 1883, 1911, 221, 755, 747, 1883, 733, 1758, 1757, 1918, 247, 759, 891,
281 1911, 766, 1783, 1918, 2039, 31, 231, 95, 239, 123, 247, 223, 255,
282 303, 764, 761, 765, 762, 766, 763, 767, 111, 743, 607, 751, 671,
283 759, 735, 767, 367, 957, 879, 1759, 957, 1783, 1759, 1791, 125, 827,
284 687, 955, 635, 891, 763, 1019, 375, 958, 887, 1911, 893, 1918, 1917,
285 1919, 239, 955, 751, 1887, 765, 1911, 1759, 1919, 383, 959, 895, 1919,
286 1021, 2039, 2031, 2047, 3, 22, 22, 54, 14, 30, 30, 55, 21,
287 106, 116, 118, 85, 115, 117, 119, 19, 108, 293, 310, 101, 229,
288 302, 311, 30, 110, 302, 365, 117, 238, 373, 375, 11, 86, 102,
289 118, 77, 94, 110, 126, 29, 107, 230, 246, 93, 221, 238, 247,
290 27, 109, 301, 365, 109, 237, 365, 382, 31, 111, 303, 367, 125,
291 239, 375, 383, 21, 116, 106, 118, 85, 117, 115, 119, 228, 626,
292 626, 630, 625, 627, 627, 631, 92, 737, 604, 822, 675, 819, 746,
293 823, 229, 741, 748, 886, 819, 883, 885, 887, 99, 678, 661, 694,
294 597, 686, 670, 695, 230, 742, 756, 758, 753, 755, 757, 759, 220,
295 739, 732, 949, 739, 947, 949, 951, 231, 743, 764, 957, 827, 955,
296 958, 959, 19, 293, 108, 310, 101, 302, 229, 311, 92, 604, 737,
297 822, 675, 746, 819, 823, 90, 602, 602, 876, 659, 748, 748, 892,
298 94, 606, 745, 877, 686, 750, 885, 893, 83, 601, 666, 822, 595,
299 745, 741, 830, 93, 605, 753, 875, 683, 747, 883, 891, 91, 603,
300 729, 877, 667, 749, 886, 894, 95, 607, 761, 879, 687, 751, 887,
301 895, 30, 302, 110, 365, 117, 373, 238, 375, 229, 748, 741, 886,
302 819, 885, 883, 887, 94, 745, 606, 877, 686, 885, 750, 893, 237,
303 749, 749, 1755, 947, 1883, 1883, 1917, 115, 746, 670, 949, 627, 885,
304 757, 958, 238, 750, 757, 1758, 883, 1883, 1907, 1911, 221, 747, 733,
305 1757, 755, 1883, 1758, 1918, 239, 751, 765, 1759, 955, 1887, 1911, 1919,
306 11, 102, 86, 118, 77, 110, 94, 126, 99, 661, 678, 694, 597,
307 670, 686, 695, 83, 666, 601, 822, 595, 741, 745, 830, 115, 670,
308 746, 949, 627, 757, 885, 958, 75, 598, 598, 630, 587, 606, 606,
309 638, 107, 669, 742, 758, 605, 733, 750, 766, 91, 667, 729, 886,
310 603, 749, 877, 894, 123, 671, 762, 957, 635, 765, 893, 1021, 29,
311 230, 107, 246, 93, 238, 221, 247, 230, 756, 742, 758, 753, 757,
312 755, 759, 93, 753, 605, 875, 683, 883, 747, 891, 238, 757, 750,
313 1758, 883, 1907, 1883, 1911, 107, 742, 669, 758, 605, 750, 733, 766,
314 246, 758, 758, 1782, 875, 1758, 1758, 1783, 221, 755, 733, 1758, 747,
315 1883, 1757, 1918, 247, 759, 766, 1783, 891, 1911, 1918, 2039, 27, 301,
316 109, 365, 109, 365, 237, 382, 220, 732, 739, 949, 739, 949, 947,
317 951, 91, 729, 603, 877, 667, 886, 749, 894, 221, 733, 747, 1757,
318 755, 1758, 1883, 1918, 91, 729, 667, 886, 603, 877, 749, 894, 221,
319 733, 755, 1758, 747, 1757, 1883, 1918, 219, 731, 731, 1755, 731, 1755,
320 1755, 2029, 223, 735, 763, 1759, 763, 1759, 1917, 2031, 31, 303, 111,
321 367, 125, 375, 239, 383, 231, 764, 743, 957, 827, 958, 955, 959,
322 95, 761, 607, 879, 687, 887, 751, 895, 239, 765, 751, 1759, 955,
323 1911, 1887, 1919, 123, 762, 671, 957, 635, 893, 765, 1021, 247, 766,
324 759, 1783, 891, 1918, 1911, 2039, 223, 763, 735, 1759, 763, 1917, 1759,
325 2031, 255, 767, 767, 1791, 1019, 1919, 1919, 2047, 7, 23, 23, 55,
326 15, 31, 31, 63, 23, 122, 124, 126, 87, 123, 125, 127, 23,
327 124, 295, 311, 103, 231, 303, 319, 55, 126, 311, 382, 119, 247,
328 375, 383, 15, 87, 103, 119, 79, 95, 111, 127, 31, 123, 231,
329 247, 95, 223, 239, 255, 31, 125, 303, 375, 111, 239, 367, 383,
330 63, 127, 319, 383, 127, 255, 383, 511, 23, 124, 122, 126, 87,
331 125, 123, 127, 295, 634, 634, 638, 633, 635, 635, 639, 124, 826,
332 634, 830, 679, 827, 762, 831, 311, 830, 892, 894, 823, 891, 893,
333 895, 103, 679, 663, 695, 599, 687, 671, 703, 303, 762, 764, 766,
334 761, 763, 765, 767, 231, 827, 764, 958, 743, 955, 957, 959, 319,
335 831, 1020, 1021, 831, 1019, 1021, 1023, 23, 295, 124, 311, 103, 303,
336 231, 319, 124, 634, 826, 830, 679, 762, 827, 831, 122, 634, 634,
337 892, 663, 764, 764, 1020, 126, 638, 830, 894, 695, 766, 958, 1021,
338 87, 633, 679, 823, 599, 761, 743, 831, 125, 635, 827, 891, 687,
339 763, 955, 1019, 123, 635, 762, 893, 671, 765, 957, 1021, 127, 639,
340 831, 895, 703, 767, 959, 1023, 55, 311, 126, 382, 119, 375, 247,
341 383, 311, 892, 830, 894, 823, 893, 891, 895, 126, 830, 638, 894,
342 695, 958, 766, 1021, 382, 894, 894, 2029, 951, 1918, 1918, 2031, 119,
343 823, 695, 951, 631, 887, 759, 959, 375, 893, 958, 1918, 887, 1917,
344 1911, 1919, 247, 891, 766, 1918, 759, 1911, 1783, 2039, 383, 895, 1021,
345 2031, 959, 1919, 2039, 2047, 15, 103, 87, 119, 79, 111, 95, 127,
346 103, 663, 679, 695, 599, 671, 687, 703, 87, 679, 633, 823, 599,
347 743, 761, 831, 119, 695, 823, 951, 631, 759, 887, 959, 79, 599,
348 599, 631, 591, 607, 607, 639, 111, 671, 743, 759, 607, 735, 751,
349 767, 95, 687, 761, 887, 607, 751, 879, 895, 127, 703, 831, 959,
350 639, 767, 895, 1023, 31, 231, 123, 247, 95, 239, 223, 255, 303,
351 764, 762, 766, 761, 765, 763, 767, 125, 827, 635, 891, 687, 955,
352 763, 1019, 375, 958, 893, 1918, 887, 1911, 1917, 1919, 111, 743, 671,
353 759, 607, 751, 735, 767, 367, 957, 957, 1783, 879, 1759, 1759, 1791,
354 239, 955, 765, 1911, 751, 1887, 1759, 1919, 383, 959, 1021, 2039, 895,
355 1919, 2031, 2047, 31, 303, 125, 375, 111, 367, 239, 383, 231, 764,
356 827, 958, 743, 957, 955, 959, 123, 762, 635, 893, 671, 957, 765,
357 1021, 247, 766, 891, 1918, 759, 1783, 1911, 2039, 95, 761, 687, 887,
358 607, 879, 751, 895, 239, 765, 955, 1911, 751, 1759, 1887, 1919, 223,
359 763, 763, 1917, 735, 1759, 1759, 2031, 255, 767, 1019, 1919, 767, 1791,
360 1919, 2047, 63, 319, 127, 383, 127, 383, 255, 511, 319, 1020, 831,
361 1021, 831, 1021, 1019, 1023, 127, 831, 639, 895, 703, 959, 767, 1023,
362 383, 1021, 895, 2031, 959, 2039, 1919, 2047, 127, 831, 703, 959, 639,
363 895, 767, 1023, 383, 1021, 959, 2039, 895, 2031, 1919, 2047, 255, 1019,
364 767, 1919, 767, 1919, 1791, 2047, 511, 1023, 1023, 2047, 1023, 2047, 2047,
365 4095
366 };
367
368 const unsigned int igraph_i_isoclass_4_idx[] = {
369 0, 8, 64, 512, 1, 0, 128, 1024, 2, 16, 0, 2048, 4, 32, 256, 0
370 };
371
372 const unsigned int igraph_i_isoclass_3u[] = { 0, 1, 1, 3, 1, 3, 3, 7 };
373
374 const unsigned int igraph_i_isoclass_3u_idx[] = { 0, 1, 2, 1, 0, 4, 2, 4, 0 };
375
376 const unsigned int igraph_i_isoclass_4u[] = {
377 0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3, 11, 12, 13, 13, 15, 1, 3, 12, 13, 3, 11, 13, 15, 3, 7,
378 13, 15, 13, 15, 30, 31, 1, 12, 3, 13, 3, 13, 11, 15, 3, 13, 7, 15, 13, 30, 15, 31, 3, 13, 13, 30,
379 7, 15, 15, 31, 11, 15, 15, 31, 15, 31, 31, 63
380 };
381
382 const unsigned int igraph_i_isoclass_4u_idx[] = {
383 0, 1, 2, 8, 1, 0, 4, 16, 2, 4, 0, 32, 8, 16, 32, 0
384 };
385
386 const unsigned int igraph_i_isoclass2_3[] = {
387 0, 1, 1, 2, 1, 3, 4, 5, 1, 4, 6, 7, 2, 5, 7, 8, 1, 4, 3, 5, 6, 9, 9, 10, 4, 11,
388 9, 12, 7, 12, 13, 14, 1, 6, 4, 7, 4, 9, 11, 12, 3, 9, 9, 13, 5, 10, 12, 14, 2, 7, 5, 8,
389 7, 13, 12, 14, 5, 12, 10, 14, 8, 14, 14, 15
390 };
391
392 const unsigned int igraph_i_isoclass2_3u[] = {
393 0, 1, 1, 2, 1, 2, 2, 3
394 };
395
396 const unsigned int igraph_i_isoclass2_4u[] = {
397 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 4, 5, 6, 6, 7, 1, 2, 5, 6, 2, 4, 6, 7, 2, 3,
398 6, 7, 6, 7, 8, 9, 1, 5, 2, 6, 2, 6, 4, 7, 2, 6, 3, 7, 6, 8, 7, 9, 2, 6, 6, 8,
399 3, 7, 7, 9, 4, 7, 7, 9, 7, 9, 9, 10
400 };
401
402 const unsigned int igraph_i_isoclass2_4[] = {
403 0, 1, 1, 2, 1, 2, 2, 3, 1, 4, 5, 6, 5, 6, 7, 8, 1, 5, 9, 10,
404 11, 12, 13, 14, 2, 6, 10, 15, 12, 16, 17, 18, 1, 5, 11, 12, 9, 10, 13, 14,
405 2, 6, 12, 16, 10, 15, 17, 18, 2, 7, 13, 17, 13, 17, 19, 20, 3, 8, 14, 18,
406 14, 18, 20, 21, 1, 5, 4, 6, 5, 7, 6, 8, 9, 22, 22, 23, 24, 25, 25, 26,
407 5, 27, 22, 28, 29, 30, 31, 32, 10, 28, 33, 34, 35, 36, 37, 38, 11, 29, 39, 40,
408 41, 42, 43, 44, 13, 31, 45, 46, 47, 48, 49, 50, 12, 30, 45, 51, 52, 53, 54, 55,
409 14, 32, 56, 57, 58, 59, 60, 61, 1, 9, 5, 10, 11, 13, 12, 14, 5, 22, 27, 28,
410 29, 31, 30, 32, 4, 22, 22, 33, 39, 45, 45, 56, 6, 23, 28, 34, 40, 46, 51, 57,
411 5, 24, 29, 35, 41, 47, 52, 58, 7, 25, 30, 36, 42, 48, 53, 59, 6, 25, 31, 37,
412 43, 49, 54, 60, 8, 26, 32, 38, 44, 50, 55, 61, 2, 10, 6, 15, 12, 17, 16, 18,
413 10, 33, 28, 34, 35, 37, 36, 38, 6, 28, 23, 34, 40, 51, 46, 57, 15, 34, 34, 62,
414 63, 64, 64, 65, 12, 35, 40, 63, 66, 67, 68, 69, 17, 37, 51, 64, 67, 70, 71, 72,
415 16, 36, 46, 64, 68, 71, 73, 74, 18, 38, 57, 65, 69, 72, 74, 75, 1, 11, 5, 12,
416 9, 13, 10, 14, 11, 39, 29, 40, 41, 43, 42, 44, 5, 29, 24, 35, 41, 52, 47, 58,
417 12, 40, 35, 63, 66, 68, 67, 69, 9, 41, 41, 66, 76, 77, 77, 78, 13, 43, 52, 68,
418 77, 79, 80, 81, 10, 42, 47, 67, 77, 80, 82, 83, 14, 44, 58, 69, 78, 81, 83, 84,
419 2, 12, 6, 16, 10, 17, 15, 18, 13, 45, 31, 46, 47, 49, 48, 50, 7, 30, 25, 36,
420 42, 53, 48, 59, 17, 51, 37, 64, 67, 71, 70, 72, 13, 52, 43, 68, 77, 80, 79, 81,
421 19, 54, 54, 73, 82, 85, 85, 86, 17, 53, 49, 71, 80, 87, 85, 88, 20, 55, 60, 74,
422 83, 88, 89, 90, 2, 13, 7, 17, 13, 19, 17, 20, 12, 45, 30, 51, 52, 54, 53, 55,
423 6, 31, 25, 37, 43, 54, 49, 60, 16, 46, 36, 64, 68, 73, 71, 74, 10, 47, 42, 67,
424 77, 82, 80, 83, 17, 49, 53, 71, 80, 85, 87, 88, 15, 48, 48, 70, 79, 85, 85, 89,
425 18, 50, 59, 72, 81, 86, 88, 90, 3, 14, 8, 18, 14, 20, 18, 21, 14, 56, 32, 57,
426 58, 60, 59, 61, 8, 32, 26, 38, 44, 55, 50, 61, 18, 57, 38, 65, 69, 74, 72, 75,
427 14, 58, 44, 69, 78, 83, 81, 84, 20, 60, 55, 74, 83, 89, 88, 90, 18, 59, 50, 72,
428 81, 88, 86, 90, 21, 61, 61, 75, 84, 90, 90, 91, 1, 5, 5, 7, 4, 6, 6, 8,
429 9, 22, 24, 25, 22, 23, 25, 26, 11, 29, 41, 42, 39, 40, 43, 44, 13, 31, 47, 48,
430 45, 46, 49, 50, 5, 27, 29, 30, 22, 28, 31, 32, 10, 28, 35, 36, 33, 34, 37, 38,
431 12, 30, 52, 53, 45, 51, 54, 55, 14, 32, 58, 59, 56, 57, 60, 61, 9, 24, 22, 25,
432 22, 25, 23, 26, 76, 92, 92, 93, 92, 93, 93, 94, 41, 95, 96, 97, 98, 99, 100, 101,
433 77, 102, 103, 104, 105, 106, 107, 108, 41, 95, 98, 99, 96, 97, 100, 101, 77, 102, 105, 106,
434 103, 104, 107, 108, 66, 109, 110, 111, 110, 111, 112, 113, 78, 114, 115, 116, 115, 116, 117, 118,
435 11, 41, 29, 42, 39, 43, 40, 44, 41, 96, 95, 97, 98, 100, 99, 101, 39, 98, 98, 119,
436 120, 121, 121, 122, 43, 100, 123, 124, 121, 125, 126, 127, 29, 95, 128, 129, 98, 123, 130, 131,
437 42, 97, 129, 132, 119, 124, 133, 134, 40, 99, 130, 133, 121, 126, 135, 136, 44, 101, 131, 134,
438 122, 127, 136, 137, 13, 47, 31, 48, 45, 49, 46, 50, 77, 103, 102, 104, 105, 107, 106, 108,
439 43, 123, 100, 124, 121, 126, 125, 127, 79, 138, 138, 139, 140, 141, 141, 142, 52, 143, 130, 144,
440 110, 145, 146, 147, 80, 148, 149, 150, 151, 152, 153, 154, 68, 155, 146, 156, 157, 158, 159, 160,
441 81, 161, 162, 163, 164, 165, 166, 167, 5, 29, 27, 30, 22, 31, 28, 32, 41, 98, 95, 99,
442 96, 100, 97, 101, 29, 128, 95, 129, 98, 130, 123, 131, 52, 130, 143, 144, 110, 146, 145, 147,
443 24, 95, 95, 109, 92, 102, 102, 114, 47, 123, 143, 155, 103, 138, 148, 161, 35, 129, 143, 168,
444 105, 149, 169, 170, 58, 131, 171, 172, 115, 162, 173, 174, 10, 35, 28, 36, 33, 37, 34, 38,
445 77, 105, 102, 106, 103, 107, 104, 108, 42, 129, 97, 132, 119, 133, 124, 134, 80, 149, 148, 150,
446 151, 153, 152, 154, 47, 143, 123, 155, 103, 148, 138, 161, 82, 169, 169, 175, 176, 177, 177, 178,
447 67, 168, 145, 179, 151, 180, 181, 182, 83, 170, 173, 183, 184, 185, 186, 187, 12, 52, 30, 53,
448 45, 54, 51, 55, 66, 110, 109, 111, 110, 112, 111, 113, 40, 130, 99, 133, 121, 135, 126, 136,
449 68, 146, 155, 156, 157, 159, 158, 160, 35, 143, 129, 168, 105, 169, 149, 170, 67, 145, 168, 179,
450 151, 181, 180, 182, 63, 144, 144, 188, 140, 189, 189, 190, 69, 147, 172, 191, 164, 192, 193, 194,
451 14, 58, 32, 59, 56, 60, 57, 61, 78, 115, 114, 116, 115, 117, 116, 118, 44, 131, 101, 134,
452 122, 136, 127, 137, 81, 162, 161, 163, 164, 166, 165, 167, 58, 171, 131, 172, 115, 173, 162, 174,
453 83, 173, 170, 183, 184, 186, 185, 187, 69, 172, 147, 191, 164, 193, 192, 194, 84, 174, 174, 195,
454 196, 197, 197, 198, 1, 9, 11, 13, 5, 10, 12, 14, 5, 22, 29, 31, 27, 28, 30, 32,
455 5, 24, 41, 47, 29, 35, 52, 58, 7, 25, 42, 48, 30, 36, 53, 59, 4, 22, 39, 45,
456 22, 33, 45, 56, 6, 23, 40, 46, 28, 34, 51, 57, 6, 25, 43, 49, 31, 37, 54, 60,
457 8, 26, 44, 50, 32, 38, 55, 61, 11, 41, 39, 43, 29, 42, 40, 44, 41, 96, 98, 100,
458 95, 97, 99, 101, 29, 95, 98, 123, 128, 129, 130, 131, 42, 97, 119, 124, 129, 132, 133, 134,
459 39, 98, 120, 121, 98, 119, 121, 122, 43, 100, 121, 125, 123, 124, 126, 127, 40, 99, 121, 126,
460 130, 133, 135, 136, 44, 101, 122, 127, 131, 134, 136, 137, 9, 76, 41, 77, 41, 77, 66, 78,
461 24, 92, 95, 102, 95, 102, 109, 114, 22, 92, 96, 103, 98, 105, 110, 115, 25, 93, 97, 104,
462 99, 106, 111, 116, 22, 92, 98, 105, 96, 103, 110, 115, 25, 93, 99, 106, 97, 104, 111, 116,
463 23, 93, 100, 107, 100, 107, 112, 117, 26, 94, 101, 108, 101, 108, 113, 118, 13, 77, 43, 79,
464 52, 80, 68, 81, 47, 103, 123, 138, 143, 148, 155, 161, 31, 102, 100, 138, 130, 149, 146, 162,
465 48, 104, 124, 139, 144, 150, 156, 163, 45, 105, 121, 140, 110, 151, 157, 164, 49, 107, 126, 141,
466 145, 152, 158, 165, 46, 106, 125, 141, 146, 153, 159, 166, 50, 108, 127, 142, 147, 154, 160, 167,
467 5, 41, 29, 52, 24, 47, 35, 58, 29, 98, 128, 130, 95, 123, 129, 131, 27, 95, 95, 143,
468 95, 143, 143, 171, 30, 99, 129, 144, 109, 155, 168, 172, 22, 96, 98, 110, 92, 103, 105, 115,
469 31, 100, 130, 146, 102, 138, 149, 162, 28, 97, 123, 145, 102, 148, 169, 173, 32, 101, 131, 147,
470 114, 161, 170, 174, 12, 66, 40, 68, 35, 67, 63, 69, 52, 110, 130, 146, 143, 145, 144, 147,
471 30, 109, 99, 155, 129, 168, 144, 172, 53, 111, 133, 156, 168, 179, 188, 191, 45, 110, 121, 157,
472 105, 151, 140, 164, 54, 112, 135, 159, 169, 181, 189, 192, 51, 111, 126, 158, 149, 180, 189, 193,
473 55, 113, 136, 160, 170, 182, 190, 194, 10, 77, 42, 80, 47, 82, 67, 83, 35, 105, 129, 149,
474 143, 169, 168, 170, 28, 102, 97, 148, 123, 169, 145, 173, 36, 106, 132, 150, 155, 175, 179, 183,
475 33, 103, 119, 151, 103, 176, 151, 184, 37, 107, 133, 153, 148, 177, 180, 185, 34, 104, 124, 152,
476 138, 177, 181, 186, 38, 108, 134, 154, 161, 178, 182, 187, 14, 78, 44, 81, 58, 83, 69, 84,
477 58, 115, 131, 162, 171, 173, 172, 174, 32, 114, 101, 161, 131, 170, 147, 174, 59, 116, 134, 163,
478 172, 183, 191, 195, 56, 115, 122, 164, 115, 184, 164, 196, 60, 117, 136, 166, 173, 186, 193, 197,
479 57, 116, 127, 165, 162, 185, 192, 197, 61, 118, 137, 167, 174, 187, 194, 198, 2, 10, 12, 17,
480 6, 15, 16, 18, 10, 33, 35, 37, 28, 34, 36, 38, 12, 35, 66, 67, 40, 63, 68, 69,
481 17, 37, 67, 70, 51, 64, 71, 72, 6, 28, 40, 51, 23, 34, 46, 57, 15, 34, 63, 64,
482 34, 62, 64, 65, 16, 36, 68, 71, 46, 64, 73, 74, 18, 38, 69, 72, 57, 65, 74, 75,
483 13, 47, 45, 49, 31, 48, 46, 50, 77, 103, 105, 107, 102, 104, 106, 108, 52, 143, 110, 145,
484 130, 144, 146, 147, 80, 148, 151, 152, 149, 150, 153, 154, 43, 123, 121, 126, 100, 124, 125, 127,
485 79, 138, 140, 141, 138, 139, 141, 142, 68, 155, 157, 158, 146, 156, 159, 160, 81, 161, 164, 165,
486 162, 163, 166, 167, 13, 77, 52, 80, 43, 79, 68, 81, 47, 103, 143, 148, 123, 138, 155, 161,
487 45, 105, 110, 151, 121, 140, 157, 164, 49, 107, 145, 152, 126, 141, 158, 165, 31, 102, 130, 149,
488 100, 138, 146, 162, 48, 104, 144, 150, 124, 139, 156, 163, 46, 106, 146, 153, 125, 141, 159, 166,
489 50, 108, 147, 154, 127, 142, 160, 167, 19, 82, 54, 85, 54, 85, 73, 86, 82, 176, 169, 177,
490 169, 177, 175, 178, 54, 169, 112, 181, 135, 189, 159, 192, 85, 177, 181, 199, 189, 200, 201, 202,
491 54, 169, 135, 189, 112, 181, 159, 192, 85, 177, 189, 200, 181, 199, 201, 202, 73, 175, 159, 201,
492 159, 201, 203, 204, 86, 178, 192, 202, 192, 202, 204, 205, 7, 42, 30, 53, 25, 48, 36, 59,
493 42, 119, 129, 133, 97, 124, 132, 134, 30, 129, 109, 168, 99, 144, 155, 172, 53, 133, 168, 188,
494 111, 156, 179, 191, 25, 97, 99, 111, 93, 104, 106, 116, 48, 124, 144, 156, 104, 139, 150, 163,
495 36, 132, 155, 179, 106, 150, 175, 183, 59, 134, 172, 191, 116, 163, 183, 195, 17, 67, 51, 71,
496 37, 70, 64, 72, 80, 151, 149, 153, 148, 152, 150, 154, 53, 168, 111, 179, 133, 188, 156, 191,
497 87, 180, 180, 206, 180, 206, 206, 207, 49, 145, 126, 158, 107, 152, 141, 165, 85, 181, 189, 201,
498 177, 199, 200, 202, 71, 179, 158, 208, 153, 206, 201, 209, 88, 182, 193, 209, 185, 210, 211, 212,
499 17, 80, 53, 87, 49, 85, 71, 88, 67, 151, 168, 180, 145, 181, 179, 182, 51, 149, 111, 180,
500 126, 189, 158, 193, 71, 153, 179, 206, 158, 201, 208, 209, 37, 148, 133, 180, 107, 177, 153, 185,
501 70, 152, 188, 206, 152, 199, 206, 210, 64, 150, 156, 206, 141, 200, 201, 211, 72, 154, 191, 207,
502 165, 202, 209, 212, 20, 83, 55, 88, 60, 89, 74, 90, 83, 184, 170, 185, 173, 186, 183, 187,
503 55, 170, 113, 182, 136, 190, 160, 194, 88, 185, 182, 210, 193, 211, 209, 212, 60, 173, 136, 193,
504 117, 186, 166, 197, 89, 186, 190, 211, 186, 213, 211, 214, 74, 183, 160, 209, 166, 211, 204, 215,
505 90, 187, 194, 212, 197, 214, 215, 216, 1, 11, 9, 13, 5, 12, 10, 14, 11, 39, 41, 43,
506 29, 40, 42, 44, 9, 41, 76, 77, 41, 66, 77, 78, 13, 43, 77, 79, 52, 68, 80, 81,
507 5, 29, 41, 52, 24, 35, 47, 58, 12, 40, 66, 68, 35, 63, 67, 69, 10, 42, 77, 80,
508 47, 67, 82, 83, 14, 44, 78, 81, 58, 69, 83, 84, 5, 29, 22, 31, 27, 30, 28, 32,
509 41, 98, 96, 100, 95, 99, 97, 101, 24, 95, 92, 102, 95, 109, 102, 114, 47, 123, 103, 138,
510 143, 155, 148, 161, 29, 128, 98, 130, 95, 129, 123, 131, 52, 130, 110, 146, 143, 144, 145, 147,
511 35, 129, 105, 149, 143, 168, 169, 170, 58, 131, 115, 162, 171, 172, 173, 174, 5, 41, 24, 47,
512 29, 52, 35, 58, 29, 98, 95, 123, 128, 130, 129, 131, 22, 96, 92, 103, 98, 110, 105, 115,
513 31, 100, 102, 138, 130, 146, 149, 162, 27, 95, 95, 143, 95, 143, 143, 171, 30, 99, 109, 155,
514 129, 144, 168, 172, 28, 97, 102, 148, 123, 145, 169, 173, 32, 101, 114, 161, 131, 147, 170, 174,
515 7, 42, 25, 48, 30, 53, 36, 59, 42, 119, 97, 124, 129, 133, 132, 134, 25, 97, 93, 104,
516 99, 111, 106, 116, 48, 124, 104, 139, 144, 156, 150, 163, 30, 129, 99, 144, 109, 168, 155, 172,
517 53, 133, 111, 156, 168, 188, 179, 191, 36, 132, 106, 150, 155, 179, 175, 183, 59, 134, 116, 163,
518 172, 191, 183, 195, 4, 39, 22, 45, 22, 45, 33, 56, 39, 120, 98, 121, 98, 121, 119, 122,
519 22, 98, 92, 105, 96, 110, 103, 115, 45, 121, 105, 140, 110, 157, 151, 164, 22, 98, 96, 110,
520 92, 105, 103, 115, 45, 121, 110, 157, 105, 140, 151, 164, 33, 119, 103, 151, 103, 151, 176, 184,
521 56, 122, 115, 164, 115, 164, 184, 196, 6, 40, 23, 46, 28, 51, 34, 57, 43, 121, 100, 125,
522 123, 126, 124, 127, 25, 99, 93, 106, 97, 111, 104, 116, 49, 126, 107, 141, 145, 158, 152, 165,
523 31, 130, 100, 146, 102, 149, 138, 162, 54, 135, 112, 159, 169, 189, 181, 192, 37, 133, 107, 153,
524 148, 180, 177, 185, 60, 136, 117, 166, 173, 193, 186, 197, 6, 43, 25, 49, 31, 54, 37, 60,
525 40, 121, 99, 126, 130, 135, 133, 136, 23, 100, 93, 107, 100, 112, 107, 117, 46, 125, 106, 141,
526 146, 159, 153, 166, 28, 123, 97, 145, 102, 169, 148, 173, 51, 126, 111, 158, 149, 189, 180, 193,
527 34, 124, 104, 152, 138, 181, 177, 186, 57, 127, 116, 165, 162, 192, 185, 197, 8, 44, 26, 50,
528 32, 55, 38, 61, 44, 122, 101, 127, 131, 136, 134, 137, 26, 101, 94, 108, 101, 113, 108, 118,
529 50, 127, 108, 142, 147, 160, 154, 167, 32, 131, 101, 147, 114, 170, 161, 174, 55, 136, 113, 160,
530 170, 190, 182, 194, 38, 134, 108, 154, 161, 182, 178, 187, 61, 137, 118, 167, 174, 194, 187, 198,
531 2, 12, 10, 17, 6, 16, 15, 18, 13, 45, 47, 49, 31, 46, 48, 50, 13, 52, 77, 80,
532 43, 68, 79, 81, 19, 54, 82, 85, 54, 73, 85, 86, 7, 30, 42, 53, 25, 36, 48, 59,
533 17, 51, 67, 71, 37, 64, 70, 72, 17, 53, 80, 87, 49, 71, 85, 88, 20, 55, 83, 88,
534 60, 74, 89, 90, 10, 35, 33, 37, 28, 36, 34, 38, 77, 105, 103, 107, 102, 106, 104, 108,
535 47, 143, 103, 148, 123, 155, 138, 161, 82, 169, 176, 177, 169, 175, 177, 178, 42, 129, 119, 133,
536 97, 132, 124, 134, 80, 149, 151, 153, 148, 150, 152, 154, 67, 168, 151, 180, 145, 179, 181, 182,
537 83, 170, 184, 185, 173, 183, 186, 187, 12, 66, 35, 67, 40, 68, 63, 69, 52, 110, 143, 145,
538 130, 146, 144, 147, 45, 110, 105, 151, 121, 157, 140, 164, 54, 112, 169, 181, 135, 159, 189, 192,
539 30, 109, 129, 168, 99, 155, 144, 172, 53, 111, 168, 179, 133, 156, 188, 191, 51, 111, 149, 180,
540 126, 158, 189, 193, 55, 113, 170, 182, 136, 160, 190, 194, 17, 67, 37, 70, 51, 71, 64, 72,
541 80, 151, 148, 152, 149, 153, 150, 154, 49, 145, 107, 152, 126, 158, 141, 165, 85, 181, 177, 199,
542 189, 201, 200, 202, 53, 168, 133, 188, 111, 179, 156, 191, 87, 180, 180, 206, 180, 206, 206, 207,
543 71, 179, 153, 206, 158, 208, 201, 209, 88, 182, 185, 210, 193, 209, 211, 212, 6, 40, 28, 51,
544 23, 46, 34, 57, 43, 121, 123, 126, 100, 125, 124, 127, 31, 130, 102, 149, 100, 146, 138, 162,
545 54, 135, 169, 189, 112, 159, 181, 192, 25, 99, 97, 111, 93, 106, 104, 116, 49, 126, 145, 158,
546 107, 141, 152, 165, 37, 133, 148, 180, 107, 153, 177, 185, 60, 136, 173, 193, 117, 166, 186, 197,
547 15, 63, 34, 64, 34, 64, 62, 65, 79, 140, 138, 141, 138, 141, 139, 142, 48, 144, 104, 150,
548 124, 156, 139, 163, 85, 189, 177, 200, 181, 201, 199, 202, 48, 144, 124, 156, 104, 150, 139, 163,
549 85, 189, 181, 201, 177, 200, 199, 202, 70, 188, 152, 206, 152, 206, 199, 210, 89, 190, 186, 211,
550 186, 211, 213, 214, 16, 68, 36, 71, 46, 73, 64, 74, 68, 157, 155, 158, 146, 159, 156, 160,
551 46, 146, 106, 153, 125, 159, 141, 166, 73, 159, 175, 201, 159, 203, 201, 204, 36, 155, 132, 179,
552 106, 175, 150, 183, 71, 158, 179, 208, 153, 201, 206, 209, 64, 156, 150, 206, 141, 201, 200, 211,
553 74, 160, 183, 209, 166, 204, 211, 215, 18, 69, 38, 72, 57, 74, 65, 75, 81, 164, 161, 165,
554 162, 166, 163, 167, 50, 147, 108, 154, 127, 160, 142, 167, 86, 192, 178, 202, 192, 204, 202, 205,
555 59, 172, 134, 191, 116, 183, 163, 195, 88, 193, 182, 209, 185, 211, 210, 212, 72, 191, 154, 207,
556 165, 209, 202, 212, 90, 194, 187, 212, 197, 215, 214, 216, 2, 13, 13, 19, 7, 17, 17, 20,
557 12, 45, 52, 54, 30, 51, 53, 55, 10, 47, 77, 82, 42, 67, 80, 83, 17, 49, 80, 85,
558 53, 71, 87, 88, 6, 31, 43, 54, 25, 37, 49, 60, 16, 46, 68, 73, 36, 64, 71, 74,
559 15, 48, 79, 85, 48, 70, 85, 89, 18, 50, 81, 86, 59, 72, 88, 90, 12, 52, 45, 54,
560 30, 53, 51, 55, 66, 110, 110, 112, 109, 111, 111, 113, 35, 143, 105, 169, 129, 168, 149, 170,
561 67, 145, 151, 181, 168, 179, 180, 182, 40, 130, 121, 135, 99, 133, 126, 136, 68, 146, 157, 159,
562 155, 156, 158, 160, 63, 144, 140, 189, 144, 188, 189, 190, 69, 147, 164, 192, 172, 191, 193, 194,
563 10, 77, 47, 82, 42, 80, 67, 83, 35, 105, 143, 169, 129, 149, 168, 170, 33, 103, 103, 176,
564 119, 151, 151, 184, 37, 107, 148, 177, 133, 153, 180, 185, 28, 102, 123, 169, 97, 148, 145, 173,
565 36, 106, 155, 175, 132, 150, 179, 183, 34, 104, 138, 177, 124, 152, 181, 186, 38, 108, 161, 178,
566 134, 154, 182, 187, 17, 80, 49, 85, 53, 87, 71, 88, 67, 151, 145, 181, 168, 180, 179, 182,
567 37, 148, 107, 177, 133, 180, 153, 185, 70, 152, 152, 199, 188, 206, 206, 210, 51, 149, 126, 189,
568 111, 180, 158, 193, 71, 153, 158, 201, 179, 206, 208, 209, 64, 150, 141, 200, 156, 206, 201, 211,
569 72, 154, 165, 202, 191, 207, 209, 212, 6, 43, 31, 54, 25, 49, 37, 60, 40, 121, 130, 135,
570 99, 126, 133, 136, 28, 123, 102, 169, 97, 145, 148, 173, 51, 126, 149, 189, 111, 158, 180, 193,
571 23, 100, 100, 112, 93, 107, 107, 117, 46, 125, 146, 159, 106, 141, 153, 166, 34, 124, 138, 181,
572 104, 152, 177, 186, 57, 127, 162, 192, 116, 165, 185, 197, 16, 68, 46, 73, 36, 71, 64, 74,
573 68, 157, 146, 159, 155, 158, 156, 160, 36, 155, 106, 175, 132, 179, 150, 183, 71, 158, 153, 201,
574 179, 208, 206, 209, 46, 146, 125, 159, 106, 153, 141, 166, 73, 159, 159, 203, 175, 201, 201, 204,
575 64, 156, 141, 201, 150, 206, 200, 211, 74, 160, 166, 204, 183, 209, 211, 215, 15, 79, 48, 85,
576 48, 85, 70, 89, 63, 140, 144, 189, 144, 189, 188, 190, 34, 138, 104, 177, 124, 181, 152, 186,
577 64, 141, 150, 200, 156, 201, 206, 211, 34, 138, 124, 181, 104, 177, 152, 186, 64, 141, 156, 201,
578 150, 200, 206, 211, 62, 139, 139, 199, 139, 199, 199, 213, 65, 142, 163, 202, 163, 202, 210, 214,
579 18, 81, 50, 86, 59, 88, 72, 90, 69, 164, 147, 192, 172, 193, 191, 194, 38, 161, 108, 178,
580 134, 182, 154, 187, 72, 165, 154, 202, 191, 209, 207, 212, 57, 162, 127, 192, 116, 185, 165, 197,
581 74, 166, 160, 204, 183, 211, 209, 215, 65, 163, 142, 202, 163, 210, 202, 214, 75, 167, 167, 205,
582 195, 212, 212, 216, 3, 14, 14, 20, 8, 18, 18, 21, 14, 56, 58, 60, 32, 57, 59, 61,
583 14, 58, 78, 83, 44, 69, 81, 84, 20, 60, 83, 89, 55, 74, 88, 90, 8, 32, 44, 55,
584 26, 38, 50, 61, 18, 57, 69, 74, 38, 65, 72, 75, 18, 59, 81, 88, 50, 72, 86, 90,
585 21, 61, 84, 90, 61, 75, 90, 91, 14, 58, 56, 60, 32, 59, 57, 61, 78, 115, 115, 117,
586 114, 116, 116, 118, 58, 171, 115, 173, 131, 172, 162, 174, 83, 173, 184, 186, 170, 183, 185, 187,
587 44, 131, 122, 136, 101, 134, 127, 137, 81, 162, 164, 166, 161, 163, 165, 167, 69, 172, 164, 193,
588 147, 191, 192, 194, 84, 174, 196, 197, 174, 195, 197, 198, 14, 78, 58, 83, 44, 81, 69, 84,
589 58, 115, 171, 173, 131, 162, 172, 174, 56, 115, 115, 184, 122, 164, 164, 196, 60, 117, 173, 186,
590 136, 166, 193, 197, 32, 114, 131, 170, 101, 161, 147, 174, 59, 116, 172, 183, 134, 163, 191, 195,
591 57, 116, 162, 185, 127, 165, 192, 197, 61, 118, 174, 187, 137, 167, 194, 198, 20, 83, 60, 89,
592 55, 88, 74, 90, 83, 184, 173, 186, 170, 185, 183, 187, 60, 173, 117, 186, 136, 193, 166, 197,
593 89, 186, 186, 213, 190, 211, 211, 214, 55, 170, 136, 190, 113, 182, 160, 194, 88, 185, 193, 211,
594 182, 210, 209, 212, 74, 183, 166, 211, 160, 209, 204, 215, 90, 187, 197, 214, 194, 212, 215, 216,
595 8, 44, 32, 55, 26, 50, 38, 61, 44, 122, 131, 136, 101, 127, 134, 137, 32, 131, 114, 170,
596 101, 147, 161, 174, 55, 136, 170, 190, 113, 160, 182, 194, 26, 101, 101, 113, 94, 108, 108, 118,
597 50, 127, 147, 160, 108, 142, 154, 167, 38, 134, 161, 182, 108, 154, 178, 187, 61, 137, 174, 194,
598 118, 167, 187, 198, 18, 69, 57, 74, 38, 72, 65, 75, 81, 164, 162, 166, 161, 165, 163, 167,
599 59, 172, 116, 183, 134, 191, 163, 195, 88, 193, 185, 211, 182, 209, 210, 212, 50, 147, 127, 160,
600 108, 154, 142, 167, 86, 192, 192, 204, 178, 202, 202, 205, 72, 191, 165, 209, 154, 207, 202, 212,
601 90, 194, 197, 215, 187, 212, 214, 216, 18, 81, 59, 88, 50, 86, 72, 90, 69, 164, 172, 193,
602 147, 192, 191, 194, 57, 162, 116, 185, 127, 192, 165, 197, 74, 166, 183, 211, 160, 204, 209, 215,
603 38, 161, 134, 182, 108, 178, 154, 187, 72, 165, 191, 209, 154, 202, 207, 212, 65, 163, 163, 210,
604 142, 202, 202, 214, 75, 167, 195, 212, 167, 205, 212, 216, 21, 84, 61, 90, 61, 90, 75, 91,
605 84, 196, 174, 197, 174, 197, 195, 198, 61, 174, 118, 187, 137, 194, 167, 198, 90, 197, 187, 214,
606 194, 215, 212, 216, 61, 174, 137, 194, 118, 187, 167, 198, 90, 197, 194, 215, 187, 214, 212, 216,
607 75, 195, 167, 212, 167, 212, 205, 216, 91, 198, 198, 216, 198, 216, 216, 217
608 };
609
610 const unsigned int igraph_i_isographs_3[] = { 0, 1, 3, 5, 6, 7, 10, 11, 15, 21,
611 23, 25, 27, 30, 31, 63
612 };
613 const unsigned int igraph_i_isographs_3u[] = { 0, 1, 3, 7 };
614 const unsigned int igraph_i_isographs_4[] = {
615 0, 1, 3, 7, 9, 10, 11, 14, 15, 18, 19, 20, 21,
616 22, 23, 27, 29, 30, 31, 54, 55, 63, 73, 75, 76, 77,
617 79, 81, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95,
618 98, 99, 100, 101, 102, 103, 106, 107, 108, 109, 110, 111, 115,
619 116, 117, 118, 119, 122, 123, 124, 125, 126, 127, 219, 220, 221,
620 223, 228, 229, 230, 231, 237, 238, 239, 246, 247, 255, 292, 293,
621 295, 301, 302, 303, 310, 311, 319, 365, 367, 373, 375, 382, 383,
622 511, 585, 587, 591, 593, 594, 595, 596, 597, 598, 599, 601, 602,
623 603, 604, 605, 606, 607, 625, 626, 627, 630, 631, 633, 634, 635,
624 638, 639, 659, 660, 661, 663, 666, 667, 669, 670, 671, 674, 675,
625 678, 679, 683, 686, 687, 694, 695, 703, 729, 731, 732, 733, 735,
626 737, 739, 741, 742, 743, 745, 746, 747, 748, 749, 750, 751, 753,
627 755, 756, 757, 758, 759, 761, 762, 763, 764, 765, 766, 767, 819,
628 822, 823, 826, 827, 830, 831, 875, 876, 877, 879, 883, 885, 886,
629 887, 891, 892, 893, 894, 895, 947, 949, 951, 955, 957, 958, 959,
630 1019, 1020, 1021, 1023, 1755, 1757, 1758, 1759, 1782, 1783, 1791, 1883, 1887,
631 1907, 1911, 1917, 1918, 1919, 2029, 2031, 2039, 2047, 4095
632 };
633 const unsigned int igraph_i_isographs_4u[] = { 0, 1, 3, 7, 11, 12, 13,
634 15, 30, 31, 63
635 };
636
637 const unsigned int igraph_i_classedges_3[] = { 1, 2, 0, 2, 2, 1, 0, 1, 2, 0, 1, 0 };
638 const unsigned int igraph_i_classedges_3u[] = { 1, 2, 0, 2, 0, 1 };
639 const unsigned int igraph_i_classedges_4[] = { 2, 3, 1, 3, 0, 3, 3, 2, 1, 2, 0, 2,
640 3, 1, 2, 1, 0, 1, 3, 0, 2, 0, 1, 0
641 };
642 const unsigned int igraph_i_classedges_4u[] = { 2, 3, 1, 3, 0, 3, 1, 2, 0, 2, 0, 1 };
643
644 /**
645 * \section about_graph_isomorphism
646 *
647 * <para>igraph provides four set of functions to deal with graph
648 * isomorphism problems.</para>
649 *
650 * <para>The \ref igraph_isomorphic() and \ref igraph_subisomorphic()
651 * functions make up the first set (in addition with the \ref
652 * igraph_permute_vertices() function). These functions choose the
653 * algorithm which is best for the supplied input graph. (The choice is
654 * not very sophisticated though, see their documentation for
655 * details.)</para>
656 *
657 * <para>The VF2 graph (and subgraph) isomorphism algorithm is implemented in
658 * igraph, these functions are the second set. See \ref
659 * igraph_isomorphic_vf2() and \ref igraph_subisomorphic_vf2() for
660 * starters.</para>
661 *
662 * <para>Functions for the BLISS algorithm constitute the third set,
663 * see \ref igraph_isomorphic_bliss().</para>
664 *
665 * <para>Finally, the isomorphism classes of all graphs with three and
666 * four vertices are precomputed and stored in igraph, so for these
667 * small graphs there is a very simple fast way to decide isomorphism.
668 * See \ref igraph_isomorphic_34().
669 * </para>
670 */
671
672 /**
673 * \function igraph_isoclass
674 * \brief Determine the isomorphism class of a graph with 3 or 4 vertices
675 *
676 * </para><para>
677 * All graphs with a given number of vertices belong to a number of
678 * isomorphism classes, with every graph in a given class being
679 * isomorphic to each other.
680 *
681 * </para><para>
682 * This function gives the isomorphism class (a number) of a
683 * graph. Two graphs have the same isomorphism class if and only if
684 * they are isomorphic.
685 *
686 * </para><para>
687 * The first isomorphism class is numbered zero and it is the empty
688 * graph, the last isomorphism class is the full graph. The number of
689 * isomorphism class for directed graphs with three vertices is 16
690 * (between 0 and 15), for undirected graph it is only 4. For graphs
691 * with four vertices it is 218 (directed) and 11 (undirected).
692 *
693 * </para><para>
694 * Multi-edges and self-loops are ignored by this function.
695 *
696 * \param graph The graph object.
697 * \param isoclass Pointer to an integer, the isomorphism class will
698 * be stored here.
699 * \return Error code.
700 * \sa \ref igraph_isomorphic(), \ref igraph_isoclass_subgraph(),
701 * \ref igraph_isoclass_create(), \ref igraph_motifs_randesu().
702 *
703 * Because of some limitations this function works only for graphs
704 * with three of four vertices.
705 *
706 * </para><para>
707 * Time complexity: O(|E|), the number of edges in the graph.
708 */
709
igraph_isoclass(const igraph_t * graph,igraph_integer_t * isoclass)710 int igraph_isoclass(const igraph_t *graph, igraph_integer_t *isoclass) {
711 long int e;
712 long int no_of_nodes = igraph_vcount(graph);
713 long int no_of_edges = igraph_ecount(graph);
714 igraph_integer_t from, to;
715 unsigned char idx, mul;
716 const unsigned int *arr_idx, *arr_code;
717 int code = 0;
718
719 if (no_of_nodes < 3 || no_of_nodes > 4) {
720 IGRAPH_ERROR("Only implemented for graphs with 3 or 4 vertices",
721 IGRAPH_UNIMPLEMENTED);
722 }
723
724 if (igraph_is_directed(graph)) {
725 if (no_of_nodes == 3) {
726 arr_idx = igraph_i_isoclass_3_idx;
727 arr_code = igraph_i_isoclass2_3;
728 mul = 3;
729 } else {
730 arr_idx = igraph_i_isoclass_4_idx;
731 arr_code = igraph_i_isoclass2_4;
732 mul = 4;
733 }
734 } else {
735 if (no_of_nodes == 3) {
736 arr_idx = igraph_i_isoclass_3u_idx;
737 arr_code = igraph_i_isoclass2_3u;
738 mul = 3;
739 } else {
740 arr_idx = igraph_i_isoclass_4u_idx;
741 arr_code = igraph_i_isoclass2_4u;
742 mul = 4;
743 }
744 }
745
746 for (e = 0; e < no_of_edges; e++) {
747 igraph_edge(graph, (igraph_integer_t) e, &from, &to);
748 idx = (unsigned char) (mul * from + to);
749 code |= arr_idx[idx];
750 }
751
752 *isoclass = (igraph_integer_t) arr_code[code];
753 return 0;
754 }
755
756 /**
757 * \function igraph_isomorphic
758 * \brief Decides whether two graphs are isomorphic
759 *
760 * </para><para>
761 * In simple terms, two graphs are isomorphic if they become indistinguishable
762 * from each other once their vertex labels are removed (rendering the vertices
763 * within each graph indistiguishable). More precisely, two graphs are isomorphic
764 * if there is a one-to-one mapping from the vertices of the first one
765 * to the vertices of the second such that it transforms the edge set of the
766 * first graph into the edge set of the second. This mapping is called
767 * an \em isomorphism.
768 *
769 * </para><para>Currently, this function supports simple graphs and graphs
770 * with self-loops, but does not support multigraphs.
771 *
772 * </para><para>This function decides which graph isomorphism algorithm to be
773 * used based on the input graphs. Right now it does the following:
774 * \olist
775 * \oli If one graph is directed and the other undirected then an
776 * error is triggered.
777 * \oli If one of the graphs has multi-edges then an error is triggered.
778 * \oli If the two graphs does not have the same number of vertices
779 * and edges it returns with \c FALSE.
780 * \oli Otherwise, if the graphs have three or four vertices then an O(1)
781 * algorithm is used with precomputed data.
782 * \oli Otherwise BLISS is used, see \ref igraph_isomorphic_bliss().
783 * \endolist
784 *
785 * </para><para>Please call the VF2 and BLISS functions directly if you need
786 * something more sophisticated, e.g. you need the isomorphic mapping.
787 *
788 * \param graph1 The first graph.
789 * \param graph2 The second graph.
790 * \param iso Pointer to a logical variable, will be set to TRUE (1)
791 * if the two graphs are isomorphic, and FALSE (0) otherwise.
792 * \return Error code.
793 * \sa \ref igraph_isoclass(), \ref igraph_isoclass_subgraph(),
794 * \ref igraph_isoclass_create().
795 *
796 * Time complexity: exponential.
797 */
798
igraph_isomorphic(const igraph_t * graph1,const igraph_t * graph2,igraph_bool_t * iso)799 int igraph_isomorphic(const igraph_t *graph1, const igraph_t *graph2,
800 igraph_bool_t *iso) {
801
802 long int nodes1 = igraph_vcount(graph1), nodes2 = igraph_vcount(graph2);
803 long int edges1 = igraph_ecount(graph1), edges2 = igraph_ecount(graph2);
804 igraph_bool_t dir1 = igraph_is_directed(graph1), dir2 = igraph_is_directed(graph2);
805 igraph_bool_t loop1, loop2, multi1, multi2;
806
807 IGRAPH_CHECK(igraph_has_multiple(graph1, &multi1));
808 IGRAPH_CHECK(igraph_has_multiple(graph2, &multi2));
809
810 if (multi1 || multi2) {
811 IGRAPH_ERROR("Isomorphism testing is not implemented for multigraphs", IGRAPH_UNIMPLEMENTED);
812 }
813
814 if (dir1 != dir2) {
815 IGRAPH_ERROR("Cannot compare directed and undirected graphs", IGRAPH_EINVAL);
816 } else if (nodes1 != nodes2 || edges1 != edges2) {
817 *iso = 0;
818 } else if (nodes1 == 3 || nodes1 == 4) {
819 IGRAPH_CHECK(igraph_has_loop(graph1, &loop1));
820 IGRAPH_CHECK(igraph_has_loop(graph2, &loop2));
821 if (!loop1 && !loop2) {
822 IGRAPH_CHECK(igraph_isomorphic_34(graph1, graph2, iso));
823 } else {
824 IGRAPH_CHECK(igraph_isomorphic_bliss(graph1, graph2, NULL, NULL, iso,
825 0, 0, /*sh=*/ IGRAPH_BLISS_F, 0, 0));
826 }
827 } else {
828 IGRAPH_CHECK(igraph_isomorphic_bliss(graph1, graph2, NULL, NULL, iso,
829 0, 0, /*sh=*/ IGRAPH_BLISS_F, 0, 0));
830 }
831
832 return 0;
833 }
834
835 /**
836 * \function igraph_isomorphic_34
837 * Graph isomorphism for 3-4 vertices
838 *
839 * This function uses precomputed indices to decide isomorphism
840 * problems for graphs with only 3 or 4 vertices. Multi-edges
841 * and self-loops are ignored by this function.
842 * \param graph1 The first input graph.
843 * \param graph2 The second input graph. Must have the same
844 * directedness as \p graph1.
845 * \param iso Pointer to a boolean, the result is stored here.
846 * \return Error code.
847 *
848 * Time complexity: O(1).
849 */
850
igraph_isomorphic_34(const igraph_t * graph1,const igraph_t * graph2,igraph_bool_t * iso)851 int igraph_isomorphic_34(const igraph_t *graph1, const igraph_t *graph2,
852 igraph_bool_t *iso) {
853
854 igraph_integer_t class1, class2;
855 IGRAPH_CHECK(igraph_isoclass(graph1, &class1));
856 IGRAPH_CHECK(igraph_isoclass(graph2, &class2));
857 *iso = (class1 == class2);
858 return 0;
859 }
860
861 /**
862 * \function igraph_isoclass_subgraph
863 * \brief The isomorphism class of a subgraph of a graph.
864 *
865 * </para><para>
866 * This function is only implemented for subgraphs with three or four
867 * vertices.
868 * \param graph The graph object.
869 * \param vids A vector containing the vertex ids to be considered as
870 * a subgraph. Each vertex id should be included at most once.
871 * \param isoclass Pointer to an integer, this will be set to the
872 * isomorphism class.
873 * \return Error code.
874 * \sa \ref igraph_isoclass(), \ref igraph_isomorphic(),
875 * \ref igraph_isoclass_create().
876 *
877 * Time complexity: O((d+n)*n), d is the average degree in the network,
878 * and n is the number of vertices in \c vids.
879 */
880
igraph_isoclass_subgraph(const igraph_t * graph,igraph_vector_t * vids,igraph_integer_t * isoclass)881 int igraph_isoclass_subgraph(const igraph_t *graph, igraph_vector_t *vids,
882 igraph_integer_t *isoclass) {
883 int nodes = (int) igraph_vector_size(vids);
884 igraph_bool_t directed = igraph_is_directed(graph);
885 igraph_vector_t neis;
886
887 unsigned char mul, idx;
888 const unsigned int *arr_idx, *arr_code;
889 int code = 0;
890
891 long int i, j, s;
892
893 if (nodes < 3 || nodes > 4) {
894 IGRAPH_ERROR("Only for three- or four-vertex subgraphs",
895 IGRAPH_UNIMPLEMENTED);
896 }
897
898 IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);
899
900 if (directed) {
901 if (nodes == 3) {
902 arr_idx = igraph_i_isoclass_3_idx;
903 arr_code = igraph_i_isoclass2_3;
904 mul = 3;
905 } else {
906 arr_idx = igraph_i_isoclass_4_idx;
907 arr_code = igraph_i_isoclass2_4;
908 mul = 4;
909 }
910 } else {
911 if (nodes == 3) {
912 arr_idx = igraph_i_isoclass_3u_idx;
913 arr_code = igraph_i_isoclass2_3u;
914 mul = 3;
915 } else {
916 arr_idx = igraph_i_isoclass_4u_idx;
917 arr_code = igraph_i_isoclass2_4u;
918 mul = 4;
919 }
920 }
921
922 for (i = 0; i < nodes; i++) {
923 long int from = (long int) VECTOR(*vids)[i];
924 igraph_neighbors(graph, &neis, (igraph_integer_t) from, IGRAPH_OUT);
925 s = igraph_vector_size(&neis);
926 for (j = 0; j < s; j++) {
927 long int nei = (long int) VECTOR(neis)[j], to;
928 if (igraph_vector_search(vids, 0, nei, &to)) {
929 idx = (unsigned char) (mul * i + to);
930 code |= arr_idx[idx];
931 }
932 }
933 }
934
935 *isoclass = (igraph_integer_t) arr_code[code];
936 igraph_vector_destroy(&neis);
937 IGRAPH_FINALLY_CLEAN(1);
938 return 0;
939 }
940
941 /**
942 * \function igraph_isoclass_create
943 * \brief Creates a graph from the given isomorphism class.
944 *
945 * </para><para>
946 * This function is implemented only for graphs with three or four
947 * vertices.
948 * \param graph Pointer to an uninitialized graph object.
949 * \param size The number of vertices to add to the graph.
950 * \param number The isomorphism class.
951 * \param directed Logical constant, whether to create a directed
952 * graph.
953 * \return Error code.
954 * \sa \ref igraph_isoclass(),
955 * \ref igraph_isoclass_subgraph(),
956 * \ref igraph_isomorphic().
957 *
958 * Time complexity: O(|V|+|E|), the number of vertices plus the number
959 * of edges in the graph to create.
960 */
961
igraph_isoclass_create(igraph_t * graph,igraph_integer_t size,igraph_integer_t number,igraph_bool_t directed)962 int igraph_isoclass_create(igraph_t *graph, igraph_integer_t size,
963 igraph_integer_t number, igraph_bool_t directed) {
964 igraph_vector_t edges;
965 const unsigned int *classedges;
966 long int power;
967 long int code;
968 long int pos;
969
970 if (size < 3 || size > 4) {
971 IGRAPH_ERROR("Only for graphs with three of four vertices",
972 IGRAPH_UNIMPLEMENTED);
973 }
974
975 IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
976
977 if (directed) {
978 if (size == 3) {
979 classedges = igraph_i_classedges_3;
980
981 if (number < 0 ||
982 number >= (int)(sizeof(igraph_i_isographs_3) / sizeof(unsigned int))) {
983 IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
984 }
985
986 code = igraph_i_isographs_3[ (long int) number];
987 power = 32;
988 } else {
989 classedges = igraph_i_classedges_4;
990
991 if (number < 0 ||
992 number >= (int)(sizeof(igraph_i_isographs_4) / sizeof(unsigned int))) {
993 IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
994 }
995
996 code = igraph_i_isographs_4[ (long int) number];
997 power = 2048;
998 }
999 } else {
1000 if (size == 3) {
1001 classedges = igraph_i_classedges_3u;
1002
1003 if (number < 0 ||
1004 number >= (int)(sizeof(igraph_i_isographs_3u) /
1005 sizeof(unsigned int))) {
1006 IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
1007 }
1008
1009 code = igraph_i_isographs_3u[ (long int) number];
1010 power = 4;
1011 } else {
1012 classedges = igraph_i_classedges_4u;
1013
1014 if (number < 0 ||
1015 number >= (int)(sizeof(igraph_i_isographs_4u) /
1016 sizeof(unsigned int))) {
1017 IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
1018 }
1019
1020 code = igraph_i_isographs_4u[ (long int) number];
1021 power = 32;
1022 }
1023 }
1024
1025 pos = 0;
1026 while (code > 0) {
1027 if (code >= power) {
1028 IGRAPH_CHECK(igraph_vector_push_back(&edges, classedges[2 * pos]));
1029 IGRAPH_CHECK(igraph_vector_push_back(&edges, classedges[2 * pos + 1]));
1030 code -= power;
1031 }
1032 power /= 2;
1033 pos++;
1034 }
1035
1036 IGRAPH_CHECK(igraph_create(graph, &edges, size, directed));
1037 igraph_vector_destroy(&edges);
1038 IGRAPH_FINALLY_CLEAN(1);
1039 return 0;
1040 }
1041
1042 /**
1043 * \section about_vf2
1044 *
1045 * <para>
1046 * The VF2 algorithm can search for a subgraph in a larger graph, or check if two
1047 * graphs are isomorphic. See P. Foggia, C. Sansone, M. Vento, An Improved algorithm for
1048 * matching large graphs, Proc. of the 3rd IAPR-TC-15 International
1049 * Workshop on Graph-based Representations, Italy, 2001.
1050 * </para>
1051 *
1052 * <para>
1053 * VF2 supports both vertex and edge-colored graphs, as well as custom vertex or edge
1054 * compatibility functions.
1055 * </para>
1056 *
1057 * <para>
1058 * VF2 works with both directed and undirected graphs. Only simple graphs are supported.
1059 * Self-loops or multi-edges must not be present in the graphs. Currently, the VF2
1060 * functions do not check that the input graph is simple: it is the responsibility
1061 * of the user to pass in valid input.
1062 * </para>
1063 */
1064
1065 /**
1066 * \function igraph_isomorphic_function_vf2
1067 * The generic VF2 interface
1068 *
1069 * </para><para>
1070 * This function is an implementation of the VF2 isomorphism algorithm,
1071 * see P. Foggia, C. Sansone, M. Vento, An Improved algorithm for
1072 * matching large graphs, Proc. of the 3rd IAPR-TC-15 International
1073 * Workshop on Graph-based Representations, Italy, 2001.</para>
1074 *
1075 * <para>For using it you need to define a callback function of type
1076 * \ref igraph_isohandler_t. This function will be called whenever VF2
1077 * finds an isomorphism between the two graphs. The mapping between
1078 * the two graphs will be also provided to this function. If the
1079 * callback returns a nonzero value then the search is continued,
1080 * otherwise it stops. The callback function must not destroy the
1081 * mapping vectors that are passed to it.
1082 * \param graph1 The first input graph.
1083 * \param graph2 The second input graph.
1084 * \param vertex_color1 An optional color vector for the first graph. If
1085 * color vectors are given for both graphs, then the isomorphism is
1086 * calculated on the colored graphs; i.e. two vertices can match
1087 * only if their color also matches. Supply a null pointer here if
1088 * your graphs are not colored.
1089 * \param vertex_color2 An optional color vector for the second graph. See
1090 * the previous argument for explanation.
1091 * \param edge_color1 An optional edge color vector for the first
1092 * graph. The matching edges in the two graphs must have matching
1093 * colors as well. Supply a null pointer here if your graphs are not
1094 * edge-colored.
1095 * \param edge_color2 The edge color vector for the second graph.
1096 * \param map12 Pointer to an initialized vector or \c NULL. If not \c
1097 * NULL and the supplied graphs are isomorphic then the permutation
1098 * taking \p graph1 to \p graph is stored here. If not \c NULL and the
1099 * graphs are not isomorphic then a zero-length vector is returned.
1100 * \param map21 This is the same as \p map12, but for the permutation
1101 * taking \p graph2 to \p graph1.
1102 * \param isohandler_fn The callback function to be called if an
1103 * isomorphism is found. See also \ref igraph_isohandler_t.
1104 * \param node_compat_fn A pointer to a function of type \ref
1105 * igraph_isocompat_t. This function will be called by the algorithm to
1106 * determine whether two nodes are compatible.
1107 * \param edge_compat_fn A pointer to a function of type \ref
1108 * igraph_isocompat_t. This function will be called by the algorithm to
1109 * determine whether two edges are compatible.
1110 * \param arg Extra argument to supply to functions \p isohandler_fn, \p
1111 * node_compat_fn and \p edge_compat_fn.
1112 * \return Error code.
1113 *
1114 * Time complexity: exponential.
1115 */
1116
igraph_isomorphic_function_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_vector_t * map12,igraph_vector_t * map21,igraph_isohandler_t * isohandler_fn,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)1117 int igraph_isomorphic_function_vf2(const igraph_t *graph1, const igraph_t *graph2,
1118 const igraph_vector_int_t *vertex_color1,
1119 const igraph_vector_int_t *vertex_color2,
1120 const igraph_vector_int_t *edge_color1,
1121 const igraph_vector_int_t *edge_color2,
1122 igraph_vector_t *map12,
1123 igraph_vector_t *map21,
1124 igraph_isohandler_t *isohandler_fn,
1125 igraph_isocompat_t *node_compat_fn,
1126 igraph_isocompat_t *edge_compat_fn,
1127 void *arg) {
1128
1129 long int no_of_nodes = igraph_vcount(graph1);
1130 long int no_of_edges = igraph_ecount(graph1);
1131 igraph_vector_t mycore_1, mycore_2, *core_1 = &mycore_1, *core_2 = &mycore_2;
1132 igraph_vector_t in_1, in_2, out_1, out_2;
1133 long int in_1_size = 0, in_2_size = 0, out_1_size = 0, out_2_size = 0;
1134 igraph_vector_t *inneis_1, *inneis_2, *outneis_1, *outneis_2;
1135 long int matched_nodes = 0;
1136 long int depth;
1137 long int cand1, cand2;
1138 long int last1, last2;
1139 igraph_stack_t path;
1140 igraph_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
1141 igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;
1142
1143 if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
1144 IGRAPH_ERROR("Cannot compare directed and undirected graphs",
1145 IGRAPH_EINVAL);
1146 }
1147
1148 if ( (vertex_color1 && !vertex_color2) || (!vertex_color1 && vertex_color2) ) {
1149 IGRAPH_WARNING("Only one graph is vertex-colored, vertex colors will be ignored");
1150 vertex_color1 = vertex_color2 = 0;
1151 }
1152
1153 if ( (edge_color1 && !edge_color2) || (!edge_color1 && edge_color2)) {
1154 IGRAPH_WARNING("Only one graph is edge-colored, edge colors will be ignored");
1155 edge_color1 = edge_color2 = 0;
1156 }
1157
1158 if (no_of_nodes != igraph_vcount(graph2) ||
1159 no_of_edges != igraph_ecount(graph2)) {
1160 return 0;
1161 }
1162
1163 if (vertex_color1) {
1164 if (igraph_vector_int_size(vertex_color1) != no_of_nodes ||
1165 igraph_vector_int_size(vertex_color2) != no_of_nodes) {
1166 IGRAPH_ERROR("Invalid vertex color vector length", IGRAPH_EINVAL);
1167 }
1168 }
1169
1170 if (edge_color1) {
1171 if (igraph_vector_int_size(edge_color1) != no_of_edges ||
1172 igraph_vector_int_size(edge_color2) != no_of_edges) {
1173 IGRAPH_ERROR("Invalid edge color vector length", IGRAPH_EINVAL);
1174 }
1175 }
1176
1177 /* Check color distribution */
1178 if (vertex_color1) {
1179 int ret = 0;
1180 igraph_vector_int_t tmp1, tmp2;
1181 IGRAPH_CHECK(igraph_vector_int_copy(&tmp1, vertex_color1));
1182 IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp1);
1183 IGRAPH_CHECK(igraph_vector_int_copy(&tmp2, vertex_color2));
1184 IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp2);
1185 igraph_vector_int_sort(&tmp1);
1186 igraph_vector_int_sort(&tmp2);
1187 ret = !igraph_vector_int_all_e(&tmp1, &tmp2);
1188 igraph_vector_int_destroy(&tmp1);
1189 igraph_vector_int_destroy(&tmp2);
1190 IGRAPH_FINALLY_CLEAN(2);
1191 if (ret) {
1192 return 0;
1193 }
1194 }
1195
1196 /* Check edge color distribution */
1197 if (edge_color1) {
1198 int ret = 0;
1199 igraph_vector_int_t tmp1, tmp2;
1200 IGRAPH_CHECK(igraph_vector_int_copy(&tmp1, edge_color1));
1201 IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp1);
1202 IGRAPH_CHECK(igraph_vector_int_copy(&tmp2, edge_color2));
1203 IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp2);
1204 igraph_vector_int_sort(&tmp1);
1205 igraph_vector_int_sort(&tmp2);
1206 ret = !igraph_vector_int_all_e(&tmp1, &tmp2);
1207 igraph_vector_int_destroy(&tmp1);
1208 igraph_vector_int_destroy(&tmp2);
1209 IGRAPH_FINALLY_CLEAN(2);
1210 if (ret) {
1211 return 0;
1212 }
1213 }
1214
1215 if (map12) {
1216 core_1 = map12;
1217 IGRAPH_CHECK(igraph_vector_resize(core_1, no_of_nodes));
1218 } else {
1219 IGRAPH_VECTOR_INIT_FINALLY(core_1, no_of_nodes);
1220 }
1221 igraph_vector_fill(core_1, -1);
1222 if (map21) {
1223 core_2 = map21;
1224 IGRAPH_CHECK(igraph_vector_resize(core_2, no_of_nodes));
1225 igraph_vector_null(core_2);
1226 } else {
1227 IGRAPH_VECTOR_INIT_FINALLY(core_2, no_of_nodes);
1228 }
1229 igraph_vector_fill(core_2, -1);
1230
1231 IGRAPH_VECTOR_INIT_FINALLY(&in_1, no_of_nodes);
1232 IGRAPH_VECTOR_INIT_FINALLY(&in_2, no_of_nodes);
1233 IGRAPH_VECTOR_INIT_FINALLY(&out_1, no_of_nodes);
1234 IGRAPH_VECTOR_INIT_FINALLY(&out_2, no_of_nodes);
1235 IGRAPH_CHECK(igraph_stack_init(&path, 0));
1236 IGRAPH_FINALLY(igraph_stack_destroy, &path);
1237 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &inadj1, IGRAPH_IN,
1238 IGRAPH_SIMPLIFY));
1239 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj1);
1240 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &outadj1, IGRAPH_OUT,
1241 IGRAPH_SIMPLIFY));
1242 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj1);
1243 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &inadj2, IGRAPH_IN,
1244 IGRAPH_SIMPLIFY));
1245 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj2);
1246 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &outadj2, IGRAPH_OUT,
1247 IGRAPH_SIMPLIFY));
1248 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj2);
1249 IGRAPH_VECTOR_INIT_FINALLY(&indeg1, 0);
1250 IGRAPH_VECTOR_INIT_FINALLY(&indeg2, 0);
1251 IGRAPH_VECTOR_INIT_FINALLY(&outdeg1, 0);
1252 IGRAPH_VECTOR_INIT_FINALLY(&outdeg2, 0);
1253
1254 IGRAPH_CHECK(igraph_stack_reserve(&path, no_of_nodes * 2));
1255 IGRAPH_CHECK(igraph_degree(graph1, &indeg1, igraph_vss_all(),
1256 IGRAPH_IN, IGRAPH_LOOPS));
1257 IGRAPH_CHECK(igraph_degree(graph2, &indeg2, igraph_vss_all(),
1258 IGRAPH_IN, IGRAPH_LOOPS));
1259 IGRAPH_CHECK(igraph_degree(graph1, &outdeg1, igraph_vss_all(),
1260 IGRAPH_OUT, IGRAPH_LOOPS));
1261 IGRAPH_CHECK(igraph_degree(graph2, &outdeg2, igraph_vss_all(),
1262 IGRAPH_OUT, IGRAPH_LOOPS));
1263
1264 depth = 0; last1 = -1; last2 = -1;
1265 while (depth >= 0) {
1266 long int i;
1267
1268 IGRAPH_ALLOW_INTERRUPTION();
1269
1270 cand1 = -1; cand2 = -1;
1271 /* Search for the next pair to try */
1272 if ((in_1_size != in_2_size) ||
1273 (out_1_size != out_2_size)) {
1274 /* step back, nothing to do */
1275 } else if (out_1_size > 0 && out_2_size > 0) {
1276 /**************************************************************/
1277 /* cand2, search not always needed */
1278 if (last2 >= 0) {
1279 cand2 = last2;
1280 } else {
1281 i = 0;
1282 while (cand2 < 0 && i < no_of_nodes) {
1283 if (VECTOR(out_2)[i] > 0 && VECTOR(*core_2)[i] < 0) {
1284 cand2 = i;
1285 }
1286 i++;
1287 }
1288 }
1289 /* search for cand1 now, it should be bigger than last1 */
1290 i = last1 + 1;
1291 while (cand1 < 0 && i < no_of_nodes) {
1292 if (VECTOR(out_1)[i] > 0 && VECTOR(*core_1)[i] < 0) {
1293 cand1 = i;
1294 }
1295 i++;
1296 }
1297 } else if (in_1_size > 0 && in_2_size > 0) {
1298 /**************************************************************/
1299 /* cand2, search not always needed */
1300 if (last2 >= 0) {
1301 cand2 = last2;
1302 } else {
1303 i = 0;
1304 while (cand2 < 0 && i < no_of_nodes) {
1305 if (VECTOR(in_2)[i] > 0 && VECTOR(*core_2)[i] < 0) {
1306 cand2 = i;
1307 }
1308 i++;
1309 }
1310 }
1311 /* search for cand1 now, should be bigger than last1 */
1312 i = last1 + 1;
1313 while (cand1 < 0 && i < no_of_nodes) {
1314 if (VECTOR(in_1)[i] > 0 && VECTOR(*core_1)[i] < 0) {
1315 cand1 = i;
1316 }
1317 i++;
1318 }
1319 } else {
1320 /**************************************************************/
1321 /* cand2, search not always needed */
1322 if (last2 >= 0) {
1323 cand2 = last2;
1324 } else {
1325 i = 0;
1326 while (cand2 < 0 && i < no_of_nodes) {
1327 if (VECTOR(*core_2)[i] < 0) {
1328 cand2 = i;
1329 }
1330 i++;
1331 }
1332 }
1333 /* search for cand1, should be bigger than last1 */
1334 i = last1 + 1;
1335 while (cand1 < 0 && i < no_of_nodes) {
1336 if (VECTOR(*core_1)[i] < 0) {
1337 cand1 = i;
1338 }
1339 i++;
1340 }
1341 }
1342
1343 /* Ok, we have cand1, cand2 as candidates. Or not? */
1344 if (cand1 < 0 || cand2 < 0) {
1345 /**************************************************************/
1346 /* dead end, step back, if possible. Otherwise we'll terminate */
1347 if (depth >= 1) {
1348 last2 = (long int) igraph_stack_pop(&path);
1349 last1 = (long int) igraph_stack_pop(&path);
1350 matched_nodes -= 1;
1351 VECTOR(*core_1)[last1] = -1;
1352 VECTOR(*core_2)[last2] = -1;
1353
1354 if (VECTOR(in_1)[last1] != 0) {
1355 in_1_size += 1;
1356 }
1357 if (VECTOR(out_1)[last1] != 0) {
1358 out_1_size += 1;
1359 }
1360 if (VECTOR(in_2)[last2] != 0) {
1361 in_2_size += 1;
1362 }
1363 if (VECTOR(out_2)[last2] != 0) {
1364 out_2_size += 1;
1365 }
1366
1367 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) last1);
1368 for (i = 0; i < igraph_vector_size(inneis_1); i++) {
1369 long int node = (long int) VECTOR(*inneis_1)[i];
1370 if (VECTOR(in_1)[node] == depth) {
1371 VECTOR(in_1)[node] = 0;
1372 in_1_size -= 1;
1373 }
1374 }
1375 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) last1);
1376 for (i = 0; i < igraph_vector_size(outneis_1); i++) {
1377 long int node = (long int) VECTOR(*outneis_1)[i];
1378 if (VECTOR(out_1)[node] == depth) {
1379 VECTOR(out_1)[node] = 0;
1380 out_1_size -= 1;
1381 }
1382 }
1383 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) last2);
1384 for (i = 0; i < igraph_vector_size(inneis_2); i++) {
1385 long int node = (long int) VECTOR(*inneis_2)[i];
1386 if (VECTOR(in_2)[node] == depth) {
1387 VECTOR(in_2)[node] = 0;
1388 in_2_size -= 1;
1389 }
1390 }
1391 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) last2);
1392 for (i = 0; i < igraph_vector_size(outneis_2); i++) {
1393 long int node = (long int) VECTOR(*outneis_2)[i];
1394 if (VECTOR(out_2)[node] == depth) {
1395 VECTOR(out_2)[node] = 0;
1396 out_2_size -= 1;
1397 }
1398 }
1399
1400 } /* end of stepping back */
1401
1402 depth -= 1;
1403
1404 } else {
1405 /**************************************************************/
1406 /* step forward if worth, check if worth first */
1407 long int xin1 = 0, xin2 = 0, xout1 = 0, xout2 = 0;
1408 igraph_bool_t end = 0;
1409 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
1410 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
1411 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
1412 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
1413 if (VECTOR(indeg1)[cand1] != VECTOR(indeg2)[cand2] ||
1414 VECTOR(outdeg1)[cand1] != VECTOR(outdeg2)[cand2]) {
1415 end = 1;
1416 }
1417 if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
1418 end = 1;
1419 }
1420 if (node_compat_fn && !node_compat_fn(graph1, graph2,
1421 (igraph_integer_t) cand1,
1422 (igraph_integer_t) cand2, arg)) {
1423 end = 1;
1424 }
1425
1426 for (i = 0; !end && i < igraph_vector_size(inneis_1); i++) {
1427 long int node = (long int) VECTOR(*inneis_1)[i];
1428 if (VECTOR(*core_1)[node] >= 0) {
1429 long int node2 = (long int) VECTOR(*core_1)[node];
1430 /* check if there is a node2->cand2 edge */
1431 if (!igraph_vector_binsearch2(inneis_2, node2)) {
1432 end = 1;
1433 } else if (edge_color1 || edge_compat_fn) {
1434 igraph_integer_t eid1, eid2;
1435 igraph_get_eid(graph1, &eid1, (igraph_integer_t) node,
1436 (igraph_integer_t) cand1, /*directed=*/ 1,
1437 /*error=*/ 1);
1438 igraph_get_eid(graph2, &eid2, (igraph_integer_t) node2,
1439 (igraph_integer_t) cand2, /*directed=*/ 1,
1440 /*error=*/ 1);
1441 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
1442 VECTOR(*edge_color2)[(long int)eid2]) {
1443 end = 1;
1444 }
1445 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
1446 eid1, eid2, arg)) {
1447 end = 1;
1448 }
1449 }
1450 } else {
1451 if (VECTOR(in_1)[node] != 0) {
1452 xin1++;
1453 }
1454 if (VECTOR(out_1)[node] != 0) {
1455 xout1++;
1456 }
1457 }
1458 }
1459 for (i = 0; !end && i < igraph_vector_size(outneis_1); i++) {
1460 long int node = (long int) VECTOR(*outneis_1)[i];
1461 if (VECTOR(*core_1)[node] >= 0) {
1462 long int node2 = (long int) VECTOR(*core_1)[node];
1463 /* check if there is a cand2->node2 edge */
1464 if (!igraph_vector_binsearch2(outneis_2, node2)) {
1465 end = 1;
1466 } else if (edge_color1 || edge_compat_fn) {
1467 igraph_integer_t eid1, eid2;
1468 igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1,
1469 (igraph_integer_t) node, /*directed=*/ 1,
1470 /*error=*/ 1);
1471 igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2,
1472 (igraph_integer_t) node2, /*directed=*/ 1,
1473 /*error=*/ 1);
1474 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
1475 VECTOR(*edge_color2)[(long int)eid2]) {
1476 end = 1;
1477 }
1478 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
1479 eid1, eid2, arg)) {
1480 end = 1;
1481 }
1482 }
1483 } else {
1484 if (VECTOR(in_1)[node] != 0) {
1485 xin1++;
1486 }
1487 if (VECTOR(out_1)[node] != 0) {
1488 xout1++;
1489 }
1490 }
1491 }
1492 for (i = 0; !end && i < igraph_vector_size(inneis_2); i++) {
1493 long int node = (long int) VECTOR(*inneis_2)[i];
1494 if (VECTOR(*core_2)[node] >= 0) {
1495 long int node2 = (long int) VECTOR(*core_2)[node];
1496 /* check if there is a node2->cand1 edge */
1497 if (!igraph_vector_binsearch2(inneis_1, node2)) {
1498 end = 1;
1499 } else if (edge_color1 || edge_compat_fn) {
1500 igraph_integer_t eid1, eid2;
1501 igraph_get_eid(graph1, &eid1, (igraph_integer_t) node2,
1502 (igraph_integer_t) cand1, /*directed=*/ 1,
1503 /*error=*/ 1);
1504 igraph_get_eid(graph2, &eid2, (igraph_integer_t) node,
1505 (igraph_integer_t) cand2, /*directed=*/ 1,
1506 /*error=*/ 1);
1507 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
1508 VECTOR(*edge_color2)[(long int)eid2]) {
1509 end = 1;
1510 }
1511 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
1512 eid1, eid2, arg)) {
1513 end = 1;
1514 }
1515 }
1516 } else {
1517 if (VECTOR(in_2)[node] != 0) {
1518 xin2++;
1519 }
1520 if (VECTOR(out_2)[node] != 0) {
1521 xout2++;
1522 }
1523 }
1524 }
1525 for (i = 0; !end && i < igraph_vector_size(outneis_2); i++) {
1526 long int node = (long int) VECTOR(*outneis_2)[i];
1527 if (VECTOR(*core_2)[node] >= 0) {
1528 long int node2 = (long int) VECTOR(*core_2)[node];
1529 /* check if there is a cand1->node2 edge */
1530 if (!igraph_vector_binsearch2(outneis_1, node2)) {
1531 end = 1;
1532 } else if (edge_color1 || edge_compat_fn) {
1533 igraph_integer_t eid1, eid2;
1534 igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1,
1535 (igraph_integer_t) node2, /*directed=*/ 1,
1536 /*error=*/ 1);
1537 igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2,
1538 (igraph_integer_t) node, /*directed=*/ 1,
1539 /*error=*/ 1);
1540 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
1541 VECTOR(*edge_color2)[(long int)eid2]) {
1542 end = 1;
1543 }
1544 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
1545 eid1, eid2, arg)) {
1546 end = 1;
1547 }
1548 }
1549 } else {
1550 if (VECTOR(in_2)[node] != 0) {
1551 xin2++;
1552 }
1553 if (VECTOR(out_2)[node] != 0) {
1554 xout2++;
1555 }
1556 }
1557 }
1558
1559 if (!end && (xin1 == xin2 && xout1 == xout2)) {
1560 /* Ok, we add the (cand1, cand2) pair to the mapping */
1561 depth += 1;
1562 IGRAPH_CHECK(igraph_stack_push(&path, cand1));
1563 IGRAPH_CHECK(igraph_stack_push(&path, cand2));
1564 matched_nodes += 1;
1565 VECTOR(*core_1)[cand1] = cand2;
1566 VECTOR(*core_2)[cand2] = cand1;
1567
1568 /* update in_*, out_* */
1569 if (VECTOR(in_1)[cand1] != 0) {
1570 in_1_size -= 1;
1571 }
1572 if (VECTOR(out_1)[cand1] != 0) {
1573 out_1_size -= 1;
1574 }
1575 if (VECTOR(in_2)[cand2] != 0) {
1576 in_2_size -= 1;
1577 }
1578 if (VECTOR(out_2)[cand2] != 0) {
1579 out_2_size -= 1;
1580 }
1581
1582 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
1583 for (i = 0; i < igraph_vector_size(inneis_1); i++) {
1584 long int node = (long int) VECTOR(*inneis_1)[i];
1585 if (VECTOR(in_1)[node] == 0 && VECTOR(*core_1)[node] < 0) {
1586 VECTOR(in_1)[node] = depth;
1587 in_1_size += 1;
1588 }
1589 }
1590 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
1591 for (i = 0; i < igraph_vector_size(outneis_1); i++) {
1592 long int node = (long int) VECTOR(*outneis_1)[i];
1593 if (VECTOR(out_1)[node] == 0 && VECTOR(*core_1)[node] < 0) {
1594 VECTOR(out_1)[node] = depth;
1595 out_1_size += 1;
1596 }
1597 }
1598 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
1599 for (i = 0; i < igraph_vector_size(inneis_2); i++) {
1600 long int node = (long int) VECTOR(*inneis_2)[i];
1601 if (VECTOR(in_2)[node] == 0 && VECTOR(*core_2)[node] < 0) {
1602 VECTOR(in_2)[node] = depth;
1603 in_2_size += 1;
1604 }
1605 }
1606 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
1607 for (i = 0; i < igraph_vector_size(outneis_2); i++) {
1608 long int node = (long int) VECTOR(*outneis_2)[i];
1609 if (VECTOR(out_2)[node] == 0 && VECTOR(*core_2)[node] < 0) {
1610 VECTOR(out_2)[node] = depth;
1611 out_2_size += 1;
1612 }
1613 }
1614 last1 = -1; last2 = -1; /* this the first time here */
1615 } else {
1616 last1 = cand1;
1617 last2 = cand2;
1618 }
1619
1620 }
1621
1622 if (matched_nodes == no_of_nodes && isohandler_fn) {
1623 if (!isohandler_fn(core_1, core_2, arg)) {
1624 break;
1625 }
1626 }
1627 }
1628
1629 igraph_vector_destroy(&outdeg2);
1630 igraph_vector_destroy(&outdeg1);
1631 igraph_vector_destroy(&indeg2);
1632 igraph_vector_destroy(&indeg1);
1633 igraph_lazy_adjlist_destroy(&outadj2);
1634 igraph_lazy_adjlist_destroy(&inadj2);
1635 igraph_lazy_adjlist_destroy(&outadj1);
1636 igraph_lazy_adjlist_destroy(&inadj1);
1637 igraph_stack_destroy(&path);
1638 igraph_vector_destroy(&out_2);
1639 igraph_vector_destroy(&out_1);
1640 igraph_vector_destroy(&in_2);
1641 igraph_vector_destroy(&in_1);
1642 IGRAPH_FINALLY_CLEAN(13);
1643 if (!map21) {
1644 igraph_vector_destroy(core_2);
1645 IGRAPH_FINALLY_CLEAN(1);
1646 }
1647 if (!map12) {
1648 igraph_vector_destroy(core_1);
1649 IGRAPH_FINALLY_CLEAN(1);
1650 }
1651
1652 return 0;
1653 }
1654
1655 typedef struct {
1656 igraph_isocompat_t *node_compat_fn, *edge_compat_fn;
1657 void *arg, *carg;
1658 } igraph_i_iso_cb_data_t;
1659
igraph_i_isocompat_node_cb(const igraph_t * graph1,const igraph_t * graph2,const igraph_integer_t g1_num,const igraph_integer_t g2_num,void * arg)1660 static igraph_bool_t igraph_i_isocompat_node_cb(
1661 const igraph_t *graph1,
1662 const igraph_t *graph2,
1663 const igraph_integer_t g1_num,
1664 const igraph_integer_t g2_num,
1665 void *arg) {
1666 igraph_i_iso_cb_data_t *data = arg;
1667 return data->node_compat_fn(graph1, graph2, g1_num, g2_num, data->carg);
1668 }
1669
igraph_i_isocompat_edge_cb(const igraph_t * graph1,const igraph_t * graph2,const igraph_integer_t g1_num,const igraph_integer_t g2_num,void * arg)1670 static igraph_bool_t igraph_i_isocompat_edge_cb(
1671 const igraph_t *graph1,
1672 const igraph_t *graph2,
1673 const igraph_integer_t g1_num,
1674 const igraph_integer_t g2_num,
1675 void *arg) {
1676 igraph_i_iso_cb_data_t *data = arg;
1677 return data->edge_compat_fn(graph1, graph2, g1_num, g2_num, data->carg);
1678 }
1679
igraph_i_isomorphic_vf2(igraph_vector_t * map12,igraph_vector_t * map21,void * arg)1680 static igraph_bool_t igraph_i_isomorphic_vf2(igraph_vector_t *map12,
1681 igraph_vector_t *map21,
1682 void *arg) {
1683 igraph_i_iso_cb_data_t *data = arg;
1684 igraph_bool_t *iso = data->arg;
1685 IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
1686 *iso = 1;
1687 return 0; /* don't need to continue */
1688 }
1689
1690 /**
1691 * \function igraph_isomorphic_vf2
1692 * \brief Isomorphism via VF2
1693 *
1694 * </para><para>
1695 * This function performs the VF2 algorithm via calling \ref
1696 * igraph_isomorphic_function_vf2().
1697 *
1698 * </para><para> Note that this function cannot be used for
1699 * deciding subgraph isomorphism, use \ref igraph_subisomorphic_vf2()
1700 * for that.
1701 * \param graph1 The first graph, may be directed or undirected.
1702 * \param graph2 The second graph. It must have the same directedness
1703 * as \p graph1, otherwise an error is reported.
1704 * \param vertex_color1 An optional color vector for the first graph. If
1705 * color vectors are given for both graphs, then the isomorphism is
1706 * calculated on the colored graphs; i.e. two vertices can match
1707 * only if their color also matches. Supply a null pointer here if
1708 * your graphs are not colored.
1709 * \param vertex_color2 An optional color vector for the second graph. See
1710 * the previous argument for explanation.
1711 * \param edge_color1 An optional edge color vector for the first
1712 * graph. The matching edges in the two graphs must have matching
1713 * colors as well. Supply a null pointer here if your graphs are not
1714 * edge-colored.
1715 * \param edge_color2 The edge color vector for the second graph.
1716 * \param iso Pointer to a logical constant, the result of the
1717 * algorithm will be placed here.
1718 * \param map12 Pointer to an initialized vector or a NULL pointer. If not
1719 * a NULL pointer then the mapping from \p graph1 to \p graph2 is
1720 * stored here. If the graphs are not isomorphic then the vector is
1721 * cleared (i.e. has zero elements).
1722 * \param map21 Pointer to an initialized vector or a NULL pointer. If not
1723 * a NULL pointer then the mapping from \p graph2 to \p graph1 is
1724 * stored here. If the graphs are not isomorphic then the vector is
1725 * cleared (i.e. has zero elements).
1726 * \param node_compat_fn A pointer to a function of type \ref
1727 * igraph_isocompat_t. This function will be called by the algorithm to
1728 * determine whether two nodes are compatible.
1729 * \param edge_compat_fn A pointer to a function of type \ref
1730 * igraph_isocompat_t. This function will be called by the algorithm to
1731 * determine whether two edges are compatible.
1732 * \param arg Extra argument to supply to functions \p node_compat_fn
1733 * and \p edge_compat_fn.
1734 * \return Error code.
1735 *
1736 * \sa \ref igraph_subisomorphic_vf2(),
1737 * \ref igraph_count_isomorphisms_vf2(),
1738 * \ref igraph_get_isomorphisms_vf2(),
1739 *
1740 * Time complexity: exponential, what did you expect?
1741 *
1742 * \example examples/simple/igraph_isomorphic_vf2.c
1743 */
1744
igraph_isomorphic_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_bool_t * iso,igraph_vector_t * map12,igraph_vector_t * map21,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)1745 int igraph_isomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2,
1746 const igraph_vector_int_t *vertex_color1,
1747 const igraph_vector_int_t *vertex_color2,
1748 const igraph_vector_int_t *edge_color1,
1749 const igraph_vector_int_t *edge_color2,
1750 igraph_bool_t *iso, igraph_vector_t *map12,
1751 igraph_vector_t *map21,
1752 igraph_isocompat_t *node_compat_fn,
1753 igraph_isocompat_t *edge_compat_fn,
1754 void *arg) {
1755
1756 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, iso, arg };
1757 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
1758 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
1759 *iso = 0;
1760 IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2,
1761 vertex_color1, vertex_color2,
1762 edge_color1, edge_color2,
1763 map12, map21,
1764 (igraph_isohandler_t*)
1765 igraph_i_isomorphic_vf2,
1766 ncb, ecb, &data));
1767 if (! *iso) {
1768 if (map12) {
1769 igraph_vector_clear(map12);
1770 }
1771 if (map21) {
1772 igraph_vector_clear(map21);
1773 }
1774 }
1775 return 0;
1776 }
1777
igraph_i_count_isomorphisms_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)1778 static igraph_bool_t igraph_i_count_isomorphisms_vf2(
1779 const igraph_vector_t *map12,
1780 const igraph_vector_t *map21,
1781 void *arg) {
1782 igraph_i_iso_cb_data_t *data = arg;
1783 igraph_integer_t *count = data->arg;
1784 IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
1785 *count += 1;
1786 return 1; /* always continue */
1787 }
1788
1789 /**
1790 * \function igraph_count_isomorphisms_vf2
1791 * Number of isomorphisms via VF2
1792 *
1793 * This function counts the number of isomorphic mappings between two
1794 * graphs. It uses the generic \ref igraph_isomorphic_function_vf2()
1795 * function.
1796 * \param graph1 The first input graph, may be directed or undirected.
1797 * \param graph2 The second input graph, it must have the same
1798 * directedness as \p graph1, or an error will be reported.
1799 * \param vertex_color1 An optional color vector for the first graph. If
1800 * color vectors are given for both graphs, then the isomorphism is
1801 * calculated on the colored graphs; i.e. two vertices can match
1802 * only if their color also matches. Supply a null pointer here if
1803 * your graphs are not colored.
1804 * \param vertex_color2 An optional color vector for the second graph. See
1805 * the previous argument for explanation.
1806 * \param edge_color1 An optional edge color vector for the first
1807 * graph. The matching edges in the two graphs must have matching
1808 * colors as well. Supply a null pointer here if your graphs are not
1809 * edge-colored.
1810 * \param edge_color2 The edge color vector for the second graph.
1811 * \param count Point to an integer, the result will be stored here.
1812 * \param node_compat_fn A pointer to a function of type \ref
1813 * igraph_isocompat_t. This function will be called by the algorithm to
1814 * determine whether two nodes are compatible.
1815 * \param edge_compat_fn A pointer to a function of type \ref
1816 * igraph_isocompat_t. This function will be called by the algorithm to
1817 * determine whether two edges are compatible.
1818 * \param arg Extra argument to supply to functions \p node_compat_fn and
1819 * \p edge_compat_fn.
1820 * \return Error code.
1821 *
1822 * Time complexity: exponential.
1823 */
1824
igraph_count_isomorphisms_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_integer_t * count,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)1825 int igraph_count_isomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2,
1826 const igraph_vector_int_t *vertex_color1,
1827 const igraph_vector_int_t *vertex_color2,
1828 const igraph_vector_int_t *edge_color1,
1829 const igraph_vector_int_t *edge_color2,
1830 igraph_integer_t *count,
1831 igraph_isocompat_t *node_compat_fn,
1832 igraph_isocompat_t *edge_compat_fn,
1833 void *arg) {
1834
1835 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn,
1836 count, arg
1837 };
1838 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
1839 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
1840 *count = 0;
1841 IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2,
1842 vertex_color1, vertex_color2,
1843 edge_color1, edge_color2,
1844 0, 0,
1845 (igraph_isohandler_t*)
1846 igraph_i_count_isomorphisms_vf2,
1847 ncb, ecb, &data));
1848 return 0;
1849 }
1850
igraph_i_get_isomorphisms_free(igraph_vector_ptr_t * data)1851 static void igraph_i_get_isomorphisms_free(igraph_vector_ptr_t *data) {
1852 long int i, n = igraph_vector_ptr_size(data);
1853 for (i = 0; i < n; i++) {
1854 igraph_vector_t *vec = VECTOR(*data)[i];
1855 igraph_vector_destroy(vec);
1856 igraph_free(vec);
1857 }
1858 }
1859
igraph_i_get_isomorphisms_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)1860 static igraph_bool_t igraph_i_get_isomorphisms_vf2(
1861 const igraph_vector_t *map12,
1862 const igraph_vector_t *map21,
1863 void *arg) {
1864
1865 igraph_i_iso_cb_data_t *data = arg;
1866 igraph_vector_ptr_t *ptrvector = data->arg;
1867 igraph_vector_t *newvector = igraph_Calloc(1, igraph_vector_t);
1868 IGRAPH_UNUSED(map12);
1869 if (!newvector) {
1870 igraph_error("Out of memory", __FILE__, __LINE__, IGRAPH_ENOMEM);
1871 return 0; /* stop right here */
1872 }
1873 IGRAPH_FINALLY(igraph_free, newvector);
1874 IGRAPH_CHECK(igraph_vector_copy(newvector, map21));
1875 IGRAPH_FINALLY(igraph_vector_destroy, newvector);
1876 IGRAPH_CHECK(igraph_vector_ptr_push_back(ptrvector, newvector));
1877 IGRAPH_FINALLY_CLEAN(2);
1878
1879 return 1; /* continue finding subisomorphisms */
1880 }
1881
1882 /**
1883 * \function igraph_get_isomorphisms_vf2
1884 * Collect the isomorphic mappings
1885 *
1886 * This function finds all the isomorphic mappings between two
1887 * graphs. It uses the \ref igraph_isomorphic_function_vf2()
1888 * function. Call the function with the same graph as \p graph1 and \p
1889 * graph2 to get automorphisms.
1890 * \param graph1 The first input graph, may be directed or undirected.
1891 * \param graph2 The second input graph, it must have the same
1892 * directedness as \p graph1, or an error will be reported.
1893 * \param vertex_color1 An optional color vector for the first graph. If
1894 * color vectors are given for both graphs, then the isomorphism is
1895 * calculated on the colored graphs; i.e. two vertices can match
1896 * only if their color also matches. Supply a null pointer here if
1897 * your graphs are not colored.
1898 * \param vertex_color2 An optional color vector for the second graph. See
1899 * the previous argument for explanation.
1900 * \param edge_color1 An optional edge color vector for the first
1901 * graph. The matching edges in the two graphs must have matching
1902 * colors as well. Supply a null pointer here if your graphs are not
1903 * edge-colored.
1904 * \param edge_color2 The edge color vector for the second graph.
1905 * \param maps Pointer vector. On return it is empty if the input graphs
1906 * are no isomorphic. Otherwise it contains pointers to
1907 * \ref igraph_vector_t objects, each vector is an
1908 * isomorphic mapping of \p graph2 to \p graph1. Please note that
1909 * you need to 1) Destroy the vectors via \ref
1910 * igraph_vector_destroy(), 2) free them via
1911 * \ref igraph_free() and then 3) call \ref
1912 * igraph_vector_ptr_destroy() on the pointer vector to deallocate all
1913 * memory when \p maps is no longer needed.
1914 * \param node_compat_fn A pointer to a function of type \ref
1915 * igraph_isocompat_t. This function will be called by the algorithm to
1916 * determine whether two nodes are compatible.
1917 * \param edge_compat_fn A pointer to a function of type \ref
1918 * igraph_isocompat_t. This function will be called by the algorithm to
1919 * determine whether two edges are compatible.
1920 * \param arg Extra argument to supply to functions \p node_compat_fn
1921 * and \p edge_compat_fn.
1922 * \return Error code.
1923 *
1924 * Time complexity: exponential.
1925 */
1926
igraph_get_isomorphisms_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_vector_ptr_t * maps,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)1927 int igraph_get_isomorphisms_vf2(const igraph_t *graph1,
1928 const igraph_t *graph2,
1929 const igraph_vector_int_t *vertex_color1,
1930 const igraph_vector_int_t *vertex_color2,
1931 const igraph_vector_int_t *edge_color1,
1932 const igraph_vector_int_t *edge_color2,
1933 igraph_vector_ptr_t *maps,
1934 igraph_isocompat_t *node_compat_fn,
1935 igraph_isocompat_t *edge_compat_fn,
1936 void *arg) {
1937
1938 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, maps, arg };
1939 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
1940 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
1941
1942 igraph_vector_ptr_clear(maps);
1943 IGRAPH_FINALLY(igraph_i_get_isomorphisms_free, maps);
1944 IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2,
1945 vertex_color1, vertex_color2,
1946 edge_color1, edge_color2,
1947 0, 0,
1948 (igraph_isohandler_t*)
1949 igraph_i_get_isomorphisms_vf2,
1950 ncb, ecb, &data));
1951 IGRAPH_FINALLY_CLEAN(1);
1952 return 0;
1953 }
1954
1955
1956 /**
1957 * \function igraph_subisomorphic
1958 * Decide subgraph isomorphism
1959 *
1960 * Check whether \p graph2 is isomorphic to a subgraph of \p graph1.
1961 * Currently this function just calls \ref igraph_subisomorphic_vf2()
1962 * for all graphs.
1963 * \param graph1 The first input graph, may be directed or
1964 * undirected. This is supposed to be the bigger graph.
1965 * \param graph2 The second input graph, it must have the same
1966 * directedness as \p graph2, or an error is triggered. This is
1967 * supposed to be the smaller graph.
1968 * \param iso Pointer to a boolean, the result is stored here.
1969 * \return Error code.
1970 *
1971 * Time complexity: exponential.
1972 */
1973
igraph_subisomorphic(const igraph_t * graph1,const igraph_t * graph2,igraph_bool_t * iso)1974 int igraph_subisomorphic(const igraph_t *graph1, const igraph_t *graph2,
1975 igraph_bool_t *iso) {
1976
1977 return igraph_subisomorphic_vf2(graph1, graph2, 0, 0, 0, 0, iso, 0, 0, 0, 0, 0);
1978 }
1979
1980 /**
1981 * \function igraph_subisomorphic_function_vf2
1982 * Generic VF2 function for subgraph isomorphism problems
1983 *
1984 * This function is the pair of \ref igraph_isomorphic_function_vf2(),
1985 * for subgraph isomorphism problems. It searches for subgraphs of \p
1986 * graph1 which are isomorphic to \p graph2. When it founds an
1987 * isomorphic mapping it calls the supplied callback \p isohandler_fn.
1988 * The mapping (and its inverse) and the additional \p arg argument
1989 * are supplied to the callback.
1990 * \param graph1 The first input graph, may be directed or
1991 * undirected. This is supposed to be the larger graph.
1992 * \param graph2 The second input graph, it must have the same
1993 * directedness as \p graph1. This is supposed to be the smaller
1994 * graph.
1995 * \param vertex_color1 An optional color vector for the first graph. If
1996 * color vectors are given for both graphs, then the subgraph isomorphism is
1997 * calculated on the colored graphs; i.e. two vertices can match
1998 * only if their color also matches. Supply a null pointer here if
1999 * your graphs are not colored.
2000 * \param vertex_color2 An optional color vector for the second graph. See
2001 * the previous argument for explanation.
2002 * \param edge_color1 An optional edge color vector for the first
2003 * graph. The matching edges in the two graphs must have matching
2004 * colors as well. Supply a null pointer here if your graphs are not
2005 * edge-colored.
2006 * \param edge_color2 The edge color vector for the second graph.
2007 * \param map12 Pointer to a vector or \c NULL. If not \c NULL, then an
2008 * isomorphic mapping from \p graph1 to \p graph2 is stored here.
2009 * \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
2010 * an isomorphic mapping from \p graph2 to \p graph1 is stored
2011 * here.
2012 * \param isohandler_fn A pointer to a function of type \ref
2013 * igraph_isohandler_t. This will be called whenever a subgraph
2014 * isomorphism is found. If the function returns with a non-zero value
2015 * then the search is continued, otherwise it stops and the function
2016 * returns.
2017 * \param node_compat_fn A pointer to a function of type \ref
2018 * igraph_isocompat_t. This function will be called by the algorithm to
2019 * determine whether two nodes are compatible.
2020 * \param edge_compat_fn A pointer to a function of type \ref
2021 * igraph_isocompat_t. This function will be called by the algorithm to
2022 * determine whether two edges are compatible.
2023 * \param arg Extra argument to supply to functions \p isohandler_fn, \p
2024 * node_compat_fn and \p edge_compat_fn.
2025 * \return Error code.
2026 *
2027 * Time complexity: exponential.
2028 */
2029
igraph_subisomorphic_function_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_vector_t * map12,igraph_vector_t * map21,igraph_isohandler_t * isohandler_fn,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)2030 int igraph_subisomorphic_function_vf2(const igraph_t *graph1,
2031 const igraph_t *graph2,
2032 const igraph_vector_int_t *vertex_color1,
2033 const igraph_vector_int_t *vertex_color2,
2034 const igraph_vector_int_t *edge_color1,
2035 const igraph_vector_int_t *edge_color2,
2036 igraph_vector_t *map12,
2037 igraph_vector_t *map21,
2038 igraph_isohandler_t *isohandler_fn,
2039 igraph_isocompat_t *node_compat_fn,
2040 igraph_isocompat_t *edge_compat_fn,
2041 void *arg) {
2042
2043 long int no_of_nodes1 = igraph_vcount(graph1),
2044 no_of_nodes2 = igraph_vcount(graph2);
2045 long int no_of_edges1 = igraph_ecount(graph1),
2046 no_of_edges2 = igraph_ecount(graph2);
2047 igraph_vector_t mycore_1, mycore_2, *core_1 = &mycore_1, *core_2 = &mycore_2;
2048 igraph_vector_t in_1, in_2, out_1, out_2;
2049 long int in_1_size = 0, in_2_size = 0, out_1_size = 0, out_2_size = 0;
2050 igraph_vector_t *inneis_1, *inneis_2, *outneis_1, *outneis_2;
2051 long int matched_nodes = 0;
2052 long int depth;
2053 long int cand1, cand2;
2054 long int last1, last2;
2055 igraph_stack_t path;
2056 igraph_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
2057 igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;
2058
2059 if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
2060 IGRAPH_ERROR("Cannot compare directed and undirected graphs",
2061 IGRAPH_EINVAL);
2062 }
2063
2064 if (no_of_nodes1 < no_of_nodes2 ||
2065 no_of_edges1 < no_of_edges2) {
2066 return 0;
2067 }
2068
2069 if ( (vertex_color1 && !vertex_color2) || (!vertex_color1 && vertex_color2) ) {
2070 IGRAPH_WARNING("Only one graph is vertex colored, colors will be ignored");
2071 vertex_color1 = vertex_color2 = 0;
2072 }
2073
2074 if ( (edge_color1 && !edge_color2) || (!edge_color1 && edge_color2) ) {
2075 IGRAPH_WARNING("Only one graph is edge colored, colors will be ignored");
2076 edge_color1 = edge_color2 = 0;
2077 }
2078
2079 if (vertex_color1) {
2080 if (igraph_vector_int_size(vertex_color1) != no_of_nodes1 ||
2081 igraph_vector_int_size(vertex_color2) != no_of_nodes2) {
2082 IGRAPH_ERROR("Invalid vertex color vector length", IGRAPH_EINVAL);
2083 }
2084 }
2085
2086 if (edge_color1) {
2087 if (igraph_vector_int_size(edge_color1) != no_of_edges1 ||
2088 igraph_vector_int_size(edge_color2) != no_of_edges2) {
2089 IGRAPH_ERROR("Invalid edge color vector length", IGRAPH_EINVAL);
2090 }
2091 }
2092
2093 /* Check color distribution */
2094 if (vertex_color1) {
2095 /* TODO */
2096 }
2097
2098 /* Check edge color distribution */
2099 if (edge_color1) {
2100 /* TODO */
2101 }
2102
2103 if (map12) {
2104 core_1 = map12;
2105 IGRAPH_CHECK(igraph_vector_resize(core_1, no_of_nodes1));
2106 } else {
2107 IGRAPH_VECTOR_INIT_FINALLY(core_1, no_of_nodes1);
2108 }
2109 igraph_vector_fill(core_1, -1);
2110 if (map21) {
2111 core_2 = map21;
2112 IGRAPH_CHECK(igraph_vector_resize(core_2, no_of_nodes2));
2113 } else {
2114 IGRAPH_VECTOR_INIT_FINALLY(core_2, no_of_nodes2);
2115 }
2116 igraph_vector_fill(core_2, -1);
2117 IGRAPH_VECTOR_INIT_FINALLY(&in_1, no_of_nodes1);
2118 IGRAPH_VECTOR_INIT_FINALLY(&in_2, no_of_nodes2);
2119 IGRAPH_VECTOR_INIT_FINALLY(&out_1, no_of_nodes1);
2120 IGRAPH_VECTOR_INIT_FINALLY(&out_2, no_of_nodes2);
2121 IGRAPH_CHECK(igraph_stack_init(&path, 0));
2122 IGRAPH_FINALLY(igraph_stack_destroy, &path);
2123 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &inadj1, IGRAPH_IN,
2124 IGRAPH_SIMPLIFY));
2125 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj1);
2126 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &outadj1, IGRAPH_OUT,
2127 IGRAPH_SIMPLIFY));
2128 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj1);
2129 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &inadj2, IGRAPH_IN,
2130 IGRAPH_SIMPLIFY));
2131 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj2);
2132 IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &outadj2, IGRAPH_OUT,
2133 IGRAPH_SIMPLIFY));
2134 IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj2);
2135 IGRAPH_VECTOR_INIT_FINALLY(&indeg1, 0);
2136 IGRAPH_VECTOR_INIT_FINALLY(&indeg2, 0);
2137 IGRAPH_VECTOR_INIT_FINALLY(&outdeg1, 0);
2138 IGRAPH_VECTOR_INIT_FINALLY(&outdeg2, 0);
2139
2140 IGRAPH_CHECK(igraph_stack_reserve(&path, no_of_nodes2 * 2));
2141 IGRAPH_CHECK(igraph_degree(graph1, &indeg1, igraph_vss_all(),
2142 IGRAPH_IN, IGRAPH_LOOPS));
2143 IGRAPH_CHECK(igraph_degree(graph2, &indeg2, igraph_vss_all(),
2144 IGRAPH_IN, IGRAPH_LOOPS));
2145 IGRAPH_CHECK(igraph_degree(graph1, &outdeg1, igraph_vss_all(),
2146 IGRAPH_OUT, IGRAPH_LOOPS));
2147 IGRAPH_CHECK(igraph_degree(graph2, &outdeg2, igraph_vss_all(),
2148 IGRAPH_OUT, IGRAPH_LOOPS));
2149
2150 depth = 0; last1 = -1; last2 = -1;
2151 while (depth >= 0) {
2152 long int i;
2153
2154 IGRAPH_ALLOW_INTERRUPTION();
2155
2156 cand1 = -1; cand2 = -1;
2157 /* Search for the next pair to try */
2158 if ((in_1_size < in_2_size) ||
2159 (out_1_size < out_2_size)) {
2160 /* step back, nothing to do */
2161 } else if (out_1_size > 0 && out_2_size > 0) {
2162 /**************************************************************/
2163 /* cand2, search not always needed */
2164 if (last2 >= 0) {
2165 cand2 = last2;
2166 } else {
2167 i = 0;
2168 while (cand2 < 0 && i < no_of_nodes2) {
2169 if (VECTOR(out_2)[i] > 0 && VECTOR(*core_2)[i] < 0) {
2170 cand2 = i;
2171 }
2172 i++;
2173 }
2174 }
2175 /* search for cand1 now, it should be bigger than last1 */
2176 i = last1 + 1;
2177 while (cand1 < 0 && i < no_of_nodes1) {
2178 if (VECTOR(out_1)[i] > 0 && VECTOR(*core_1)[i] < 0) {
2179 cand1 = i;
2180 }
2181 i++;
2182 }
2183 } else if (in_1_size > 0 && in_2_size > 0) {
2184 /**************************************************************/
2185 /* cand2, search not always needed */
2186 if (last2 >= 0) {
2187 cand2 = last2;
2188 } else {
2189 i = 0;
2190 while (cand2 < 0 && i < no_of_nodes2) {
2191 if (VECTOR(in_2)[i] > 0 && VECTOR(*core_2)[i] < 0) {
2192 cand2 = i;
2193 }
2194 i++;
2195 }
2196 }
2197 /* search for cand1 now, should be bigger than last1 */
2198 i = last1 + 1;
2199 while (cand1 < 0 && i < no_of_nodes1) {
2200 if (VECTOR(in_1)[i] > 0 && VECTOR(*core_1)[i] < 0) {
2201 cand1 = i;
2202 }
2203 i++;
2204 }
2205 } else {
2206 /**************************************************************/
2207 /* cand2, search not always needed */
2208 if (last2 >= 0) {
2209 cand2 = last2;
2210 } else {
2211 i = 0;
2212 while (cand2 < 0 && i < no_of_nodes2) {
2213 if (VECTOR(*core_2)[i] < 0) {
2214 cand2 = i;
2215 }
2216 i++;
2217 }
2218 }
2219 /* search for cand1, should be bigger than last1 */
2220 i = last1 + 1;
2221 while (cand1 < 0 && i < no_of_nodes1) {
2222 if (VECTOR(*core_1)[i] < 0) {
2223 cand1 = i;
2224 }
2225 i++;
2226 }
2227 }
2228
2229 /* Ok, we have cand1, cand2 as candidates. Or not? */
2230 if (cand1 < 0 || cand2 < 0) {
2231 /**************************************************************/
2232 /* dead end, step back, if possible. Otherwise we'll terminate */
2233 if (depth >= 1) {
2234 last2 = (long int) igraph_stack_pop(&path);
2235 last1 = (long int) igraph_stack_pop(&path);
2236 matched_nodes -= 1;
2237 VECTOR(*core_1)[last1] = -1;
2238 VECTOR(*core_2)[last2] = -1;
2239
2240 if (VECTOR(in_1)[last1] != 0) {
2241 in_1_size += 1;
2242 }
2243 if (VECTOR(out_1)[last1] != 0) {
2244 out_1_size += 1;
2245 }
2246 if (VECTOR(in_2)[last2] != 0) {
2247 in_2_size += 1;
2248 }
2249 if (VECTOR(out_2)[last2] != 0) {
2250 out_2_size += 1;
2251 }
2252
2253 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) last1);
2254 for (i = 0; i < igraph_vector_size(inneis_1); i++) {
2255 long int node = (long int) VECTOR(*inneis_1)[i];
2256 if (VECTOR(in_1)[node] == depth) {
2257 VECTOR(in_1)[node] = 0;
2258 in_1_size -= 1;
2259 }
2260 }
2261 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) last1);
2262 for (i = 0; i < igraph_vector_size(outneis_1); i++) {
2263 long int node = (long int) VECTOR(*outneis_1)[i];
2264 if (VECTOR(out_1)[node] == depth) {
2265 VECTOR(out_1)[node] = 0;
2266 out_1_size -= 1;
2267 }
2268 }
2269 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) last2);
2270 for (i = 0; i < igraph_vector_size(inneis_2); i++) {
2271 long int node = (long int) VECTOR(*inneis_2)[i];
2272 if (VECTOR(in_2)[node] == depth) {
2273 VECTOR(in_2)[node] = 0;
2274 in_2_size -= 1;
2275 }
2276 }
2277 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) last2);
2278 for (i = 0; i < igraph_vector_size(outneis_2); i++) {
2279 long int node = (long int) VECTOR(*outneis_2)[i];
2280 if (VECTOR(out_2)[node] == depth) {
2281 VECTOR(out_2)[node] = 0;
2282 out_2_size -= 1;
2283 }
2284 }
2285
2286 } /* end of stepping back */
2287
2288 depth -= 1;
2289
2290 } else {
2291 /**************************************************************/
2292 /* step forward if worth, check if worth first */
2293 long int xin1 = 0, xin2 = 0, xout1 = 0, xout2 = 0;
2294 igraph_bool_t end = 0;
2295 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
2296 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
2297 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
2298 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
2299 if (VECTOR(indeg1)[cand1] < VECTOR(indeg2)[cand2] ||
2300 VECTOR(outdeg1)[cand1] < VECTOR(outdeg2)[cand2]) {
2301 end = 1;
2302 }
2303 if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
2304 end = 1;
2305 }
2306 if (node_compat_fn && !node_compat_fn(graph1, graph2,
2307 (igraph_integer_t) cand1,
2308 (igraph_integer_t) cand2, arg)) {
2309 end = 1;
2310 }
2311
2312 for (i = 0; !end && i < igraph_vector_size(inneis_1); i++) {
2313 long int node = (long int) VECTOR(*inneis_1)[i];
2314 if (VECTOR(*core_1)[node] < 0) {
2315 if (VECTOR(in_1)[node] != 0) {
2316 xin1++;
2317 }
2318 if (VECTOR(out_1)[node] != 0) {
2319 xout1++;
2320 }
2321 }
2322 }
2323 for (i = 0; !end && i < igraph_vector_size(outneis_1); i++) {
2324 long int node = (long int) VECTOR(*outneis_1)[i];
2325 if (VECTOR(*core_1)[node] < 0) {
2326 if (VECTOR(in_1)[node] != 0) {
2327 xin1++;
2328 }
2329 if (VECTOR(out_1)[node] != 0) {
2330 xout1++;
2331 }
2332 }
2333 }
2334 for (i = 0; !end && i < igraph_vector_size(inneis_2); i++) {
2335 long int node = (long int) VECTOR(*inneis_2)[i];
2336 if (VECTOR(*core_2)[node] >= 0) {
2337 long int node2 = (long int) VECTOR(*core_2)[node];
2338 /* check if there is a node2->cand1 edge */
2339 if (!igraph_vector_binsearch2(inneis_1, node2)) {
2340 end = 1;
2341 } else if (edge_color1 || edge_compat_fn) {
2342 igraph_integer_t eid1, eid2;
2343 igraph_get_eid(graph1, &eid1, (igraph_integer_t) node2,
2344 (igraph_integer_t) cand1, /*directed=*/ 1,
2345 /*error=*/ 1);
2346 igraph_get_eid(graph2, &eid2, (igraph_integer_t) node,
2347 (igraph_integer_t) cand2, /*directed=*/ 1,
2348 /*error=*/ 1);
2349 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
2350 VECTOR(*edge_color2)[(long int)eid2]) {
2351 end = 1;
2352 }
2353 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
2354 eid1, eid2, arg)) {
2355 end = 1;
2356 }
2357 }
2358 } else {
2359 if (VECTOR(in_2)[node] != 0) {
2360 xin2++;
2361 }
2362 if (VECTOR(out_2)[node] != 0) {
2363 xout2++;
2364 }
2365 }
2366 }
2367 for (i = 0; !end && i < igraph_vector_size(outneis_2); i++) {
2368 long int node = (long int) VECTOR(*outneis_2)[i];
2369 if (VECTOR(*core_2)[node] >= 0) {
2370 long int node2 = (long int) VECTOR(*core_2)[node];
2371 /* check if there is a cand1->node2 edge */
2372 if (!igraph_vector_binsearch2(outneis_1, node2)) {
2373 end = 1;
2374 } else if (edge_color1 || edge_compat_fn) {
2375 igraph_integer_t eid1, eid2;
2376 igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1,
2377 (igraph_integer_t) node2, /*directed=*/ 1,
2378 /*error=*/ 1);
2379 igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2,
2380 (igraph_integer_t) node, /*directed=*/ 1,
2381 /*error=*/ 1);
2382 if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
2383 VECTOR(*edge_color2)[(long int)eid2]) {
2384 end = 1;
2385 }
2386 if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
2387 eid1, eid2, arg)) {
2388 end = 1;
2389 }
2390 }
2391 } else {
2392 if (VECTOR(in_2)[node] != 0) {
2393 xin2++;
2394 }
2395 if (VECTOR(out_2)[node] != 0) {
2396 xout2++;
2397 }
2398 }
2399 }
2400
2401 if (!end && (xin1 >= xin2 && xout1 >= xout2)) {
2402 /* Ok, we add the (cand1, cand2) pair to the mapping */
2403 depth += 1;
2404 IGRAPH_CHECK(igraph_stack_push(&path, cand1));
2405 IGRAPH_CHECK(igraph_stack_push(&path, cand2));
2406 matched_nodes += 1;
2407 VECTOR(*core_1)[cand1] = cand2;
2408 VECTOR(*core_2)[cand2] = cand1;
2409
2410 /* update in_*, out_* */
2411 if (VECTOR(in_1)[cand1] != 0) {
2412 in_1_size -= 1;
2413 }
2414 if (VECTOR(out_1)[cand1] != 0) {
2415 out_1_size -= 1;
2416 }
2417 if (VECTOR(in_2)[cand2] != 0) {
2418 in_2_size -= 1;
2419 }
2420 if (VECTOR(out_2)[cand2] != 0) {
2421 out_2_size -= 1;
2422 }
2423
2424 inneis_1 = igraph_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
2425 for (i = 0; i < igraph_vector_size(inneis_1); i++) {
2426 long int node = (long int) VECTOR(*inneis_1)[i];
2427 if (VECTOR(in_1)[node] == 0 && VECTOR(*core_1)[node] < 0) {
2428 VECTOR(in_1)[node] = depth;
2429 in_1_size += 1;
2430 }
2431 }
2432 outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
2433 for (i = 0; i < igraph_vector_size(outneis_1); i++) {
2434 long int node = (long int) VECTOR(*outneis_1)[i];
2435 if (VECTOR(out_1)[node] == 0 && VECTOR(*core_1)[node] < 0) {
2436 VECTOR(out_1)[node] = depth;
2437 out_1_size += 1;
2438 }
2439 }
2440 inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
2441 for (i = 0; i < igraph_vector_size(inneis_2); i++) {
2442 long int node = (long int) VECTOR(*inneis_2)[i];
2443 if (VECTOR(in_2)[node] == 0 && VECTOR(*core_2)[node] < 0) {
2444 VECTOR(in_2)[node] = depth;
2445 in_2_size += 1;
2446 }
2447 }
2448 outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
2449 for (i = 0; i < igraph_vector_size(outneis_2); i++) {
2450 long int node = (long int) VECTOR(*outneis_2)[i];
2451 if (VECTOR(out_2)[node] == 0 && VECTOR(*core_2)[node] < 0) {
2452 VECTOR(out_2)[node] = depth;
2453 out_2_size += 1;
2454 }
2455 }
2456 last1 = -1; last2 = -1; /* this the first time here */
2457 } else {
2458 last1 = cand1;
2459 last2 = cand2;
2460 }
2461
2462 }
2463
2464 if (matched_nodes == no_of_nodes2 && isohandler_fn) {
2465 if (!isohandler_fn(core_1, core_2, arg)) {
2466 break;
2467 }
2468 }
2469 }
2470
2471 igraph_vector_destroy(&outdeg2);
2472 igraph_vector_destroy(&outdeg1);
2473 igraph_vector_destroy(&indeg2);
2474 igraph_vector_destroy(&indeg1);
2475 igraph_lazy_adjlist_destroy(&outadj2);
2476 igraph_lazy_adjlist_destroy(&inadj2);
2477 igraph_lazy_adjlist_destroy(&outadj1);
2478 igraph_lazy_adjlist_destroy(&inadj1);
2479 igraph_stack_destroy(&path);
2480 igraph_vector_destroy(&out_2);
2481 igraph_vector_destroy(&out_1);
2482 igraph_vector_destroy(&in_2);
2483 igraph_vector_destroy(&in_1);
2484 IGRAPH_FINALLY_CLEAN(13);
2485 if (!map21) {
2486 igraph_vector_destroy(core_2);
2487 IGRAPH_FINALLY_CLEAN(1);
2488 }
2489 if (!map12) {
2490 igraph_vector_destroy(core_1);
2491 IGRAPH_FINALLY_CLEAN(1);
2492 }
2493
2494 return 0;
2495 }
2496
igraph_i_subisomorphic_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)2497 static igraph_bool_t igraph_i_subisomorphic_vf2(
2498 const igraph_vector_t *map12,
2499 const igraph_vector_t *map21,
2500 void *arg) {
2501 igraph_i_iso_cb_data_t *data = arg;
2502 igraph_bool_t *iso = data->arg;
2503 IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
2504 *iso = 1;
2505 return 0; /* stop */
2506 }
2507
2508 /**
2509 * \function igraph_subisomorphic_vf2
2510 * Decide subgraph isomorphism using VF2
2511 *
2512 * Decides whether a subgraph of \p graph1 is isomorphic to \p
2513 * graph2. It uses \ref igraph_subisomorphic_function_vf2().
2514 * \param graph1 The first input graph, may be directed or
2515 * undirected. This is supposed to be the larger graph.
2516 * \param graph2 The second input graph, it must have the same
2517 * directedness as \p graph1. This is supposed to be the smaller
2518 * graph.
2519 * \param vertex_color1 An optional color vector for the first graph. If
2520 * color vectors are given for both graphs, then the subgraph isomorphism is
2521 * calculated on the colored graphs; i.e. two vertices can match
2522 * only if their color also matches. Supply a null pointer here if
2523 * your graphs are not colored.
2524 * \param vertex_color2 An optional color vector for the second graph. See
2525 * the previous argument for explanation.
2526 * \param edge_color1 An optional edge color vector for the first
2527 * graph. The matching edges in the two graphs must have matching
2528 * colors as well. Supply a null pointer here if your graphs are not
2529 * edge-colored.
2530 * \param edge_color2 The edge color vector for the second graph.
2531 * \param iso Pointer to a boolean. The result of the decision problem
2532 * is stored here.
2533 * \param map12 Pointer to a vector or \c NULL. If not \c NULL, then an
2534 * isomorphic mapping from \p graph1 to \p graph2 is stored here.
2535 * \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
2536 * an isomorphic mapping from \p graph2 to \p graph1 is stored
2537 * here.
2538 * \param node_compat_fn A pointer to a function of type \ref
2539 * igraph_isocompat_t. This function will be called by the algorithm to
2540 * determine whether two nodes are compatible.
2541 * \param edge_compat_fn A pointer to a function of type \ref
2542 * igraph_isocompat_t. This function will be called by the algorithm to
2543 * determine whether two edges are compatible.
2544 * \param arg Extra argument to supply to functions \p node_compat_fn
2545 * and \p edge_compat_fn.
2546 * \return Error code.
2547 *
2548 * Time complexity: exponential.
2549 */
2550
igraph_subisomorphic_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_bool_t * iso,igraph_vector_t * map12,igraph_vector_t * map21,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)2551 int igraph_subisomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2,
2552 const igraph_vector_int_t *vertex_color1,
2553 const igraph_vector_int_t *vertex_color2,
2554 const igraph_vector_int_t *edge_color1,
2555 const igraph_vector_int_t *edge_color2,
2556 igraph_bool_t *iso, igraph_vector_t *map12,
2557 igraph_vector_t *map21,
2558 igraph_isocompat_t *node_compat_fn,
2559 igraph_isocompat_t *edge_compat_fn,
2560 void *arg) {
2561
2562 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, iso, arg };
2563 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
2564 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
2565
2566 *iso = 0;
2567 IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2,
2568 vertex_color1, vertex_color2,
2569 edge_color1, edge_color2,
2570 map12, map21,
2571 (igraph_isohandler_t *)
2572 igraph_i_subisomorphic_vf2,
2573 ncb, ecb, &data));
2574 if (! *iso) {
2575 if (map12) {
2576 igraph_vector_clear(map12);
2577 }
2578 if (map21) {
2579 igraph_vector_clear(map21);
2580 }
2581 }
2582 return 0;
2583 }
2584
igraph_i_count_subisomorphisms_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)2585 static igraph_bool_t igraph_i_count_subisomorphisms_vf2(
2586 const igraph_vector_t *map12,
2587 const igraph_vector_t *map21,
2588 void *arg) {
2589 igraph_i_iso_cb_data_t *data = arg;
2590 igraph_integer_t *count = data->arg;
2591 IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
2592 *count += 1;
2593 return 1; /* always continue */
2594 }
2595
2596 /**
2597 * \function igraph_count_subisomorphisms_vf2
2598 * Number of subgraph isomorphisms using VF2
2599 *
2600 * Count the number of isomorphisms between subgraphs of \p graph1 and
2601 * \p graph2. This function uses \ref
2602 * igraph_subisomorphic_function_vf2().
2603 * \param graph1 The first input graph, may be directed or
2604 * undirected. This is supposed to be the larger graph.
2605 * \param graph2 The second input graph, it must have the same
2606 * directedness as \p graph1. This is supposed to be the smaller
2607 * graph.
2608 * \param vertex_color1 An optional color vector for the first graph. If
2609 * color vectors are given for both graphs, then the subgraph isomorphism is
2610 * calculated on the colored graphs; i.e. two vertices can match
2611 * only if their color also matches. Supply a null pointer here if
2612 * your graphs are not colored.
2613 * \param vertex_color2 An optional color vector for the second graph. See
2614 * the previous argument for explanation.
2615 * \param edge_color1 An optional edge color vector for the first
2616 * graph. The matching edges in the two graphs must have matching
2617 * colors as well. Supply a null pointer here if your graphs are not
2618 * edge-colored.
2619 * \param edge_color2 The edge color vector for the second graph.
2620 * \param count Pointer to an integer. The number of subgraph
2621 * isomorphisms is stored here.
2622 * \param node_compat_fn A pointer to a function of type \ref
2623 * igraph_isocompat_t. This function will be called by the algorithm to
2624 * determine whether two nodes are compatible.
2625 * \param edge_compat_fn A pointer to a function of type \ref
2626 * igraph_isocompat_t. This function will be called by the algorithm to
2627 * determine whether two edges are compatible.
2628 * \param arg Extra argument to supply to functions \p node_compat_fn and
2629 * \p edge_compat_fn.
2630 * \return Error code.
2631 *
2632 * Time complexity: exponential.
2633 */
2634
igraph_count_subisomorphisms_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_integer_t * count,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)2635 int igraph_count_subisomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2,
2636 const igraph_vector_int_t *vertex_color1,
2637 const igraph_vector_int_t *vertex_color2,
2638 const igraph_vector_int_t *edge_color1,
2639 const igraph_vector_int_t *edge_color2,
2640 igraph_integer_t *count,
2641 igraph_isocompat_t *node_compat_fn,
2642 igraph_isocompat_t *edge_compat_fn,
2643 void *arg) {
2644
2645 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn,
2646 count, arg
2647 };
2648 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
2649 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
2650 *count = 0;
2651 IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2,
2652 vertex_color1, vertex_color2,
2653 edge_color1, edge_color2,
2654 0, 0,
2655 (igraph_isohandler_t*)
2656 igraph_i_count_subisomorphisms_vf2,
2657 ncb, ecb, &data));
2658 return 0;
2659 }
2660
igraph_i_get_subisomorphisms_free(igraph_vector_ptr_t * data)2661 static void igraph_i_get_subisomorphisms_free(igraph_vector_ptr_t *data) {
2662 long int i, n = igraph_vector_ptr_size(data);
2663 for (i = 0; i < n; i++) {
2664 igraph_vector_t *vec = VECTOR(*data)[i];
2665 igraph_vector_destroy(vec);
2666 igraph_free(vec);
2667 }
2668 }
2669
igraph_i_get_subisomorphisms_vf2(const igraph_vector_t * map12,const igraph_vector_t * map21,void * arg)2670 static igraph_bool_t igraph_i_get_subisomorphisms_vf2(
2671 const igraph_vector_t *map12,
2672 const igraph_vector_t *map21,
2673 void *arg) {
2674
2675 igraph_i_iso_cb_data_t *data = arg;
2676 igraph_vector_ptr_t *vector = data->arg;
2677 igraph_vector_t *newvector = igraph_Calloc(1, igraph_vector_t);
2678 IGRAPH_UNUSED(map12);
2679 if (!newvector) {
2680 igraph_error("Out of memory", __FILE__, __LINE__, IGRAPH_ENOMEM);
2681 return 0; /* stop right here */
2682 }
2683 IGRAPH_FINALLY(igraph_free, newvector);
2684 IGRAPH_CHECK(igraph_vector_copy(newvector, map21));
2685 IGRAPH_FINALLY(igraph_vector_destroy, newvector);
2686 IGRAPH_CHECK(igraph_vector_ptr_push_back(vector, newvector));
2687 IGRAPH_FINALLY_CLEAN(2);
2688
2689 return 1; /* continue finding subisomorphisms */
2690 }
2691
2692 /**
2693 * \function igraph_get_subisomorphisms_vf2
2694 * Return all subgraph isomorphic mappings
2695 *
2696 * This function collects all isomorphic mappings of \p graph2 to a
2697 * subgraph of \p graph1. It uses the \ref
2698 * igraph_subisomorphic_function_vf2() function.
2699 * \param graph1 The first input graph, may be directed or
2700 * undirected. This is supposed to be the larger graph.
2701 * \param graph2 The second input graph, it must have the same
2702 * directedness as \p graph1. This is supposed to be the smaller
2703 * graph.
2704 * \param vertex_color1 An optional color vector for the first graph. If
2705 * color vectors are given for both graphs, then the subgraph isomorphism is
2706 * calculated on the colored graphs; i.e. two vertices can match
2707 * only if their color also matches. Supply a null pointer here if
2708 * your graphs are not colored.
2709 * \param vertex_color2 An optional color vector for the second graph. See
2710 * the previous argument for explanation.
2711 * \param edge_color1 An optional edge color vector for the first
2712 * graph. The matching edges in the two graphs must have matching
2713 * colors as well. Supply a null pointer here if your graphs are not
2714 * edge-colored.
2715 * \param edge_color2 The edge color vector for the second graph.
2716 * \param maps Pointer vector. On return it contains pointers to
2717 * \ref igraph_vector_t objects, each vector is an
2718 * isomorphic mapping of \p graph2 to a subgraph of \p graph1. Please note that
2719 * you need to 1) Destroy the vectors via \ref
2720 * igraph_vector_destroy(), 2) free them via
2721 * \ref igraph_free() and then 3) call \ref
2722 * igraph_vector_ptr_destroy() on the pointer vector to deallocate all
2723 * memory when \p maps is no longer needed.
2724 * \param node_compat_fn A pointer to a function of type \ref
2725 * igraph_isocompat_t. This function will be called by the algorithm to
2726 * determine whether two nodes are compatible.
2727 * \param edge_compat_fn A pointer to a function of type \ref
2728 * igraph_isocompat_t. This function will be called by the algorithm to
2729 * determine whether two edges are compatible.
2730 * \param arg Extra argument to supply to functions \p node_compat_fn
2731 * and \p edge_compat_fn.
2732 * \return Error code.
2733 *
2734 * Time complexity: exponential.
2735 */
2736
igraph_get_subisomorphisms_vf2(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * vertex_color1,const igraph_vector_int_t * vertex_color2,const igraph_vector_int_t * edge_color1,const igraph_vector_int_t * edge_color2,igraph_vector_ptr_t * maps,igraph_isocompat_t * node_compat_fn,igraph_isocompat_t * edge_compat_fn,void * arg)2737 int igraph_get_subisomorphisms_vf2(const igraph_t *graph1,
2738 const igraph_t *graph2,
2739 const igraph_vector_int_t *vertex_color1,
2740 const igraph_vector_int_t *vertex_color2,
2741 const igraph_vector_int_t *edge_color1,
2742 const igraph_vector_int_t *edge_color2,
2743 igraph_vector_ptr_t *maps,
2744 igraph_isocompat_t *node_compat_fn,
2745 igraph_isocompat_t *edge_compat_fn,
2746 void *arg) {
2747
2748 igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, maps, arg };
2749 igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
2750 igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
2751
2752 igraph_vector_ptr_clear(maps);
2753 IGRAPH_FINALLY(igraph_i_get_subisomorphisms_free, maps);
2754 IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2,
2755 vertex_color1, vertex_color2,
2756 edge_color1, edge_color2,
2757 0, 0,
2758 (igraph_isohandler_t*)
2759 igraph_i_get_subisomorphisms_vf2,
2760 ncb, ecb, &data));
2761 IGRAPH_FINALLY_CLEAN(1);
2762 return 0;
2763 }
2764
2765 /**
2766 * \function igraph_permute_vertices
2767 * Permute the vertices
2768 *
2769 * This function creates a new graph from the input graph by permuting
2770 * its vertices according to the specified mapping. Call this function
2771 * with the output of \ref igraph_canonical_permutation() to create
2772 * the canonical form of a graph.
2773 * \param graph The input graph.
2774 * \param res Pointer to an uninitialized graph object. The new graph
2775 * is created here.
2776 * \param permutation The permutation to apply. Vertex 0 is mapped to
2777 * the first element of the vector, vertex 1 to the second,
2778 * etc. Note that it is not checked that the vector contains every
2779 * element only once, and no range checking is performed either.
2780 * \return Error code.
2781 *
2782 * Time complexity: O(|V|+|E|), linear in terms of the number of
2783 * vertices and edges.
2784 */
2785
igraph_permute_vertices(const igraph_t * graph,igraph_t * res,const igraph_vector_t * permutation)2786 int igraph_permute_vertices(const igraph_t *graph, igraph_t *res,
2787 const igraph_vector_t *permutation) {
2788
2789 long int no_of_nodes = igraph_vcount(graph);
2790 long int no_of_edges = igraph_ecount(graph);
2791 igraph_vector_t edges;
2792 long int i, p = 0;
2793
2794 if (igraph_vector_size(permutation) != no_of_nodes) {
2795 IGRAPH_ERROR("Permute vertices: invalid permutation vector size", IGRAPH_EINVAL);
2796 }
2797
2798 IGRAPH_VECTOR_INIT_FINALLY(&edges, no_of_edges * 2);
2799
2800 for (i = 0; i < no_of_edges; i++) {
2801 VECTOR(edges)[p++] = VECTOR(*permutation)[ (long int) IGRAPH_FROM(graph, i) ];
2802 VECTOR(edges)[p++] = VECTOR(*permutation)[ (long int) IGRAPH_TO(graph, i) ];
2803 }
2804
2805 IGRAPH_CHECK(igraph_create(res, &edges, (igraph_integer_t) no_of_nodes,
2806 igraph_is_directed(graph)));
2807
2808 /* Attributes */
2809 if (graph->attr) {
2810 igraph_vector_t index;
2811 igraph_vector_t vtypes;
2812 IGRAPH_I_ATTRIBUTE_DESTROY(res);
2813 IGRAPH_I_ATTRIBUTE_COPY(res, graph, /*graph=*/1, /*vertex=*/0, /*edge=*/1);
2814 IGRAPH_VECTOR_INIT_FINALLY(&vtypes, 0);
2815 IGRAPH_CHECK(igraph_i_attribute_get_info(graph, 0, 0, 0, &vtypes, 0, 0));
2816 if (igraph_vector_size(&vtypes) != 0) {
2817 IGRAPH_VECTOR_INIT_FINALLY(&index, no_of_nodes);
2818 for (i = 0; i < no_of_nodes; i++) {
2819 VECTOR(index)[ (long int) VECTOR(*permutation)[i] ] = i;
2820 }
2821 IGRAPH_CHECK(igraph_i_attribute_permute_vertices(graph, res, &index));
2822 igraph_vector_destroy(&index);
2823 IGRAPH_FINALLY_CLEAN(1);
2824 }
2825 igraph_vector_destroy(&vtypes);
2826 IGRAPH_FINALLY_CLEAN(1);
2827 }
2828
2829 igraph_vector_destroy(&edges);
2830 IGRAPH_FINALLY_CLEAN(1);
2831 return 0;
2832 }
2833
2834 /**
2835 * \section about_bliss
2836 *
2837 * <para>
2838 * BLISS is a successor of the famous NAUTY algorithm and
2839 * implementation. While using the same ideas in general, with better
2840 * heuristics and data structures BLISS outperforms NAUTY on most
2841 * graphs.
2842 * </para>
2843 *
2844 * <para>
2845 * BLISS was developed and implemented by Tommi Junttila and Petteri Kaski at
2846 * Helsinki University of Technology, Finland. For more information,
2847 * see the BLISS homepage at http://www.tcs.hut.fi/Software/bliss/ and the publication
2848 * Tommi Junttila, Petteri Kaski: "Engineering an Efficient Canonical Labeling
2849 * Tool for Large and Sparse Graphs" at https://doi.org/10.1137/1.9781611972870.13
2850 * </para>
2851 *
2852 * <para>
2853 * BLISS works with both directed graphs and undirected graphs. It supports graphs with
2854 * self-loops, but not graphs with multi-edges.
2855 * </para>
2856 *
2857 * <para>
2858 * BLISS version 0.73 is included in igraph.
2859 * </para>
2860 */
2861
2862 /**
2863 * \function igraph_isomorphic_bliss
2864 * Graph isomorphism via BLISS
2865 *
2866 * This function uses the BLISS graph isomorphism algorithm, a
2867 * successor of the famous NAUTY algorithm and implementation. BLISS
2868 * is open source and licensed according to the GNU GPL. See
2869 * http://www.tcs.hut.fi/Software/bliss/index.html for
2870 * details. Currently the 0.73 version of BLISS is included in igraph.
2871 *
2872 * </para><para>
2873 *
2874 * \param graph1 The first input graph. Multiple edges between the same nodes
2875 * are not supported and will cause an incorrect result to be returned.
2876 * \param graph2 The second input graph. Multiple edges between the same nodes
2877 * are not supported and will cause an incorrect result to be returned.
2878 * \param colors1 An optional vertex color vector for the first graph. Supply a
2879 * null pointer if your graph is not colored.
2880 * \param colors2 An optional vertex color vector for the second graph. Supply a
2881 * null pointer if your graph is not colored.
2882 * \param iso Pointer to a boolean, the result is stored here.
2883 * \param map12 A vector or \c NULL pointer. If not \c NULL then an
2884 * isomorphic mapping from \p graph1 to \p graph2 is stored here.
2885 * If the input graphs are not isomorphic then this vector is
2886 * cleared, i.e. it will have length zero.
2887 * \param map21 Similar to \p map12, but for the mapping from \p
2888 * graph2 to \p graph1.
2889 * \param sh Splitting heuristics to be used for the graphs. See
2890 * \ref igraph_bliss_sh_t.
2891 * \param info1 If not \c NULL, information about the canonization of
2892 * the first input graph is stored here. See \ref igraph_bliss_info_t
2893 * for details. Note that if the two graphs have different number
2894 * of vertices or edges, then this is not filled.
2895 * \param info2 Same as \p info1, but for the second graph.
2896 * \return Error code.
2897 *
2898 * Time complexity: exponential, but in practice it is quite fast.
2899 */
2900
igraph_isomorphic_bliss(const igraph_t * graph1,const igraph_t * graph2,const igraph_vector_int_t * colors1,const igraph_vector_int_t * colors2,igraph_bool_t * iso,igraph_vector_t * map12,igraph_vector_t * map21,igraph_bliss_sh_t sh,igraph_bliss_info_t * info1,igraph_bliss_info_t * info2)2901 int igraph_isomorphic_bliss(const igraph_t *graph1, const igraph_t *graph2,
2902 const igraph_vector_int_t *colors1, const igraph_vector_int_t *colors2,
2903 igraph_bool_t *iso, igraph_vector_t *map12,
2904 igraph_vector_t *map21, igraph_bliss_sh_t sh,
2905 igraph_bliss_info_t *info1, igraph_bliss_info_t *info2) {
2906
2907 long int no_of_nodes = igraph_vcount(graph1);
2908 long int no_of_edges = igraph_ecount(graph1);
2909 igraph_vector_t perm1, perm2;
2910 igraph_vector_t vmap12, *mymap12 = &vmap12;
2911 igraph_vector_t from, to, index;
2912 igraph_vector_t from2, to2, index2;
2913 igraph_bool_t directed;
2914 long int i, j;
2915
2916 *iso = 0;
2917 if (info1) {
2918 info1->nof_nodes = info1->nof_leaf_nodes = info1->nof_bad_nodes =
2919 info1->nof_canupdates = info1->max_level = info1->nof_generators = -1;
2920 info1->group_size = 0;
2921 }
2922 if (info2) {
2923 info2->nof_nodes = info2->nof_leaf_nodes = info2->nof_bad_nodes =
2924 info2->nof_canupdates = info2->max_level = info2->nof_generators = -1;
2925 info2->group_size = 0;
2926 }
2927
2928 directed = igraph_is_directed(graph1);
2929 if (igraph_is_directed(graph2) != directed) {
2930 IGRAPH_ERROR("Cannot compare directed and undirected graphs",
2931 IGRAPH_EINVAL);
2932 }
2933 if ((colors1 == NULL || colors2 == NULL) && colors1 != colors2) {
2934 IGRAPH_WARNING("Only one of the graphs is vertex colored, colors will be ignored");
2935 colors1 = NULL; colors2 = NULL;
2936 }
2937
2938 if (no_of_nodes != igraph_vcount(graph2) ||
2939 no_of_edges != igraph_ecount(graph2)) {
2940 if (map12) {
2941 igraph_vector_clear(map12);
2942 }
2943 if (map21) {
2944 igraph_vector_clear(map21);
2945 }
2946 return 0;
2947 }
2948
2949 if (map12) {
2950 mymap12 = map12;
2951 } else {
2952 IGRAPH_VECTOR_INIT_FINALLY(mymap12, 0);
2953 }
2954
2955 IGRAPH_VECTOR_INIT_FINALLY(&perm1, no_of_nodes);
2956 IGRAPH_VECTOR_INIT_FINALLY(&perm2, no_of_nodes);
2957
2958 IGRAPH_CHECK(igraph_canonical_permutation(graph1, colors1, &perm1, sh, info1));
2959 IGRAPH_CHECK(igraph_canonical_permutation(graph2, colors2, &perm2, sh, info2));
2960
2961 IGRAPH_CHECK(igraph_vector_resize(mymap12, no_of_nodes));
2962
2963 /* The inverse of perm2 is produced in mymap12 */
2964 for (i = 0; i < no_of_nodes; i++) {
2965 VECTOR(*mymap12)[ (long int)VECTOR(perm2)[i] ] = i;
2966 }
2967 /* Now we produce perm2^{-1} o perm1 in perm2 */
2968 for (i = 0; i < no_of_nodes; i++) {
2969 VECTOR(perm2)[i] = VECTOR(*mymap12)[ (long int) VECTOR(perm1)[i] ];
2970 }
2971 /* Copy it to mymap12 */
2972 igraph_vector_update(mymap12, &perm2);
2973
2974 igraph_vector_destroy(&perm1);
2975 igraph_vector_destroy(&perm2);
2976 IGRAPH_FINALLY_CLEAN(2);
2977
2978 /* Check isomorphism, we apply the permutation in mymap12 to graph1
2979 and should get graph2 */
2980
2981 IGRAPH_VECTOR_INIT_FINALLY(&from, no_of_edges);
2982 IGRAPH_VECTOR_INIT_FINALLY(&to, no_of_edges);
2983 IGRAPH_VECTOR_INIT_FINALLY(&index, no_of_edges);
2984 IGRAPH_VECTOR_INIT_FINALLY(&from2, no_of_edges * 2);
2985 IGRAPH_VECTOR_INIT_FINALLY(&to2, no_of_edges);
2986 IGRAPH_VECTOR_INIT_FINALLY(&index2, no_of_edges);
2987
2988 for (i = 0; i < no_of_edges; i++) {
2989 VECTOR(from)[i] = VECTOR(*mymap12)[ (long int) IGRAPH_FROM(graph1, i) ];
2990 VECTOR(to)[i] = VECTOR(*mymap12)[ (long int) IGRAPH_TO (graph1, i) ];
2991 if (! directed && VECTOR(from)[i] < VECTOR(to)[i]) {
2992 igraph_real_t tmp = VECTOR(from)[i];
2993 VECTOR(from)[i] = VECTOR(to)[i];
2994 VECTOR(to)[i] = tmp;
2995 }
2996 }
2997 igraph_vector_order(&from, &to, &index, no_of_nodes);
2998
2999 igraph_get_edgelist(graph2, &from2, /*bycol=*/ 1);
3000 for (i = 0, j = no_of_edges; i < no_of_edges; i++, j++) {
3001 VECTOR(to2)[i] = VECTOR(from2)[j];
3002 if (! directed && VECTOR(from2)[i] < VECTOR(to2)[i]) {
3003 igraph_real_t tmp = VECTOR(from2)[i];
3004 VECTOR(from2)[i] = VECTOR(to2)[i];
3005 VECTOR(to2)[i] = tmp;
3006 }
3007 }
3008 igraph_vector_resize(&from2, no_of_edges);
3009 igraph_vector_order(&from2, &to2, &index2, no_of_nodes);
3010
3011 *iso = 1;
3012 for (i = 0; i < no_of_edges; i++) {
3013 long int i1 = (long int) VECTOR(index)[i];
3014 long int i2 = (long int) VECTOR(index2)[i];
3015 if (VECTOR(from)[i1] != VECTOR(from2)[i2] ||
3016 VECTOR(to)[i1] != VECTOR(to2)[i2]) {
3017 *iso = 0;
3018 break;
3019 }
3020 }
3021
3022 /* If the graphs are coloured, we also need to check that applying the
3023 permutation mymap12 to colors1 gives colors2. */
3024
3025 if (*iso && colors1 != NULL) {
3026 for (i = 0; i < no_of_nodes; i++) {
3027 if (VECTOR(*colors1)[i] != VECTOR(*colors2)[(long int) VECTOR(*mymap12)[i] ]) {
3028 *iso = 0;
3029 break;
3030 }
3031 }
3032 }
3033
3034 igraph_vector_destroy(&index2);
3035 igraph_vector_destroy(&to2);
3036 igraph_vector_destroy(&from2);
3037 igraph_vector_destroy(&index);
3038 igraph_vector_destroy(&to);
3039 igraph_vector_destroy(&from);
3040 IGRAPH_FINALLY_CLEAN(6);
3041
3042 if (*iso) {
3043 /* The inverse of mymap12 */
3044 if (map21) {
3045 IGRAPH_CHECK(igraph_vector_resize(map21, no_of_nodes));
3046 for (i = 0; i < no_of_nodes; i++) {
3047 VECTOR(*map21)[ (long int) VECTOR(*mymap12)[i] ] = i;
3048 }
3049 }
3050 } else {
3051 if (map12) {
3052 igraph_vector_clear(map12);
3053 }
3054 if (map21) {
3055 igraph_vector_clear(map21);
3056 }
3057 }
3058
3059 if (!map12) {
3060 igraph_vector_destroy(mymap12);
3061 IGRAPH_FINALLY_CLEAN(1);
3062 }
3063
3064 return 0;
3065 }
3066
3067
3068 /**
3069 * \function igraph_simplify_and_colorize
3070 * \brief Simplify the graph and compute self-loop and edge multiplicities.
3071 *
3072 * </para><para>
3073 * This function creates a vertex and edge colored simple graph from the input
3074 * graph. The vertex colors are computed as the number of incident self-loops
3075 * to each vertex in the input graph. The edge colors are computed as the number of
3076 * parallel edges in the input graph that were merged to create each edge
3077 * in the simple graph.
3078 *
3079 * </para><para>
3080 * The resulting colored simple graph is suitable for use by isomorphism checking
3081 * algorithms such as VF2, which only support simple graphs, but can consider
3082 * vertex and edge colors.
3083 *
3084 * \param graph The graph object, typically having self-loops or multi-edges.
3085 * \param res An uninitialized graph object. The result will be stored here
3086 * \param vertex_color Computed vertex colors corresponding to self-loop multiplicities.
3087 * \param edge_color Computed edge colors corresponding to edge multiplicities
3088 * \return Error code.
3089 *
3090 * \sa \ref igraph_simplify(), \ref igraph_isomorphic_vf2(), \ref igraph_subisomorphic_vf2()
3091 *
3092 */
igraph_simplify_and_colorize(const igraph_t * graph,igraph_t * res,igraph_vector_int_t * vertex_color,igraph_vector_int_t * edge_color)3093 int igraph_simplify_and_colorize(
3094 const igraph_t *graph, igraph_t *res,
3095 igraph_vector_int_t *vertex_color, igraph_vector_int_t *edge_color) {
3096 igraph_es_t es;
3097 igraph_eit_t eit;
3098 igraph_vector_t edges;
3099 long int no_of_nodes = igraph_vcount(graph);
3100 long int no_of_edges = igraph_ecount(graph);
3101 long int pto = -1, pfrom = -1;
3102 long int i;
3103
3104 IGRAPH_CHECK(igraph_es_all(&es, IGRAPH_EDGEORDER_FROM));
3105 IGRAPH_FINALLY(igraph_es_destroy, &es);
3106 IGRAPH_CHECK(igraph_eit_create(graph, es, &eit));
3107 IGRAPH_FINALLY(igraph_eit_destroy, &eit);
3108
3109 IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
3110 IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges * 2));
3111
3112 IGRAPH_CHECK(igraph_vector_int_resize(vertex_color, no_of_nodes));
3113 igraph_vector_int_null(vertex_color);
3114
3115 IGRAPH_CHECK(igraph_vector_int_resize(edge_color, no_of_edges));
3116 igraph_vector_int_null(edge_color);
3117
3118 i = -1;
3119 for (; !IGRAPH_EIT_END(eit); IGRAPH_EIT_NEXT(eit)) {
3120 long int edge = IGRAPH_EIT_GET(eit);
3121 long int from = IGRAPH_FROM(graph, edge);
3122 long int to = IGRAPH_TO(graph, edge);
3123
3124 if (to == from) {
3125 VECTOR(*vertex_color)[to]++;
3126 continue;
3127 }
3128
3129 if (to == pto && from == pfrom) {
3130 VECTOR(*edge_color)[i]++;
3131 } else {
3132 igraph_vector_push_back(&edges, from);
3133 igraph_vector_push_back(&edges, to);
3134 i++;
3135 VECTOR(*edge_color)[i] = 1;
3136 }
3137
3138 pfrom = from; pto = to;
3139 }
3140
3141 igraph_vector_int_resize(edge_color, i + 1);
3142
3143 igraph_eit_destroy(&eit);
3144 igraph_es_destroy(&es);
3145 IGRAPH_FINALLY_CLEAN(2);
3146
3147 IGRAPH_CHECK(igraph_create(res, &edges, no_of_nodes, igraph_is_directed(graph)));
3148
3149 igraph_vector_destroy(&edges);
3150 IGRAPH_FINALLY_CLEAN(1);
3151
3152 return IGRAPH_SUCCESS;
3153 }
3154