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.

[stumpc5]

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

[SimonKing]

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]

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.

[SimonKing]

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]

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]

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]

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]

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

[git]

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

​7ea99bd

first version of bliss graph from labelled edges

[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]

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

[git]

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

​4661b86

playing the labelled graphs for now

[git]

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

​74506c4

slighly avoiding some code duplication

[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

[git]

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

​496cc9f

cleaing the file

[git]

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

​9416670

some more reorganization

[stumpc5]

@Dima: the new implementation follows your suggestion to use Vnr*log(Lnr) many vertices, I would appreciate feedback!

[stumpc5]

(The current version does not provide the automorphism groups, but the methods automorphism_group and automorphism_group_old are captured to profile the bliss graph constructor from a labelled graph with Vnr*log(Lnr) vertices.

Here is some output:

sage: from sage.graphs.bliss import canonical_form, automorphism_group, automorphism_group_old
sage: G = graphs.RandomGNM(1000,1000000)

and then

sage: %crun automorphism_group(G)
PROFILE: interrupts/evictions/bytes = 45/0/20936
Using local file /home/stumpc5/Programs/sage/local/bin/python2.
Using local file /home/stumpc5/.sage/temp/associahedron/19913/tmp_zjuPxl.perf.
Total: 45 samples
       0   0.0%   0.0%       45 100.0% PyEval_EvalCode
       0   0.0%   0.0%       45 100.0% PyEval_EvalCodeEx
       0   0.0%   0.0%       45 100.0% PyEval_EvalFrameEx
       0   0.0%   0.0%       45 100.0% PyObject_Call
       0   0.0%   0.0%       45 100.0% PyRun_FileExFlags
       0   0.0%   0.0%       45 100.0% PyRun_SimpleFileExFlags
       0   0.0%   0.0%       45 100.0% PyRun_StringFlags
       0   0.0%   0.0%       45 100.0% Py_Main
       0   0.0%   0.0%       45 100.0% __libc_start_main
       2   4.4%   4.4%       45 100.0% __pyx_f_4sage_6graphs_5bliss_automorphism_group (inline)
       0   0.0%   4.4%       45 100.0% __pyx_pf_4sage_6graphs_5bliss_6automorphism_group (inline)
       0   0.0%   4.4%       45 100.0% __pyx_pw_4sage_6graphs_5bliss_7automorphism_group
       0   0.0%   4.4%       45 100.0% call_function (inline)
       0   0.0%   4.4%       45 100.0% exec_statement (inline)
       0   0.0%   4.4%       45 100.0% ext_do_call (inline)
       0   0.0%   4.4%       45 100.0% fast_function (inline)
       0   0.0%   4.4%       45 100.0% function_call
       0   0.0%   4.4%       45 100.0% run_mod (inline)
       0   0.0%   4.4%       44  97.8% _start
       0   0.0%   4.4%       35  77.8% __Pyx_PyObject_Call
       0   0.0%   4.4%       35  77.8% do_call (inline)
       0   0.0%   4.4%       35  77.8% instancemethod_call
       0   0.0%   4.4%       18  40.0% listsort
       0   0.0%   4.4%       17  37.8% __Pyx_Coroutine_SendEx.isra.12
       2   4.4%   8.9%       17  37.8% __pyx_gb_4sage_6graphs_4base_12sparse_graph_18SparseGraphBackend_14generator
       0   0.0%   8.9%       17  37.8% list_init
       0   0.0%   8.9%       17  37.8% listextend
       0   0.0%   8.9%       17  37.8% type_call
       4   8.9%  17.8%       16  35.6% PyObject_RichCompareBool
       7  15.6%  33.3%       15  33.3% PyObject_RichCompare
       1   2.2%  35.6%       10  22.2% merge_at
       0   0.0%  35.6%       10  22.2% merge_collapse (inline)
       1   2.2%  37.8%        7  15.6% PyTuple_New
       0   0.0%  37.8%        7  15.6% binarysort (inline)
       1   2.2%  40.0%        7  15.6% tuplerichcompare
       0   0.0%  40.0%        6  13.3% _PyObject_GC_Malloc
       0   0.0%  40.0%        6  13.3% _PyObject_GC_NewVar
       0   0.0%  40.0%        5  11.1% collect
       0   0.0%  40.0%        5  11.1% collect_generations (inline)
       1   2.2%  42.2%        5  11.1% list_dealloc
       0   0.0%  42.2%        5  11.1% merge_lo (inline)
       1   2.2%  44.4%        4   8.9% __pyx_f_4sage_6graphs_4base_12sparse_graph_11SparseGraph_out_arcs_unsafe
       1   2.2%  46.7%        4   8.9% merge_hi (inline)
       1   2.2%  48.9%        4   8.9% tupledealloc
       0   0.0%  48.9%        3   6.7% gallop_right
       0   0.0%  48.9%        3   6.7% move_unreachable (inline)
       2   4.4%  53.3%        2   4.4% PyInt_FromLong
       0   0.0%  53.3%        2   4.4% PyObject_Free
       2   4.4%  57.8%        2   4.4% PyObject_GetItem
       2   4.4%  62.2%        2   4.4% _PyTuple_MaybeUntrack
       0   0.0%  62.2%        2   4.4% __Pyx_PyInt_From_int (inline)
       2   4.4%  66.7%        2   4.4% __munmap
       0   0.0%  66.7%        2   4.4% __pyx_f_4sage_6graphs_4base_7c_graph_13CGraphBackend_vertex_label
       2   4.4%  71.1%        2   4.4% convert_3way_to_object (inline)
       0   0.0%  71.1%        2   4.4% gallop_left
       2   4.4%  75.6%        2   4.4% int_compare
       1   2.2%  77.8%        2   4.4% subtract_refs (inline)
       1   2.2%  80.0%        1   2.2% PyDict_Contains
       0   0.0%  80.0%        1   2.2% PyList_Append
       1   2.2%  82.2%        1   2.2% PyObject_Malloc
       0   0.0%  82.2%        1   2.2% _IO_str_seekoff
       0   0.0%  82.2%        1   2.2% __Pyx_PyDict_ContainsTF (inline)
       1   2.2%  84.4%        1   2.2% __nss_passwd_lookup
       1   2.2%  86.7%        1   2.2% __pyx_f_4sage_6graphs_4base_12sparse_graph_11SparseGraph_out_neighbors_BTNode_unsafe
       1   2.2%  88.9%        1   2.2% adjust_tp_compare
       0   0.0%  88.9%        1   2.2% app1 (inline)
       0   0.0%  88.9%        1   2.2% count_run (inline)
       0   0.0%  88.9%        1   2.2% dict_subscript
       0   0.0%  88.9%        1   2.2% do_richcmp (inline)
       1   2.2%  91.1%        1   2.2% int_dealloc
       1   2.2%  93.3%        1   2.2% list_item (inline)
       0   0.0%  93.3%        1   2.2% list_resize (inline)
       0   0.0%  93.3%        1   2.2% list_subscript
       0   0.0%  93.3%        1   2.2% list_traverse
       1   2.2%  95.6%        1   2.2% lookdict
       0   0.0%  95.6%        1   2.2% realloc
       0   0.0%  95.6%        1   2.2% try_3way_to_rich_compare (inline)
       1   2.2%  97.8%        1   2.2% tupletraverse
       1   2.2% 100.0%        1   2.2% visit_reachable

and

sage: %crun automorphism_group_old(G)
PROFILE: interrupts/evictions/bytes = 38/0/16080
Using local file /home/stumpc5/Programs/sage/local/bin/python2.
Using local file /home/stumpc5/.sage/temp/associahedron/20717/tmp_0m26KQ.perf.
Total: 38 samples
       0   0.0%   0.0%       36  94.7% PyEval_EvalCode
       0   0.0%   0.0%       36  94.7% PyEval_EvalCodeEx
       0   0.0%   0.0%       36  94.7% PyEval_EvalFrameEx
       0   0.0%   0.0%       36  94.7% PyObject_Call
       0   0.0%   0.0%       36  94.7% PyRun_FileExFlags
       0   0.0%   0.0%       36  94.7% PyRun_SimpleFileExFlags
       0   0.0%   0.0%       36  94.7% PyRun_StringFlags
       0   0.0%   0.0%       36  94.7% Py_Main
       2   5.3%   5.3%       36  94.7% __pyx_f_4sage_6graphs_5bliss_bliss_graph
       0   0.0%   5.3%       36  94.7% __pyx_pf_4sage_6graphs_5bliss_10automorphism_group_old (inline)
       0   0.0%   5.3%       36  94.7% __pyx_pw_4sage_6graphs_5bliss_11automorphism_group_old
       0   0.0%   5.3%       36  94.7% call_function (inline)
       0   0.0%   5.3%       36  94.7% exec_statement (inline)
       0   0.0%   5.3%       36  94.7% ext_do_call (inline)
       0   0.0%   5.3%       36  94.7% fast_function (inline)
       0   0.0%   5.3%       36  94.7% function_call
       0   0.0%   5.3%       36  94.7% run_mod (inline)
       0   0.0%   5.3%       35  92.1% __libc_start_main
       0   0.0%   5.3%       34  89.5% _start
       0   0.0%   5.3%       30  78.9% __Pyx_PyObject_Call
       0   0.0%   5.3%       30  78.9% do_call (inline)
       0   0.0%   5.3%       30  78.9% instancemethod_call
       0   0.0%   5.3%       17  44.7% listsort
       8  21.1%  26.3%       15  39.5% PyObject_RichCompare
       2   5.3%  31.6%       15  39.5% PyObject_RichCompareBool
       0   0.0%  31.6%       13  34.2% list_init
       1   2.6%  34.2%       13  34.2% listextend
       0   0.0%  34.2%       13  34.2% type_call
       0   0.0%  34.2%       12  31.6% __Pyx_Coroutine_SendEx.isra.12
       2   5.3%  39.5%       12  31.6% __pyx_gb_4sage_6graphs_4base_12sparse_graph_18SparseGraphBackend_14generator
       0   0.0%  39.5%       11  28.9% merge_at
       0   0.0%  39.5%       11  28.9% merge_collapse (inline)
       1   2.6%  42.1%        7  18.4% tuplerichcompare
       0   0.0%  42.1%        6  15.8% binarysort (inline)
       2   5.3%  47.4%        6  15.8% merge_lo (inline)
       0   0.0%  47.4%        5  13.2% PyTuple_New
       0   0.0%  47.4%        5  13.2% _PyObject_GC_Malloc
       0   0.0%  47.4%        5  13.2% _PyObject_GC_NewVar
       0   0.0%  47.4%        4  10.5% merge_hi (inline)
       3   7.9%  55.3%        3   7.9% PyObject_Malloc
       0   0.0%  55.3%        3   7.9% __pyx_f_4sage_6graphs_4base_12sparse_graph_11SparseGraph_out_arcs_unsafe
       2   5.3%  60.5%        2   5.3% __pyx_f_4sage_6graphs_4base_12sparse_graph_11SparseGraph_out_neighbors_BTNode_unsafe
       2   5.3%  65.8%        2   5.3% _init@3cc28
       1   2.6%  68.4%        2   5.3% adjust_tp_compare
       0   0.0%  68.4%        2   5.3% collect
       0   0.0%  68.4%        2   5.3% collect_generations (inline)
       2   5.3%  73.7%        2   5.3% convert_3way_to_object (inline)
       0   0.0%  73.7%        2   5.3% dict_subscript
       0   0.0%  73.7%        2   5.3% do_richcmp (inline)
       0   0.0%  73.7%        2   5.3% gallop_right
       0   0.0%  73.7%        2   5.3% list_dealloc
       1   2.6%  76.3%        2   5.3% lookdict
       0   0.0%  76.3%        2   5.3% try_3way_to_rich_compare (inline)
       1   2.6%  78.9%        2   5.3% tupledealloc
       0   0.0%  78.9%        1   2.6% 0x0000558037bbae7f
       1   2.6%  81.6%        1   2.6% PyErr_Occurred
       0   0.0%  81.6%        1   2.6% PyList_Append
       1   2.6%  84.2%        1   2.6% PyObject_GC_UnTrack
       1   2.6%  86.8%        1   2.6% _PyTuple_MaybeUntrack
       0   0.0%  86.8%        1   2.6% __Pyx_PyList_Append (inline)
       1   2.6%  89.5%        1   2.6% __nss_passwd_lookup
       1   2.6%  92.1%        1   2.6% __pyx_f_4sage_6graphs_4base_7c_graph_13CGraphBackend_vertex_label
       0   0.0%  92.1%        1   2.6% _init@708
       0   0.0%  92.1%        1   2.6% app1 (inline)
       0   0.0%  92.1%        1   2.6% gallop_left
       1   2.6%  94.7%        1   2.6% int_compare
       0   0.0%  94.7%        1   2.6% list_resize (inline)
       0   0.0%  94.7%        1   2.6% move_unreachable (inline)
       1   2.6%  97.4%        1   2.6% realloc
       0   0.0%  97.4%        1   2.6% subtract_refs (inline)
       0   0.0%  97.4%        1   2.6% tupletraverse
       1   2.6% 100.0%        1   2.6% visit_decref

How do I interpret these outputs? In particular whether it tells me some bottlenecks I should look at?

Thanks!

[stumpc5]

Question: is there a way, or rather what to do, to get a line-by-line profiling of the file? A typical question I'd ask is whether is would improve if I replace the python lists Vout, Vin, and labels by c lists as Simon suggested.

[git]

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

​6ede189

found that vertex and edge iterator are 3 times faster for big graphs

[git]

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

​a1d5491

added some further doctests, fixed a bug for automorphism group

[stumpc5]

Since I haven't gotten any feedback here, I now set it to needs review in the hope the ticket gets some attention...

[gh-dimpase]

What are these automorphism_group_old and other *_old functions? It's still prototyping, right?

Regarding profiling, can't you use some kind of graphical tool, such as google-pprof, on /home/stumpc5/.sage/temp/associahedron/20717/tmp_0m26KQ.perf ? (unless I totally mix this up)

[gh-dimpase]

Anyway, I think the bottlenecks correspond to larger values in the 2nd column, e.g. PyObject_RichCompare is 15% on the 1st listing and 21% on the 2nd listing.

Are you testing on the complete graph on purpose? (cause the number of edges is the square of the number of vertices, it's K_1000).

It would be interesting to look at how this performs on other graphs.

You can fing more details on the profiler (e.g. how to do per line profiles) at the gperftools installation on your system. (I don't know why they don't have it online). (on linux, man pprof would give you more pointers).

[stumpc5]

Thanks, Dima, for checking!

What are these automorphism_group_old and other *_old functions?

I just left these for you (or another referee to compare timings, if desired. Beside, they are good to be removed.

PyObject_RichCompare is 15% on the 1st listing and 21% on the 2nd listing.

I got rid of these by not using .vertices and .edges but instead the iterators. The PyObject_RichCompare were there because the vertices and edges were sorted by default.

Are you testing on the complete graph on purpose?

I was testing on many random graphs, and just ended up with the complete graph by pure chance.

I think the next optimization would be to use the internal graph structure on 0 ... Vnr-1 directly without first getting the edges as python objects and then turning them back into a bliss graph. But I don't plan to do this.

To summarize the situation: the new functionality for edge labelled graphs is up and working, and as quick as the old implementation on unlabelled graphs. So this is ready for review. I still see possible improvements using the cgraph structure, but leave this open for now.

[stumpc5]

Dear Dima and Simon -- any chance I could get a review for this ticket so that I can move forward to the tickets based on this one? Thanks!

[dimpase]

Could you add more docs to automorphism_group(G, partition=None), in particular, can G itself have coloured vertices and/or (directed) edges?

I'd also add more tests with bigger graphs, just to make sure...

[git]

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

​a0ff5a3

added more doctests for automorphism group, including edge and label, directed graphs, and big examples

[stumpc5]

done

[dimpase]

Thanks. How about more docs for this function? E.g. it's unclear how the partition parameter interacts with vertex colours of the graph. Docs need not be very formal, it's OK to move some tests into Examples section, and use them to illustrate the way the function works, e.g.

EXAMPLES:

    blah works ::

        sage:....
    ...

    you can also foo ::

        sage:....

[git]

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

​9474fa0

moved some tests to examples

[stumpc5]

...like this

[dimpase]

EXAMPLES:: -> EXAMPLES:

(only put :: after EXAMPLES/TESTS is there is no subitems ending (by right) with ::)

And, once again, can we please have an explanation/test/example of what happens is the vertex partitions of the graph (from its vertex labelling) and the partition supplied as the parameter are not compatible (I expect it would work with a common refinement, but one has to make sure, that's a corner where bugs would nest...).

[stumpc5]

It currently looks like

    EXAMPLES::

        sage: from sage.graphs.bliss import automorphism_group                  # optional - bliss

    Computing the automorphism group of a graph or digraph::

        sage: G = graphs.CompleteMultipartiteGraph([1,1,1,2])                   # optional - bliss

Don't I need to put the :: because of the following indented line?

I do not understand your other issue (and thought it was a typo and you meant edge coloring): What do you mean by vertex labelling?

• The vertex labelling must be injective if I see it correctly:

  sage: G = Graph(graphs.CompleteMultipartiteGraph([1,1,1,3]),sparse=True)
  sage: G.relabel({0:"A",1:"A",2:"B"})
  ...
  NotImplementedError: Non injective relabeling
  

• Any vertex labelling is completely ignored when it comes to the automorphism group, EXCEPT that the permutation group is built such that it acts on the vertex labels (see the last two doctests).

Am I missunderstanding what you mean?

[dimpase]

Regarding ::, you are correct, I didn't think straight.

Then, I meant loops:

sage: gg=graphs.CompleteGraph(3)
sage: gg.allow_loops(True)
sage: gg.add_edge((1,1))
sage: gg.automorphism_group()
Permutation Group with generators [(0,2)]

this is without bliss installed. That is, at least the default automorphisms code respects loops, but there seems to be neither docs nor tests for this.

Also, your branch should modify the default docs on automorphisms, for it currently says

   * "edge_labels" - default False, otherwise allows only
     permutations respecting edge labels. Note that this option is not
     supported if "algorithm="bliss""

---and so the last sentence should go.

[git]

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

​29883cb	Merge branch 'develop' into t/24924/making_the_bliss_canonical_form_available_for_edge_labelled_graphs
​9a209f5	added test for automorphism group of looped graph with vertex partition
​0683347	removed sentence that edge labels are not supported for bliss graphs
​994d327	added reference for edge labelled graph automorphism computation

[stumpc5]

done...

[stumpc5]

Should I remove the old functionalities ?

cdef Graph *bliss_graph(G, partition, vert2int, int2vert)
cdef Digraph *bliss_digraph(G, partition, vert2int, int2vert)
def canonical_form_old(G, partition=None, return_graph=False, certificate=False)
def automorphism_group_old(G, partition=None)

At least the two methods bliss_graph and bliss_digraph might be used in some private code, so I vote for keeping all of them for a while...

[git]

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

​808559a

removed the verbose option with printing as this was mainly for debugging

[git]

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

​9528bc8

removed the verbose option with printing as this was mainly for debugging

[git]

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

​1900147

removed the cython profiler message

[git]

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

​40164a3

removed non-ascii characters that sneaked into the link

[dimpase]

I'd remove these *_old() functions you(?) introduced.

[git]

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

​d8b8104

removed *_old functions

[git]

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

​9e2a3d2

added a few missing opional flags

[stumpc5]

the patchbot seems to have no complaints anymore concerning the bliss code...

[dimpase]

there are more mentions of Bliss in graphs/generic_graph.py that should be modified, e.g.

  if edge_labels and algorithm == 'bliss':
      raise NotImplementedError("algorithm 'bliss' can not be used when edge_labels=True")

looks like something that needs to be looked into.

[git]

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

​370bc8b

hopefully updated the use of edge labels using bliss in generic_graph

[git]

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

​5910141	added some doctests
​70cb231	added optional argument 'use_edge_labels', fixed bug for vertices partition, added some doctests

[stumpc5]

updated generic_graph.py and fixed a bug in bliss.pyx.

Question: Is it really the right decision to have edge_labels=False per default in automorphism_group and canonical_form ? --I don't really care, but given an edge labelled graph, my first impression is that this edge labelling should be considered per default. The new underlying bliss methods have True per default which is overwritten from the graph methods then.

[dimpase]

Replying to stumpc5:

updated generic_graph.py and fixed a bug in bliss.pyx.

Question: Is it really the right decision to have edge_labels=False per default in automorphism_group and canonical_form ? --I don't really care, but given an edge labelled graph, my first impression is that this edge labelling should be considered per default. The new underlying bliss methods have True per default which is overwritten from the graph methods then.

The default should be edge_labels=True if you ask me. But such a change should be properly deprecated.

[stumpc5]

Observe that I came across this strange default seeing that the doctest

sage: digraphs.DeBruijn(3,1).is_circulant(certificate = True)
(True, [(3, [0, 1, 2])])

failed since now bliss was used with the wrong optional argument. I think I just leave it for now since changing the default might cause more problems than it actually solves... Btw: graphs are also plotted without edge labels per default. Also there, I believe that it should be plotted with edge labels, and the edge label None is generally not shown ever.

[git]

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

​dd0fa55

added missing optional flag

[stumpc5]

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

[dimpase]

looks good to me, thanks!

[vbraun]

Merge conflict

[dimpase]

needs to be rebased over #20382 (commit 8e4c504f07e), 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]

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]

it looks like a trivial rebase, so...

[stumpc5]

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