Opened 4 years ago

Closed 3 years ago

#24924 closed enhancement (fixed)

Making the bliss canonical form available for edge labelled graphs

Reported by: stumpc5 Owned by:
Priority: major Milestone: sage-8.3
Component: graph theory Keywords: bliss, graph automorphism, canonical form
Cc: SimonKing, dimpase, gh-dimpase, ​etn40ff Merged in:
Authors: Christian Stump Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 0830efc (Commits, GitHub, GitLab) Commit: 0830efc90604f7d4b432e013b9242b24e618c762
Dependencies: #20382 Stopgaps:

Status badges

Description (last modified by 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.

Change History (66)

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:

ff80980first version of bliss canonical form from edge list

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

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

comment:6 follow-up: 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

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.

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:

7ea99bdfirst 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:

3f07264fixed 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:

3f07264fixed 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:

4661b86playing 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:

74506c4slighly 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:

996e110new 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:

496cc9fcleaing 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:

9416670some 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:

6ede189found 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:

a1d5491added 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:29 Changed 4 years ago by stumpc5

  • Cc ​etn40ff added

comment:30 Changed 4 years ago by stumpc5

  • Cc gh-dimpase added

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:

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

comment:33 Changed 4 years ago by stumpc5

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:

9474fa0moved some tests to examples

comment:36 Changed 4 years ago by stumpc5

...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.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.

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:

29883cbMerge branch 'develop' into t/24924/making_the_bliss_canonical_form_available_for_edge_labelled_graphs
9a209f5added test for automorphism group of looped graph with vertex partition
0683347removed sentence that edge labels are not supported for bliss graphs
994d327added reference for edge labelled graph automorphism computation

comment:41 Changed 4 years ago by stumpc5

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:

808559aremoved 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:

9528bc8removed 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:

1900147removed 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:

40164a3removed 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:

d8b8104removed *_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:

9e2a3d2added 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:

370bc8bhopefully 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:

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

comment:55 follow-up: 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

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.

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:

dd0fa55added 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:

8e4c504Add Features to check the environment at runtime
f2b1903Merge commit '8e4c504f07e' into morebliss
ad6dcc6Cleanup feature tests
d94fe9bMerge branch 'u/jdemeyer/features' of trac.sagemath.org:sage into morebliss
0830efcMerge 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.