CoCalc -- check_graphs_using

Path: Boolean-Cayley-graphs/sage-code / check_graphs_using_gap.py
Views: ⁸⁸⁰⁰
1

2
#*****************************************************************************
3
#       Copyright (C) 2016 Paul Leopardi [email protected]
4
#
5
#  Distributed under the terms of the GNU General Public License (GPL)
6
#  as published by the Free Software Foundation; either version 2 of
7
#  the License, or (at your option) any later version.
8
#                  http://www.gnu.org/licenses/
9
#*****************************************************************************
10

11
gap.load_package('grape')
12
gap.eval('GRAPE_NAUTY := true;')
13

14
def graphs_are_isomorphic(g_0, g_1):
15
    r"""
16
    Check that two graphs are isomorphic.
17
    """
18
    m_0 = g_0.adjacency_matrix()
19
    m_1 = g_1.adjacency_matrix()
20
    dim = str(m_0.dimensions()[0])
21
    gap.eval('M_0 := '+gap(m_0).str()+';')
22
    gap.eval('M_1 := '+gap(m_1).str()+';')
23
    gap.eval('GR := Group( () );')
24
    gap.eval('G_0 := Graph( GR, [1..' + dim +'], OnPoints, '
25
        + 'function(x,y) return M_0[x][y] = 1; end, true );')
26
    gap.eval('G_1 := Graph( GR, [1..' + dim + '], OnPoints, '
27
        + 'function(x,y) return M_1[x][y] = 1; end, true );')
28
    return gap.eval('IsIsomorphicGraph(G_0, G_1);') == 'true'
29

30

31
def check_graph_class_list(g_list):
32
    r"""
33
    Check that no two graphs in a list are isomorphic.
34
    """
35
    result = True
36
    n = len(g_list)
37
    for i in range(n):
38
        for j in range(i + 1, n):
39
            result &= not graphs_are_isomorphic(g_list[i], g_list[j])
40
    return result
41

42