Opened 3 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: |
Description (last modified by )
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 3 years ago by
- 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 3 years ago by
- Description modified (diff)
comment:3 Changed 3 years ago by
- Branch set to u/stumpc5/making_the_bliss_canonical_form_available_for_edge_labelled_graphs
comment:4 Changed 3 years ago by
- Commit set to ff80980c1687ab4a09412d48600ddbe547e32864
comment:5 Changed 3 years ago by
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.
comment:6 follow-up: ↓ 7 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
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 3 years ago by
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 3 years ago by
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 3 years ago by
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 3 years ago by
- 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 3 years ago by
- 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 3 years ago by
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 3 years ago by
- 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 3 years ago by
- 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 3 years ago by
- 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 3 years ago by
- Commit changed from 996e110908b283e63e6c357533686b618421637a to 496cc9f5064b9942821af618b3e50018a5015fc6
Branch pushed to git repo; I updated commit sha1. New commits:
496cc9f | cleaing the file
|
comment:19 Changed 3 years ago by
- Commit changed from 496cc9f5064b9942821af618b3e50018a5015fc6 to 941667017eb6b09cd4dbb02302c38fc4b1e4847b
Branch pushed to git repo; I updated commit sha1. New commits:
9416670 | some more reorganization
|
comment:20 Changed 3 years ago by
@Dima: the new implementation follows your suggestion to use Vnr*log(Lnr)
many vertices, I would appreciate feedback!
comment:21 Changed 3 years ago by
(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 3 years ago by
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.
comment:23 Changed 3 years ago by
- 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 3 years ago by
- 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 3 years ago by
- 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 3 years ago by
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 3 years ago by
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).
comment:28 Changed 3 years ago by
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 3 years ago by
- Cc etn40ff added
comment:30 Changed 3 years ago by
- 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 3 years ago by
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 3 years ago by
- 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
|
comment:33 Changed 3 years ago by
done
comment:34 Changed 3 years ago by
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 3 years ago by
- Commit changed from a0ff5a3710304a19f756d0e087d71e4c7a4ea9cc to 9474fa052b56b3f02ca43e6ee74c0bdf7f834f05
Branch pushed to git repo; I updated commit sha1. New commits:
9474fa0 | moved some tests to examples
|
comment:36 Changed 3 years ago by
...like this
comment:37 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
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.
comment:40 Changed 3 years ago by
- 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
|
comment:41 Changed 3 years ago by
done...
comment:42 Changed 3 years ago by
comment:43 Changed 3 years ago by
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 3 years ago by
- 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 3 years ago by
- 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 3 years ago by
- 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 3 years ago by
- 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 3 years ago by
I'd remove these *_old()
functions you(?) introduced.
comment:49 Changed 3 years ago by
- Commit changed from 40164a3d3d7b703664d6235c17c63572ce199e08 to d8b8104053c81b5a01e70b81235e6eaabbd19eb2
Branch pushed to git repo; I updated commit sha1. New commits:
d8b8104 | removed *_old functions
|
comment:50 Changed 3 years ago by
- 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 3 years ago by
the patchbot seems to have no complaints anymore concerning the bliss code...
comment:52 Changed 3 years ago by
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 3 years ago by
- 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 3 years ago by
- Commit changed from 370bc8bc7dabe0844d639b58192cd3be7e67b8c2 to 70cb231acd43f717f37e4268320689ddb095e27b
comment:55 follow-up: ↓ 56 Changed 3 years ago by
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 3 years ago by
Replying to stumpc5:
updated
generic_graph.py
and fixed a bug inbliss.pyx
.Question: Is it really the right decision to have
edge_labels=False
per default inautomorphism_group
andcanonical_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 haveTrue
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 3 years ago by
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 3 years ago by
- 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 3 years ago by
I hope everything is there now and the bot doesn't seem to show any bliss related doctest failures...
comment:60 Changed 3 years ago by
- Reviewers set to Dima Pasechnik
- Status changed from needs_review to positive_review
looks good to me, thanks!
comment:62 Changed 3 years ago by
- 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
- 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
comment:64 Changed 3 years ago by
- Status changed from needs_review to positive_review
it looks like a trivial rebase, so...
comment:65 Changed 3 years ago by
Thanks for getting back to it, the recheck somehow got lost on my todo list...
comment:66 Changed 3 years ago by
- 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
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 immediatelyNew commits:
first version of bliss canonical form from edge list