Making the bliss canonical form available for edge labelled graphs

[stumpc5]

This is a discussion ticket for improving the bliss canonical form input, based on https://groups.google.com/d/topic/sage-support/oZ7Uu5jTR9k/discussion.

Christian's aim: make the canonical form of a graph given by an integer matrix much faster.

This basic idea is to provide an alternative version of sage.graphs.bliss.canonical_form using a list of labelled edges as input rather than a graph. Maybe

def canonical_form_list(Vnr, edges, partition)

where we assume that (i,j,color) in edges has the property 0 <= i,j < Vnr and colors 0 <= color < k where the color 0 means "uncolored" and is assumed to be the most common color.

Since this is an internal speed-critial functionality, Christian believes that it would then be the user's responsibility to turn any input format of graph, if needed, into this format.

As Dima pointed out, we can turn this edge labelled graph into an unlabelled graph with O(Vnr log k) vertices as described in Sect 14 in http://pallini.di.uniroma1.it/Guide.html.

For now, this is only for discussion design and code snippets.

Depends on #20382

CC: @simon-king-jena @dimpase @dimpase @Etn40ff

Component: graph theory

Keywords: bliss, graph automorphism, canonical form

Author: Christian Stump

Branch/Commit: 0830efc

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/24924

[stumpc5]

Branch: u/stumpc5/making_the_bliss_canonical_form_available_for_edge_labelled_graphs

[stumpc5]

comment:4

I have provided a first almost trivial version, I will send some timings later -- comparing the hash I posted on sage-support with its new counterpart using this new bliss canonical form (yielding the very same hash without ever constructing a sage DiGraph) gives immediately

sage: M = matrix([(0, -1, 0, 0, 0, 0, 0, 1),
....:  (1, 0, 1, 0, 0, 0, 0, 0),
....:  (0, -1, 0, 0, 1, 0, 0, 0),
....:  (0, 0, 0, 0, 0, 1, 0, 0),
....:  (0, 0, -1, 0, 0, 0, 1, 0),
....:  (0, 0, 0, -1, 0, 0, -1, 0),
....:  (0, 0, 0, 0, -1, 1, 0, 0),
....:  (-2, 0, 0, 0, 0, 0, 0, 0),
....:  (-1, 1, 0, 0, 0, 0, 0, 0),
....:  (0, 1, 0, 0, 0, 0, 0, -1),
....:  (0, 1, 0, 1, 0, -1, 0, -1),
....:  (0, 2, -1, 1, 0, -1, 0, -1),
....:  (0, 2, -1, 0, 0, -1, 0, -1),
....:  (0, 2, 0, 0, -1, -1, 0, -1),
....:  (0, 2, 0, 0, -1, 0, -1, -1),
....:  (0, 2, 0, 0, 0, 0, -2, -1)]
....: )
sage: %timeit matrix_canonical_hash(M,8,8)
1000 loops, best of 3: 177 µs per loop
sage: %timeit matrix_canonical_hash_cython(M)
10000 loops, best of 3: 20.3 µs per loop

---

New commits:

ff80980

first version of bliss canonical form from edge list

[stumpc5]

Commit: ff80980

[simon-king-jena]

comment:5

So far it looks good. But if I understand correctly, your actual aim is to get a canonical from associated with a matrix. Hence, you shouldn't need canonical_form_from_edge_list. I guess you want to create the bliss graph directly from the matrix (also using .get_unsafe() for element access), so that you don't need to create an edge list as an intermediate result of the bliss graph creation.

[stumpc5]

comment:6

I have also the following:

cpdef matrix_to_edge_list(Matrix M):
    cdef Py_ssize_t i, j
    cdef int a,b, x

    cdef list edges = list()
    cdef dict edge_labels = dict()
    cdef list new_partition = list()

    cdef bint pos

    cdef int n = M._ncols
    cdef int m = M._nrows - n

    cdef int Vnew = n+m

    for i from 0 <= i < n+m:
        for j from 0 <= j < n:
            a = M.get_unsafe(i,j)
            if i < n:
                b = M.get_unsafe(j,i)
            else:
                b = -a

            if a > 0:
                if a == 1 and b == -1:
                    edges.append((i,j))
                else:
                    try:
                        x = edge_labels[(a,b)]
                    except KeyError:
                        x = len(new_partition)
                        edge_labels[(a,b)] = x
                        new_partition.append([])
                    finally:
                        edges.append((i,Vnew))
                        edges.append((Vnew,j))
                        new_partition[x].append(Vnew)
                        Vnew += 1
            elif i >= n:
                if a == -1 and b == 1:
                    edges.append((j,i))
                else:
                    a = -a
                    b = -b
                    try:
                        x = edge_labels[(a,b)]
                    except KeyError:
                        x = len(new_partition)
                        edge_labels[(a,b)] = x
                        new_partition.append([])
                    finally:
                        edges.append((j,Vnew))
                        edges.append((Vnew,i))
                        new_partition[x].append(Vnew)
                        Vnew += 1

    partition = [list(range(n))]
    if m > 0:
        partition.append(list(range(n,n+m)))
    if new_partition:
        partition.extend(new_partition)

    return Vnew, edges, partition

But since it is not far from that, I now plan to implement what Dima pointed out from Sect 14 in ​http://pallini.di.uniroma1.it/Guide.html.

My impression is that, given that I need to know the number of vertices of the graph a priori, I need to first read the complete matrix before I can start creating the bliss Digraph.

[simon-king-jena]

comment:7

Replying to @stumpc5:

My impression is that, given that I need to know the number of vertices of the graph a priori, I need to first read the complete matrix before I can start creating the bliss Digraph.

Hm. That would be unfortunate. In that case, I suppose it will be impossible to avoid the creation of an intermediate edge list --- but you could create it by means of two int* (i.e., a C list for start points and a C list for end points). That might be a more efficient intermediate data structure than a python list of pairs.

[stumpc5]

comment:8

Independent of the matrix version, I think it would be overall nice to have

• the version I provided for a list of unlabelled edges (I think I should add a flag whether its directed or undirected), and

• a version for labelled edges, that are first turned into an equivalent version for undirected edges and then passed to the first

[stumpc5]

comment:9

In that case, I suppose it will be impossible to avoid the creation of an intermediate edge list

what I could actually do is to overestimate the number of vertices in the first place (given the matrix is size nxm, there are at most nm/2 edges, so even if all had the different labellings, I could go with log(mn/2)+max(n,m) many vertices, which is for m,n <= 20 still very small) and then possibly have chosen a few ununsed vertices floating around...

[stumpc5]

comment:10

Could I ask you to provide a pxd file for the headers so that I can cimport the bliss Digraph? I don't know how to do that correctly (I guess the pxd file looks like matrix0.pxd though...).

[stumpc5]

comment:11

That might be a more efficient intermediate data structure than a python list of pairs.

I first have to do some cython timings (which I haven't done before) to see where the bottleneck is -- maybe the list construction is not actually that time consuming, I don't know

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7ea99bd

first version of bliss graph from labelled edges

[sagetrac-git]

Changed commit from ff80980 to 7ea99bd

[sagetrac-git]

Changed commit from 7ea99bd to 3f07264

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3f07264

fixed typo, added labelled edge return and fixed bug in relabelling

[stumpc5]

comment:14

I pushed a first hopefully working version of the edge labelled bliss graph as described in Dima's reference.

Example:

sage: from sage.graphs.bliss import canonical_form_from_edge_list
sage: Vout = [0,0,1,2,2,3,3]; Vin = [0,1,2,0,3,0,2]; labels = [2,0,2,1,1,1,0]
sage: canonical_form_from_edge_list(4,Vout,Vin,3,labels, directed=False, certificate=True)

sage: Vout = [0,0,1,1]; Vin = [1,2,0,2]; labels = [0,1,0,1]
sage: canonical_form_from_edge_list(3,Vout,Vin,2,labels, directed=False, certificate=True)

• Could you please have a look and see if it works as desired
• Please in particular check that the vertex coloring scheme is correct

Once that is settled, I would also need help in improving (speeding) the code as much as easily possible, I already use three lists Vout, Vin, and labels which probably could be turned into c arrays instead...

---

New commits:

3f07264

fixed typo, added labelled edge return and fixed bug in relabelling

[sagetrac-git]

Changed commit from 3f07264 to 4661b86

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4661b86

playing the labelled graphs for now

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

74506c4

slighly avoiding some code duplication

[sagetrac-git]

Changed commit from 4661b86 to 74506c4

[sagetrac-git]

Changed commit from 74506c4 to 996e110

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

996e110

new canonical form for graphs, compare canonical_form_old with canonical_form

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

496cc9f

cleaing the file

[sagetrac-git]

Changed commit from 996e110 to 496cc9f

[sagetrac-git]

Changed commit from 496cc9f to 9416670

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

dd0fa55

added missing optional flag

[sagetrac-git]

Changed commit from 70cb231 to dd0fa55

[stumpc5]

comment:59

I hope everything is there now and the bot doesn't seem to show any bliss related doctest failures...

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:60

looks good to me, thanks!

[vbraun]

comment:61

Merge conflict

[dimpase]

Dependencies: #20382

[dimpase]

comment:62

needs to be rebased over #20382 (commit 8e4c504), as it got into the 1st alpha
already (see https://github.com/vbraun/sage/tree/develop)
This is very small change to be done.

[dimpase]

Changed branch from u/stumpc5/making_the_bliss_canonical_form_available_for_edge_labelled_graphs to public/graphs/making_the_bliss_canonical_form_available_for_edge_labelled_graphs

[dimpase]

Changed commit from dd0fa55 to 0830efc

[dimpase]

New commits:

8e4c504	Add Features to check the environment at runtime
f2b1903	Merge commit '8e4c504f07e' into morebliss
ad6dcc6	Cleanup feature tests
d94fe9b	Merge branch 'u/jdemeyer/features' of trac.sagemath.org:sage into morebliss
0830efc	Merge with sage.features from #20382

[dimpase]

comment:64

it looks like a trivial rebase, so...

[stumpc5]

comment:65

Thanks for getting back to it, the recheck somehow got lost on my todo list...

[vbraun]

Changed branch from public/graphs/making_the_bliss_canonical_form_available_for_edge_labelled_graphs to 0830efc