Opened 4 years ago

Closed 3 years ago

# Making the bliss canonical form available for edge labelled graphs

Reported by: Owned by: stumpc5 major sage-8.3 graph theory bliss, graph automorphism, canonical form SimonKing, dimpase, gh-dimpase, ​etn40ff Christian Stump Dima Pasechnik N/A 0830efc 0830efc90604f7d4b432e013b9242b24e618c762 #20382

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.

### comment:1 Changed 4 years ago by stumpc5

• Summary changed from Ḿaking the bliss canonical form available for edge labelled graphs to Making the bliss canonical form available for edge labelled graphs

### comment:2 Changed 4 years ago by stumpc5

• Description modified (diff)

### comment:3 Changed 4 years ago by stumpc5

• Branch set to u/stumpc5/making_the_bliss_canonical_form_available_for_edge_labelled_graphs

### comment:4 Changed 4 years ago by stumpc5

• Commit set to ff80980c1687ab4a09412d48600ddbe547e32864

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`

### comment:5 Changed 4 years ago by SimonKing

So far it looks good. But 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.

Version 0, edited 4 years ago by SimonKing (next)

### comment:6 follow-up: ↓ 7 Changed 4 years ago by 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`.

### comment:7 in reply to: ↑ 6 Changed 4 years ago by SimonKing

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.

### comment:8 Changed 4 years ago by 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

### comment:9 Changed 4 years ago by 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...

### comment:10 Changed 4 years ago by 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...).

### comment:11 Changed 4 years ago by 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

### comment:12 Changed 4 years ago by git

• Commit changed from ff80980c1687ab4a09412d48600ddbe547e32864 to 7ea99bdfc7cc420607638f064ace7dbebfcb61c2

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

 ​7ea99bd `first version of bliss graph from labelled edges`

### comment:13 Changed 4 years ago by git

• Commit changed from 7ea99bdfc7cc420607638f064ace7dbebfcb61c2 to 3f072641398635ad1bc9797449fae01ce4b7b651

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

 ​3f07264 `fixed typo, added labelled edge return and fixed bug in relabelling`

### comment:14 Changed 4 years ago by 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`

### comment:15 Changed 4 years ago by git

• Commit changed from 3f072641398635ad1bc9797449fae01ce4b7b651 to 4661b864eca996578cfaf060f6de9beec4e62bf0

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

 ​4661b86 `playing the labelled graphs for now`

### comment:16 Changed 4 years ago by git

• Commit changed from 4661b864eca996578cfaf060f6de9beec4e62bf0 to 74506c45616d77af9569ab479718ab40aa74ffa5

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

 ​74506c4 `slighly avoiding some code duplication`

### comment:17 Changed 4 years ago by git

• Commit changed from 74506c45616d77af9569ab479718ab40aa74ffa5 to 996e110908b283e63e6c357533686b618421637a

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

 ​996e110 `new canonical form for graphs, compare canonical_form_old with canonical_form`

### comment:18 Changed 4 years ago by git

• Commit changed from 996e110908b283e63e6c357533686b618421637a to 496cc9f5064b9942821af618b3e50018a5015fc6

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

 ​496cc9f `cleaing the file`

### comment:19 Changed 4 years ago by git

• Commit changed from 496cc9f5064b9942821af618b3e50018a5015fc6 to 941667017eb6b09cd4dbb02302c38fc4b1e4847b

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

 ​9416670 `some more reorganization`

### comment:20 Changed 4 years ago by stumpc5

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

### comment:21 Changed 4 years ago by 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!

### comment:22 Changed 4 years ago by 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.

Last edited 4 years ago by stumpc5 (previous) (diff)

### comment:23 Changed 4 years ago by git

• Commit changed from 941667017eb6b09cd4dbb02302c38fc4b1e4847b to 6ede189564c6e33a456645200ca799f1de958658

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`

### comment:24 Changed 4 years ago by git

• Commit changed from 6ede189564c6e33a456645200ca799f1de958658 to a1d549109fb9318d062119399cfb8597b9d2710b

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

 ​a1d5491 `added some further doctests, fixed a bug for automorphism group`

### comment:25 Changed 4 years ago by stumpc5

• Keywords bliss graph automorphism canonical form added
• Status changed from new to needs_review

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

### comment:26 Changed 4 years ago by 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)

### comment:27 Changed 4 years ago by 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).

Last edited 4 years ago by gh-dimpase (previous) (diff)

### comment:28 Changed 4 years ago by 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.

### comment:30 Changed 4 years ago by 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!

### comment:31 Changed 4 years ago by 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...

### comment:32 Changed 4 years ago by git

• Commit changed from a1d549109fb9318d062119399cfb8597b9d2710b to a0ff5a3710304a19f756d0e087d71e4c7a4ea9cc

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`

done

### comment:34 Changed 4 years ago by 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:....
```

### comment:35 Changed 4 years ago by git

• Commit changed from a0ff5a3710304a19f756d0e087d71e4c7a4ea9cc to 9474fa052b56b3f02ca43e6ee74c0bdf7f834f05

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

 ​9474fa0 `moved some tests to examples`

...like this

### comment:37 Changed 4 years ago by 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...).

### comment:38 Changed 4 years ago by 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?

### comment:39 Changed 4 years ago by 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.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.

Last edited 4 years ago by dimpase (previous) (diff)

### comment:40 Changed 4 years ago by git

• Commit changed from 9474fa052b56b3f02ca43e6ee74c0bdf7f834f05 to 994d327fe8da8d52310de2c0cfd7c67760449dd3

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`

done...

### comment:42 Changed 4 years ago by stumpc5

• Authors set to Christian Stump

### comment:43 Changed 4 years ago by 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...

### comment:44 Changed 4 years ago by git

• Commit changed from 994d327fe8da8d52310de2c0cfd7c67760449dd3 to 808559a1cf1835883dd02b8c2622f9de2349bd5c

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

 ​808559a `removed the verbose option with printing as this was mainly for debugging`

### comment:45 Changed 4 years ago by git

• Commit changed from 808559a1cf1835883dd02b8c2622f9de2349bd5c to 9528bc8563f92df248590f9841b2855a16e04cb5

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

 ​9528bc8 `removed the verbose option with printing as this was mainly for debugging`

### comment:46 Changed 4 years ago by git

• Commit changed from 9528bc8563f92df248590f9841b2855a16e04cb5 to 190014743332c22e2a1337fd11625d45d64b2922

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

 ​1900147 `removed the cython profiler message`

### comment:47 Changed 4 years ago by git

• Commit changed from 190014743332c22e2a1337fd11625d45d64b2922 to 40164a3d3d7b703664d6235c17c63572ce199e08

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

 ​40164a3 `removed non-ascii characters that sneaked into the link`

### comment:48 Changed 4 years ago by dimpase

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

### comment:49 Changed 4 years ago by git

• Commit changed from 40164a3d3d7b703664d6235c17c63572ce199e08 to d8b8104053c81b5a01e70b81235e6eaabbd19eb2

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

 ​d8b8104 `removed *_old functions`

### comment:50 Changed 4 years ago by git

• Commit changed from d8b8104053c81b5a01e70b81235e6eaabbd19eb2 to 9e2a3d2b521f2cacda9ac086e7a6b9cbaa4f663f

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

 ​9e2a3d2 `added a few missing opional flags`

### comment:51 Changed 4 years ago by stumpc5

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

### comment:52 Changed 4 years ago by 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.

### comment:53 Changed 4 years ago by git

• Commit changed from 9e2a3d2b521f2cacda9ac086e7a6b9cbaa4f663f to 370bc8bc7dabe0844d639b58192cd3be7e67b8c2

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

 ​370bc8b `hopefully updated the use of edge labels using bliss in generic_graph`

### comment:54 Changed 4 years ago by git

• Commit changed from 370bc8bc7dabe0844d639b58192cd3be7e67b8c2 to 70cb231acd43f717f37e4268320689ddb095e27b

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`

### comment:55 follow-up: ↓ 56 Changed 4 years ago by 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.

### comment:56 in reply to: ↑ 55 Changed 4 years ago by dimpase

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.

### comment:57 Changed 4 years ago by 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.

### comment:58 Changed 4 years ago by git

• Commit changed from 70cb231acd43f717f37e4268320689ddb095e27b to dd0fa5505e5f70b43407d2c18cf94ce3886945d5

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

 ​dd0fa55 `added missing optional flag`

### comment:59 Changed 4 years ago by stumpc5

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

### comment:60 Changed 4 years ago by dimpase

• Reviewers set to Dima Pasechnik
• Status changed from needs_review to positive_review

looks good to me, thanks!

### comment:61 Changed 3 years ago by vbraun

• Status changed from positive_review to needs_work

Merge conflict

### comment:62 Changed 3 years ago by dimpase

• Dependencies set to #20382
• Milestone changed from sage-8.2 to sage-8.3

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.

### comment:63 Changed 3 years ago by dimpase

• Branch changed 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
• Commit changed from dd0fa5505e5f70b43407d2c18cf94ce3886945d5 to 0830efc90604f7d4b432e013b9242b24e618c762
• Status changed from needs_work to needs_review

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`

### comment:64 Changed 3 years ago by dimpase

• Status changed from needs_review to positive_review

it looks like a trivial rebase, so...

### comment:65 Changed 3 years ago by stumpc5

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

### comment:66 Changed 3 years ago by vbraun

• Branch changed from public/graphs/making_the_bliss_canonical_form_available_for_edge_labelled_graphs to 0830efc90604f7d4b432e013b9242b24e618c762
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.