haskell-igraph-0.8.0: igraph/src/topology.c
/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 USA
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_topology.h"
#include "igraph_memory.h"
#include "igraph_adjlist.h"
#include "igraph_interface.h"
#include "igraph_interrupt_internal.h"
#include "igraph_constructors.h"
#include "igraph_conversion.h"
#include "igraph_stack.h"
#include "igraph_attributes.h"
#include "igraph_structural.h"
#include "config.h"
const 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
};
const unsigned int igraph_i_isoclass_3_idx[] = { 0, 4, 16, 1, 0, 32, 2, 8, 0 };
const 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
};
const unsigned int igraph_i_isoclass_4_idx[] = {
0, 8, 64, 512, 1, 0, 128, 1024, 2, 16, 0, 2048, 4, 32, 256, 0
};
const unsigned int igraph_i_isoclass_3u[] = { 0, 1, 1, 3, 1, 3, 3, 7 };
const unsigned int igraph_i_isoclass_3u_idx[] = { 0, 1, 2, 1, 0, 4, 2, 4, 0 };
const 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
};
const unsigned int igraph_i_isoclass_4u_idx[] = {
0, 1, 2, 8, 1, 0, 4, 16, 2, 4, 0, 32, 8, 16, 32, 0
};
const 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
};
const unsigned int igraph_i_isoclass2_3u[] = {
0, 1, 1, 2, 1, 2, 2, 3
};
const 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
};
const 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
};
const unsigned int igraph_i_isographs_3[] = { 0, 1, 3, 5, 6, 7, 10, 11, 15, 21,
23, 25, 27, 30, 31, 63
};
const unsigned int igraph_i_isographs_3u[] = { 0, 1, 3, 7 };
const 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
};
const unsigned int igraph_i_isographs_4u[] = { 0, 1, 3, 7, 11, 12, 13,
15, 30, 31, 63
};
const unsigned int igraph_i_classedges_3[] = { 1, 2, 0, 2, 2, 1, 0, 1, 2, 0, 1, 0 };
const unsigned int igraph_i_classedges_3u[] = { 1, 2, 0, 2, 0, 1 };
const 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
};
const unsigned int igraph_i_classedges_4u[] = { 2, 3, 1, 3, 0, 3, 1, 2, 0, 2, 0, 1 };
/**
* \section about_graph_isomorphism
*
* <para>igraph provides four set of functions to deal with graph
* isomorphism problems.</para>
*
* <para>The \ref igraph_isomorphic() and \ref igraph_subisomorphic()
* functions make up the first set (in addition with the \ref
* igraph_permute_vertices() function). These functions choose the
* algorithm which is best for the supplied input graph. (The choice is
* not very sophisticated though, see their documentation for
* details.)</para>
*
* <para>The VF2 graph (and subgraph) isomorphism algorithm is implemented in
* igraph, these functions are the second set. See \ref
* igraph_isomorphic_vf2() and \ref igraph_subisomorphic_vf2() for
* starters.</para>
*
* <para>Functions for the BLISS algorithm constitute the third set,
* see \ref igraph_isomorphic_bliss().</para>
*
* <para>Finally, the isomorphism classes of all graphs with three and
* four vertices are precomputed and stored in igraph, so for these
* small graphs there is a very simple fast way to decide isomorphism.
* See \ref igraph_isomorphic_34().
* </para>
*/
/**
* \function igraph_isoclass
* \brief Determine the isomorphism class of a graph with 3 or 4 vertices
*
* </para><para>
* All graphs with a given number of vertices belong to a number of
* isomorphism 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, igraph_integer_t *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;
const 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, (igraph_integer_t) e, &from, &to);
idx = (unsigned char) (mul * from + to);
code |= arr_idx[idx];
}
*isoclass = (igraph_integer_t) 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.</para>
*
* <para>This function decides which graph isomorphism algorithm to be
* used based on the input graphs. Right now it does the following:
* \olist
* \oli If one graph is directed and the other undirected then an
* error is triggered.
* \oli If the two graphs does not have the same number of vertices
* and edges it returns with \c FALSE.
* \oli Otherwise, if the graphs have three or four vertices then an O(1)
* algorithm is used with precomputed data.
* \oli Otherwise BLISS is used, see \ref igraph_isomorphic_bliss().
* \endolist
* </para>
*
* <para> Please call the VF2 and BLISS functions directly if you need
* something more sophisticated, e.g. you need the isomorphic mapping.
*
* \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: exponential.
*/
int igraph_isomorphic(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso) {
long int nodes1 = igraph_vcount(graph1), nodes2 = igraph_vcount(graph2);
long int edges1 = igraph_ecount(graph1), edges2 = igraph_ecount(graph2);
igraph_bool_t dir1 = igraph_is_directed(graph1), dir2 = igraph_is_directed(graph2);
igraph_bool_t loop1, loop2;
if (dir1 != dir2) {
IGRAPH_ERROR("Cannot compare directed and undirected graphs", IGRAPH_EINVAL);
} else if (nodes1 != nodes2 || edges1 != edges2) {
*iso = 0;
} else if (nodes1 == 3 || nodes1 == 4) {
IGRAPH_CHECK(igraph_has_loop(graph1, &loop1));
IGRAPH_CHECK(igraph_has_loop(graph2, &loop2));
if (!loop1 && !loop2) {
IGRAPH_CHECK(igraph_isomorphic_34(graph1, graph2, iso));
} else {
IGRAPH_CHECK(igraph_isomorphic_bliss(graph1, graph2, NULL, NULL, iso,
0, 0, /*sh=*/ IGRAPH_BLISS_F, 0, 0));
}
} else {
IGRAPH_CHECK(igraph_isomorphic_bliss(graph1, graph2, NULL, NULL, iso,
0, 0, /*sh=*/ IGRAPH_BLISS_F, 0, 0));
}
return 0;
}
/**
* \function igraph_isomorphic_34
* Graph isomorphism for 3-4 vertices
*
* This function uses precomputed indices to decide isomorphism
* problems for graphs with only 3 or 4 vertices.
* \param graph1 The first input graph.
* \param graph2 The second input graph. Must have the same
* directedness as \p graph1.
* \param iso Pointer to a boolean, the result is stored here.
* \return Error code.
*
* Time complexity: O(1).
*/
int igraph_isomorphic_34(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso) {
igraph_integer_t class1, class2;
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,
igraph_integer_t *isoclass) {
int nodes = (int) igraph_vector_size(vids);
igraph_bool_t directed = igraph_is_directed(graph);
igraph_vector_t neis;
unsigned char mul, idx;
const 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 = (long int) VECTOR(*vids)[i];
igraph_neighbors(graph, &neis, (igraph_integer_t) from, IGRAPH_OUT);
s = igraph_vector_size(&neis);
for (j = 0; j < s; j++) {
long int nei = (long int) VECTOR(neis)[j], to;
if (igraph_vector_search(vids, 0, nei, &to)) {
idx = (unsigned char) (mul * i + to);
code |= arr_idx[idx];
}
}
}
*isoclass = (igraph_integer_t) 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;
const 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 >= (int)(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 >= (int)(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 >= (int)(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 >= (int)(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;
}
/**
* \section about_vf2
*
* <para>
* The VF2 algorithm can search for a subgraph in a larger graph, or check if two
* graphs are isomorphic. See P. Foggia, C. Sansone, M. Vento, An Improved algorithm for
* matching large graphs, Proc. of the 3rd IAPR-TC-15 International
* Workshop on Graph-based Representations, Italy, 2001.
* </para>
*
* <para>
* VF2 supports both vertex and edge-colored graphs, as well as custom vertex or edge
* compatibility functions.
* </para>
*
* <para>
* VF2 works with both directed and undirected graphs. Only simple graphs are supported.
* Self-loops or multi-edges must not be present in the graphs. Currently, the VF2
* functions do not check that the input graph is simple: it is the responsibility
* of the user to pass in valid input.
* </para>
*/
/**
* \function igraph_isomorphic_function_vf2
* The generic VF2 interface
*
* </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, Proc. of the 3rd IAPR-TC-15 International
* Workshop on Graph-based Representations, Italy, 2001.</para>
*
* <para>For using it you need to define a callback function of type
* \ref igraph_isohandler_t. This function will be called whenever VF2
* finds an isomorphism between the two graphs. The mapping between
* the two graphs will be also provided to this function. If the
* callback returns a nonzero value then the search is continued,
* otherwise it stops. The callback function must not destroy the
* mapping vectors that are passed to it.
* \param graph1 The first input graph.
* \param graph2 The second input graph.
* \param vertex_color1 An optional color vector for the first graph. If
* color vectors are given for both graphs, then the isomorphism is
* calculated on the colored graphs; i.e. two vertices can match
* only if their color also matches. Supply a null pointer here if
* your graphs are not colored.
* \param vertex_color2 An optional color vector for the second graph. See
* the previous argument for explanation.
* \param edge_color1 An optional edge color vector for the first
* graph. The matching edges in the two graphs must have matching
* colors as well. Supply a null pointer here if your graphs are not
* edge-colored.
* \param edge_color2 The edge color vector for the second graph.
* \param map12 Pointer to an initialized vector or \c NULL. If not \c
* NULL and the supplied graphs are isomorphic then the permutation
* taking \p graph1 to \p graph is stored here. If not \c NULL and the
* graphs are not isomorphic then a zero-length vector is returned.
* \param map21 This is the same as \p map12, but for the permutation
* taking \p graph2 to \p graph1.
* \param isohandler_fn The callback function to be called if an
* isomorphism is found. See also \ref igraph_isohandler_t.
* \param node_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two nodes are compatible.
* \param edge_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two edges are compatible.
* \param arg Extra argument to supply to functions \p isohandler_fn, \p
* node_compat_fn and \p edge_compat_fn.
* \return Error code.
*
* Time complexity: exponential.
*/
int 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) {
long int no_of_nodes = igraph_vcount(graph1);
long int no_of_edges = igraph_ecount(graph1);
igraph_vector_t mycore_1, mycore_2, *core_1 = &mycore_1, *core_2 = &mycore_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_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;
if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
IGRAPH_ERROR("Cannot compare directed and undirected graphs",
IGRAPH_EINVAL);
}
if ( (vertex_color1 && !vertex_color2) || (!vertex_color1 && vertex_color2) ) {
IGRAPH_WARNING("Only one graph is vertex-colored, vertex colors will be ignored");
vertex_color1 = vertex_color2 = 0;
}
if ( (edge_color1 && !edge_color2) || (!edge_color1 && edge_color2)) {
IGRAPH_WARNING("Only one graph is edge-colored, edge colors will be ignored");
edge_color1 = edge_color2 = 0;
}
if (no_of_nodes != igraph_vcount(graph2) ||
no_of_edges != igraph_ecount(graph2)) {
return 0;
}
if (vertex_color1) {
if (igraph_vector_int_size(vertex_color1) != no_of_nodes ||
igraph_vector_int_size(vertex_color2) != no_of_nodes) {
IGRAPH_ERROR("Invalid vertex color vector length", IGRAPH_EINVAL);
}
}
if (edge_color1) {
if (igraph_vector_int_size(edge_color1) != no_of_edges ||
igraph_vector_int_size(edge_color2) != no_of_edges) {
IGRAPH_ERROR("Invalid edge color vector length", IGRAPH_EINVAL);
}
}
/* Check color distribution */
if (vertex_color1) {
int ret = 0;
igraph_vector_int_t tmp1, tmp2;
IGRAPH_CHECK(igraph_vector_int_copy(&tmp1, vertex_color1));
IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp1);
IGRAPH_CHECK(igraph_vector_int_copy(&tmp2, vertex_color2));
IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp2);
igraph_vector_int_sort(&tmp1);
igraph_vector_int_sort(&tmp2);
ret = !igraph_vector_int_all_e(&tmp1, &tmp2);
igraph_vector_int_destroy(&tmp1);
igraph_vector_int_destroy(&tmp2);
IGRAPH_FINALLY_CLEAN(2);
if (ret) {
return 0;
}
}
/* Check edge color distribution */
if (edge_color1) {
int ret = 0;
igraph_vector_int_t tmp1, tmp2;
IGRAPH_CHECK(igraph_vector_int_copy(&tmp1, edge_color1));
IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp1);
IGRAPH_CHECK(igraph_vector_int_copy(&tmp2, edge_color2));
IGRAPH_FINALLY(igraph_vector_int_destroy, &tmp2);
igraph_vector_int_sort(&tmp1);
igraph_vector_int_sort(&tmp2);
ret = !igraph_vector_int_all_e(&tmp1, &tmp2);
igraph_vector_int_destroy(&tmp1);
igraph_vector_int_destroy(&tmp2);
IGRAPH_FINALLY_CLEAN(2);
if (ret) {
return 0;
}
}
if (map12) {
core_1 = map12;
IGRAPH_CHECK(igraph_vector_resize(core_1, no_of_nodes));
} else {
IGRAPH_VECTOR_INIT_FINALLY(core_1, no_of_nodes);
}
igraph_vector_fill(core_1, -1);
if (map21) {
core_2 = map21;
IGRAPH_CHECK(igraph_vector_resize(core_2, no_of_nodes));
igraph_vector_null(core_2);
} else {
IGRAPH_VECTOR_INIT_FINALLY(core_2, no_of_nodes);
}
igraph_vector_fill(core_2, -1);
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_lazy_adjlist_init(graph1, &inadj1, IGRAPH_IN,
IGRAPH_SIMPLIFY));
IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj1);
IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &outadj1, IGRAPH_OUT,
IGRAPH_SIMPLIFY));
IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj1);
IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &inadj2, IGRAPH_IN,
IGRAPH_SIMPLIFY));
IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj2);
IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &outadj2, IGRAPH_OUT,
IGRAPH_SIMPLIFY));
IGRAPH_FINALLY(igraph_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));
depth = 0; last1 = -1; last2 = -1;
while (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 && i < no_of_nodes) {
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 && i < no_of_nodes) {
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 && i < no_of_nodes) {
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 = (long int) igraph_stack_pop(&path);
last1 = (long int) igraph_stack_pop(&path);
matched_nodes -= 1;
VECTOR(*core_1)[last1] = -1;
VECTOR(*core_2)[last2] = -1;
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_lazy_adjlist_get(&inadj1, (igraph_integer_t) last1);
for (i = 0; i < igraph_vector_size(inneis_1); i++) {
long int node = (long int) VECTOR(*inneis_1)[i];
if (VECTOR(in_1)[node] == depth) {
VECTOR(in_1)[node] = 0;
in_1_size -= 1;
}
}
outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) last1);
for (i = 0; i < igraph_vector_size(outneis_1); i++) {
long int node = (long int) VECTOR(*outneis_1)[i];
if (VECTOR(out_1)[node] == depth) {
VECTOR(out_1)[node] = 0;
out_1_size -= 1;
}
}
inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) last2);
for (i = 0; i < igraph_vector_size(inneis_2); i++) {
long int node = (long int) VECTOR(*inneis_2)[i];
if (VECTOR(in_2)[node] == depth) {
VECTOR(in_2)[node] = 0;
in_2_size -= 1;
}
}
outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) last2);
for (i = 0; i < igraph_vector_size(outneis_2); i++) {
long int node = (long int) 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_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
if (VECTOR(indeg1)[cand1] != VECTOR(indeg2)[cand2] ||
VECTOR(outdeg1)[cand1] != VECTOR(outdeg2)[cand2]) {
end = 1;
}
if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
end = 1;
}
if (node_compat_fn && !node_compat_fn(graph1, graph2,
(igraph_integer_t) cand1,
(igraph_integer_t) cand2, arg)) {
end = 1;
}
for (i = 0; !end && i < igraph_vector_size(inneis_1); i++) {
long int node = (long int) VECTOR(*inneis_1)[i];
if (VECTOR(*core_1)[node] >= 0) {
long int node2 = (long int) VECTOR(*core_1)[node];
/* check if there is a node2->cand2 edge */
if (!igraph_vector_binsearch2(inneis_2, node2)) {
end = 1;
} else if (edge_color1 || edge_compat_fn) {
igraph_integer_t eid1, eid2;
igraph_get_eid(graph1, &eid1, (igraph_integer_t) node,
(igraph_integer_t) cand1, /*directed=*/ 1,
/*error=*/ 1);
igraph_get_eid(graph2, &eid2, (igraph_integer_t) node2,
(igraph_integer_t) cand2, /*directed=*/ 1,
/*error=*/ 1);
if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
VECTOR(*edge_color2)[(long int)eid2]) {
end = 1;
}
if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
eid1, eid2, arg)) {
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 = (long int) VECTOR(*outneis_1)[i];
if (VECTOR(*core_1)[node] >= 0) {
long int node2 = (long int) VECTOR(*core_1)[node];
/* check if there is a cand2->node2 edge */
if (!igraph_vector_binsearch2(outneis_2, node2)) {
end = 1;
} else if (edge_color1 || edge_compat_fn) {
igraph_integer_t eid1, eid2;
igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1,
(igraph_integer_t) node, /*directed=*/ 1,
/*error=*/ 1);
igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2,
(igraph_integer_t) node2, /*directed=*/ 1,
/*error=*/ 1);
if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
VECTOR(*edge_color2)[(long int)eid2]) {
end = 1;
}
if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
eid1, eid2, arg)) {
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 = (long int) VECTOR(*inneis_2)[i];
if (VECTOR(*core_2)[node] >= 0) {
long int node2 = (long int) VECTOR(*core_2)[node];
/* check if there is a node2->cand1 edge */
if (!igraph_vector_binsearch2(inneis_1, node2)) {
end = 1;
} else if (edge_color1 || edge_compat_fn) {
igraph_integer_t eid1, eid2;
igraph_get_eid(graph1, &eid1, (igraph_integer_t) node2,
(igraph_integer_t) cand1, /*directed=*/ 1,
/*error=*/ 1);
igraph_get_eid(graph2, &eid2, (igraph_integer_t) node,
(igraph_integer_t) cand2, /*directed=*/ 1,
/*error=*/ 1);
if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
VECTOR(*edge_color2)[(long int)eid2]) {
end = 1;
}
if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
eid1, eid2, arg)) {
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 = (long int) VECTOR(*outneis_2)[i];
if (VECTOR(*core_2)[node] >= 0) {
long int node2 = (long int) VECTOR(*core_2)[node];
/* check if there is a cand1->node2 edge */
if (!igraph_vector_binsearch2(outneis_1, node2)) {
end = 1;
} else if (edge_color1 || edge_compat_fn) {
igraph_integer_t eid1, eid2;
igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1,
(igraph_integer_t) node2, /*directed=*/ 1,
/*error=*/ 1);
igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2,
(igraph_integer_t) node, /*directed=*/ 1,
/*error=*/ 1);
if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
VECTOR(*edge_color2)[(long int)eid2]) {
end = 1;
}
if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
eid1, eid2, arg)) {
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;
VECTOR(*core_2)[cand2] = cand1;
/* 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_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
for (i = 0; i < igraph_vector_size(inneis_1); i++) {
long int node = (long int) 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_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
for (i = 0; i < igraph_vector_size(outneis_1); i++) {
long int node = (long int) 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_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
for (i = 0; i < igraph_vector_size(inneis_2); i++) {
long int node = (long int) 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_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
for (i = 0; i < igraph_vector_size(outneis_2); i++) {
long int node = (long int) 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;
}
}
if (matched_nodes == no_of_nodes && isohandler_fn) {
if (!isohandler_fn(core_1, core_2, arg)) {
break;
}
}
}
igraph_vector_destroy(&outdeg2);
igraph_vector_destroy(&outdeg1);
igraph_vector_destroy(&indeg2);
igraph_vector_destroy(&indeg1);
igraph_lazy_adjlist_destroy(&outadj2);
igraph_lazy_adjlist_destroy(&inadj2);
igraph_lazy_adjlist_destroy(&outadj1);
igraph_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_FINALLY_CLEAN(13);
if (!map21) {
igraph_vector_destroy(core_2);
IGRAPH_FINALLY_CLEAN(1);
}
if (!map12) {
igraph_vector_destroy(core_1);
IGRAPH_FINALLY_CLEAN(1);
}
return 0;
}
typedef struct {
igraph_isocompat_t *node_compat_fn, *edge_compat_fn;
void *arg, *carg;
} igraph_i_iso_cb_data_t;
igraph_bool_t 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) {
igraph_i_iso_cb_data_t *data = arg;
return data->node_compat_fn(graph1, graph2, g1_num, g2_num, data->carg);
}
igraph_bool_t 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) {
igraph_i_iso_cb_data_t *data = arg;
return data->edge_compat_fn(graph1, graph2, g1_num, g2_num, data->carg);
}
igraph_bool_t igraph_i_isomorphic_vf2(igraph_vector_t *map12,
igraph_vector_t *map21,
void *arg) {
igraph_i_iso_cb_data_t *data = arg;
igraph_bool_t *iso = data->arg;
IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
*iso = 1;
return 0; /* don't need to continue */
}
/**
* \function igraph_isomorphic_vf2
* \brief Isomorphism via VF2
*
* </para><para>
* This function performs the VF2 algorithm via calling \ref
* igraph_isomorphic_function_vf2().
*
* </para><para> Note that this function cannot be used for
* deciding subgraph isomorphism, use \ref igraph_subisomorphic_vf2()
* for that.
* \param graph1 The first graph, may be directed or undirected.
* \param graph2 The second graph. It must have the same directedness
* as \p graph1, otherwise an error is reported.
* \param vertex_color1 An optional color vector for the first graph. If
* color vectors are given for both graphs, then the isomorphism is
* calculated on the colored graphs; i.e. two vertices can match
* only if their color also matches. Supply a null pointer here if
* your graphs are not colored.
* \param vertex_color2 An optional color vector for the second graph. See
* the previous argument for explanation.
* \param edge_color1 An optional edge color vector for the first
* graph. The matching edges in the two graphs must have matching
* colors as well. Supply a null pointer here if your graphs are not
* edge-colored.
* \param edge_color2 The edge color vector for the second graph.
* \param iso Pointer to a logical constant, the result of the
* algorithm will be placed here.
* \param map12 Pointer to an initialized vector or a NULL pointer. If not
* a NULL pointer then the mapping from \p graph1 to \p graph2 is
* stored here. If the graphs are not isomorphic then the vector is
* cleared (ie. has zero elements).
* \param map21 Pointer to an initialized vector or a NULL pointer. If not
* a NULL pointer then the mapping from \p graph2 to \p graph1 is
* stored here. If the graphs are not isomorphic then the vector is
* cleared (ie. has zero elements).
* \param node_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two nodes are compatible.
* \param edge_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two edges are compatible.
* \param arg Extra argument to supply to functions \p node_compat_fn
* and \p edge_compat_fn.
* \return Error code.
*
* \sa \ref igraph_subisomorphic_vf2(),
* \ref igraph_count_isomorphisms_vf2(),
* \ref igraph_get_isomorphisms_vf2(),
*
* Time complexity: exponential, what did you expect?
*
* \example examples/simple/igraph_isomorphic_vf2.c
*/
int 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) {
igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, iso, arg };
igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
*iso = 0;
IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2,
vertex_color1, vertex_color2,
edge_color1, edge_color2,
map12, map21,
(igraph_isohandler_t*)
igraph_i_isomorphic_vf2,
ncb, ecb, &data));
if (! *iso) {
if (map12) {
igraph_vector_clear(map12);
}
if (map21) {
igraph_vector_clear(map21);
}
}
return 0;
}
igraph_bool_t igraph_i_count_isomorphisms_vf2(const igraph_vector_t *map12,
const igraph_vector_t *map21,
void *arg) {
igraph_i_iso_cb_data_t *data = arg;
igraph_integer_t *count = data->arg;
IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
*count += 1;
return 1; /* always continue */
}
/**
* \function igraph_count_isomorphisms_vf2
* Number of isomorphisms via VF2
*
* This function counts the number of isomorphic mappings between two
* graphs. It uses the generic \ref igraph_isomorphic_function_vf2()
* function.
* \param graph1 The first input graph, may be directed or undirected.
* \param graph2 The second input graph, it must have the same
* directedness as \p graph1, or an error will be reported.
* \param vertex_color1 An optional color vector for the first graph. If
* color vectors are given for both graphs, then the isomorphism is
* calculated on the colored graphs; i.e. two vertices can match
* only if their color also matches. Supply a null pointer here if
* your graphs are not colored.
* \param vertex_color2 An optional color vector for the second graph. See
* the previous argument for explanation.
* \param edge_color1 An optional edge color vector for the first
* graph. The matching edges in the two graphs must have matching
* colors as well. Supply a null pointer here if your graphs are not
* edge-colored.
* \param edge_color2 The edge color vector for the second graph.
* \param count Point to an integer, the result will be stored here.
* \param node_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two nodes are compatible.
* \param edge_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two edges are compatible.
* \param arg Extra argument to supply to functions \p node_compat_fn and
* \p edge_compat_fn.
* \return Error code.
*
* Time complexity: exponential.
*/
int 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) {
igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn,
count, arg
};
igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
*count = 0;
IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2,
vertex_color1, vertex_color2,
edge_color1, edge_color2,
0, 0,
(igraph_isohandler_t*)
igraph_i_count_isomorphisms_vf2,
ncb, ecb, &data));
return 0;
}
void igraph_i_get_isomorphisms_free(igraph_vector_ptr_t *data) {
long int i, n = igraph_vector_ptr_size(data);
for (i = 0; i < n; i++) {
igraph_vector_t *vec = VECTOR(*data)[i];
igraph_vector_destroy(vec);
igraph_free(vec);
}
}
igraph_bool_t igraph_i_get_isomorphisms_vf2(const igraph_vector_t *map12,
const igraph_vector_t *map21,
void *arg) {
igraph_i_iso_cb_data_t *data = arg;
igraph_vector_ptr_t *ptrvector = data->arg;
igraph_vector_t *newvector = igraph_Calloc(1, igraph_vector_t);
IGRAPH_UNUSED(map12);
if (!newvector) {
igraph_error("Out of memory", __FILE__, __LINE__, IGRAPH_ENOMEM);
return 0; /* stop right here */
}
IGRAPH_FINALLY(igraph_free, newvector);
IGRAPH_CHECK(igraph_vector_copy(newvector, map21));
IGRAPH_FINALLY(igraph_vector_destroy, newvector);
IGRAPH_CHECK(igraph_vector_ptr_push_back(ptrvector, newvector));
IGRAPH_FINALLY_CLEAN(2);
return 1; /* continue finding subisomorphisms */
}
/**
* \function igraph_get_isomorphisms_vf2
* Collect the isomorphic mappings
*
* This function finds all the isomorphic mappings between two
* graphs. It uses the \ref igraph_isomorphic_function_vf2()
* function. Call the function with the same graph as \p graph1 and \p
* graph2 to get automorphisms.
* \param graph1 The first input graph, may be directed or undirected.
* \param graph2 The second input graph, it must have the same
* directedness as \p graph1, or an error will be reported.
* \param vertex_color1 An optional color vector for the first graph. If
* color vectors are given for both graphs, then the isomorphism is
* calculated on the colored graphs; i.e. two vertices can match
* only if their color also matches. Supply a null pointer here if
* your graphs are not colored.
* \param vertex_color2 An optional color vector for the second graph. See
* the previous argument for explanation.
* \param edge_color1 An optional edge color vector for the first
* graph. The matching edges in the two graphs must have matching
* colors as well. Supply a null pointer here if your graphs are not
* edge-colored.
* \param edge_color2 The edge color vector for the second graph.
* \param maps Pointer vector. On return it is empty if the input graphs
* are no isomorphic. Otherwise it contains pointers to
* <type>igraph_vector_t</type> objects, each vector is an
* isomorphic mapping of \p graph2 to \p graph1. Please note that
* you need to 1) Destroy the vectors via \ref
* igraph_vector_destroy(), 2) free them via
* <function>free()</function> and then 3) call \ref
* igraph_vector_ptr_destroy() on the pointer vector to deallocate all
* memory when \p maps is no longer needed.
* \param node_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two nodes are compatible.
* \param edge_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two edges are compatible.
* \param arg Extra argument to supply to functions \p node_compat_fn
* and \p edge_compat_fn.
* \return Error code.
*
* Time complexity: exponential.
*/
int 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) {
igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, maps, arg };
igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
igraph_vector_ptr_clear(maps);
IGRAPH_FINALLY(igraph_i_get_isomorphisms_free, maps);
IGRAPH_CHECK(igraph_isomorphic_function_vf2(graph1, graph2,
vertex_color1, vertex_color2,
edge_color1, edge_color2,
0, 0,
(igraph_isohandler_t*)
igraph_i_get_isomorphisms_vf2,
ncb, ecb, &data));
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \function igraph_subisomorphic
* Decide subgraph isomorphism
*
* Check whether \p graph2 is isomorphic to a subgraph of \p graph1.
* Currently this function just calls \ref igraph_subisomorphic_vf2()
* for all graphs.
* \param graph1 The first input graph, may be directed or
* undirected. This is supposed to be the bigger graph.
* \param graph2 The second input graph, it must have the same
* directedness as \p graph2, or an error is triggered. This is
* supposed to be the smaller graph.
* \param iso Pointer to a boolean, the result is stored here.
* \return Error code.
*
* Time complexity: exponential.
*/
int igraph_subisomorphic(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso) {
return igraph_subisomorphic_vf2(graph1, graph2, 0, 0, 0, 0, iso, 0, 0, 0, 0, 0);
}
/**
* \function igraph_subisomorphic_function_vf2
* Generic VF2 function for subgraph isomorphism problems
*
* This function is the pair of \ref igraph_isomorphic_function_vf2(),
* for subgraph isomorphism problems. It searches for subgraphs of \p
* graph1 which are isomorphic to \p graph2. When it founds an
* isomorphic mapping it calls the supplied callback \p isohandler_fn.
* The mapping (and its inverse) and the additional \p arg argument
* are supplied to the callback.
* \param graph1 The first input graph, may be directed or
* undirected. This is supposed to be the larger graph.
* \param graph2 The second input graph, it must have the same
* directedness as \p graph1. This is supposed to be the smaller
* graph.
* \param vertex_color1 An optional color vector for the first graph. If
* color vectors are given for both graphs, then the subgraph isomorphism is
* calculated on the colored graphs; i.e. two vertices can match
* only if their color also matches. Supply a null pointer here if
* your graphs are not colored.
* \param vertex_color2 An optional color vector for the second graph. See
* the previous argument for explanation.
* \param edge_color1 An optional edge color vector for the first
* graph. The matching edges in the two graphs must have matching
* colors as well. Supply a null pointer here if your graphs are not
* edge-colored.
* \param edge_color2 The edge color vector for the second graph.
* \param map12 Pointer to a vector or \c NULL. If not \c NULL, then an
* isomorphic mapping from \p graph1 to \p graph2 is stored here.
* \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
* an isomorphic mapping from \p graph2 to \p graph1 is stored
* here.
* \param isohandler_fn A pointer to a function of type \ref
* igraph_isohandler_t. This will be called whenever a subgraph
* isomorphism is found. If the function returns with a non-zero value
* then the search is continued, otherwise it stops and the function
* returns.
* \param node_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two nodes are compatible.
* \param edge_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two edges are compatible.
* \param arg Extra argument to supply to functions \p isohandler_fn, \p
* node_compat_fn and \p edge_compat_fn.
* \return Error code.
*
* Time complexity: exponential.
*/
int 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) {
long int no_of_nodes1 = igraph_vcount(graph1),
no_of_nodes2 = igraph_vcount(graph2);
long int no_of_edges1 = igraph_ecount(graph1),
no_of_edges2 = igraph_ecount(graph2);
igraph_vector_t mycore_1, mycore_2, *core_1 = &mycore_1, *core_2 = &mycore_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_lazy_adjlist_t inadj1, inadj2, outadj1, outadj2;
igraph_vector_t indeg1, indeg2, outdeg1, outdeg2;
if (igraph_is_directed(graph1) != igraph_is_directed(graph2)) {
IGRAPH_ERROR("Cannot compare directed and undirected graphs",
IGRAPH_EINVAL);
}
if (no_of_nodes1 < no_of_nodes2 ||
no_of_edges1 < no_of_edges2) {
return 0;
}
if ( (vertex_color1 && !vertex_color2) || (!vertex_color1 && vertex_color2) ) {
IGRAPH_WARNING("Only one graph is vertex colored, colors will be ignored");
vertex_color1 = vertex_color2 = 0;
}
if ( (edge_color1 && !edge_color2) || (!edge_color1 && edge_color2) ) {
IGRAPH_WARNING("Only one graph is edge colored, colors will be ignored");
edge_color1 = edge_color2 = 0;
}
if (vertex_color1) {
if (igraph_vector_int_size(vertex_color1) != no_of_nodes1 ||
igraph_vector_int_size(vertex_color2) != no_of_nodes2) {
IGRAPH_ERROR("Invalid vertex color vector length", IGRAPH_EINVAL);
}
}
if (edge_color1) {
if (igraph_vector_int_size(edge_color1) != no_of_edges1 ||
igraph_vector_int_size(edge_color2) != no_of_edges2) {
IGRAPH_ERROR("Invalid edge color vector length", IGRAPH_EINVAL);
}
}
/* Check color distribution */
if (vertex_color1) {
/* TODO */
}
/* Check edge color distribution */
if (edge_color1) {
/* TODO */
}
if (map12) {
core_1 = map12;
IGRAPH_CHECK(igraph_vector_resize(core_1, no_of_nodes1));
} else {
IGRAPH_VECTOR_INIT_FINALLY(core_1, no_of_nodes1);
}
igraph_vector_fill(core_1, -1);
if (map21) {
core_2 = map21;
IGRAPH_CHECK(igraph_vector_resize(core_2, no_of_nodes2));
} else {
IGRAPH_VECTOR_INIT_FINALLY(core_2, no_of_nodes2);
}
igraph_vector_fill(core_2, -1);
IGRAPH_VECTOR_INIT_FINALLY(&in_1, no_of_nodes1);
IGRAPH_VECTOR_INIT_FINALLY(&in_2, no_of_nodes2);
IGRAPH_VECTOR_INIT_FINALLY(&out_1, no_of_nodes1);
IGRAPH_VECTOR_INIT_FINALLY(&out_2, no_of_nodes2);
IGRAPH_CHECK(igraph_stack_init(&path, 0));
IGRAPH_FINALLY(igraph_stack_destroy, &path);
IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &inadj1, IGRAPH_IN,
IGRAPH_SIMPLIFY));
IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj1);
IGRAPH_CHECK(igraph_lazy_adjlist_init(graph1, &outadj1, IGRAPH_OUT,
IGRAPH_SIMPLIFY));
IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &outadj1);
IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &inadj2, IGRAPH_IN,
IGRAPH_SIMPLIFY));
IGRAPH_FINALLY(igraph_lazy_adjlist_destroy, &inadj2);
IGRAPH_CHECK(igraph_lazy_adjlist_init(graph2, &outadj2, IGRAPH_OUT,
IGRAPH_SIMPLIFY));
IGRAPH_FINALLY(igraph_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_nodes2 * 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));
depth = 0; last1 = -1; last2 = -1;
while (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 && i < no_of_nodes2) {
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_nodes1) {
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 && i < no_of_nodes2) {
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_nodes1) {
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 && i < no_of_nodes2) {
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_nodes1) {
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 = (long int) igraph_stack_pop(&path);
last1 = (long int) igraph_stack_pop(&path);
matched_nodes -= 1;
VECTOR(*core_1)[last1] = -1;
VECTOR(*core_2)[last2] = -1;
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_lazy_adjlist_get(&inadj1, (igraph_integer_t) last1);
for (i = 0; i < igraph_vector_size(inneis_1); i++) {
long int node = (long int) VECTOR(*inneis_1)[i];
if (VECTOR(in_1)[node] == depth) {
VECTOR(in_1)[node] = 0;
in_1_size -= 1;
}
}
outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) last1);
for (i = 0; i < igraph_vector_size(outneis_1); i++) {
long int node = (long int) VECTOR(*outneis_1)[i];
if (VECTOR(out_1)[node] == depth) {
VECTOR(out_1)[node] = 0;
out_1_size -= 1;
}
}
inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) last2);
for (i = 0; i < igraph_vector_size(inneis_2); i++) {
long int node = (long int) VECTOR(*inneis_2)[i];
if (VECTOR(in_2)[node] == depth) {
VECTOR(in_2)[node] = 0;
in_2_size -= 1;
}
}
outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) last2);
for (i = 0; i < igraph_vector_size(outneis_2); i++) {
long int node = (long int) 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_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
outneis_1 = igraph_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
inneis_2 = igraph_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
outneis_2 = igraph_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
if (VECTOR(indeg1)[cand1] < VECTOR(indeg2)[cand2] ||
VECTOR(outdeg1)[cand1] < VECTOR(outdeg2)[cand2]) {
end = 1;
}
if (vertex_color1 && VECTOR(*vertex_color1)[cand1] != VECTOR(*vertex_color2)[cand2]) {
end = 1;
}
if (node_compat_fn && !node_compat_fn(graph1, graph2,
(igraph_integer_t) cand1,
(igraph_integer_t) cand2, arg)) {
end = 1;
}
for (i = 0; !end && i < igraph_vector_size(inneis_1); i++) {
long int node = (long int) VECTOR(*inneis_1)[i];
if (VECTOR(*core_1)[node] < 0) {
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 = (long int) VECTOR(*outneis_1)[i];
if (VECTOR(*core_1)[node] < 0) {
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 = (long int) VECTOR(*inneis_2)[i];
if (VECTOR(*core_2)[node] >= 0) {
long int node2 = (long int) VECTOR(*core_2)[node];
/* check if there is a node2->cand1 edge */
if (!igraph_vector_binsearch2(inneis_1, node2)) {
end = 1;
} else if (edge_color1 || edge_compat_fn) {
igraph_integer_t eid1, eid2;
igraph_get_eid(graph1, &eid1, (igraph_integer_t) node2,
(igraph_integer_t) cand1, /*directed=*/ 1,
/*error=*/ 1);
igraph_get_eid(graph2, &eid2, (igraph_integer_t) node,
(igraph_integer_t) cand2, /*directed=*/ 1,
/*error=*/ 1);
if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
VECTOR(*edge_color2)[(long int)eid2]) {
end = 1;
}
if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
eid1, eid2, arg)) {
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 = (long int) VECTOR(*outneis_2)[i];
if (VECTOR(*core_2)[node] >= 0) {
long int node2 = (long int) VECTOR(*core_2)[node];
/* check if there is a cand1->node2 edge */
if (!igraph_vector_binsearch2(outneis_1, node2)) {
end = 1;
} else if (edge_color1 || edge_compat_fn) {
igraph_integer_t eid1, eid2;
igraph_get_eid(graph1, &eid1, (igraph_integer_t) cand1,
(igraph_integer_t) node2, /*directed=*/ 1,
/*error=*/ 1);
igraph_get_eid(graph2, &eid2, (igraph_integer_t) cand2,
(igraph_integer_t) node, /*directed=*/ 1,
/*error=*/ 1);
if (edge_color1 && VECTOR(*edge_color1)[(long int)eid1] !=
VECTOR(*edge_color2)[(long int)eid2]) {
end = 1;
}
if (edge_compat_fn && !edge_compat_fn(graph1, graph2,
eid1, eid2, arg)) {
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;
VECTOR(*core_2)[cand2] = cand1;
/* 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_lazy_adjlist_get(&inadj1, (igraph_integer_t) cand1);
for (i = 0; i < igraph_vector_size(inneis_1); i++) {
long int node = (long int) 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_lazy_adjlist_get(&outadj1, (igraph_integer_t) cand1);
for (i = 0; i < igraph_vector_size(outneis_1); i++) {
long int node = (long int) 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_lazy_adjlist_get(&inadj2, (igraph_integer_t) cand2);
for (i = 0; i < igraph_vector_size(inneis_2); i++) {
long int node = (long int) 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_lazy_adjlist_get(&outadj2, (igraph_integer_t) cand2);
for (i = 0; i < igraph_vector_size(outneis_2); i++) {
long int node = (long int) 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;
}
}
if (matched_nodes == no_of_nodes2 && isohandler_fn) {
if (!isohandler_fn(core_1, core_2, arg)) {
break;
}
}
}
igraph_vector_destroy(&outdeg2);
igraph_vector_destroy(&outdeg1);
igraph_vector_destroy(&indeg2);
igraph_vector_destroy(&indeg1);
igraph_lazy_adjlist_destroy(&outadj2);
igraph_lazy_adjlist_destroy(&inadj2);
igraph_lazy_adjlist_destroy(&outadj1);
igraph_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_FINALLY_CLEAN(13);
if (!map21) {
igraph_vector_destroy(core_2);
IGRAPH_FINALLY_CLEAN(1);
}
if (!map12) {
igraph_vector_destroy(core_1);
IGRAPH_FINALLY_CLEAN(1);
}
return 0;
}
igraph_bool_t igraph_i_subisomorphic_vf2(const igraph_vector_t *map12,
const igraph_vector_t *map21,
void *arg) {
igraph_i_iso_cb_data_t *data = arg;
igraph_bool_t *iso = data->arg;
IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
*iso = 1;
return 0; /* stop */
}
/**
* \function igraph_subisomorphic_vf2
* Decide subgraph isomorphism using VF2
*
* Decides whether a subgraph of \p graph1 is isomorphic to \p
* graph2. It uses \ref igraph_subisomorphic_function_vf2().
* \param graph1 The first input graph, may be directed or
* undirected. This is supposed to be the larger graph.
* \param graph2 The second input graph, it must have the same
* directedness as \p graph1. This is supposed to be the smaller
* graph.
* \param vertex_color1 An optional color vector for the first graph. If
* color vectors are given for both graphs, then the subgraph isomorphism is
* calculated on the colored graphs; i.e. two vertices can match
* only if their color also matches. Supply a null pointer here if
* your graphs are not colored.
* \param vertex_color2 An optional color vector for the second graph. See
* the previous argument for explanation.
* \param edge_color1 An optional edge color vector for the first
* graph. The matching edges in the two graphs must have matching
* colors as well. Supply a null pointer here if your graphs are not
* edge-colored.
* \param edge_color2 The edge color vector for the second graph.
* \param iso Pointer to a boolean. The result of the decision problem
* is stored here.
* \param map12 Pointer to a vector or \c NULL. If not \c NULL, then an
* isomorphic mapping from \p graph1 to \p graph2 is stored here.
* \param map21 Pointer to a vector ot \c NULL. If not \c NULL, then
* an isomorphic mapping from \p graph2 to \p graph1 is stored
* here.
* \param node_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two nodes are compatible.
* \param edge_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two edges are compatible.
* \param arg Extra argument to supply to functions \p node_compat_fn
* and \p edge_compat_fn.
* \return Error code.
*
* Time complexity: exponential.
*/
int 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) {
igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, iso, arg };
igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
*iso = 0;
IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2,
vertex_color1, vertex_color2,
edge_color1, edge_color2,
map12, map21,
(igraph_isohandler_t *)
igraph_i_subisomorphic_vf2,
ncb, ecb, &data));
if (! *iso) {
if (map12) {
igraph_vector_clear(map12);
}
if (map21) {
igraph_vector_clear(map21);
}
}
return 0;
}
igraph_bool_t igraph_i_count_subisomorphisms_vf2(const igraph_vector_t *map12,
const igraph_vector_t *map21,
void *arg) {
igraph_i_iso_cb_data_t *data = arg;
igraph_integer_t *count = data->arg;
IGRAPH_UNUSED(map12); IGRAPH_UNUSED(map21);
*count += 1;
return 1; /* always continue */
}
/**
* \function igraph_count_subisomorphisms_vf2
* Number of subgraph isomorphisms using VF2
*
* Count the number of isomorphisms between subgraphs of \p graph1 and
* \p graph2. This function uses \ref
* igraph_subisomorphic_function_vf2().
* \param graph1 The first input graph, may be directed or
* undirected. This is supposed to be the larger graph.
* \param graph2 The second input graph, it must have the same
* directedness as \p graph1. This is supposed to be the smaller
* graph.
* \param vertex_color1 An optional color vector for the first graph. If
* color vectors are given for both graphs, then the subgraph isomorphism is
* calculated on the colored graphs; i.e. two vertices can match
* only if their color also matches. Supply a null pointer here if
* your graphs are not colored.
* \param vertex_color2 An optional color vector for the second graph. See
* the previous argument for explanation.
* \param edge_color1 An optional edge color vector for the first
* graph. The matching edges in the two graphs must have matching
* colors as well. Supply a null pointer here if your graphs are not
* edge-colored.
* \param edge_color2 The edge color vector for the second graph.
* \param count Pointer to an integer. The number of subgraph
* isomorphisms is stored here.
* \param node_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two nodes are compatible.
* \param edge_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two edges are compatible.
* \param arg Extra argument to supply to functions \p node_compat_fn and
* \p edge_compat_fn.
* \return Error code.
*
* Time complexity: exponential.
*/
int 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) {
igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn,
count, arg
};
igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
*count = 0;
IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2,
vertex_color1, vertex_color2,
edge_color1, edge_color2,
0, 0,
(igraph_isohandler_t*)
igraph_i_count_subisomorphisms_vf2,
ncb, ecb, &data));
return 0;
}
void igraph_i_get_subisomorphisms_free(igraph_vector_ptr_t *data) {
long int i, n = igraph_vector_ptr_size(data);
for (i = 0; i < n; i++) {
igraph_vector_t *vec = VECTOR(*data)[i];
igraph_vector_destroy(vec);
igraph_free(vec);
}
}
igraph_bool_t igraph_i_get_subisomorphisms_vf2(const igraph_vector_t *map12,
const igraph_vector_t *map21,
void *arg) {
igraph_i_iso_cb_data_t *data = arg;
igraph_vector_ptr_t *vector = data->arg;
igraph_vector_t *newvector = igraph_Calloc(1, igraph_vector_t);
IGRAPH_UNUSED(map12);
if (!newvector) {
igraph_error("Out of memory", __FILE__, __LINE__, IGRAPH_ENOMEM);
return 0; /* stop right here */
}
IGRAPH_FINALLY(igraph_free, newvector);
IGRAPH_CHECK(igraph_vector_copy(newvector, map21));
IGRAPH_FINALLY(igraph_vector_destroy, newvector);
IGRAPH_CHECK(igraph_vector_ptr_push_back(vector, newvector));
IGRAPH_FINALLY_CLEAN(2);
return 1; /* continue finding subisomorphisms */
}
/**
* \function igraph_get_subisomorphisms_vf2
* Return all subgraph isomorphic mappings
*
* This function collects all isomorphic mappings of \p graph2 to a
* subgraph of \p graph1. It uses the \ref
* igraph_subisomorphic_function_vf2() function.
* \param graph1 The first input graph, may be directed or
* undirected. This is supposed to be the larger graph.
* \param graph2 The second input graph, it must have the same
* directedness as \p graph1. This is supposed to be the smaller
* graph.
* \param vertex_color1 An optional color vector for the first graph. If
* color vectors are given for both graphs, then the subgraph isomorphism is
* calculated on the colored graphs; i.e. two vertices can match
* only if their color also matches. Supply a null pointer here if
* your graphs are not colored.
* \param vertex_color2 An optional color vector for the second graph. See
* the previous argument for explanation.
* \param edge_color1 An optional edge color vector for the first
* graph. The matching edges in the two graphs must have matching
* colors as well. Supply a null pointer here if your graphs are not
* edge-colored.
* \param edge_color2 The edge color vector for the second graph.
* \param maps Pointer vector. On return it contains pointers to
* <type>igraph_vector_t</type> objects, each vector is an
* isomorphic mapping of \p graph2 to a subgraph of \p graph1. Please note that
* you need to 1) Destroy the vectors via \ref
* igraph_vector_destroy(), 2) free them via
* <function>free()</function> and then 3) call \ref
* igraph_vector_ptr_destroy() on the pointer vector to deallocate all
* memory when \p maps is no longer needed.
* \param node_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two nodes are compatible.
* \param edge_compat_fn A pointer to a function of type \ref
* igraph_isocompat_t. This function will be called by the algorithm to
* determine whether two edges are compatible.
* \param arg Extra argument to supply to functions \p node_compat_fn
* and \p edge_compat_fn.
* \return Error code.
*
* Time complexity: exponential.
*/
int 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) {
igraph_i_iso_cb_data_t data = { node_compat_fn, edge_compat_fn, maps, arg };
igraph_isocompat_t *ncb = node_compat_fn ? igraph_i_isocompat_node_cb : 0;
igraph_isocompat_t *ecb = edge_compat_fn ? igraph_i_isocompat_edge_cb : 0;
igraph_vector_ptr_clear(maps);
IGRAPH_FINALLY(igraph_i_get_subisomorphisms_free, maps);
IGRAPH_CHECK(igraph_subisomorphic_function_vf2(graph1, graph2,
vertex_color1, vertex_color2,
edge_color1, edge_color2,
0, 0,
(igraph_isohandler_t*)
igraph_i_get_subisomorphisms_vf2,
ncb, ecb, &data));
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \function igraph_permute_vertices
* Permute the vertices
*
* This function creates a new graph from the input graph by permuting
* its vertices according to the specified mapping. Call this function
* with the output of \ref igraph_canonical_permutation() to create
* the canonical form of a graph.
* \param graph The input graph.
* \param res Pointer to an uninitialized graph object. The new graph
* is created here.
* \param permutation The permutation to apply. Vertex 0 is mapped to
* the first element of the vector, vertex 1 to the second,
* etc. Note that it is not checked that the vector contains every
* element only once, and no range checking is performed either.
* \return Error code.
*
* Time complexity: O(|V|+|E|), linear in terms of the number of
* vertices and edges.
*/
int igraph_permute_vertices(const igraph_t *graph, igraph_t *res,
const igraph_vector_t *permutation) {
long int no_of_nodes = igraph_vcount(graph);
long int no_of_edges = igraph_ecount(graph);
igraph_vector_t edges;
long int i, p = 0;
if (igraph_vector_size(permutation) != no_of_nodes) {
IGRAPH_ERROR("Permute vertices: invalid permutation vector size", IGRAPH_EINVAL);
}
IGRAPH_VECTOR_INIT_FINALLY(&edges, no_of_edges * 2);
for (i = 0; i < no_of_edges; i++) {
VECTOR(edges)[p++] = VECTOR(*permutation)[ (long int) IGRAPH_FROM(graph, i) ];
VECTOR(edges)[p++] = VECTOR(*permutation)[ (long int) IGRAPH_TO(graph, i) ];
}
IGRAPH_CHECK(igraph_create(res, &edges, (igraph_integer_t) no_of_nodes,
igraph_is_directed(graph)));
/* Attributes */
if (graph->attr) {
igraph_vector_t index;
igraph_vector_t vtypes;
IGRAPH_I_ATTRIBUTE_DESTROY(res);
IGRAPH_I_ATTRIBUTE_COPY(res, graph, /*graph=*/1, /*vertex=*/0, /*edge=*/1);
IGRAPH_VECTOR_INIT_FINALLY(&vtypes, 0);
IGRAPH_CHECK(igraph_i_attribute_get_info(graph, 0, 0, 0, &vtypes, 0, 0));
if (igraph_vector_size(&vtypes) != 0) {
IGRAPH_VECTOR_INIT_FINALLY(&index, no_of_nodes);
for (i = 0; i < no_of_nodes; i++) {
VECTOR(index)[ (long int) VECTOR(*permutation)[i] ] = i;
}
IGRAPH_CHECK(igraph_i_attribute_permute_vertices(graph, res, &index));
igraph_vector_destroy(&index);
IGRAPH_FINALLY_CLEAN(1);
}
igraph_vector_destroy(&vtypes);
IGRAPH_FINALLY_CLEAN(1);
}
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return 0;
}
/**
* \section about_bliss
*
* <para>
* BLISS is a successor of the famous NAUTY algorithm and
* implementation. While using the same ideas in general, with better
* heuristics and data structures BLISS outperforms NAUTY on most
* graphs.
* </para>
*
* <para>
* BLISS was developed and implemented by Tommi Junttila and Petteri Kaski at
* Helsinki University of Technology, Finland. For more information,
* see the BLISS homepage at http://www.tcs.hut.fi/Software/bliss/ and the publication
* Tommi Junttila, Petteri Kaski: "Engineering an Efficient Canonical Labeling
* Tool for Large and Sparse Graphs" at https://doi.org/10.1137/1.9781611972870.13
* </para>
*
* <para>
* BLISS works with both directed graphs and undirected graphs. It supports graphs with
* self-loops, but not graphs with multi-edges.
* </para>
*
* <para>
* BLISS version 0.73 is included in igraph.
* </para>
*/
/**
* \function igraph_isomorphic_bliss
* Graph isomorphism via BLISS
*
* This function uses the BLISS graph isomorphism algorithm, a
* successor of the famous NAUTY algorithm and implementation. BLISS
* is open source and licensed according to the GNU GPL. See
* http://www.tcs.hut.fi/Software/bliss/index.html for
* details. Currently the 0.73 version of BLISS is included in igraph.
*
* </para><para>
*
* \param graph1 The first input graph. Multiple edges between the same nodes
* are not supported and will cause an incorrect result to be returned.
* \param graph2 The second input graph. Multiple edges between the same nodes
* are not supported and will cause an incorrect result to be returned.
* \param colors1 An optional vertex color vector for the first graph. Supply a
* null pointer if your graph is not colored.
* \param colors2 An optional vertex color vector for the second graph. Supply a
* null pointer if your graph is not colored.
* \param iso Pointer to a boolean, the result is stored here.
* \param map12 A vector or \c NULL pointer. If not \c NULL then an
* isomorphic mapping from \p graph1 to \p graph2 is stored here.
* If the input graphs are not isomorphic then this vector is
* cleared, i.e. it will have length zero.
* \param map21 Similar to \p map12, but for the mapping from \p
* graph2 to \p graph1.
* \param sh Splitting heuristics to be used for the graphs. See
* \ref igraph_bliss_sh_t.
* \param info1 If not \c NULL, information about the canonization of
* the first input graph is stored here. See \ref igraph_bliss_info_t
* for details. Note that if the two graphs have different number
* of vertices or edges, then this is not filled.
* \param info2 Same as \p info1, but for the second graph.
* \return Error code.
*
* Time complexity: exponential, but in practice it is quite fast.
*/
int 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) {
long int no_of_nodes = igraph_vcount(graph1);
long int no_of_edges = igraph_ecount(graph1);
igraph_vector_t perm1, perm2;
igraph_vector_t vmap12, *mymap12 = &vmap12;
igraph_vector_t from, to, index;
igraph_vector_t from2, to2, index2;
igraph_bool_t directed;
long int i, j;
*iso = 0;
if (info1) {
info1->nof_nodes = info1->nof_leaf_nodes = info1->nof_bad_nodes =
info1->nof_canupdates = info1->max_level = info1->nof_generators = -1;
info1->group_size = 0;
}
if (info2) {
info2->nof_nodes = info2->nof_leaf_nodes = info2->nof_bad_nodes =
info2->nof_canupdates = info2->max_level = info2->nof_generators = -1;
info2->group_size = 0;
}
directed = igraph_is_directed(graph1);
if (igraph_is_directed(graph2) != directed) {
IGRAPH_ERROR("Cannot compare directed and undirected graphs",
IGRAPH_EINVAL);
}
if ((colors1 == NULL || colors2 == NULL) && colors1 != colors2) {
IGRAPH_WARNING("Only one of the graphs is vertex colored, colors will be ignored");
colors1 = NULL; colors2 = NULL;
}
if (no_of_nodes != igraph_vcount(graph2) ||
no_of_edges != igraph_ecount(graph2)) {
if (map12) {
igraph_vector_clear(map12);
}
if (map21) {
igraph_vector_clear(map21);
}
return 0;
}
if (map12) {
mymap12 = map12;
} else {
IGRAPH_VECTOR_INIT_FINALLY(mymap12, 0);
}
IGRAPH_VECTOR_INIT_FINALLY(&perm1, no_of_nodes);
IGRAPH_VECTOR_INIT_FINALLY(&perm2, no_of_nodes);
IGRAPH_CHECK(igraph_canonical_permutation(graph1, colors1, &perm1, sh, info1));
IGRAPH_CHECK(igraph_canonical_permutation(graph2, colors2, &perm2, sh, info2));
IGRAPH_CHECK(igraph_vector_resize(mymap12, no_of_nodes));
/* The inverse of perm2 is produced in mymap12 */
for (i = 0; i < no_of_nodes; i++) {
VECTOR(*mymap12)[ (long int)VECTOR(perm2)[i] ] = i;
}
/* Now we produce perm2^{-1} o perm1 in perm2 */
for (i = 0; i < no_of_nodes; i++) {
VECTOR(perm2)[i] = VECTOR(*mymap12)[ (long int) VECTOR(perm1)[i] ];
}
/* Copy it to mymap12 */
igraph_vector_update(mymap12, &perm2);
igraph_vector_destroy(&perm1);
igraph_vector_destroy(&perm2);
IGRAPH_FINALLY_CLEAN(2);
/* Check isomorphism, we apply the permutation in mymap12 to graph1
and should get graph2 */
IGRAPH_VECTOR_INIT_FINALLY(&from, no_of_edges);
IGRAPH_VECTOR_INIT_FINALLY(&to, no_of_edges);
IGRAPH_VECTOR_INIT_FINALLY(&index, no_of_edges);
IGRAPH_VECTOR_INIT_FINALLY(&from2, no_of_edges * 2);
IGRAPH_VECTOR_INIT_FINALLY(&to2, no_of_edges);
IGRAPH_VECTOR_INIT_FINALLY(&index2, no_of_edges);
for (i = 0; i < no_of_edges; i++) {
VECTOR(from)[i] = VECTOR(*mymap12)[ (long int) IGRAPH_FROM(graph1, i) ];
VECTOR(to)[i] = VECTOR(*mymap12)[ (long int) IGRAPH_TO (graph1, i) ];
if (! directed && VECTOR(from)[i] < VECTOR(to)[i]) {
igraph_real_t tmp = VECTOR(from)[i];
VECTOR(from)[i] = VECTOR(to)[i];
VECTOR(to)[i] = tmp;
}
}
igraph_vector_order(&from, &to, &index, no_of_nodes);
igraph_get_edgelist(graph2, &from2, /*bycol=*/ 1);
for (i = 0, j = no_of_edges; i < no_of_edges; i++, j++) {
VECTOR(to2)[i] = VECTOR(from2)[j];
if (! directed && VECTOR(from2)[i] < VECTOR(to2)[i]) {
igraph_real_t tmp = VECTOR(from2)[i];
VECTOR(from2)[i] = VECTOR(to2)[i];
VECTOR(to2)[i] = tmp;
}
}
igraph_vector_resize(&from2, no_of_edges);
igraph_vector_order(&from2, &to2, &index2, no_of_nodes);
*iso = 1;
for (i = 0; i < no_of_edges; i++) {
long int i1 = (long int) VECTOR(index)[i];
long int i2 = (long int) VECTOR(index2)[i];
if (VECTOR(from)[i1] != VECTOR(from2)[i2] ||
VECTOR(to)[i1] != VECTOR(to2)[i2]) {
*iso = 0;
break;
}
}
/* If the graphs are coloured, we also need to check that applying the
permutation mymap12 to colors1 gives colors2. */
if (*iso && colors1 != NULL) {
for (i = 0; i < no_of_nodes; i++) {
if (VECTOR(*colors1)[i] != VECTOR(*colors2)[(long int) VECTOR(*mymap12)[i] ]) {
*iso = 0;
break;
}
}
}
igraph_vector_destroy(&index2);
igraph_vector_destroy(&to2);
igraph_vector_destroy(&from2);
igraph_vector_destroy(&index);
igraph_vector_destroy(&to);
igraph_vector_destroy(&from);
IGRAPH_FINALLY_CLEAN(6);
if (*iso) {
/* The inverse of mymap12 */
if (map21) {
IGRAPH_CHECK(igraph_vector_resize(map21, no_of_nodes));
for (i = 0; i < no_of_nodes; i++) {
VECTOR(*map21)[ (long int) VECTOR(*mymap12)[i] ] = i;
}
}
} else {
if (map12) {
igraph_vector_clear(map12);
}
if (map21) {
igraph_vector_clear(map21);
}
}
if (!map12) {
igraph_vector_destroy(mymap12);
IGRAPH_FINALLY_CLEAN(1);
}
return 0;
}
/**
* \function igraph_simplify_and_colorize
* \brief Simplify the graph and compute self-loop and edge multiplicities.
*
* </para><para>
* This function creates a vertex and edge colored simple graph from the input
* graph. The vertex colors are computed as the number of incident self-loops
* to each vertex in the input graph. The edge colors are computed as the number of
* parallel edges in the input graph that were merged to create each edge
* in the simple graph.
*
* </para><para>
* The resulting colored simple graph is suitable for use by isomorphism checking
* algorithms such as VF2, which only support simple graphs, but can consider
* vertex and edge colors.
*
* \param graph The graph object, typically having self-loops or multi-edges.
* \param res An uninitialized graph object. The result will be stored here
* \param vertex_color Computed vertex colors corresponding to self-loop multiplicities.
* \param edge_color Computed edge colors corresponding to edge multiplicities
* \return Error code.
*
* \sa \ref igraph_simplify(), \ref igraph_isomorphic_vf2(), \ref igraph_subisomorphic_vf2()
*
*/
int igraph_simplify_and_colorize(
const igraph_t *graph, igraph_t *res,
igraph_vector_int_t *vertex_color, igraph_vector_int_t *edge_color) {
igraph_es_t es;
igraph_eit_t eit;
igraph_vector_t edges;
long int no_of_nodes = igraph_vcount(graph);
long int no_of_edges = igraph_ecount(graph);
long int pto = -1, pfrom = -1;
long int i;
IGRAPH_CHECK(igraph_es_all(&es, IGRAPH_EDGEORDER_FROM));
IGRAPH_FINALLY(igraph_es_destroy, &es);
IGRAPH_CHECK(igraph_eit_create(graph, es, &eit));
IGRAPH_FINALLY(igraph_eit_destroy, &eit);
IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges * 2));
IGRAPH_CHECK(igraph_vector_int_resize(vertex_color, no_of_nodes));
igraph_vector_int_null(vertex_color);
IGRAPH_CHECK(igraph_vector_int_resize(edge_color, no_of_edges));
igraph_vector_int_null(edge_color);
i = -1;
for (; !IGRAPH_EIT_END(eit); IGRAPH_EIT_NEXT(eit)) {
long int edge = IGRAPH_EIT_GET(eit);
long int from = IGRAPH_FROM(graph, edge);
long int to = IGRAPH_TO(graph, edge);
if (to == from) {
VECTOR(*vertex_color)[to]++;
continue;
}
if (to == pto && from == pfrom) {
VECTOR(*edge_color)[i]++;
} else {
igraph_vector_push_back(&edges, from);
igraph_vector_push_back(&edges, to);
i++;
VECTOR(*edge_color)[i] = 1;
}
pfrom = from; pto = to;
}
igraph_vector_int_resize(edge_color, i + 1);
igraph_eit_destroy(&eit);
igraph_es_destroy(&es);
IGRAPH_FINALLY_CLEAN(2);
IGRAPH_CHECK(igraph_create(res, &edges, no_of_nodes, igraph_is_directed(graph)));
igraph_vector_destroy(&edges);
IGRAPH_FINALLY_CLEAN(1);
return IGRAPH_SUCCESS;
}