/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2006 Gabor Csardi <csardi@rmki.kfki.hu>
MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA
*/
#include "igraph.h"
unsigned int igraph_i_isoclass_3[] = { 0, 1, 1, 3, 1, 5, 6, 7,
1, 6,10,11, 3, 7,11,15,
1, 6, 5, 7,10,21,21,23,
6,25,21,27,11,27,30,31,
1,10, 6,11, 6,21,25,27,
5,21,21,30, 7,23,27,31,
3,11, 7,15,11,30,27,31,
7,27,23,31,15,31,31,63 };
unsigned int igraph_i_isoclass_3_idx[] = { 0, 4, 16, 1, 0, 32, 2, 8, 0 };
unsigned int igraph_i_isoclass_4[] = {
0, 1, 1, 3, 1, 3, 3, 7, 1, 9, 10, 11, 10,
11, 14, 15, 1, 10, 18, 19, 20, 21, 22, 23, 3, 11,
19, 27, 21, 29, 30, 31, 1, 10, 20, 21, 18, 19, 22,
23, 3, 11, 21, 29, 19, 27, 30, 31, 3, 14, 22, 30,
22, 30, 54, 55, 7, 15, 23, 31, 23, 31, 55, 63, 1,
10, 9, 11, 10, 14, 11, 15, 18, 73, 73, 75, 76, 77,
77, 79, 10, 81, 73, 83, 84, 85, 86, 87, 19, 83, 90,
91, 92, 93, 94, 95, 20, 84, 98, 99, 100, 101, 102, 103,
22, 86, 106, 107, 108, 109, 110, 111, 21, 85, 106, 115, 116,
117, 118, 119, 23, 87, 122, 123, 124, 125, 126, 127, 1, 18,
10, 19, 20, 22, 21, 23, 10, 73, 81, 83, 84, 86, 85,
87, 9, 73, 73, 90, 98, 106, 106, 122, 11, 75, 83, 91,
99, 107, 115, 123, 10, 76, 84, 92, 100, 108, 116, 124, 14,
77, 85, 93, 101, 109, 117, 125, 11, 77, 86, 94, 102, 110,
118, 126, 15, 79, 87, 95, 103, 111, 119, 127, 3, 19, 11,
27, 21, 30, 29, 31, 19, 90, 83, 91, 92, 94, 93, 95,
11, 83, 75, 91, 99, 115, 107, 123, 27, 91, 91, 219, 220,
221, 221, 223, 21, 92, 99, 220, 228, 229, 230, 231, 30, 94,
115, 221, 229, 237, 238, 239, 29, 93, 107, 221, 230, 238, 246,
247, 31, 95, 123, 223, 231, 239, 247, 255, 1, 20, 10, 21,
18, 22, 19, 23, 20, 98, 84, 99, 100, 102, 101, 103, 10,
84, 76, 92, 100, 116, 108, 124, 21, 99, 92, 220, 228, 230,
229, 231, 18, 100, 100, 228, 292, 293, 293, 295, 22, 102, 116,
230, 293, 301, 302, 303, 19, 101, 108, 229, 293, 302, 310, 311,
23, 103, 124, 231, 295, 303, 311, 319, 3, 21, 11, 29, 19,
30, 27, 31, 22, 106, 86, 107, 108, 110, 109, 111, 14, 85,
77, 93, 101, 117, 109, 125, 30, 115, 94, 221, 229, 238, 237,
239, 22, 116, 102, 230, 293, 302, 301, 303, 54, 118, 118, 246,
310, 365, 365, 367, 30, 117, 110, 238, 302, 373, 365, 375, 55,
119, 126, 247, 311, 375, 382, 383, 3, 22, 14, 30, 22, 54,
30, 55, 21, 106, 85, 115, 116, 118, 117, 119, 11, 86, 77,
94, 102, 118, 110, 126, 29, 107, 93, 221, 230, 246, 238, 247,
19, 108, 101, 229, 293, 310, 302, 311, 30, 110, 117, 238, 302,
365, 373, 375, 27, 109, 109, 237, 301, 365, 365, 382, 31, 111,
125, 239, 303, 367, 375, 383, 7, 23, 15, 31, 23, 55, 31,
63, 23, 122, 87, 123, 124, 126, 125, 127, 15, 87, 79, 95,
103, 119, 111, 127, 31, 123, 95, 223, 231, 247, 239, 255, 23,
124, 103, 231, 295, 311, 303, 319, 55, 126, 119, 247, 311, 382,
375, 383, 31, 125, 111, 239, 303, 375, 367, 383, 63, 127, 127,
255, 319, 383, 383, 511, 1, 10, 10, 14, 9, 11, 11, 15,
18, 73, 76, 77, 73, 75, 77, 79, 20, 84, 100, 101, 98,
99, 102, 103, 22, 86, 108, 109, 106, 107, 110, 111, 10, 81,
84, 85, 73, 83, 86, 87, 19, 83, 92, 93, 90, 91, 94,
95, 21, 85, 116, 117, 106, 115, 118, 119, 23, 87, 124, 125,
122, 123, 126, 127, 18, 76, 73, 77, 73, 77, 75, 79, 292,
585, 585, 587, 585, 587, 587, 591, 100, 593, 594, 595, 596, 597,
598, 599, 293, 601, 602, 603, 604, 605, 606, 607, 100, 593, 596,
597, 594, 595, 598, 599, 293, 601, 604, 605, 602, 603, 606, 607,
228, 625, 626, 627, 626, 627, 630, 631, 295, 633, 634, 635, 634,
635, 638, 639, 20, 100, 84, 101, 98, 102, 99, 103, 100, 594,
593, 595, 596, 598, 597, 599, 98, 596, 596, 659, 660, 661, 661,
663, 102, 598, 666, 667, 661, 669, 670, 671, 84, 593, 674, 675,
596, 666, 678, 679, 101, 595, 675, 683, 659, 667, 686, 687, 99,
597, 678, 686, 661, 670, 694, 695, 103, 599, 679, 687, 663, 671,
695, 703, 22, 108, 86, 109, 106, 110, 107, 111, 293, 602, 601,
603, 604, 606, 605, 607, 102, 666, 598, 667, 661, 670, 669, 671,
301, 729, 729, 731, 732, 733, 733, 735, 116, 737, 678, 739, 626,
741, 742, 743, 302, 745, 746, 747, 748, 749, 750, 751, 230, 753,
742, 755, 756, 757, 758, 759, 303, 761, 762, 763, 764, 765, 766,
767, 10, 84, 81, 85, 73, 86, 83, 87, 100, 596, 593, 597,
594, 598, 595, 599, 84, 674, 593, 675, 596, 678, 666, 679, 116,
678, 737, 739, 626, 742, 741, 743, 76, 593, 593, 625, 585, 601,
601, 633, 108, 666, 737, 753, 602, 729, 745, 761, 92, 675, 737,
819, 604, 746, 822, 823, 124, 679, 826, 827, 634, 762, 830, 831,
19, 92, 83, 93, 90, 94, 91, 95, 293, 604, 601, 605, 602,
606, 603, 607, 101, 675, 595, 683, 659, 686, 667, 687, 302, 746,
745, 747, 748, 750, 749, 751, 108, 737, 666, 753, 602, 745, 729,
761, 310, 822, 822, 875, 876, 877, 877, 879, 229, 819, 741, 883,
748, 885, 886, 887, 311, 823, 830, 891, 892, 893, 894, 895, 21,
116, 85, 117, 106, 118, 115, 119, 228, 626, 625, 627, 626, 630,
627, 631, 99, 678, 597, 686, 661, 694, 670, 695, 230, 742, 753,
755, 756, 758, 757, 759, 92, 737, 675, 819, 604, 822, 746, 823,
229, 741, 819, 883, 748, 886, 885, 887, 220, 739, 739, 947, 732,
949, 949, 951, 231, 743, 827, 955, 764, 957, 958, 959, 23, 124,
87, 125, 122, 126, 123, 127, 295, 634, 633, 635, 634, 638, 635,
639, 103, 679, 599, 687, 663, 695, 671, 703, 303, 762, 761, 763,
764, 766, 765, 767, 124, 826, 679, 827, 634, 830, 762, 831, 311,
830, 823, 891, 892, 894, 893, 895, 231, 827, 743, 955, 764, 958,
957, 959, 319, 831, 831,1019,1020,1021,1021,1023, 1, 18, 20,
22, 10, 19, 21, 23, 10, 73, 84, 86, 81, 83, 85, 87,
10, 76, 100, 108, 84, 92, 116, 124, 14, 77, 101, 109, 85,
93, 117, 125, 9, 73, 98, 106, 73, 90, 106, 122, 11, 75,
99, 107, 83, 91, 115, 123, 11, 77, 102, 110, 86, 94, 118,
126, 15, 79, 103, 111, 87, 95, 119, 127, 20, 100, 98, 102,
84, 101, 99, 103, 100, 594, 596, 598, 593, 595, 597, 599, 84,
593, 596, 666, 674, 675, 678, 679, 101, 595, 659, 667, 675, 683,
686, 687, 98, 596, 660, 661, 596, 659, 661, 663, 102, 598, 661,
669, 666, 667, 670, 671, 99, 597, 661, 670, 678, 686, 694, 695,
103, 599, 663, 671, 679, 687, 695, 703, 18, 292, 100, 293, 100,
293, 228, 295, 76, 585, 593, 601, 593, 601, 625, 633, 73, 585,
594, 602, 596, 604, 626, 634, 77, 587, 595, 603, 597, 605, 627,
635, 73, 585, 596, 604, 594, 602, 626, 634, 77, 587, 597, 605,
595, 603, 627, 635, 75, 587, 598, 606, 598, 606, 630, 638, 79,
591, 599, 607, 599, 607, 631, 639, 22, 293, 102, 301, 116, 302,
230, 303, 108, 602, 666, 729, 737, 745, 753, 761, 86, 601, 598,
729, 678, 746, 742, 762, 109, 603, 667, 731, 739, 747, 755, 763,
106, 604, 661, 732, 626, 748, 756, 764, 110, 606, 670, 733, 741,
749, 757, 765, 107, 605, 669, 733, 742, 750, 758, 766, 111, 607,
671, 735, 743, 751, 759, 767, 10, 100, 84, 116, 76, 108, 92,
124, 84, 596, 674, 678, 593, 666, 675, 679, 81, 593, 593, 737,
593, 737, 737, 826, 85, 597, 675, 739, 625, 753, 819, 827, 73,
594, 596, 626, 585, 602, 604, 634, 86, 598, 678, 742, 601, 729,
746, 762, 83, 595, 666, 741, 601, 745, 822, 830, 87, 599, 679,
743, 633, 761, 823, 831, 21, 228, 99, 230, 92, 229, 220, 231,
116, 626, 678, 742, 737, 741, 739, 743, 85, 625, 597, 753, 675,
819, 739, 827, 117, 627, 686, 755, 819, 883, 947, 955, 106, 626,
661, 756, 604, 748, 732, 764, 118, 630, 694, 758, 822, 886, 949,
957, 115, 627, 670, 757, 746, 885, 949, 958, 119, 631, 695, 759,
823, 887, 951, 959, 19, 293, 101, 302, 108, 310, 229, 311, 92,
604, 675, 746, 737, 822, 819, 823, 83, 601, 595, 745, 666, 822,
741, 830, 93, 605, 683, 747, 753, 875, 883, 891, 90, 602, 659,
748, 602, 876, 748, 892, 94, 606, 686, 750, 745, 877, 885, 893,
91, 603, 667, 749, 729, 877, 886, 894, 95, 607, 687, 751, 761,
879, 887, 895, 23, 295, 103, 303, 124, 311, 231, 319, 124, 634,
679, 762, 826, 830, 827, 831, 87, 633, 599, 761, 679, 823, 743,
831, 125, 635, 687, 763, 827, 891, 955,1019, 122, 634, 663, 764,
634, 892, 764,1020, 126, 638, 695, 766, 830, 894, 958,1021, 123,
635, 671, 765, 762, 893, 957,1021, 127, 639, 703, 767, 831, 895,
959,1023, 3, 19, 21, 30, 11, 27, 29, 31, 19, 90, 92,
94, 83, 91, 93, 95, 21, 92, 228, 229, 99, 220, 230, 231,
30, 94, 229, 237, 115, 221, 238, 239, 11, 83, 99, 115, 75,
91, 107, 123, 27, 91, 220, 221, 91, 219, 221, 223, 29, 93,
230, 238, 107, 221, 246, 247, 31, 95, 231, 239, 123, 223, 247,
255, 22, 108, 106, 110, 86, 109, 107, 111, 293, 602, 604, 606,
601, 603, 605, 607, 116, 737, 626, 741, 678, 739, 742, 743, 302,
745, 748, 749, 746, 747, 750, 751, 102, 666, 661, 670, 598, 667,
669, 671, 301, 729, 732, 733, 729, 731, 733, 735, 230, 753, 756,
757, 742, 755, 758, 759, 303, 761, 764, 765, 762, 763, 766, 767,
22, 293, 116, 302, 102, 301, 230, 303, 108, 602, 737, 745, 666,
729, 753, 761, 106, 604, 626, 748, 661, 732, 756, 764, 110, 606,
741, 749, 670, 733, 757, 765, 86, 601, 678, 746, 598, 729, 742,
762, 109, 603, 739, 747, 667, 731, 755, 763, 107, 605, 742, 750,
669, 733, 758, 766, 111, 607, 743, 751, 671, 735, 759, 767, 54,
310, 118, 365, 118, 365, 246, 367, 310, 876, 822, 877, 822, 877,
875, 879, 118, 822, 630, 886, 694, 949, 758, 957, 365, 877, 886,
1755, 949,1757,1758,1759, 118, 822, 694, 949, 630, 886, 758, 957,
365, 877, 949,1757, 886,1755,1758,1759, 246, 875, 758,1758, 758,
1758,1782,1783, 367, 879, 957,1759, 957,1759,1783,1791, 14, 101,
85, 117, 77, 109, 93, 125, 101, 659, 675, 686, 595, 667, 683,
687, 85, 675, 625, 819, 597, 739, 753, 827, 117, 686, 819, 947,
627, 755, 883, 955, 77, 595, 597, 627, 587, 603, 605, 635, 109,
667, 739, 755, 603, 731, 747, 763, 93, 683, 753, 883, 605, 747,
875, 891, 125, 687, 827, 955, 635, 763, 891,1019, 30, 229, 115,
238, 94, 237, 221, 239, 302, 748, 746, 750, 745, 749, 747, 751,
117, 819, 627, 883, 686, 947, 755, 955, 373, 885, 885,1883, 885,
1883,1883,1887, 110, 741, 670, 757, 606, 749, 733, 765, 365, 886,
949,1758, 877,1755,1757,1759, 238, 883, 757,1907, 750,1883,1758,
1911, 375, 887, 958,1911, 893,1917,1918,1919, 30, 302, 117, 373,
110, 365, 238, 375, 229, 748, 819, 885, 741, 886, 883, 887, 115,
746, 627, 885, 670, 949, 757, 958, 238, 750, 883,1883, 757,1758,
1907,1911, 94, 745, 686, 885, 606, 877, 750, 893, 237, 749, 947,
1883, 749,1755,1883,1917, 221, 747, 755,1883, 733,1757,1758,1918,
239, 751, 955,1887, 765,1759,1911,1919, 55, 311, 119, 375, 126,
382, 247, 383, 311, 892, 823, 893, 830, 894, 891, 895, 119, 823,
631, 887, 695, 951, 759, 959, 375, 893, 887,1917, 958,1918,1911,
1919, 126, 830, 695, 958, 638, 894, 766,1021, 382, 894, 951,1918,
894,2029,1918,2031, 247, 891, 759,1911, 766,1918,1783,2039, 383,
895, 959,1919,1021,2031,2039,2047, 1, 20, 18, 22, 10, 21,
19, 23, 20, 98, 100, 102, 84, 99, 101, 103, 18, 100, 292,
293, 100, 228, 293, 295, 22, 102, 293, 301, 116, 230, 302, 303,
10, 84, 100, 116, 76, 92, 108, 124, 21, 99, 228, 230, 92,
220, 229, 231, 19, 101, 293, 302, 108, 229, 310, 311, 23, 103,
295, 303, 124, 231, 311, 319, 10, 84, 73, 86, 81, 85, 83,
87, 100, 596, 594, 598, 593, 597, 595, 599, 76, 593, 585, 601,
593, 625, 601, 633, 108, 666, 602, 729, 737, 753, 745, 761, 84,
674, 596, 678, 593, 675, 666, 679, 116, 678, 626, 742, 737, 739,
741, 743, 92, 675, 604, 746, 737, 819, 822, 823, 124, 679, 634,
762, 826, 827, 830, 831, 10, 100, 76, 108, 84, 116, 92, 124,
84, 596, 593, 666, 674, 678, 675, 679, 73, 594, 585, 602, 596,
626, 604, 634, 86, 598, 601, 729, 678, 742, 746, 762, 81, 593,
593, 737, 593, 737, 737, 826, 85, 597, 625, 753, 675, 739, 819,
827, 83, 595, 601, 745, 666, 741, 822, 830, 87, 599, 633, 761,
679, 743, 823, 831, 14, 101, 77, 109, 85, 117, 93, 125, 101,
659, 595, 667, 675, 686, 683, 687, 77, 595, 587, 603, 597, 627,
605, 635, 109, 667, 603, 731, 739, 755, 747, 763, 85, 675, 597,
739, 625, 819, 753, 827, 117, 686, 627, 755, 819, 947, 883, 955,
93, 683, 605, 747, 753, 883, 875, 891, 125, 687, 635, 763, 827,
955, 891,1019, 9, 98, 73, 106, 73, 106, 90, 122, 98, 660,
596, 661, 596, 661, 659, 663, 73, 596, 585, 604, 594, 626, 602,
634, 106, 661, 604, 732, 626, 756, 748, 764, 73, 596, 594, 626,
585, 604, 602, 634, 106, 661, 626, 756, 604, 732, 748, 764, 90,
659, 602, 748, 602, 748, 876, 892, 122, 663, 634, 764, 634, 764,
892,1020, 11, 99, 75, 107, 83, 115, 91, 123, 102, 661, 598,
669, 666, 670, 667, 671, 77, 597, 587, 605, 595, 627, 603, 635,
110, 670, 606, 733, 741, 757, 749, 765, 86, 678, 598, 742, 601,
746, 729, 762, 118, 694, 630, 758, 822, 949, 886, 957, 94, 686,
606, 750, 745, 885, 877, 893, 126, 695, 638, 766, 830, 958, 894,
1021, 11, 102, 77, 110, 86, 118, 94, 126, 99, 661, 597, 670,
678, 694, 686, 695, 75, 598, 587, 606, 598, 630, 606, 638, 107,
669, 605, 733, 742, 758, 750, 766, 83, 666, 595, 741, 601, 822,
745, 830, 115, 670, 627, 757, 746, 949, 885, 958, 91, 667, 603,
749, 729, 886, 877, 894, 123, 671, 635, 765, 762, 957, 893,1021,
15, 103, 79, 111, 87, 119, 95, 127, 103, 663, 599, 671, 679,
695, 687, 703, 79, 599, 591, 607, 599, 631, 607, 639, 111, 671,
607, 735, 743, 759, 751, 767, 87, 679, 599, 743, 633, 823, 761,
831, 119, 695, 631, 759, 823, 951, 887, 959, 95, 687, 607, 751,
761, 887, 879, 895, 127, 703, 639, 767, 831, 959, 895,1023, 3,
21, 19, 30, 11, 29, 27, 31, 22, 106, 108, 110, 86, 107,
109, 111, 22, 116, 293, 302, 102, 230, 301, 303, 54, 118, 310,
365, 118, 246, 365, 367, 14, 85, 101, 117, 77, 93, 109, 125,
30, 115, 229, 238, 94, 221, 237, 239, 30, 117, 302, 373, 110,
238, 365, 375, 55, 119, 311, 375, 126, 247, 382, 383, 19, 92,
90, 94, 83, 93, 91, 95, 293, 604, 602, 606, 601, 605, 603,
607, 108, 737, 602, 745, 666, 753, 729, 761, 310, 822, 876, 877,
822, 875, 877, 879, 101, 675, 659, 686, 595, 683, 667, 687, 302,
746, 748, 750, 745, 747, 749, 751, 229, 819, 748, 885, 741, 883,
886, 887, 311, 823, 892, 893, 830, 891, 894, 895, 21, 228, 92,
229, 99, 230, 220, 231, 116, 626, 737, 741, 678, 742, 739, 743,
106, 626, 604, 748, 661, 756, 732, 764, 118, 630, 822, 886, 694,
758, 949, 957, 85, 625, 675, 819, 597, 753, 739, 827, 117, 627,
819, 883, 686, 755, 947, 955, 115, 627, 746, 885, 670, 757, 949,
958, 119, 631, 823, 887, 695, 759, 951, 959, 30, 229, 94, 237,
115, 238, 221, 239, 302, 748, 745, 749, 746, 750, 747, 751, 110,
741, 606, 749, 670, 757, 733, 765, 365, 886, 877,1755, 949,1758,
1757,1759, 117, 819, 686, 947, 627, 883, 755, 955, 373, 885, 885,
1883, 885,1883,1883,1887, 238, 883, 750,1883, 757,1907,1758,1911,
375, 887, 893,1917, 958,1911,1918,1919, 11, 99, 83, 115, 75,
107, 91, 123, 102, 661, 666, 670, 598, 669, 667, 671, 86, 678,
601, 746, 598, 742, 729, 762, 118, 694, 822, 949, 630, 758, 886,
957, 77, 597, 595, 627, 587, 605, 603, 635, 110, 670, 741, 757,
606, 733, 749, 765, 94, 686, 745, 885, 606, 750, 877, 893, 126,
695, 830, 958, 638, 766, 894,1021, 27, 220, 91, 221, 91, 221,
219, 223, 301, 732, 729, 733, 729, 733, 731, 735, 109, 739, 603,
747, 667, 755, 731, 763, 365, 949, 877,1757, 886,1758,1755,1759,
109, 739, 667, 755, 603, 747, 731, 763, 365, 949, 886,1758, 877,
1757,1755,1759, 237, 947, 749,1883, 749,1883,1755,1917, 382, 951,
894,1918, 894,1918,2029,2031, 29, 230, 93, 238, 107, 246, 221,
247, 230, 756, 753, 757, 742, 758, 755, 759, 107, 742, 605, 750,
669, 758, 733, 766, 246, 758, 875,1758, 758,1782,1758,1783, 93,
753, 683, 883, 605, 875, 747, 891, 238, 757, 883,1907, 750,1758,
1883,1911, 221, 755, 747,1883, 733,1758,1757,1918, 247, 759, 891,
1911, 766,1783,1918,2039, 31, 231, 95, 239, 123, 247, 223, 255,
303, 764, 761, 765, 762, 766, 763, 767, 111, 743, 607, 751, 671,
759, 735, 767, 367, 957, 879,1759, 957,1783,1759,1791, 125, 827,
687, 955, 635, 891, 763,1019, 375, 958, 887,1911, 893,1918,1917,
1919, 239, 955, 751,1887, 765,1911,1759,1919, 383, 959, 895,1919,
1021,2039,2031,2047, 3, 22, 22, 54, 14, 30, 30, 55, 21,
106, 116, 118, 85, 115, 117, 119, 19, 108, 293, 310, 101, 229,
302, 311, 30, 110, 302, 365, 117, 238, 373, 375, 11, 86, 102,
118, 77, 94, 110, 126, 29, 107, 230, 246, 93, 221, 238, 247,
27, 109, 301, 365, 109, 237, 365, 382, 31, 111, 303, 367, 125,
239, 375, 383, 21, 116, 106, 118, 85, 117, 115, 119, 228, 626,
626, 630, 625, 627, 627, 631, 92, 737, 604, 822, 675, 819, 746,
823, 229, 741, 748, 886, 819, 883, 885, 887, 99, 678, 661, 694,
597, 686, 670, 695, 230, 742, 756, 758, 753, 755, 757, 759, 220,
739, 732, 949, 739, 947, 949, 951, 231, 743, 764, 957, 827, 955,
958, 959, 19, 293, 108, 310, 101, 302, 229, 311, 92, 604, 737,
822, 675, 746, 819, 823, 90, 602, 602, 876, 659, 748, 748, 892,
94, 606, 745, 877, 686, 750, 885, 893, 83, 601, 666, 822, 595,
745, 741, 830, 93, 605, 753, 875, 683, 747, 883, 891, 91, 603,
729, 877, 667, 749, 886, 894, 95, 607, 761, 879, 687, 751, 887,
895, 30, 302, 110, 365, 117, 373, 238, 375, 229, 748, 741, 886,
819, 885, 883, 887, 94, 745, 606, 877, 686, 885, 750, 893, 237,
749, 749,1755, 947,1883,1883,1917, 115, 746, 670, 949, 627, 885,
757, 958, 238, 750, 757,1758, 883,1883,1907,1911, 221, 747, 733,
1757, 755,1883,1758,1918, 239, 751, 765,1759, 955,1887,1911,1919,
11, 102, 86, 118, 77, 110, 94, 126, 99, 661, 678, 694, 597,
670, 686, 695, 83, 666, 601, 822, 595, 741, 745, 830, 115, 670,
746, 949, 627, 757, 885, 958, 75, 598, 598, 630, 587, 606, 606,
638, 107, 669, 742, 758, 605, 733, 750, 766, 91, 667, 729, 886,
603, 749, 877, 894, 123, 671, 762, 957, 635, 765, 893,1021, 29,
230, 107, 246, 93, 238, 221, 247, 230, 756, 742, 758, 753, 757,
755, 759, 93, 753, 605, 875, 683, 883, 747, 891, 238, 757, 750,
1758, 883,1907,1883,1911, 107, 742, 669, 758, 605, 750, 733, 766,
246, 758, 758,1782, 875,1758,1758,1783, 221, 755, 733,1758, 747,
1883,1757,1918, 247, 759, 766,1783, 891,1911,1918,2039, 27, 301,
109, 365, 109, 365, 237, 382, 220, 732, 739, 949, 739, 949, 947,
951, 91, 729, 603, 877, 667, 886, 749, 894, 221, 733, 747,1757,
755,1758,1883,1918, 91, 729, 667, 886, 603, 877, 749, 894, 221,
733, 755,1758, 747,1757,1883,1918, 219, 731, 731,1755, 731,1755,
1755,2029, 223, 735, 763,1759, 763,1759,1917,2031, 31, 303, 111,
367, 125, 375, 239, 383, 231, 764, 743, 957, 827, 958, 955, 959,
95, 761, 607, 879, 687, 887, 751, 895, 239, 765, 751,1759, 955,
1911,1887,1919, 123, 762, 671, 957, 635, 893, 765,1021, 247, 766,
759,1783, 891,1918,1911,2039, 223, 763, 735,1759, 763,1917,1759,
2031, 255, 767, 767,1791,1019,1919,1919,2047, 7, 23, 23, 55,
15, 31, 31, 63, 23, 122, 124, 126, 87, 123, 125, 127, 23,
124, 295, 311, 103, 231, 303, 319, 55, 126, 311, 382, 119, 247,
375, 383, 15, 87, 103, 119, 79, 95, 111, 127, 31, 123, 231,
247, 95, 223, 239, 255, 31, 125, 303, 375, 111, 239, 367, 383,
63, 127, 319, 383, 127, 255, 383, 511, 23, 124, 122, 126, 87,
125, 123, 127, 295, 634, 634, 638, 633, 635, 635, 639, 124, 826,
634, 830, 679, 827, 762, 831, 311, 830, 892, 894, 823, 891, 893,
895, 103, 679, 663, 695, 599, 687, 671, 703, 303, 762, 764, 766,
761, 763, 765, 767, 231, 827, 764, 958, 743, 955, 957, 959, 319,
831,1020,1021, 831,1019,1021,1023, 23, 295, 124, 311, 103, 303,
231, 319, 124, 634, 826, 830, 679, 762, 827, 831, 122, 634, 634,
892, 663, 764, 764,1020, 126, 638, 830, 894, 695, 766, 958,1021,
87, 633, 679, 823, 599, 761, 743, 831, 125, 635, 827, 891, 687,
763, 955,1019, 123, 635, 762, 893, 671, 765, 957,1021, 127, 639,
831, 895, 703, 767, 959,1023, 55, 311, 126, 382, 119, 375, 247,
383, 311, 892, 830, 894, 823, 893, 891, 895, 126, 830, 638, 894,
695, 958, 766,1021, 382, 894, 894,2029, 951,1918,1918,2031, 119,
823, 695, 951, 631, 887, 759, 959, 375, 893, 958,1918, 887,1917,
1911,1919, 247, 891, 766,1918, 759,1911,1783,2039, 383, 895,1021,
2031, 959,1919,2039,2047, 15, 103, 87, 119, 79, 111, 95, 127,
103, 663, 679, 695, 599, 671, 687, 703, 87, 679, 633, 823, 599,
743, 761, 831, 119, 695, 823, 951, 631, 759, 887, 959, 79, 599,
599, 631, 591, 607, 607, 639, 111, 671, 743, 759, 607, 735, 751,
767, 95, 687, 761, 887, 607, 751, 879, 895, 127, 703, 831, 959,
639, 767, 895,1023, 31, 231, 123, 247, 95, 239, 223, 255, 303,
764, 762, 766, 761, 765, 763, 767, 125, 827, 635, 891, 687, 955,
763,1019, 375, 958, 893,1918, 887,1911,1917,1919, 111, 743, 671,
759, 607, 751, 735, 767, 367, 957, 957,1783, 879,1759,1759,1791,
239, 955, 765,1911, 751,1887,1759,1919, 383, 959,1021,2039, 895,
1919,2031,2047, 31, 303, 125, 375, 111, 367, 239, 383, 231, 764,
827, 958, 743, 957, 955, 959, 123, 762, 635, 893, 671, 957, 765,
1021, 247, 766, 891,1918, 759,1783,1911,2039, 95, 761, 687, 887,
607, 879, 751, 895, 239, 765, 955,1911, 751,1759,1887,1919, 223,
763, 763,1917, 735,1759,1759,2031, 255, 767,1019,1919, 767,1791,
1919,2047, 63, 319, 127, 383, 127, 383, 255, 511, 319,1020, 831,
1021, 831,1021,1019,1023, 127, 831, 639, 895, 703, 959, 767,1023,
383,1021, 895,2031, 959,2039,1919,2047, 127, 831, 703, 959, 639,
895, 767,1023, 383,1021, 959,2039, 895,2031,1919,2047, 255,1019,
767,1919, 767,1919,1791,2047, 511,1023,1023,2047,1023,2047,2047,
4095 };
unsigned int igraph_i_isoclass_4_idx[] = {
0, 8, 64, 512, 1, 0, 128, 1024, 2, 16, 0, 2048, 4, 32, 256, 0 };
unsigned int igraph_i_isoclass_3u[] = { 0,1,1,3,1,3,3,7 };
unsigned int igraph_i_isoclass_3u_idx[] = { 0,1,2,1,0,4,2,4,0 };
unsigned int igraph_i_isoclass_4u[] = {
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,
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,
7,15,15,31,11,15,15,31,15,31,31,63 };
unsigned int igraph_i_isoclass_4u_idx[] = {
0, 1, 2, 8, 1, 0, 4, 16, 2, 4, 0, 32, 8, 16, 32, 0 };
unsigned int igraph_i_isoclass2_3[] = {
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,
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,
7,13,12,14, 5,12,10,14, 8,14,14,15
};
unsigned int igraph_i_isoclass2_3u[] = {
0,1,1,2,1,2,2,3
};
unsigned int igraph_i_isoclass2_4u[] = {
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,
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,
3, 7, 7, 9, 4, 7, 7, 9, 7, 9, 9,10
};
unsigned int igraph_i_isoclass2_4[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 4, 5, 6, 5, 6, 7, 8, 1, 5, 9, 10,
11, 12, 13, 14, 2, 6, 10, 15, 12, 16, 17, 18, 1, 5, 11, 12, 9, 10, 13, 14,
2, 6, 12, 16, 10, 15, 17, 18, 2, 7, 13, 17, 13, 17, 19, 20, 3, 8, 14, 18,
14, 18, 20, 21, 1, 5, 4, 6, 5, 7, 6, 8, 9, 22, 22, 23, 24, 25, 25, 26,
5, 27, 22, 28, 29, 30, 31, 32, 10, 28, 33, 34, 35, 36, 37, 38, 11, 29, 39, 40,
41, 42, 43, 44, 13, 31, 45, 46, 47, 48, 49, 50, 12, 30, 45, 51, 52, 53, 54, 55,
14, 32, 56, 57, 58, 59, 60, 61, 1, 9, 5, 10, 11, 13, 12, 14, 5, 22, 27, 28,
29, 31, 30, 32, 4, 22, 22, 33, 39, 45, 45, 56, 6, 23, 28, 34, 40, 46, 51, 57,
5, 24, 29, 35, 41, 47, 52, 58, 7, 25, 30, 36, 42, 48, 53, 59, 6, 25, 31, 37,
43, 49, 54, 60, 8, 26, 32, 38, 44, 50, 55, 61, 2, 10, 6, 15, 12, 17, 16, 18,
10, 33, 28, 34, 35, 37, 36, 38, 6, 28, 23, 34, 40, 51, 46, 57, 15, 34, 34, 62,
63, 64, 64, 65, 12, 35, 40, 63, 66, 67, 68, 69, 17, 37, 51, 64, 67, 70, 71, 72,
16, 36, 46, 64, 68, 71, 73, 74, 18, 38, 57, 65, 69, 72, 74, 75, 1, 11, 5, 12,
9, 13, 10, 14, 11, 39, 29, 40, 41, 43, 42, 44, 5, 29, 24, 35, 41, 52, 47, 58,
12, 40, 35, 63, 66, 68, 67, 69, 9, 41, 41, 66, 76, 77, 77, 78, 13, 43, 52, 68,
77, 79, 80, 81, 10, 42, 47, 67, 77, 80, 82, 83, 14, 44, 58, 69, 78, 81, 83, 84,
2, 12, 6, 16, 10, 17, 15, 18, 13, 45, 31, 46, 47, 49, 48, 50, 7, 30, 25, 36,
42, 53, 48, 59, 17, 51, 37, 64, 67, 71, 70, 72, 13, 52, 43, 68, 77, 80, 79, 81,
19, 54, 54, 73, 82, 85, 85, 86, 17, 53, 49, 71, 80, 87, 85, 88, 20, 55, 60, 74,
83, 88, 89, 90, 2, 13, 7, 17, 13, 19, 17, 20, 12, 45, 30, 51, 52, 54, 53, 55,
6, 31, 25, 37, 43, 54, 49, 60, 16, 46, 36, 64, 68, 73, 71, 74, 10, 47, 42, 67,
77, 82, 80, 83, 17, 49, 53, 71, 80, 85, 87, 88, 15, 48, 48, 70, 79, 85, 85, 89,
18, 50, 59, 72, 81, 86, 88, 90, 3, 14, 8, 18, 14, 20, 18, 21, 14, 56, 32, 57,
58, 60, 59, 61, 8, 32, 26, 38, 44, 55, 50, 61, 18, 57, 38, 65, 69, 74, 72, 75,
14, 58, 44, 69, 78, 83, 81, 84, 20, 60, 55, 74, 83, 89, 88, 90, 18, 59, 50, 72,
81, 88, 86, 90, 21, 61, 61, 75, 84, 90, 90, 91, 1, 5, 5, 7, 4, 6, 6, 8,
9, 22, 24, 25, 22, 23, 25, 26, 11, 29, 41, 42, 39, 40, 43, 44, 13, 31, 47, 48,
45, 46, 49, 50, 5, 27, 29, 30, 22, 28, 31, 32, 10, 28, 35, 36, 33, 34, 37, 38,
12, 30, 52, 53, 45, 51, 54, 55, 14, 32, 58, 59, 56, 57, 60, 61, 9, 24, 22, 25,
22, 25, 23, 26, 76, 92, 92, 93, 92, 93, 93, 94, 41, 95, 96, 97, 98, 99,100,101,
77,102,103,104,105,106,107,108, 41, 95, 98, 99, 96, 97,100,101, 77,102,105,106,
103,104,107,108, 66,109,110,111,110,111,112,113, 78,114,115,116,115,116,117,118,
11, 41, 29, 42, 39, 43, 40, 44, 41, 96, 95, 97, 98,100, 99,101, 39, 98, 98,119,
120,121,121,122, 43,100,123,124,121,125,126,127, 29, 95,128,129, 98,123,130,131,
42, 97,129,132,119,124,133,134, 40, 99,130,133,121,126,135,136, 44,101,131,134,
122,127,136,137, 13, 47, 31, 48, 45, 49, 46, 50, 77,103,102,104,105,107,106,108,
43,123,100,124,121,126,125,127, 79,138,138,139,140,141,141,142, 52,143,130,144,
110,145,146,147, 80,148,149,150,151,152,153,154, 68,155,146,156,157,158,159,160,
81,161,162,163,164,165,166,167, 5, 29, 27, 30, 22, 31, 28, 32, 41, 98, 95, 99,
96,100, 97,101, 29,128, 95,129, 98,130,123,131, 52,130,143,144,110,146,145,147,
24, 95, 95,109, 92,102,102,114, 47,123,143,155,103,138,148,161, 35,129,143,168,
105,149,169,170, 58,131,171,172,115,162,173,174, 10, 35, 28, 36, 33, 37, 34, 38,
77,105,102,106,103,107,104,108, 42,129, 97,132,119,133,124,134, 80,149,148,150,
151,153,152,154, 47,143,123,155,103,148,138,161, 82,169,169,175,176,177,177,178,
67,168,145,179,151,180,181,182, 83,170,173,183,184,185,186,187, 12, 52, 30, 53,
45, 54, 51, 55, 66,110,109,111,110,112,111,113, 40,130, 99,133,121,135,126,136,
68,146,155,156,157,159,158,160, 35,143,129,168,105,169,149,170, 67,145,168,179,
151,181,180,182, 63,144,144,188,140,189,189,190, 69,147,172,191,164,192,193,194,
14, 58, 32, 59, 56, 60, 57, 61, 78,115,114,116,115,117,116,118, 44,131,101,134,
122,136,127,137, 81,162,161,163,164,166,165,167, 58,171,131,172,115,173,162,174,
83,173,170,183,184,186,185,187, 69,172,147,191,164,193,192,194, 84,174,174,195,
196,197,197,198, 1, 9, 11, 13, 5, 10, 12, 14, 5, 22, 29, 31, 27, 28, 30, 32,
5, 24, 41, 47, 29, 35, 52, 58, 7, 25, 42, 48, 30, 36, 53, 59, 4, 22, 39, 45,
22, 33, 45, 56, 6, 23, 40, 46, 28, 34, 51, 57, 6, 25, 43, 49, 31, 37, 54, 60,
8, 26, 44, 50, 32, 38, 55, 61, 11, 41, 39, 43, 29, 42, 40, 44, 41, 96, 98,100,
95, 97, 99,101, 29, 95, 98,123,128,129,130,131, 42, 97,119,124,129,132,133,134,
39, 98,120,121, 98,119,121,122, 43,100,121,125,123,124,126,127, 40, 99,121,126,
130,133,135,136, 44,101,122,127,131,134,136,137, 9, 76, 41, 77, 41, 77, 66, 78,
24, 92, 95,102, 95,102,109,114, 22, 92, 96,103, 98,105,110,115, 25, 93, 97,104,
99,106,111,116, 22, 92, 98,105, 96,103,110,115, 25, 93, 99,106, 97,104,111,116,
23, 93,100,107,100,107,112,117, 26, 94,101,108,101,108,113,118, 13, 77, 43, 79,
52, 80, 68, 81, 47,103,123,138,143,148,155,161, 31,102,100,138,130,149,146,162,
48,104,124,139,144,150,156,163, 45,105,121,140,110,151,157,164, 49,107,126,141,
145,152,158,165, 46,106,125,141,146,153,159,166, 50,108,127,142,147,154,160,167,
5, 41, 29, 52, 24, 47, 35, 58, 29, 98,128,130, 95,123,129,131, 27, 95, 95,143,
95,143,143,171, 30, 99,129,144,109,155,168,172, 22, 96, 98,110, 92,103,105,115,
31,100,130,146,102,138,149,162, 28, 97,123,145,102,148,169,173, 32,101,131,147,
114,161,170,174, 12, 66, 40, 68, 35, 67, 63, 69, 52,110,130,146,143,145,144,147,
30,109, 99,155,129,168,144,172, 53,111,133,156,168,179,188,191, 45,110,121,157,
105,151,140,164, 54,112,135,159,169,181,189,192, 51,111,126,158,149,180,189,193,
55,113,136,160,170,182,190,194, 10, 77, 42, 80, 47, 82, 67, 83, 35,105,129,149,
143,169,168,170, 28,102, 97,148,123,169,145,173, 36,106,132,150,155,175,179,183,
33,103,119,151,103,176,151,184, 37,107,133,153,148,177,180,185, 34,104,124,152,
138,177,181,186, 38,108,134,154,161,178,182,187, 14, 78, 44, 81, 58, 83, 69, 84,
58,115,131,162,171,173,172,174, 32,114,101,161,131,170,147,174, 59,116,134,163,
172,183,191,195, 56,115,122,164,115,184,164,196, 60,117,136,166,173,186,193,197,
57,116,127,165,162,185,192,197, 61,118,137,167,174,187,194,198, 2, 10, 12, 17,
6, 15, 16, 18, 10, 33, 35, 37, 28, 34, 36, 38, 12, 35, 66, 67, 40, 63, 68, 69,
17, 37, 67, 70, 51, 64, 71, 72, 6, 28, 40, 51, 23, 34, 46, 57, 15, 34, 63, 64,
34, 62, 64, 65, 16, 36, 68, 71, 46, 64, 73, 74, 18, 38, 69, 72, 57, 65, 74, 75,
13, 47, 45, 49, 31, 48, 46, 50, 77,103,105,107,102,104,106,108, 52,143,110,145,
130,144,146,147, 80,148,151,152,149,150,153,154, 43,123,121,126,100,124,125,127,
79,138,140,141,138,139,141,142, 68,155,157,158,146,156,159,160, 81,161,164,165,
162,163,166,167, 13, 77, 52, 80, 43, 79, 68, 81, 47,103,143,148,123,138,155,161,
45,105,110,151,121,140,157,164, 49,107,145,152,126,141,158,165, 31,102,130,149,
100,138,146,162, 48,104,144,150,124,139,156,163, 46,106,146,153,125,141,159,166,
50,108,147,154,127,142,160,167, 19, 82, 54, 85, 54, 85, 73, 86, 82,176,169,177,
169,177,175,178, 54,169,112,181,135,189,159,192, 85,177,181,199,189,200,201,202,
54,169,135,189,112,181,159,192, 85,177,189,200,181,199,201,202, 73,175,159,201,
159,201,203,204, 86,178,192,202,192,202,204,205, 7, 42, 30, 53, 25, 48, 36, 59,
42,119,129,133, 97,124,132,134, 30,129,109,168, 99,144,155,172, 53,133,168,188,
111,156,179,191, 25, 97, 99,111, 93,104,106,116, 48,124,144,156,104,139,150,163,
36,132,155,179,106,150,175,183, 59,134,172,191,116,163,183,195, 17, 67, 51, 71,
37, 70, 64, 72, 80,151,149,153,148,152,150,154, 53,168,111,179,133,188,156,191,
87,180,180,206,180,206,206,207, 49,145,126,158,107,152,141,165, 85,181,189,201,
177,199,200,202, 71,179,158,208,153,206,201,209, 88,182,193,209,185,210,211,212,
17, 80, 53, 87, 49, 85, 71, 88, 67,151,168,180,145,181,179,182, 51,149,111,180,
126,189,158,193, 71,153,179,206,158,201,208,209, 37,148,133,180,107,177,153,185,
70,152,188,206,152,199,206,210, 64,150,156,206,141,200,201,211, 72,154,191,207,
165,202,209,212, 20, 83, 55, 88, 60, 89, 74, 90, 83,184,170,185,173,186,183,187,
55,170,113,182,136,190,160,194, 88,185,182,210,193,211,209,212, 60,173,136,193,
117,186,166,197, 89,186,190,211,186,213,211,214, 74,183,160,209,166,211,204,215,
90,187,194,212,197,214,215,216, 1, 11, 9, 13, 5, 12, 10, 14, 11, 39, 41, 43,
29, 40, 42, 44, 9, 41, 76, 77, 41, 66, 77, 78, 13, 43, 77, 79, 52, 68, 80, 81,
5, 29, 41, 52, 24, 35, 47, 58, 12, 40, 66, 68, 35, 63, 67, 69, 10, 42, 77, 80,
47, 67, 82, 83, 14, 44, 78, 81, 58, 69, 83, 84, 5, 29, 22, 31, 27, 30, 28, 32,
41, 98, 96,100, 95, 99, 97,101, 24, 95, 92,102, 95,109,102,114, 47,123,103,138,
143,155,148,161, 29,128, 98,130, 95,129,123,131, 52,130,110,146,143,144,145,147,
35,129,105,149,143,168,169,170, 58,131,115,162,171,172,173,174, 5, 41, 24, 47,
29, 52, 35, 58, 29, 98, 95,123,128,130,129,131, 22, 96, 92,103, 98,110,105,115,
31,100,102,138,130,146,149,162, 27, 95, 95,143, 95,143,143,171, 30, 99,109,155,
129,144,168,172, 28, 97,102,148,123,145,169,173, 32,101,114,161,131,147,170,174,
7, 42, 25, 48, 30, 53, 36, 59, 42,119, 97,124,129,133,132,134, 25, 97, 93,104,
99,111,106,116, 48,124,104,139,144,156,150,163, 30,129, 99,144,109,168,155,172,
53,133,111,156,168,188,179,191, 36,132,106,150,155,179,175,183, 59,134,116,163,
172,191,183,195, 4, 39, 22, 45, 22, 45, 33, 56, 39,120, 98,121, 98,121,119,122,
22, 98, 92,105, 96,110,103,115, 45,121,105,140,110,157,151,164, 22, 98, 96,110,
92,105,103,115, 45,121,110,157,105,140,151,164, 33,119,103,151,103,151,176,184,
56,122,115,164,115,164,184,196, 6, 40, 23, 46, 28, 51, 34, 57, 43,121,100,125,
123,126,124,127, 25, 99, 93,106, 97,111,104,116, 49,126,107,141,145,158,152,165,
31,130,100,146,102,149,138,162, 54,135,112,159,169,189,181,192, 37,133,107,153,
148,180,177,185, 60,136,117,166,173,193,186,197, 6, 43, 25, 49, 31, 54, 37, 60,
40,121, 99,126,130,135,133,136, 23,100, 93,107,100,112,107,117, 46,125,106,141,
146,159,153,166, 28,123, 97,145,102,169,148,173, 51,126,111,158,149,189,180,193,
34,124,104,152,138,181,177,186, 57,127,116,165,162,192,185,197, 8, 44, 26, 50,
32, 55, 38, 61, 44,122,101,127,131,136,134,137, 26,101, 94,108,101,113,108,118,
50,127,108,142,147,160,154,167, 32,131,101,147,114,170,161,174, 55,136,113,160,
170,190,182,194, 38,134,108,154,161,182,178,187, 61,137,118,167,174,194,187,198,
2, 12, 10, 17, 6, 16, 15, 18, 13, 45, 47, 49, 31, 46, 48, 50, 13, 52, 77, 80,
43, 68, 79, 81, 19, 54, 82, 85, 54, 73, 85, 86, 7, 30, 42, 53, 25, 36, 48, 59,
17, 51, 67, 71, 37, 64, 70, 72, 17, 53, 80, 87, 49, 71, 85, 88, 20, 55, 83, 88,
60, 74, 89, 90, 10, 35, 33, 37, 28, 36, 34, 38, 77,105,103,107,102,106,104,108,
47,143,103,148,123,155,138,161, 82,169,176,177,169,175,177,178, 42,129,119,133,
97,132,124,134, 80,149,151,153,148,150,152,154, 67,168,151,180,145,179,181,182,
83,170,184,185,173,183,186,187, 12, 66, 35, 67, 40, 68, 63, 69, 52,110,143,145,
130,146,144,147, 45,110,105,151,121,157,140,164, 54,112,169,181,135,159,189,192,
30,109,129,168, 99,155,144,172, 53,111,168,179,133,156,188,191, 51,111,149,180,
126,158,189,193, 55,113,170,182,136,160,190,194, 17, 67, 37, 70, 51, 71, 64, 72,
80,151,148,152,149,153,150,154, 49,145,107,152,126,158,141,165, 85,181,177,199,
189,201,200,202, 53,168,133,188,111,179,156,191, 87,180,180,206,180,206,206,207,
71,179,153,206,158,208,201,209, 88,182,185,210,193,209,211,212, 6, 40, 28, 51,
23, 46, 34, 57, 43,121,123,126,100,125,124,127, 31,130,102,149,100,146,138,162,
54,135,169,189,112,159,181,192, 25, 99, 97,111, 93,106,104,116, 49,126,145,158,
107,141,152,165, 37,133,148,180,107,153,177,185, 60,136,173,193,117,166,186,197,
15, 63, 34, 64, 34, 64, 62, 65, 79,140,138,141,138,141,139,142, 48,144,104,150,
124,156,139,163, 85,189,177,200,181,201,199,202, 48,144,124,156,104,150,139,163,
85,189,181,201,177,200,199,202, 70,188,152,206,152,206,199,210, 89,190,186,211,
186,211,213,214, 16, 68, 36, 71, 46, 73, 64, 74, 68,157,155,158,146,159,156,160,
46,146,106,153,125,159,141,166, 73,159,175,201,159,203,201,204, 36,155,132,179,
106,175,150,183, 71,158,179,208,153,201,206,209, 64,156,150,206,141,201,200,211,
74,160,183,209,166,204,211,215, 18, 69, 38, 72, 57, 74, 65, 75, 81,164,161,165,
162,166,163,167, 50,147,108,154,127,160,142,167, 86,192,178,202,192,204,202,205,
59,172,134,191,116,183,163,195, 88,193,182,209,185,211,210,212, 72,191,154,207,
165,209,202,212, 90,194,187,212,197,215,214,216, 2, 13, 13, 19, 7, 17, 17, 20,
12, 45, 52, 54, 30, 51, 53, 55, 10, 47, 77, 82, 42, 67, 80, 83, 17, 49, 80, 85,
53, 71, 87, 88, 6, 31, 43, 54, 25, 37, 49, 60, 16, 46, 68, 73, 36, 64, 71, 74,
15, 48, 79, 85, 48, 70, 85, 89, 18, 50, 81, 86, 59, 72, 88, 90, 12, 52, 45, 54,
30, 53, 51, 55, 66,110,110,112,109,111,111,113, 35,143,105,169,129,168,149,170,
67,145,151,181,168,179,180,182, 40,130,121,135, 99,133,126,136, 68,146,157,159,
155,156,158,160, 63,144,140,189,144,188,189,190, 69,147,164,192,172,191,193,194,
10, 77, 47, 82, 42, 80, 67, 83, 35,105,143,169,129,149,168,170, 33,103,103,176,
119,151,151,184, 37,107,148,177,133,153,180,185, 28,102,123,169, 97,148,145,173,
36,106,155,175,132,150,179,183, 34,104,138,177,124,152,181,186, 38,108,161,178,
134,154,182,187, 17, 80, 49, 85, 53, 87, 71, 88, 67,151,145,181,168,180,179,182,
37,148,107,177,133,180,153,185, 70,152,152,199,188,206,206,210, 51,149,126,189,
111,180,158,193, 71,153,158,201,179,206,208,209, 64,150,141,200,156,206,201,211,
72,154,165,202,191,207,209,212, 6, 43, 31, 54, 25, 49, 37, 60, 40,121,130,135,
99,126,133,136, 28,123,102,169, 97,145,148,173, 51,126,149,189,111,158,180,193,
23,100,100,112, 93,107,107,117, 46,125,146,159,106,141,153,166, 34,124,138,181,
104,152,177,186, 57,127,162,192,116,165,185,197, 16, 68, 46, 73, 36, 71, 64, 74,
68,157,146,159,155,158,156,160, 36,155,106,175,132,179,150,183, 71,158,153,201,
179,208,206,209, 46,146,125,159,106,153,141,166, 73,159,159,203,175,201,201,204,
64,156,141,201,150,206,200,211, 74,160,166,204,183,209,211,215, 15, 79, 48, 85,
48, 85, 70, 89, 63,140,144,189,144,189,188,190, 34,138,104,177,124,181,152,186,
64,141,150,200,156,201,206,211, 34,138,124,181,104,177,152,186, 64,141,156,201,
150,200,206,211, 62,139,139,199,139,199,199,213, 65,142,163,202,163,202,210,214,
18, 81, 50, 86, 59, 88, 72, 90, 69,164,147,192,172,193,191,194, 38,161,108,178,
134,182,154,187, 72,165,154,202,191,209,207,212, 57,162,127,192,116,185,165,197,
74,166,160,204,183,211,209,215, 65,163,142,202,163,210,202,214, 75,167,167,205,
195,212,212,216, 3, 14, 14, 20, 8, 18, 18, 21, 14, 56, 58, 60, 32, 57, 59, 61,
14, 58, 78, 83, 44, 69, 81, 84, 20, 60, 83, 89, 55, 74, 88, 90, 8, 32, 44, 55,
26, 38, 50, 61, 18, 57, 69, 74, 38, 65, 72, 75, 18, 59, 81, 88, 50, 72, 86, 90,
21, 61, 84, 90, 61, 75, 90, 91, 14, 58, 56, 60, 32, 59, 57, 61, 78,115,115,117,
114,116,116,118, 58,171,115,173,131,172,162,174, 83,173,184,186,170,183,185,187,
44,131,122,136,101,134,127,137, 81,162,164,166,161,163,165,167, 69,172,164,193,
147,191,192,194, 84,174,196,197,174,195,197,198, 14, 78, 58, 83, 44, 81, 69, 84,
58,115,171,173,131,162,172,174, 56,115,115,184,122,164,164,196, 60,117,173,186,
136,166,193,197, 32,114,131,170,101,161,147,174, 59,116,172,183,134,163,191,195,
57,116,162,185,127,165,192,197, 61,118,174,187,137,167,194,198, 20, 83, 60, 89,
55, 88, 74, 90, 83,184,173,186,170,185,183,187, 60,173,117,186,136,193,166,197,
89,186,186,213,190,211,211,214, 55,170,136,190,113,182,160,194, 88,185,193,211,
182,210,209,212, 74,183,166,211,160,209,204,215, 90,187,197,214,194,212,215,216,
8, 44, 32, 55, 26, 50, 38, 61, 44,122,131,136,101,127,134,137, 32,131,114,170,
101,147,161,174, 55,136,170,190,113,160,182,194, 26,101,101,113, 94,108,108,118,
50,127,147,160,108,142,154,167, 38,134,161,182,108,154,178,187, 61,137,174,194,
118,167,187,198, 18, 69, 57, 74, 38, 72, 65, 75, 81,164,162,166,161,165,163,167,
59,172,116,183,134,191,163,195, 88,193,185,211,182,209,210,212, 50,147,127,160,
108,154,142,167, 86,192,192,204,178,202,202,205, 72,191,165,209,154,207,202,212,
90,194,197,215,187,212,214,216, 18, 81, 59, 88, 50, 86, 72, 90, 69,164,172,193,
147,192,191,194, 57,162,116,185,127,192,165,197, 74,166,183,211,160,204,209,215,
38,161,134,182,108,178,154,187, 72,165,191,209,154,202,207,212, 65,163,163,210,
142,202,202,214, 75,167,195,212,167,205,212,216, 21, 84, 61, 90, 61, 90, 75, 91,
84,196,174,197,174,197,195,198, 61,174,118,187,137,194,167,198, 90,197,187,214,
194,215,212,216, 61,174,137,194,118,187,167,198, 90,197,194,215,187,214,212,216,
75,195,167,212,167,212,205,216, 91,198,198,216,198,216,216,217
};
unsigned int igraph_i_isographs_3[] = { 0, 1, 3, 5, 6, 7, 10, 11, 15, 21,
23, 25, 27, 30, 31, 63 };
unsigned int igraph_i_isographs_3u[] = { 0, 1, 3, 7 };
unsigned int igraph_i_isographs_4[] = {
0, 1, 3, 7, 9, 10, 11, 14, 15, 18, 19, 20, 21,
22, 23, 27, 29, 30, 31, 54, 55, 63, 73, 75, 76, 77,
79, 81, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95,
98, 99, 100, 101, 102, 103, 106, 107, 108, 109, 110, 111, 115,
116, 117, 118, 119, 122, 123, 124, 125, 126, 127, 219, 220, 221,
223, 228, 229, 230, 231, 237, 238, 239, 246, 247, 255, 292, 293,
295, 301, 302, 303, 310, 311, 319, 365, 367, 373, 375, 382, 383,
511, 585, 587, 591, 593, 594, 595, 596, 597, 598, 599, 601, 602,
603, 604, 605, 606, 607, 625, 626, 627, 630, 631, 633, 634, 635,
638, 639, 659, 660, 661, 663, 666, 667, 669, 670, 671, 674, 675,
678, 679, 683, 686, 687, 694, 695, 703, 729, 731, 732, 733, 735,
737, 739, 741, 742, 743, 745, 746, 747, 748, 749, 750, 751, 753,
755, 756, 757, 758, 759, 761, 762, 763, 764, 765, 766, 767, 819,
822, 823, 826, 827, 830, 831, 875, 876, 877, 879, 883, 885, 886,
887, 891, 892, 893, 894, 895, 947, 949, 951, 955, 957, 958, 959,
1019, 1020, 1021, 1023, 1755, 1757, 1758, 1759, 1782, 1783, 1791, 1883, 1887,
1907, 1911, 1917, 1918, 1919, 2029, 2031, 2039, 2047, 4095};
unsigned int igraph_i_isographs_4u[] = { 0, 1, 3, 7, 11, 12, 13,
15, 30, 31, 63};
unsigned int igraph_i_classedges_3[] = { 1,2, 0,2, 2,1, 0,1, 2,0, 1,0 };
unsigned int igraph_i_classedges_3u[] = { 1,2, 0,2, 0,1 };
unsigned int igraph_i_classedges_4[] = { 2,3, 1,3, 0,3, 3,2, 1,2, 0,2,
3,1, 2,1, 0,1, 3,0, 2,0, 1,0 };
unsigned int igraph_i_classedges_4u[] = { 2,3, 1,3, 0,3, 1,2, 0,2, 0,1 };
/**
* \function igraph_isoclass
* \brief Determine the isomorphism class of a graph
*
* </para><para>
* All graphs with a given number of vertices belong to a number of
* isomorpism classes, with every graph in a given class being
* isomorphic to each other.
*
* </para><para>
* This function gives the isomorphism class (a number) of a
* graph. Two graphs have the same isomorphism class if and only if
* they are isomorphic.
*
* </para><para>
* The first isomorphism class is numbered zero and it is the empty
* graph, the last isomorphism class is the full graph. The number of
* isomorphism class for directed graphs with three vertices is 16
* (between 0 and 15), for undirected graph it is only 4. For graphs
* with four vertices it is 218 (directed) and 11 (undirected).
*
* \param graph The graph object.
* \param isoclass Pointer to an integer, the isomorphism class will
* be stored here.
* \return Error code.
* \sa \ref igraph_isomorphic(), \ref igraph_isoclass_subgraph(),
* \ref igraph_isoclass_create(), \ref igraph_motifs_randesu().
*
* Because of some limitations this function works only for graphs
* with three of four vertices.
*
* </para><para>
* Time complexity: O(|E|), the number of edges in the graph.
*/
int igraph_isoclass(const igraph_t *graph, int *isoclass) {
long int e;
long int no_of_nodes=igraph_vcount(graph);
long int no_of_edges=igraph_ecount(graph);
igraph_integer_t from, to;
unsigned char idx, mul;
unsigned int *arr_idx, *arr_code;
int code=0;
if (no_of_nodes < 3 || no_of_nodes > 4) {
IGRAPH_ERROR("Only implemented for graphs with 3 or 4 vertices",
IGRAPH_UNIMPLEMENTED);
}
if (igraph_is_directed(graph)) {
if (no_of_nodes==3) {
arr_idx=igraph_i_isoclass_3_idx;
arr_code=igraph_i_isoclass2_3;
mul=3;
} else {
arr_idx=igraph_i_isoclass_4_idx;
arr_code=igraph_i_isoclass2_4;
mul=4;
}
} else {
if (no_of_nodes==3) {
arr_idx=igraph_i_isoclass_3u_idx;
arr_code=igraph_i_isoclass2_3u;
mul=3;
} else {
arr_idx=igraph_i_isoclass_4u_idx;
arr_code=igraph_i_isoclass2_4u;
mul=4;
}
}
for (e=0; e<no_of_edges; e++) {
igraph_edge(graph, e, &from, &to);
idx=mul*from+to;
code |= arr_idx[idx];
}
*isoclass=arr_code[code];
return 0;
}
/**
* \function igraph_isomorphic
* \brief Decides whether two graphs are isomorphic
*
* </para><para>
* From Wikipedia: The graph isomorphism problem or GI problem is the
* graph theory problem of determining whether, given two graphs G1
* and G2, it is possible to permute (or relabel) the vertices of one
* graph so that it is equal to the other. Such a permutation is
* called a graph isomorphism.
*
* \param graph1 The first graph.
* \param graph2 The second graph.
* \param iso Pointer to a logical variable, will be set to TRUE (1)
* if the two graphs are isomorphic, and FALSE (0) otherwise.
* \return Error code.
* \sa \ref igraph_isoclass(), \ref igraph_isoclass_subgraph(),
* \ref igraph_isoclass_create().
*
* Time complexity: O(|E|), the number of edges in the
* graphs. (If they don't have the same number edges they're trivially
* non-isomorphic and this is recognized in O(1) time.)
*/
int igraph_isomorphic(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso) {
int class1, class2;
if (igraph_vcount(graph1) != igraph_vcount(graph2) ||
igraph_ecount(graph1) != igraph_ecount(graph2)) {
*iso=0;
} else {
IGRAPH_CHECK(igraph_isoclass(graph1, &class1));
IGRAPH_CHECK(igraph_isoclass(graph2, &class2));
*iso= (class1 == class2);
}
return 0;
}
/**
* \function igraph_isoclass_subgraph
* \brief The isomorphism class of a subgraph of a graph.
*
* </para><para>
* This function is only implemented for subgraphs with three or four
* vertices.
* \param graph The graph object.
* \param vids A vector containing the vertex ids to be considered as
* a subgraph. Each vertex id should be included at most once.
* \param isoclass Pointer to an integer, this will be set to the
* isomorphism class.
* \return Error code.
* \sa \ref igraph_isoclass(), \ref igraph_isomorphic(),
* \ref igraph_isoclass_create().
*
* Time complexity: O((d+n)*n), d is the average degree in the network,
* and n is the number of vertices in \c vids.
*/
int igraph_isoclass_subgraph(const igraph_t *graph, igraph_vector_t *vids,
int *isoclass) {
int nodes=igraph_vector_size(vids);
igraph_bool_t directed=igraph_is_directed(graph);
igraph_vector_t neis;
unsigned char mul, idx;
unsigned int *arr_idx, *arr_code;
int code=0;
long int i, j, s;
if (nodes < 3 || nodes > 4) {
IGRAPH_ERROR("Only for three- or four-vertex subgraphs",
IGRAPH_UNIMPLEMENTED);
}
IGRAPH_VECTOR_INIT_FINALLY(&neis, 0);
if (directed) {
if (nodes==3) {
arr_idx=igraph_i_isoclass_3_idx;
arr_code=igraph_i_isoclass2_3;
mul=3;
} else {
arr_idx=igraph_i_isoclass_4_idx;
arr_code=igraph_i_isoclass2_4;
mul=4;
}
} else {
if (nodes==3) {
arr_idx=igraph_i_isoclass_3u_idx;
arr_code=igraph_i_isoclass2_3u;
mul=3;
} else {
arr_idx=igraph_i_isoclass_4u_idx;
arr_code=igraph_i_isoclass2_4u;
mul=4;
}
}
for (i=0; i<nodes; i++) {
long int from=VECTOR(*vids)[i];
igraph_neighbors(graph, &neis, from, IGRAPH_OUT);
s=igraph_vector_size(&neis);
for (j=0; j<s; j++) {
long int nei=VECTOR(neis)[j], to;
if (igraph_vector_search(vids, 0, nei, &to)) {
idx=mul*i+to;
code |= arr_idx[idx];
}
}
}
*isoclass=arr_code[code];
igraph_vector_destroy(&neis);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \function igraph_isoclass_create
* \brief Creates a graph from the given isomorphism class.
*
* </para><para>
* This function is implemented only for graphs with three or four
* vertices.
* \param graph Pointer to an uninitialized graph object.
* \param size The number of vertices to add to the graph.
* \param number The isomorphism class.
* \param directed Logical constant, whether to create a directed
* graph.
* \return Error code.
* \sa \ref igraph_isoclass(),
* \ref igraph_isoclass_subgraph(),
* \ref igraph_isomorphic().
*
* Time complexity: O(|V|+|E|), the number of vertices plus the number
* of edges in the graph to create.
*/
int igraph_isoclass_create(igraph_t *graph, igraph_integer_t size,
igraph_integer_t number, igraph_bool_t directed) {
igraph_vector_t edges;
unsigned int *classedges;
long int power;
long int code;
long int pos;
if (size < 3 || size > 4) {
IGRAPH_ERROR("Only for graphs with three of four vertices",
IGRAPH_UNIMPLEMENTED);
}
IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
if (directed) {
if (size==3) {
classedges=igraph_i_classedges_3;
if (number < 0 ||
number >= sizeof(igraph_i_isographs_3)/sizeof(unsigned int)) {
IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
}
code=igraph_i_isographs_3[ (long int) number];
power=32;
} else {
classedges=igraph_i_classedges_4;
if (number < 0 ||
number >= sizeof(igraph_i_isographs_4)/sizeof(unsigned int)) {
IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
}
code=igraph_i_isographs_4[ (long int) number];
power=2048;
}
} else {
if (size==3) {
classedges=igraph_i_classedges_3u;
if (number < 0 ||
number >= sizeof(igraph_i_isographs_3u)/sizeof(unsigned int)) {
IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
}
code=igraph_i_isographs_3u[ (long int) number];
power=4;
} else {
classedges=igraph_i_classedges_4u;
if (number < 0 ||
number >= sizeof(igraph_i_isographs_4u)/sizeof(unsigned int)) {
IGRAPH_ERROR("`number' invalid, cannot create graph", IGRAPH_EINVAL);
}
code=igraph_i_isographs_4u[ (long int) number];
power=32;
}
}
pos=0;
while (code > 0) {
if (code >= power) {
IGRAPH_CHECK(igraph_vector_push_back(&edges, classedges[2*pos]));
IGRAPH_CHECK(igraph_vector_push_back(&edges, classedges[2*pos+1]));
code -= power;
}
power /= 2;
pos++;
}
IGRAPH_CHECK(igraph_create(graph, &edges, size, directed));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/* TODO: return matching */
/* TODO: does not work for unconnected graphs */
/**
* \function igraph_isomorphic_vf2
* \brief Decides whether two graphs are isomorphic.
*
* </para><para>
* This function is an implementation of the VF2 isomorphism algorithm,
* see P. Foggia, C. Sansone, M. Vento, An Improved algorithm for
* matching large graphs, Prof. of the 3rd IAPR-TC-15 International
* Workshop on Graph-based Representations, Italy, 2001.
*
* </para><para> In the future the general \ref igraph_isomorphic()
* function should be responsible for calling this function.
*
* </para><para> Note that this function cannot be used for subgraph
* deciding subgraph isomorphism.
* \param graph1 The first graph, it should be connected.
* \param graph2 The second graph, it should be connected and should
* have the same number of vertices and edges as \p graph1.
* \param iso Pointer to a logical constant, the result of the
* algorithm will be placed here.
* \return Error code.
*
* \sa \ref igraph_isomorphic().
*
* Time complexity: exponential, what did you expect?
*/
int igraph_isomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso) {
long int no_of_nodes=igraph_vcount(graph1);
igraph_vector_t core_1, core_2;
igraph_vector_t in_1, in_2, out_1, out_2;
long int in_1_size=0, in_2_size=0, out_1_size=0, out_2_size=0;
igraph_vector_t *inneis_1, *inneis_2, *outneis_1, *outneis_2;
long int matched_nodes=0;
long int depth;
long int cand1, cand2;
long int last1, last2;
igraph_stack_t path;
igraph_i_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;
IGRAPH_VECTOR_INIT_FINALLY(&core_1, no_of_nodes);
IGRAPH_VECTOR_INIT_FINALLY(&core_2, no_of_nodes);
IGRAPH_VECTOR_INIT_FINALLY(&in_1, no_of_nodes);
IGRAPH_VECTOR_INIT_FINALLY(&in_2, no_of_nodes);
IGRAPH_VECTOR_INIT_FINALLY(&out_1, no_of_nodes);
IGRAPH_VECTOR_INIT_FINALLY(&out_2, no_of_nodes);
IGRAPH_CHECK(igraph_stack_init(&path, 0));
IGRAPH_FINALLY(igraph_stack_destroy, &path);
IGRAPH_CHECK(igraph_i_lazy_adjlist_init(graph1, &inadj1, IGRAPH_IN,
IGRAPH_I_SIMPLIFY));
IGRAPH_FINALLY(igraph_i_lazy_adjlist_destroy, &inadj1);
IGRAPH_CHECK(igraph_i_lazy_adjlist_init(graph1, &outadj1, IGRAPH_OUT,
IGRAPH_I_SIMPLIFY));
IGRAPH_FINALLY(igraph_i_lazy_adjlist_destroy, &outadj1);
IGRAPH_CHECK(igraph_i_lazy_adjlist_init(graph2, &inadj2, IGRAPH_IN,
IGRAPH_I_SIMPLIFY));
IGRAPH_FINALLY(igraph_i_lazy_adjlist_destroy, &inadj2);
IGRAPH_CHECK(igraph_i_lazy_adjlist_init(graph2, &outadj2, IGRAPH_OUT,
IGRAPH_I_SIMPLIFY));
IGRAPH_FINALLY(igraph_i_lazy_adjlist_destroy, &outadj2);
IGRAPH_VECTOR_INIT_FINALLY(&indeg1, 0);
IGRAPH_VECTOR_INIT_FINALLY(&indeg2, 0);
IGRAPH_VECTOR_INIT_FINALLY(&outdeg1, 0);
IGRAPH_VECTOR_INIT_FINALLY(&outdeg2, 0);
IGRAPH_CHECK(igraph_stack_reserve(&path, no_of_nodes*2));
IGRAPH_CHECK(igraph_degree(graph1, &indeg1, igraph_vss_all(),
IGRAPH_IN, IGRAPH_LOOPS));
IGRAPH_CHECK(igraph_degree(graph2, &indeg2, igraph_vss_all(),
IGRAPH_IN, IGRAPH_LOOPS));
IGRAPH_CHECK(igraph_degree(graph1, &outdeg1, igraph_vss_all(),
IGRAPH_OUT, IGRAPH_LOOPS));
IGRAPH_CHECK(igraph_degree(graph2, &outdeg2, igraph_vss_all(),
IGRAPH_OUT, IGRAPH_LOOPS));
*iso=0;
depth=0; last1=-1; last2=-1;
while (matched_nodes != no_of_nodes && depth >= 0) {
long int i;
IGRAPH_ALLOW_INTERRUPTION();
cand1=-1; cand2=-1;
/* Search for the next pair to try */
if ((in_1_size != in_2_size) ||
(out_1_size != out_2_size)) {
/* step back, nothing to do */
} else if (out_1_size > 0 && out_2_size > 0) {
/**************************************************************/
/* cand2, search not always needed */
if (last2 >= 0) {
cand2=last2;
} else {
i=0;
while (cand2<0) {
if (VECTOR(out_2)[i]>0 && VECTOR(core_2)[i]==0) {
cand2=i;
}
i++;
}
}
/* search for cand1 now, it should be bigger than last1 */
i=last1+1;
while (cand1<0 && i<no_of_nodes) {
if (VECTOR(out_1)[i]>0 && VECTOR(core_1)[i]==0) {
cand1=i;
}
i++;
}
} else if (in_1_size > 0 && in_2_size > 0) {
/**************************************************************/
/* cand2, search not always needed */
if (last2 >= 0) {
cand2=last2;
} else {
i=0;
while (cand2<0) {
if (VECTOR(in_2)[i]>0 && VECTOR(core_2)[i]==0) {
cand2=i;
}
i++;
}
}
/* search for cand1 now, should be bigger than last1 */
i=last1+1;
while (cand1<0 && i<no_of_nodes) {
if (VECTOR(in_1)[i]>0 && VECTOR(core_1)[i]==0) {
cand1=i;
}
i++;
}
} else {
/**************************************************************/
/* cand2, search not always needed */
if (last2 >= 0) {
cand2=last2;
} else {
i=0;
while (cand2<0) {
if (VECTOR(core_2)[i]==0) {
cand2=i;
}
i++;
}
}
/* search for cand1, should be bigger than last1 */
i=last1+1;
while (cand1<0 && i<no_of_nodes) {
if (VECTOR(core_1)[i]==0) {
cand1=i;
}
i++;
}
}
/* Ok, we have cand1, cand2 as candidates. Or not? */
if (cand1<0 || cand2<0) {
/**************************************************************/
/* dead end, step back, if possible. Otherwise we'll terminate */
if (depth >= 1) {
last2=igraph_stack_pop(&path);
last1=igraph_stack_pop(&path);
matched_nodes -= 1;
VECTOR(core_1)[last1]=0;
VECTOR(core_2)[last2]=0;
if (VECTOR(in_1)[last1] != 0) {
in_1_size += 1;
}
if (VECTOR(out_1)[last1] != 0) {
out_1_size += 1;
}
if (VECTOR(in_2)[last2] != 0) {
in_2_size += 1;
}
if (VECTOR(out_2)[last2] != 0) {
out_2_size += 1;
}
inneis_1=igraph_i_lazy_adjlist_get(&inadj1, last1);
for (i=0; i<igraph_vector_size(inneis_1); i++) {
long int node=VECTOR(*inneis_1)[i];
if (VECTOR(in_1)[node] == depth) {
VECTOR(in_1)[node]=0;
in_1_size -= 1;
}
}
outneis_1=igraph_i_lazy_adjlist_get(&outadj1, last1);
for (i=0; i<igraph_vector_size(outneis_1); i++) {
long int node=VECTOR(*outneis_1)[i];
if (VECTOR(out_1)[node] == depth) {
VECTOR(out_1)[node]=0;
out_1_size -= 1;
}
}
inneis_2=igraph_i_lazy_adjlist_get(&inadj2, last2);
for (i=0; i<igraph_vector_size(inneis_2); i++) {
long int node=VECTOR(*inneis_2)[i];
if (VECTOR(in_2)[node] == depth) {
VECTOR(in_2)[node]=0;
in_2_size -= 1;
}
}
outneis_2=igraph_i_lazy_adjlist_get(&outadj2, last2);
for (i=0; i<igraph_vector_size(outneis_2); i++) {
long int node=VECTOR(*outneis_2)[i];
if (VECTOR(out_2)[node] == depth) {
VECTOR(out_2)[node]=0;
out_2_size -= 1;
}
}
} /* end of stepping back */
depth -= 1;
} else {
/**************************************************************/
/* step forward if worth, check if worth first */
long int xin1=0, xin2=0, xout1=0, xout2=0;
igraph_bool_t end=0;
inneis_1=igraph_i_lazy_adjlist_get(&inadj1, cand1);
outneis_1=igraph_i_lazy_adjlist_get(&outadj1, cand1);
inneis_2=igraph_i_lazy_adjlist_get(&inadj2, cand2);
outneis_2=igraph_i_lazy_adjlist_get(&outadj2, cand2);
if (VECTOR(indeg1)[cand1] != VECTOR(indeg2)[cand2] ||
VECTOR(outdeg1)[cand1] != VECTOR(outdeg2)[cand2]) {
end=1;
}
for (i=0; !end && i<igraph_vector_size(inneis_1); i++) {
long int node=VECTOR(*inneis_1)[i];
if (VECTOR(core_1)[node]!=0) {
long int node2=VECTOR(core_1)[node]-1;
/* check if there is a node2->cand2 edge */
if (!igraph_vector_binsearch2(inneis_2, node2)) {
end=1;
}
} else {
if (VECTOR(in_1)[node] != 0) {
xin1++;
}
if (VECTOR(out_1)[node] != 0) {
xout1++;
}
}
}
for (i=0; !end && i<igraph_vector_size(outneis_1); i++) {
long int node=VECTOR(*outneis_1)[i];
if (VECTOR(core_1)[node]!=0) {
long int node2=VECTOR(core_1)[node]-1;
/* check if there is a cand2->node2 edge */
if (!igraph_vector_binsearch2(outneis_2, node2)) {
end=1;
}
} else {
if (VECTOR(in_1)[node] != 0) {
xin1++;
}
if (VECTOR(out_1)[node] != 0) {
xout1++;
}
}
}
for (i=0; !end && i<igraph_vector_size(inneis_2); i++) {
long int node=VECTOR(*inneis_2)[i];
if (VECTOR(core_2)[node]!=0) {
long int node2=VECTOR(core_2)[node]-1;
/* check if there is a node2->cand1 edge */
if (!igraph_vector_binsearch2(inneis_1, node2)) {
end=1;
}
} else {
if (VECTOR(in_2)[node] != 0) {
xin2++;
}
if (VECTOR(out_2)[node] != 0) {
xout2++;
}
}
}
for (i=0; !end && i<igraph_vector_size(outneis_2); i++) {
long int node=VECTOR(*outneis_2)[i];
if (VECTOR(core_2)[node] != 0) {
long int node2=VECTOR(core_2)[node]-1;
/* check if there is a cand1->node2 edge */
if (!igraph_vector_binsearch2(outneis_1, node2)) {
end=1;
}
} else {
if (VECTOR(in_2)[node] != 0) {
xin2++;
}
if (VECTOR(out_2)[node] != 0) {
xout2++;
}
}
}
if (!end && (xin1==xin2 && xout1==xout2)) {
/* Ok, we add the (cand1, cand2) pair to the mapping */
depth += 1;
IGRAPH_CHECK(igraph_stack_push(&path, cand1));
IGRAPH_CHECK(igraph_stack_push(&path, cand2));
matched_nodes += 1;
VECTOR(core_1)[cand1]=cand2+1;
VECTOR(core_2)[cand2]=cand1+1;
/* update in_*, out_* */
if (VECTOR(in_1)[cand1] != 0) {
in_1_size -= 1;
}
if (VECTOR(out_1)[cand1] != 0) {
out_1_size -= 1;
}
if (VECTOR(in_2)[cand2] != 0) {
in_2_size -= 1;
}
if (VECTOR(out_2)[cand2] != 0) {
out_2_size -= 1;
}
inneis_1=igraph_i_lazy_adjlist_get(&inadj1, cand1);
for (i=0; i<igraph_vector_size(inneis_1); i++) {
long int node=VECTOR(*inneis_1)[i];
if (VECTOR(in_1)[node]==0 && VECTOR(core_1)[node]==0) {
VECTOR(in_1)[node]=depth;
in_1_size += 1;
}
}
outneis_1=igraph_i_lazy_adjlist_get(&outadj1, cand1);
for (i=0; i<igraph_vector_size(outneis_1); i++) {
long int node=VECTOR(*outneis_1)[i];
if (VECTOR(out_1)[node]==0 && VECTOR(core_1)[node]==0) {
VECTOR(out_1)[node]=depth;
out_1_size += 1;
}
}
inneis_2=igraph_i_lazy_adjlist_get(&inadj2, cand2);
for (i=0; i<igraph_vector_size(inneis_2); i++) {
long int node=VECTOR(*inneis_2)[i];
if (VECTOR(in_2)[node]==0 && VECTOR(core_2)[node]==0) {
VECTOR(in_2)[node]=depth;
in_2_size += 1;
}
}
outneis_2=igraph_i_lazy_adjlist_get(&outadj2, cand2);
for (i=0; i<igraph_vector_size(outneis_2); i++) {
long int node=VECTOR(*outneis_2)[i];
if (VECTOR(out_2)[node]==0 && VECTOR(core_2)[node]==0) {
VECTOR(out_2)[node]=depth;
out_2_size += 1;
}
}
last1=-1; last2=-1; /* this the first time here */
} else {
last1=cand1;
last2=cand2;
}
}
}
*iso=(matched_nodes==no_of_nodes);
igraph_vector_destroy(&outdeg2);
igraph_vector_destroy(&outdeg1);
igraph_vector_destroy(&indeg2);
igraph_vector_destroy(&indeg1);
igraph_i_lazy_adjlist_destroy(&outadj2);
igraph_i_lazy_adjlist_destroy(&inadj2);
igraph_i_lazy_adjlist_destroy(&outadj1);
igraph_i_lazy_adjlist_destroy(&inadj1);
igraph_stack_destroy(&path);
igraph_vector_destroy(&out_2);
igraph_vector_destroy(&out_1);
igraph_vector_destroy(&in_2);
igraph_vector_destroy(&in_1);
igraph_vector_destroy(&core_2);
igraph_vector_destroy(&core_1);
IGRAPH_FINALLY_CLEAN(15);
return 0;
}
syntax highlighted by Code2HTML, v. 0.9.1