#17464 closed enhancement (fixed)
Computing the automorphism group of a graph with Bliss
Reported by:  azi  Owned by:  

Priority:  major  Milestone:  sage6.5 
Component:  graph theory  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Jernej Azarija  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  e403f16 (Commits)  Commit:  
Dependencies:  #17552, #18145  Stopgaps: 
Description
Hello!
I have a suggestion for a big improvement for the Graph Theoretical module of Sage. Right now I am a not in the proper mood to do it myself so I am leaving this here in case anyone is willing to do it or as a TODO note for a later time.
Consider the graph on ~10k vertices located in the file https://www.dropbox.com/s/pbtk2965ti71u9n/graph.txt.gz?dl=0 where each line contains an edge pair.
Using the standard way in Sage (read graph call automorphism_group() ) takes a few hours (I'll tell the exact time when it actually finishes) to compute and makes a 30GB memory footprint.
The same thing can be done using bliss http://www.tcs.tkk.fi/Software/bliss/index.html with no actual memory footprint in 20 seconds.
So right now its much cheaper for me to just write the graph into DIMACS format call bliss and parse its output.
I guess the same kind of performance can be obtained using nauty so I suppose there is something OFF with the current implementation of the automorphism group method. IIRC it is written in Python?
Hopefully we can make this into a productive patch.
Change History (157)
comment:1 Changed 6 years ago by
 Branch set to u/azi/bliss
 Commit set to 3f4553d1cb40c8d2dbfd55bdef4323877c0b4321
 Status changed from new to needs_info
comment:2 Changed 6 years ago by
I'd be glad if someone could take a look at this branch. It is far from being "production ready" and I mainly posting it here because
 I want any comments and suggestions if its going in the right direction(to avoid later rewrites :D)
 I need someone to explain how to make a spkg so that I can properly include bliss headers and be able to link against bliss.
 Discuss what to do with the add_gen function that converts a permutation to cycle notation. Do you agree that I leave it there and avoid using Permutation.to_cycle()?
 How to handle digraphs elegantly?
As is for now, the code correctly compute the aut of a graph/digraph provided that libbliss.a is in the sage lib folder and the location of the bliss header is correctly set in bliss.pyx.
I wrote that above question for the general audience but honestly,.. Nathann what do you think??
comment:3 Changed 6 years ago by
 Commit changed from 3f4553d1cb40c8d2dbfd55bdef4323877c0b4321 to f8dcb7e4ffca76715b478ada498be1714e0f38f1
Branch pushed to git repo; I updated commit sha1. New commits:
f8dcb7e  trac #17464: Added module_list as well

comment:4 Changed 6 years ago by
Yoooooooooooo !
Well, so far your branch does not look "that bad". The only weird thing is that I do not get why this bliss branch should do that modifications :P
+ :meth:`~GenericGraph.geodetic_number`  Returns the geodetic number of the given graph.
The right way to write this code, however, begins as you say by writing the spkg, as nobody can test it without it. And the right way to do that, as usual is copy and paste.
1) There is a developer's manual that I am trying to improve these days. There is a section I never read about exactly that: http://www.sagemath.org/doc/developer/packaging.html. If you find anything wrong/unclear in there, please fix it if you can. We must make this clear to everybody. If you do not understand, tell me where it is and I will try to fix it.
2) spkgs are rather simple nowadays. The code that installs the program is a Sage code, like any other. You will find it in SAGE_ROOT/build/. Take a look at the structure of buckygen
, for instance: it is an optional graph package, just like bliss will be.
3) That was for the Sage code, but the nonsage code (i.e. the source code of bliss) must be stored in the SAGE_ROOT/upstream folder. You will figure out that the code in build/ is actually instruction about what to do with the blissversion.tar.bz2 that must be there, and which is only the official bliss release.
4) Then there are he "checksums": http://www.sagemath.org/doc/developer/packaging.html#checksums
So before continuing with this you should create a ticket to add bliss as a spkg. It could be quick, and if you have time right now we can settle it fast, I won't get to bed before one hour at least, I can review it before.
A ticket that adds a new package should contain:
1) A branch that adds the required files in the build/ folder
2) A .tar.bz2 file (hosted wherever you like) that I should download in the upstream/ folder before typing "sage i bliss".
I am a bit offline this evening because I have a very short ethernet cable next to an uncomfortable chair. I come back from time to time to check my emails :P
Good luck !
Nathann
comment:5 followup: ↓ 6 Changed 6 years ago by
Thanks for the input!!
Continuing our talk here I have a short question. The class definitions of a Graph and Digraph in bliss both contain the same functions add_edge(int i, int j) and change_color(int x, int c).
Now as far as I see *if* we patch bliss to make these two functions a (virtual) part of the abstract graph class then we could do something like
AbstractGraph *g; g = either Graph or Digraph g.add_edge(i,j) g.change_color(i,c) g.find_automorphisms()
I think this would be the most efficient way to handle digraphs/graphs.
Do you think this will work out or do you see any other way to handle these two types?
comment:6 in reply to: ↑ 5 ; followup: ↓ 8 Changed 6 years ago by
Yo !
Continuing our talk here I have a short question. The class definitions of a Graph and Digraph in bliss both contain the same functions add_edge(int i, int j) and change_color(int x, int c).
Now as far as I see *if* we patch bliss to make these two functions a (virtual) part of the abstract graph class then we could do something like
Oh. Well... It would be best to not patch anything in bliss, just in case they release a new version... You can add whatever code you need in the Sage code though.
But really if it is just to avoid some "if", perhaps that's going a bit far O_o
Nathann
comment:7 followup: ↓ 9 Changed 6 years ago by
Note: it would be cool to make bliss the default algorithm for the computation of automorphism group <when it is available>. Some other code call this graph automorphism code: we should of course add an optional flag there to ask those function to use bliss, but it could also help if it was used by default when available.
Just in case we forget it, from time to time. 'Cause I think that this code is really called from many obscure places in Sage.
Nathann
comment:8 in reply to: ↑ 6 Changed 6 years ago by
Replying to ncohen:
Yo !
Continuing our talk here I have a short question. The class definitions of a Graph and Digraph in bliss both contain the same functions add_edge(int i, int j) and change_color(int x, int c).
Now as far as I see *if* we patch bliss to make these two functions a (virtual) part of the abstract graph class then we could do something like
Oh. Well... It would be best to not patch anything in bliss, just in case they release a new version... You can add whatever code you need in the Sage code though.
But really if it is just to avoid some "if", perhaps that's going a bit far
O_o
Yes I am most likely overthinking it. Though with the if part we get an awful lot of duplicated (ugly). I guess there is some other way to make it nice while still being efficient  more to this when the actual branch is ready for review.
Best,
Jernej
Nathann
comment:9 in reply to: ↑ 7 ; followup: ↓ 10 Changed 6 years ago by
Replying to ncohen:
Note: it would be cool to make bliss the default algorithm for the computation of automorphism group <when it is available>. Some other code call this graph automorphism code: we should of course add an optional flag there to ask those function to use bliss, but it could also help if it was used by default when available.
I agree ! Let me first check how this performance thing works out for general graphs.
Just in case we forget it, from time to time. 'Cause I think that this code is really called from many obscure places in Sage.
Which code, the automorphism thing?
Nathann
comment:10 in reply to: ↑ 9 Changed 6 years ago by
Just in case we forget it, from time to time. 'Cause I think that this code is really called from many obscure places in Sage.
Which code, the automorphism thing?
Yep. I'd be surprised if all functions named "automorphism_group" in Sage don't redirect to that in the end.
Nathann
comment:11 Changed 6 years ago by
 Branch changed from u/azi/bliss to public/bliss
 Commit f8dcb7e4ffca76715b478ada498be1714e0f38f1 deleted
comment:12 Changed 6 years ago by
 Commit set to f8e2618b7b644a6bee364379405485a5c8468418
Branch pushed to git repo; I updated commit sha1. New commits:
343b145  trac #17552: Initial attempt at creating a SPKG for bliss

0e2d04f  trac #17552: review

b353d5f  trac #17552: Reviewing the review

6239dea  trac #17552: Added copying of headers to the include dir

7cb683c  trac #17552: Added move of "kqueue.hh" header to local/include

2222588  Cython wrapper example

9d56af3  trac #17464: First attempt at integrating bliss into sage

85ef58c  trac #17464: Added module_list as well

696590c  trac #17464: few modifications to the bliss wrapper

f8e2618  trac #17464: spliting graph/digraph creating function

comment:13 Changed 6 years ago by
The speedup looks promising. Just a quick preview :
sage: G = graphs.CubeGraph(4) sage: %timeit automorphism_group_bliss(G) 1000 loops, best of 3: 885 µs per loop sage: %timeit G.automorphism_group() 1000 loops, best of 3: 1.31 ms per loop
sage: G = graphs.GeneralizedPetersenGraph(250,2) sage: %timeit automorphism_group_bliss(G) 100 loops, best of 3: 7.21 ms per loop sage: %timeit G.automorphism_group() 10 loops, best of 3: 45.8 ms per loop
sage: G.order() sage: 9369 sage: t1 = time() ; A = automorphism_group_bliss(G); t2 = time() sage: t2t1 37.43013310432434 sage: t1 = time() ; A = G.automorphism_group(); t2 = time() # uses 50% of RAM sage: t2t1 624.5415680408478
Asymmetric graphs:
sage: G = graphs.RandomGNP(500,0.8) sage: %timeit G.automorphism_group() 1 loops, best of 3: 499 ms per loop sage: %timeit automorphism_group_bliss(G) 10 loops, best of 3: 163 ms per loop sage: G = graphs.RandomGNP(3300, 0.1) sage: %timeit automorphism_group_bliss(G) 1 loops, best of 3: 923 ms per loop sage: %timeit G.automorphism_group() 1 loops, best of 3: 6.49 s per loop
comment:14 Changed 6 years ago by
Looks good ! I'm eager to use this in my hypergraph computations :PPPP
Nathann
comment:15 Changed 6 years ago by
For the modules_list.py file: look in the same file for occurrences of "CPLEX" or "gurobi". They are also optional packages, and for optional packages you should first make sure that they are installed before asking Sage to compile the .pyx.
Nathann
comment:16 followup: ↓ 24 Changed 6 years ago by
Did this! Also tested your example from the other day.
A workable branch is now available at public/bliss2. I am having a mismatch trying to push it to public/bliss.
Before we change Graph.canonical_form,is_isomorphic,automorphism_group I suggest that we address the FIXME stuff in the bliss.pyx code.
Another "issue" that is not in the code is what are we to do with the heuristics. There are a few heuristics for bliss and we can make them as an available choice for Sage or just go ahead with the default one.
Let me know what you think,
Jernej
Ohh, and here is your bipartite graph example:
sage: t1 = time() ; A = automorphism_group_bliss(G); t2 = time() sage: t2t1 0.15731596946716309 sage: t1 = time() ; A = G.automorphism_group(); t2 = time() ....... indefinitely..............
comment:17 Changed 6 years ago by
 Branch changed from public/bliss to public/bliss2
 Commit changed from f8e2618b7b644a6bee364379405485a5c8468418 to 152b2eb748fa36b4306ac12d13433c6e9b741be3
 Status changed from needs_info to needs_work
New commits:
48805f5  Cython wrapper example

95dcb37  trac #17464: First attempt at integrating bliss into sage

50eb67f  trac #17464: Added module_list as well

076a55e  trac #17464: few modifications to the bliss wrapper

ebba1ae  trac #17464: spliting graph/digraph creating function

3e0caa8  trac #17552: Added move of "kqueue.hh" header to local/include

7fe9974  trac #17522: idk

152b2eb  trac #17464: Working version of bliss wrapper including isomorphism testing and computation of canonical forms.

comment:18 Changed 6 years ago by
Oh wow what a mess again...
comment:19 Changed 6 years ago by
 Branch changed from public/bliss2 to public/bliss
 Commit changed from 152b2eb748fa36b4306ac12d13433c6e9b741be3 to f8e2618b7b644a6bee364379405485a5c8468418
New commits:
7cb683c  trac #17552: Added move of "kqueue.hh" header to local/include

2222588  Cython wrapper example

9d56af3  trac #17464: First attempt at integrating bliss into sage

85ef58c  trac #17464: Added module_list as well

696590c  trac #17464: few modifications to the bliss wrapper

f8e2618  trac #17464: spliting graph/digraph creating function

comment:20 Changed 6 years ago by
Reverted back to the public/bliss branch, apparently I've pushed some old unrelated nonsesne...
comment:21 Changed 6 years ago by
 Commit changed from f8e2618b7b644a6bee364379405485a5c8468418 to 3c37cb81e7bfbc58f953035054dd4c30d0750880
Branch pushed to git repo; I updated commit sha1. New commits:
3c37cb8  trac #17464: First workable version of bliss

comment:22 Changed 6 years ago by
I think this last pushed branch should be good.
comment:23 Changed 6 years ago by
 Dependencies set to #17552
comment:24 in reply to: ↑ 16 ; followup: ↓ 25 Changed 6 years ago by
Yo !
Before we change Graph.canonical_form,is_isomorphic,automorphism_group I suggest that we address the FIXME stuff in the bliss.pyx code.
I am already writing some code at the moment and when I will be done I must go back to my blackboard. Is there is some specific question that you have for this patch please ask it, but if I begin to look at bliss' API, understand your code and answer the questions that you wrote inside it will probably take me as much time as writing the interface from scratch :P
Another "issue" that is not in the code is what are we to do with the heuristics. There are a few heuristics for bliss and we can make them as an available choice for Sage or just go ahead with the default one.
The current branch contains already many commits, and there are many things to pay attention to (we really don't want this code to return wrong results because of a typo) so it will probably be best to keep this branch to a minimum.
That does not mean that anything will have to be delayed: this branch will be sooner in positive_review
, and then you can expose those features in another ticket.
Good luck ! :P
Nathann
comment:25 in reply to: ↑ 24 ; followup: ↓ 26 Changed 6 years ago by
Replying to ncohen:
Yo !
Before we change Graph.canonical_form,is_isomorphic,automorphism_group I suggest that we address >the FIXME stuff in the bliss.pyx code.
I am already writing some code at the moment and when I will be done I must go back to my blackboard. Is there is some specific question that you have for this patch please ask it, but if I begin to look at bliss' API, understand your code and answer the questions that you wrote inside it will probably take me as much time as writing the interface from scratch
:P
Okay.
Sooo
 Bliss returns a list of automorphisms as bijections. There is a function inside the code that then in one pass creates the respective cycle notation for the permutation while also applying the labelling of the graph. We have Permutation.to_cycle() that does the job but only on integer valued bijections. As is I'd like to leave this function in bliss.pyx and then perhaps once labelled permutations are supported by to_cycle(), revert to that. The main reason being that I am using Sage on graphs with 700k vertices and its a pain to have to iterate over and over for the sake of labels.
 There is a very erratic bug using bliss on digraphs.
sage: D = digraphs.Kautz(10,2,1) sage: from sage.graphs.bliss import * sage: D.automorphism_group().is_isomorphic(automorphism_group(D)) True sage: D.automorphism_group().is_isomorphic(automorphism_group(D)) Bliss fatal error: Internal error  unknown splitting heuristics Aborting!
I have no clue why this is happening. Do you have any intuition as to where to look for the issue? The code for Graph/Digraph? that raises this exception is identical yet this only happens sporadically with digraphs.
As far as technical questions go, this are the main things I need some input about.
Best,
Jernej
Another "issue" that is not in the code is what are we to do with the heuristics. There are a few heuristics for bliss and we can make them as an available choice for Sage or just go ahead with the default one.
The current branch contains already many commits, and there are many things to pay attention to (we really don't want this code to return wrong results because of a typo) so it will probably be best to keep this branch to a minimum.
That does not mean that anything will have to be delayed: this branch will be sooner in
positive_review
, and then you can expose those features in another ticket.Good luck !
:P
Nathann
comment:26 in reply to: ↑ 25 ; followup: ↓ 27 Changed 6 years ago by
Yoooooo !
 Bliss returns a list of automorphisms as bijections.
Which are the automorphisms which generate the full automorphism group of the graph ?
There is a function inside the code that then in one pass creates the respective cycle notation for the permutation while also applying the labelling of the graph. We have Permutation.to_cycle() that does the job but only on integer valued bijections. As is I'd like to leave this function in bliss.pyx and then perhaps once labelled permutations are supported by to_cycle(), revert to that. The main reason being that I am using Sage on graphs with 700k vertices and its a pain to have to iterate over and over for the sake of labels.
+1 to that. It is not a very big amount of code, and one can never tell the amount of useless computations done by the Permutation
code anyway :P
 There is a very erratic bug using bliss on digraphs.
I have no clue why this is happening. Do you have any intuition as to where to look for the issue? The code for Graph/Digraph? that raises this exception is identical yet this only happens sporadically with digraphs.
But can it happen the first time you call the code, or only after several attempts ? This looks like a memory leak problem... Unless it is a bug in bliss O_o
Actually, reading the code a bit, I am totally scared by how you cast Python objects like the two dictionaries to a bliss function. It expects C arrays, and you give it a pointer to a Python dictionary ? O_o;;;;
Nathann
comment:27 in reply to: ↑ 26 Changed 6 years ago by
Replying to ncohen:
Yoooooo !
 Bliss returns a list of automorphisms as bijections.
Which are the automorphisms which generate the full automorphism group of the graph ?
Yes, each time bliss discovers an automorphism it calls this function to handle it.
There is a function inside the code that then in one pass creates the respective cycle notation for the permutation while also applying the labelling of the graph. We have Permutation.to_cycle() that does the job but only on integer valued bijections. As is I'd like to leave this function in bliss.pyx and then perhaps once labelled permutations are supported by to_cycle(), revert to that. The main reason being that I am using Sage on graphs with 700k vertices and its a pain to have to iterate over and over for the sake of labels.
+1 to that. It is not a very big amount of code, and one can never tell the amount of useless computations done by the
Permutation
code anyway:P
Exactly:D
 There is a very erratic bug using bliss on digraphs.
I have no clue why this is happening. Do you have any intuition as to where to look for the issue? The code for Graph/Digraph? that raises this exception is identical yet this only happens sporadically with digraphs.
But can it happen the first time you call the code, or only after several attempts ? This looks like a memory leak problem... Unless it is a bug in bliss
O_o
Yes it can happen on first try as well!!
Actually, reading the code a bit, I am totally scared by how you cast Python objects like the two dictionaries to a bliss function. It expects C arrays, and you give it a pointer to a Python dictionary ?
O_o;;;;
No I am sure I am not doing this. The argument there is a just a void pointer that bliss then passes on to your function.
Soo bliss takes a function pointer to YOUR function and a pointer to YOUR data. And then it calls YOUR function passing it YOUR void pointer.
So that should be fine I suppose?
Nathann
comment:28 followup: ↓ 29 Changed 6 years ago by
Ohh and another reason why it may not be related to this wrapper is the fact that the same error is occuring with canonical_form which actually does not involve using this pointers/functions thing.
sage: from sage.graphs.bliss import * sage: D = digraphs.Kautz(10,1,2) sage: canonical_form(D) Bliss fatal error: Internal error  unknown splitting heuristics Aborting!
comment:29 in reply to: ↑ 28 ; followup: ↓ 30 Changed 6 years ago by
Yo !
Ohh and another reason why it may not be related to this wrapper is the fact that the same error is occuring with canonical_form which actually does not involve using this pointers/functions thing.
True. HMmmmmmm... O_o
Well, I looked at the code for a while and I really don't see anything that could produce that.... Short of a bliss bug... O_o
Nathann
comment:30 in reply to: ↑ 29 Changed 6 years ago by
Replying to ncohen:
Yo !
Ohh and another reason why it may not be related to this wrapper is the fact that the same error is occuring with canonical_form which actually does not involve using this pointers/functions thing.
True. HMmmmmmm...
O_o
Well, I looked at the code for a while and I really don't see anything that could produce that.... Short of a bliss bug...
O_o
Yeah.. I'll try to reproduce it in bliss directly.
Nathann
comment:31 Changed 6 years ago by
Looks really weird.
I am waiting to figure out how can I be able to force a certain heuristic to be used because the behaviour right now is just sick. I've changed the "hook function" to an empty function (not doing any work) and its still messy:
sage: D = digraphs.Kautz(10,3,2) sage: from sage.graphs.bliss import * sage: automorphism_group(D) Permutation Group with generators [()] sage: automorphism_group(D) Permutation Group with generators [()] sage: automorphism_group(D) Permutation Group with generators [()] sage: automorphism_group(D) Permutation Group with generators [()] sage: automorphism_group(D) Bliss fatal error: Internal error  unknown splitting heuristics Aborting!
if G is a graph then
while True: A = automorphism_group(G)
works well. :O
comment:32 Changed 6 years ago by
 Commit changed from 3c37cb81e7bfbc58f953035054dd4c30d0750880 to cad441ec9fcfa114fc481411e949557845c45ab5
Branch pushed to git repo; I updated commit sha1. New commits:
cad441e  trac #17464: Added documentation and some cleanups

comment:33 followup: ↓ 34 Changed 6 years ago by
Okay, for *now* a working fix is to change the line in bliss that declares the splitting heuristics to include an assignment:
846 SplittingHeuristic sh = shs_flm;
Since this is not done for graphs it makes all of this very suspicious but it works.
I've also talked with the author of bliss who confirmed this is an actually bug that he'll address in an upcoming release of bliss. In the meantime he says the above is a valid fix.
That said, I think it makes sense to see what is to be done to push this branch further? I have added some small documentation and would like to hear any kind of input that you may have.
Best,
Jernej
comment:34 in reply to: ↑ 33 ; followup: ↓ 35 Changed 6 years ago by
Yooooooooo !
Since this is not done for graphs it makes all of this very suspicious but it works.
I've also talked with the author of bliss who confirmed this is an actually bug that he'll address in an upcoming release of bliss. In the meantime he says the above is a valid fix.
Oh, excellent news !
That said, I think it makes sense to see what is to be done to push this branch further?
First, it would be really good to have the 'spkg' ticket in positive_review
. Jeroen set it back to needs_work
recently, and now you have something else to add to it: the patch to change this line.
Now, you cannot modify upstream directly (i.e. the .tar.bz2 file) so you must use the 'patch' mechanism that is already being used in build/pkgs/sympy (for example). Look at the sympy/spkginstall file and the patches/ folder. The corresponding doc is there:
http://www.sagemath.org/doc/developer/packaging.html#patchingsources
I have added some small documentation and would like to hear any kind of input that you may have.
Well, it seems that you still have some notes to yourself in the branch. Those that you cannot solve right now should probably appear in the documentation of the function to which they apply, and not at module level. (note: you can write a docstring in C functions. It will not appear as html do of course, but that's the right place to write the function's doc.)
In particular you have some formatting to do (a)length of lines b) the first line of doc is a oneline sentence describing the function.
You can also add the mechanism that makes GenericGraph?.automorphism_group use bliss if available by default (set algorithm=None by default, and if algorithm is None and is_package_installed("bliss")
then ...) if you like, otherwise I will do it at some point.
There is also this in the code
+ if algorithm == "bliss": + print 'yes' + return
But really that's just cleaning. Short of that I do not think that there is anything important missing.
Oh, by the way: I do not think that you should really carry those vert2int or int2vert around. You could just say somewhere that the integer names of the vertices are those obtained by the ordering of g.vertices()
Then defining the two dictionaries is rather easy
int2verts = g.vertices() vert2int = {v:i for i,v in enumerate(int2verts)}
Well, that's all. Only "code administration" ^^;
Nathann
comment:35 in reply to: ↑ 34 ; followup: ↓ 36 Changed 6 years ago by
Replying to ncohen:
Yooooooooo !
Since this is not done for graphs it makes all of this very suspicious but it works.
I've also talked with the author of bliss who confirmed this is an actually bug that he'll address in an upcoming release of bliss. In the meantime he says the above is a valid fix.
Oh, excellent news !
That said, I think it makes sense to see what is to be done to push this branch further?
First, it would be really good to have the 'spkg' ticket in
positive_review
. Jeroen set it back toneeds_work
recently, and now you have something else to add to it: the patch to change this line.Now, you cannot modify upstream directly (i.e. the .tar.bz2 file) so you must use the 'patch' mechanism that is already being used in build/pkgs/sympy (for example). Look at the sympy/spkginstall file and the patches/ folder. The corresponding doc is there:
http://www.sagemath.org/doc/developer/packaging.html#patchingsources
I have added some small documentation and would like to hear any kind of input that you may have.
I think it would be good to mention how the patch is created since there may be different parameters to diff and also since we like to just copy paste stuff and not think too much.
Well, it seems that you still have some notes to yourself in the branch. Those that you cannot solve right now should probably appear in the documentation of the function to which they apply, and not at module level. (note: you can write a docstring in C functions. It will not appear as html do of course, but that's the right place to write the function's doc.)
In particular you have some formatting to do (a)length of lines b) the first line of doc is a oneline sentence describing the function.
You can also add the mechanism that makes GenericGraph?.automorphism_group use bliss if available by default (set algorithm=None by default, and
if algorithm is None and is_package_installed("bliss")
then ...) if you like, otherwise I will do it at some point.There is also this in the code
+ if algorithm == "bliss": + print 'yes' + return
Yes, I'll make bliss the default the above was just a test. Though I we should really test this thoroughly since it can get messy if we leave a bug inside.. I spotted one before. Considering
return PermutationGroup(gens)
everything works well most of the time (since in all tested graphs every vertex appears in some cycle of the generator). But if you do not specify the domain you may get automorphism groups not acting on all the required points...
But really that's just cleaning. Short of that I do not think that there is anything important missing.
Oh, by the way: I do not think that you should really carry those vert2int or int2vert around. You could just say somewhere that the integer names of the vertices are those obtained by the ordering of
g.vertices()
Then defining the two dictionaries is rather easy
int2verts = g.vertices() vert2int = {v:i for i,v in enumerate(int2verts)}
Yes that's right. What made me choose the present version is the fact that the second line is already a for loop over the vertices and from how I understand g.vertices() that always involves a loop as well (at least to get the labels of the graph, grrr)?
Well, that's all. Only "code administration"
^^;
Thanks.
Nathann
Jernej
comment:36 in reply to: ↑ 35 Changed 6 years ago by
I think it would be good to mention how the patch is created since there may be different parameters to diff and also since we like to just copy paste stuff and not think too much.
Well, open a ticket and add the explanation. Sage's doc is changed exactly like the code is :P
Yes that's right. What made me choose the present version is the fact that the second line is already a for loop over the vertices and from how I understand g.vertices() that always involves a loop as well (at least to get the labels of the graph, grrr)?
I do not think that the time difference is anything but negligible there. Plus a "loop" does not cost anything by itself, it depends on what you loop I expect. If the loop involves many calls to .next()
or something it may cost more than doing the same on a simple list, I don't know..
Nathann
comment:37 Changed 6 years ago by
 Commit changed from cad441ec9fcfa114fc481411e949557845c45ab5 to 6679f16ab3db644a285ed8706eafa587eafee4a3
Branch pushed to git repo; I updated commit sha1. New commits:
6679f16  trac #17464: Added calls from generic_graph to bliss

comment:38 followup: ↓ 39 Changed 6 years ago by
First of all happy new year and stuff!!!!
I've now pushed the latest branch for bliss but I am having a problem since when I do sage t generic_graph.py it keeps saying
def is_vertex_transitive(self, partition=None, verbosity=0, ^ IndentationError: unindent does not match any outer indentation level
and I and vim's :list are just blind... (dont' see it)
Do you happen to see where the indentation breaks and do you happen to have any new comments about the current code? I think it should be pretty near to what it should look like.
comment:39 in reply to: ↑ 38 ; followup: ↓ 41 Changed 6 years ago by
Yop !
First of all happy new year and stuff!!!!
+1
and I and vim's :list are just blind... (dont' see it)
What I don't like about "def canonical_label(..." is that the doc appears BEFORE the function's definition. Could it be that ?
do you happen to have any new comments about the current code?
Well, definitely there is something wrong in automorphism_group
, where you define a keyword algorithm
but never read it. Then you should probably add a couple of new doctests using bliss (with an #optional flag) in the function from generic_graph
. Whatever you do with this function's input, you should probably do the same in the similar functions btw: canonical_label
, and is_isomorphic
.
Also, it looks like the test that you run in is_isomorphic
(number of edges/vertices) already appear a bit later in the code. No reason to have them appear twice.
There is still this line which has nothing to do here
+ :meth:`~GenericGraph.geodetic_number`  Returns the geodetic number of the given graph.
Oh, and several lines are still longer than 80chr, and we try to wrap them because ...
Because somebody said that we had to.
Nathann
comment:40 Changed 6 years ago by
 Commit changed from 6679f16ab3db644a285ed8706eafa587eafee4a3 to aed44e8dd39982907467b6e0d699f9def062f1af
Branch pushed to git repo; I updated commit sha1. New commits:
aed44e8  trac #17464: Made some changes as reviewer suggested

comment:41 in reply to: ↑ 39 ; followup: ↓ 42 Changed 6 years ago by
Replying to ncohen:
What I don't like about "def canonical_label(..." is that the doc appears BEFORE the function's definition. Could it be that ?
That surely didn't help but the error still persists :S I have no idea where the mismatch is.
Well, definitely there is something wrong in
automorphism_group
, where you define a keywordalgorithm
but never read it.
Yes I was following your advice from above which was to add a condition of the form
if algorithm is None and is_package_installed("bliss") :
since we only offer two algorithms for now this works fine, perhaps provided that we write the option algorithm="nice" to indicate the currently default implementation? What do you suggest?
Then you should probably add a couple of new doctests using bliss (with an #optional flag) in the function from >
generic_graph
. Whatever you do with this function's input, you should probably do the same in the similar functions btw: >canonical_label
, andis_isomorphic
.
Is it not enough to have them in bliss.pyx? If not, then I'll add some doctests when we agree on the technical aspects of the code
Also, it looks like the test that you run in
is_isomorphic
(number of edges/vertices) already appear a bit later in the code. No reason to have them appear twice.
fixed
There is still this line which has nothing to do here
+ :meth:`~GenericGraph.geodetic_number`  Returns the geodetic number of the given graph.
fixed
Oh, and several lines are still longer than 80chr, and we try to wrap them because ...
80chr is quite tight :O Also have you noticed that there appears to be some indentation inconsistency in the code? It looks like the functions on the bottom (example def graph_isom_equivalent_non_edge_labeled_graph) are not indented as the above ones?
Thanks for the input,
Jernej
comment:42 in reply to: ↑ 41 ; followup: ↓ 44 Changed 6 years ago by
Hello !
That surely didn't help but the error still persists :S I have no idea where the mismatch is.
Right now when I run the tests on generic_graph
I get several screens filled with "is_package_installed is not defined".
Yes I was following your advice from above which was to add a condition of the form
if algorithm is None and is_package_installed("bliss") :since we only offer two algorithms for now this works fine, perhaps provided that we write the option algorithm="nice" to indicate the currently default implementation? What do you suggest?
And what happens when you do G.automorphism_group(algorithm="bliss")
as indicated in the function's doc ? :P
Is it not enough to have them in bliss.pyx? If not, then I'll add some doctests when we agree on the technical aspects of the code
That would be for advertising purposes. Just one would do, just to emphasize that another algorithm is available.
80chr is quite tight :O
As usual it is some PEP's fault. It probably is PEP8. It is always PEP8's fault.
Also have you noticed that there appears to be some indentation inconsistency in the code? It looks like the functions on the bottom (example def graph_isom_equivalent_non_edge_labeled_graph) are not indented as the above ones?
Oh ? No, I never saw that. Well, some hardcore PEP8 guy will probably change it some day.
Nathann
comment:43 Changed 6 years ago by
 Commit changed from aed44e8dd39982907467b6e0d699f9def062f1af to 1d7afae64c538d1a6a0ffdec31275a65969f2068
Branch pushed to git repo; I updated commit sha1. New commits:
1d7afae  Please enter the commit message for your changes. Lines starting

comment:44 in reply to: ↑ 42 ; followup: ↓ 45 Changed 6 years ago by
Replying to ncohen:
Hello !
Hai!!
And what happens when you do
G.automorphism_group(algorithm="bliss")
as indicated in the function's doc ?:P
OFC it has no sense but I was just following the guideline. I've now changed that so that we check that algorithm = 'bliss' explicitly. In case you have something else in mind let me know.
That would be for advertising purposes. Just one would do, just to emphasize that another algorithm is available.
Advertisement added.
80chr is quite tight :O
As usual it is some PEP's fault. It probably is PEP8. It is always PEP8's fault.
Its also pretty funny that 90% of the lines are 100% over 80 char.
The current code passes all the tests and I am open for further suggestions.
As far as the empty commit message that is due to a mismatch of vim commands in nano.
Nathann
Best, Jernej
comment:45 in reply to: ↑ 44 ; followup: ↓ 46 Changed 6 years ago by
Hello !
OFC it has no sense but I was just following the guideline. I've now changed that so that we check that algorithm = 'bliss' explicitly. In case you have something else in mind let me know.
Oh sorry, I was thinking of something different:
1) We want the users who explicitly ask for "bliss" to never run any other code 2) We want users who do not care to run "bliss" if it is available (they may be calling that code through another functions without knowing)
if (algorithm is None and is_package_installed("bliss") and not edge_labels): algorithm = "bliss" if algorithm == "bliss": try: from sage.graphs.bliss import is_isomorphic except ImportError: raise RuntimeError("You must install the bliss spkg before running this code") <bliss call>
The current code passes all the tests and I am open for further suggestions.
Could you move the code comments that explain the function's behaviour inside of the function ? As you would do if it were a Python function (e.g. bliss_graph/bliss_digraph, add_gen) ? It would be cool if you could also write the documentation of these functions (e.g. INPUT section), even though you cannot doctest them.
Could you also document what empty_hook
is meant for ? It is useless right now but it would be good to know what it does if we ever want to use it for something (and that's the kind of stuff which can become *VERY* useful). Please document its parameters too.
Thanks,
Nathann
comment:46 in reply to: ↑ 45 ; followup: ↓ 47 Changed 6 years ago by
Replying to ncohen:
Hello !
OFC it has no sense but I was just following the guideline. I've now changed that so that we check that algorithm = 'bliss' explicitly. In case you have something else in mind let me know.
Oh sorry, I was thinking of something different:
1) We want the users who explicitly ask for "bliss" to never run any other code 2) We want users who do not care to run "bliss" if it is available (they may be calling that code through another functions without knowing)
if (algorithm is None and is_package_installed("bliss") and not edge_labels): algorithm = "bliss" if algorithm == "bliss": try: from sage.graphs.bliss import is_isomorphic except ImportError: raise RuntimeError("You must install the bliss spkg before running this code") <bliss call>
And this is to be placed in the say is_isomorphic/automorphism_group part and so on? If so, isn't this a bit of an overhead to be checked each time?
The current code passes all the tests and I am open for further suggestions.
Could you move the code comments that explain the function's behaviour inside of the function ? As you would do if it were a Python function (e.g. bliss_graph/bliss_digraph, add_gen) ? It would be cool if you could also write the documentation of these functions (e.g. INPUT section), even though you cannot doctest them.
Thanks. I'll do it and post a new branch when I am done.
Could you also document what
empty_hook
is meant for ? It is useless right now but it would be good to know what it does if we ever want to use it for something (and that's the kind of stuff which can become *VERY* useful). Please document its parameters too.
Best,
Jernej
Thanks,
Nathann
comment:47 in reply to: ↑ 46 Changed 6 years ago by
Yo !
And this is to be placed in the say is_isomorphic/automorphism_group part and so on? If so, isn't this a bit of an overhead to be checked each time?
Are you afraid of the call to is_package_installed
? If so, it may not be a bad option to cache it at module level. Something like a "is_bliss_available = is_package_installed("bliss")" in generic_graph.py
. It would only be loaded when the graph files are loaded first.
Nathann
comment:48 Changed 6 years ago by
sage: %timeit is_package_installed("bliss") 1000000 loops, best of 3: 1.61 µs per loop sage: g=graphs.PetersenGraph() sage: %timeit g.is_isomorphic(g) 1000 loops, best of 3: 171 µs per loop sage: %timeit g.automorphism_group() 1000 loops, best of 3: 483 µs per loop sage: %timeit g.canonical_label() 1000 loops, best of 3: 271 µs per loop
Perhaps it is not even worth that... :P
Nathann
comment:49 Changed 6 years ago by
 Commit changed from 1d7afae64c538d1a6a0ffdec31275a65969f2068 to a539b9953f9d8ccbbda67fc5b60a9372079a3eaf
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a539b99  trac #17464: Graph automorphism groups through bliss

comment:50 Changed 6 years ago by
 Summary changed from Computing the automorphism group of a graph to Computing the automorphism group of a graph with Bliss
(I merged all commits together as the history was a bit messy. It also conflicted with the latest beta)
comment:51 Changed 6 years ago by
 Commit changed from a539b9953f9d8ccbbda67fc5b60a9372079a3eaf to 7e6edd0ecf50e7d75876b619a9495c8f57b92971
Branch pushed to git repo; I updated commit sha1. New commits:
7e6edd0  trac #17464: Make IncidenceStructure.automorphism_group call Graph.automorphism_group

comment:52 followup: ↓ 54 Changed 6 years ago by
Hello again !
I made a pass on this code, added some doc, fixed a few things and... Well, now I only have a couple of questions about this branch:
 What about implementing bliss' version of
is_isomorphic
later ? The feature that we need right now isautomorphism_group
(I needed it today, the difference is amazing!), so can't the rest be done later if we need it ? By the way, I never had any slowness problem withis_isomorphic
(orcanonical_label
) that I can remember.
 It seems that the
Bliss fatal error: Internal error  unknown splitting heuristics
problem is not solved. I see it happen when I run the tests in the graph/ folder.
 I changed the code to list the vertices according to
enumerate(G.vertices())
instead ofenumerate(G)
. We have this standard in other places that when vertices are turned into integers, it is done using the ordering ofG.vertices()
.
Tell me what you think ! I would be glad to have this into Sage soon ;)
Nathann
comment:53 Changed 6 years ago by
 Commit changed from 7e6edd0ecf50e7d75876b619a9495c8f57b92971 to 60018569126f690eda0b417f5fec1485904c59ed
Branch pushed to git repo; I updated commit sha1. New commits:
6001856  trac #17464: Additional documentation

comment:54 in reply to: ↑ 52 ; followup: ↓ 55 Changed 6 years ago by
Replying to ncohen:
Hello again !
Hi there!
I made a pass on this code, added some doc, fixed a few things and... Well, now I only have a couple of questions about this branch:
 What about implementing bliss' version of
is_isomorphic
later ? The feature that we need right now isautomorphism_group
(I needed it today, the difference is amazing!), so can't the rest be done later if we need it ? By the way, I never had any slowness problem withis_isomorphic
(orcanonical_label
) that I can remember.
Hm.. I need these things, especially canonical_label. Do you have any practical reasons to leave this out? I mean it doesn't look like it needs that much effort at this point.
 It seems that the
Bliss fatal error: Internal error  unknown splitting heuristics
problem is not solved. I see it happen when I run the tests in the graph/ folder.
Weird. Are you sure you're using the patched version of bliss?
 I changed the code to list the vertices according to
enumerate(G.vertices())
instead ofenumerate(G)
. We have this standard in other places that when vertices are turned into integers, it is done using the ordering ofG.vertices()
.
good, thanks!
Tell me what you think ! I would be glad to have this into Sage soon
;)
I just have another question! Is the new add_gen function faster than before? Do you think it makes sense to try using the suggestion from here ? http://stackoverflow.com/questions/27657473/efficientlyconvertingabijectiontocyclenotation
Nathann
comment:55 in reply to: ↑ 54 ; followup: ↓ 57 Changed 6 years ago by
Hello,
Hm.. I need these things, especially canonical_label. Do you have any practical reasons to leave this out? I mean it doesn't look like it needs that much effort at this point.
Well, there is no reason to leave canonical_label
out, even though I don't get why the current canonical label function from Sage wouldn't do the job for you.
It was more about the is_isomorphic
function that is not fully implemented. I wouldn't mind having this patch in Sage quick, and report the implementation of that to another ticket.
Weird. Are you sure you're using the patched version of bliss?
I just made a test:
 Loaded the branch
 Checked that the branch contained the patches/ directory
 erased my local copy of the bliss.tar file
 installed it again
Same result when I run "sage tp 4 l generic_graph.py". Don't you get the same errors ?
I just have another question! Is the new add_gen function faster than before? Do you think it makes sense to try using the suggestion from here ? http://stackoverflow.com/questions/27657473/efficientlyconvertingabijectiontocyclenotation
Ahahah. Well, his algorithm is short, I like it :)
It's up to you. I do not think that it is the bottleneck of any computations, so to me 'the easiest to read is the best choice'
Nathann
comment:56 Changed 6 years ago by
btw: the doc does not compile on my computer because of some broken link
Nathann
comment:57 in reply to: ↑ 55 ; followup: ↓ 58 Changed 6 years ago by
Replying to ncohen:
Hello,
Hm.. I need these things, especially canonical_label. Do you have any practical reasons to leave this out? I mean it doesn't look like it needs that much effort at this point.
Well, there is no reason to leave
canonical_label
out, even though I don't get why the current canonical label function from Sage wouldn't do the job for you.
It was more about the
is_isomorphic
function that is not fully implemented. I wouldn't mind having this patch in Sage quick, and report the implementation of that to another ticket.
Okay. We can leave this is_isomorphic thing for next time.
Weird. Are you sure you're using the patched version of bliss?
I just made a test:
 Loaded the branch
 Checked that the branch contained the patches/ directory
 erased my local copy of the bliss.tar file
 installed it again
Same result when I run "sage tp 4 l generic_graph.py". Don't you get the same errors ?
Oh, yes I do get the errors as well. What do you suggest that we do at this point?
I just have another question! Is the new add_gen function faster than before? Do you think it makes sense to try using the suggestion from here ? http://stackoverflow.com/questions/27657473/efficientlyconvertingabijectiontocyclenotation
Ahahah. Well, his algorithm is short, I like it
:)
Yeah.
It's up to you. I do not think that it is the bottleneck of any computations, so to me 'the easiest to read is the best choice'
Unless you find his supercool I'd like to stay with what is already there since otherwise I have to understand how his code works. His solution is faster though.
Best,
Jernej
Nathann
comment:58 in reply to: ↑ 57 ; followup: ↓ 59 Changed 6 years ago by
Yo !
Oh, yes I do get the errors as well. What do you suggest that we do at this point?
Can you report this to the author again? The bug is not fixed, perhaps he will find the problem.
Unless you find his supercool I'd like to stay with what is already there since otherwise I have to understand how his code works. His solution is faster though.
No problem, as you like. What he implemented is exactly the same algorithm, however. He just makes it shorter by using fancier pyhon. I think that in C his algorithm would be slower than yours, but not in Python ;)
Nathann
comment:59 in reply to: ↑ 58 ; followup: ↓ 60 Changed 6 years ago by
Replying to ncohen:
Yo !
Oh, yes I do get the errors as well. What do you suggest that we do at this point?
Can you report this to the author again? The bug is not fixed, perhaps he will find the problem.
Yes sure. I am in correspondence with him and I am waiting for his reply right now. So before I flood him with this new email I'd like to wait for his answer.
In the meantime I'd like to push this thing further without having to wait for his fix/reply.
One way we could try is to call Digraph::set_heuristic or something. Though I was not able to make it work in cython due to some enum typedefs issue.
So what do you suggest that we do? Just avoid digraphs for now?
Unless you find his supercool I'd like to stay with what is already there since otherwise I have to understand how his code works. His solution is faster though.
No problem, as you like. What he implemented is exactly the same algorithm, however. He just makes it shorter by using fancier pyhon. I think that in C his algorithm would be slower than yours, but not in Python
;)
We can leave the code as is then!
As far as I get the current state of affairs, we need to
 Leave out the is_isomorphic thing
 Find a workaround for the digraph thing.
and then we are almost done?
Best,
Jernej
comment:60 in reply to: ↑ 59 Changed 6 years ago by
Hello,
So what do you suggest that we do? Just avoid digraphs for now?
Let's wait for his answer. It would be a pity to miss digraphs just because of that. He may know how to fix it.
We can leave the code as is then!
Yepyep
As far as I get the current state of affairs, we need to
 Leave out the is_isomorphic thing
 Find a workaround for the digraph thing.
and then we are almost done?
Right !
Nathann
comment:61 Changed 6 years ago by
 Commit changed from 60018569126f690eda0b417f5fec1485904c59ed to 97bb760e17aefff7c9004bcad17409627d94e99d
Branch pushed to git repo; I updated commit sha1. New commits:
97bb760  Added correct fix for digraph's missing heuristic

comment:62 Changed 6 years ago by
I think this patch now fixes the digraph issue.
We now have new test failures and I am looking into them right now.
Let me know if this patch is not correctly handled or something.
comment:63 followup: ↓ 64 Changed 6 years ago by
Okay, so all the failures now are of the form
Expected: [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]] Got: [[0, 1, 4, 2, 5, 6, 3, 9, 7, 8]] ....blahblah... Expected: [[0], [2, 3, 6, 7, 8, 9], [1, 4, 5]] Got: [[0], [1, 4, 5], [2, 3, 7, 8, 9, 6]]
now if I correct this to the bliss output it won't work on those installations that do not have bliss.
Do you have any preferences how to handle that?
comment:64 in reply to: ↑ 63 Changed 6 years ago by
Do you have any preferences how to handle that?
Do you have many of them? If not, perhaps you can solve the problem by just changing the doctests to add an 'algorithm="sage"' flag.
Nathann
comment:65 followup: ↓ 67 Changed 6 years ago by
Ohh I didn't notice you included that. I think this new fix does it. All tests pass now.
comment:66 Changed 6 years ago by
 Commit changed from 97bb760e17aefff7c9004bcad17409627d94e99d to 9a84f54d2877fa89083dfade62c5ff243f4bca31
Branch pushed to git repo; I updated commit sha1. New commits:
9a84f54  Fixed test cases so that all tests pass.

comment:67 in reply to: ↑ 65 Changed 6 years ago by
Yo!
Ohh I didn't notice you included that. I think this new fix does it. All tests pass now.
Looks good. Can you remove the is_isomorphic
code? I think that it is all that remains to be done here.
Nathann
comment:68 Changed 6 years ago by
sage t long tutte_polynomial.py # 2 doctests failed
comment:69 Changed 6 years ago by
 Commit changed from 9a84f54d2877fa89083dfade62c5ff243f4bca31 to 2942c3136ffad17f490b55cd83421c70c05ff46a
Branch pushed to git repo; I updated commit sha1. New commits:
2942c31  Removed is_isomorphic

comment:70 Changed 6 years ago by
Yeah I have only tested this thing on generic_graph.py.
I guess we must be really careful to check all the places this guys are called.
I'll check now a bit...
comment:71 Changed 6 years ago by
 Commit changed from 2942c3136ffad17f490b55cd83421c70c05ff46a to 2018dbc040e23bfafc873af17adc75f699a175cc
Branch pushed to git repo; I updated commit sha1. New commits:
2018dbc  Fixed error related to the new way of computing automorphisms.

comment:72 followup: ↓ 73 Changed 6 years ago by
I've fixed the error in Tutte poly but there is another depreciation warning that gets triggered due to loops not being explicitly specified. Do you happen to know what is causing this?
comment:73 in reply to: ↑ 72 Changed 6 years ago by
I've fixed the error in Tutte poly
It will break on a machine that does not have bliss
installed.
but there is another depreciation warning that gets triggered due to loops not being explicitly specified. Do you happen to know what is causing this?
I would say that it come from there
+ G = DiGraph(edges) + else: + from sage.graphs.graph import Graph + G = Graph(edges)
Nathann
comment:74 Changed 6 years ago by
 Commit changed from 2018dbc040e23bfafc873af17adc75f699a175cc to cac03d7f9ce6ee3de47ad48f46a9118fb0c72083
Branch pushed to git repo; I updated commit sha1. New commits:
cac03d7  Made sure canonical labels are computed with Sage's algorithm

comment:75 followup: ↓ 76 Changed 6 years ago by
Okay,
so now all doctest pass except for the loops thing in Tutte poly. I don't seem to be able to find the line that you mention. In which file is this present?
comment:76 in reply to: ↑ 75 Changed 6 years ago by
so now all doctest pass except for the loops thing in Tutte poly. I don't seem to be able to find the line that you mention. In which file is this present?
Oops, sorry. It is a line added by your branch, in the function canonical_form
.
Nathann
comment:77 Changed 6 years ago by
Jernej, you cannot make the computation of tutte polynomials avoid bliss only because of a doctest.
The doctest should be changed to be independent from the solver, or flagged as #random, or you should expose 'algorithm="sage/bliss"' in the tutte polynomial function... I mean, there are many workaround possible but you can't explicitly forbid people to use bliss for such computations only because of a doctest.
Nathann
comment:78 followup: ↓ 79 Changed 6 years ago by
Hm.. I am confused.
What I *think* I did is simply made sure the Tutte program uses sage's algorithm so that the test passes on installations not having bliss installed.
As I understand you'd like to have a new parameter for the tutte poly to use bliss?
comment:79 in reply to: ↑ 78 ; followup: ↓ 80 Changed 6 years ago by
What I *think* I did is simply made sure the Tutte program uses sage's algorithm so that the test passes on installations not having bliss installed.
Yes. But as you changed Sage's source code and not only its doctests, now tutte_polynomial
will never be able to use bliss even if it is installed.
As I understand you'd like to have a new parameter for the tutte poly to use bliss?
That is one way out. Another way out is to remove the doctest if it is not actually necessary, or to modify it in such a way that it still tests what it should test, without actually printing the ordering that may depend upon the packages installed.
Nathann
comment:80 in reply to: ↑ 79 ; followup: ↓ 83 Changed 6 years ago by
Replying to ncohen:
What I *think* I did is simply made sure the Tutte program uses sage's algorithm so that the test passes on installations not having bliss installed.
Yes. But as you changed Sage's source code and not only its doctests, now
tutte_polynomial
will never be able to use bliss even if it is installed.
Right, good point!
As I understand you'd like to have a new parameter for the tutte poly to use bliss?
That is one way out. Another way out is to remove the doctest if it is not actually necessary, or to modify it in such a way that it still tests what it should test, without actually printing the ordering that may depend upon the packages installed.
Unless you start raving I'll just remove the specific doctest  I don't think its releant.
Thanks,
Jernej
Nathann
comment:81 Changed 6 years ago by
 Commit changed from cac03d7f9ce6ee3de47ad48f46a9118fb0c72083 to c68235bf3c18d02dbfa17c92578f70a71a251b32
Branch pushed to git repo; I updated commit sha1. New commits:
c68235b  Removed (trivial) doctest complicating bliss integration

comment:82 Changed 6 years ago by
 Commit changed from c68235bf3c18d02dbfa17c92578f70a71a251b32 to acdbae661e84bad3953dd6260d2edb2aeb9719ea
comment:83 in reply to: ↑ 80 Changed 6 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_work to needs_review
Hello again,
Unless you start raving I'll just remove the specific doctest  I don't think its releant.
Err. Well, actually you can't just remove all doctests of a function. sage coverage <filename>
should answer that all functions are doctested, so at least something should call the function. I added a small commit that modified the previous doctest, in such a way that it does not depend on the ordering of the labelling.
It does not check much to be honest, only that something actually gets cached. Well.
If you are okay with this branch, you can set it to positive review. And we will at long last be able to compute automorphism groups efficiently.
Nathann
comment:84 Changed 6 years ago by
 Commit changed from acdbae661e84bad3953dd6260d2edb2aeb9719ea to b03b2b90d27d1511f111730dfcb8eb7eba7b54fa
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b03b2b9  trac #17464: Review

comment:85 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:86 Changed 6 years ago by
Thanks for helping pushing this through.I hope all is set now.
Best,
Jernej
comment:87 Changed 6 years ago by
Eeeeeeeeeeeeexcellent ! ;)
Nathann
comment:88 Changed 6 years ago by
 Status changed from positive_review to needs_work
Documentation doesn't build
comment:89 Changed 6 years ago by
 Commit changed from b03b2b90d27d1511f111730dfcb8eb7eba7b54fa to 09ec0494fa9b2e6f4b9dd9154a570cdd04cfb594
Branch pushed to git repo; I updated commit sha1. New commits:
09ec049  trac #17464: Broken doc

comment:90 Changed 6 years ago by
 Status changed from needs_work to positive_review
comment:91 Changed 6 years ago by
 Status changed from positive_review to needs_work
I get
... sage: G = Graph(multiedges=True,sparse=True) ## line 17388 ## sage: G.add_edge(('a', 'b')) ## line 17389 ## sage: G.add_edge(('a', 'b')) ## line 17390 ## sage: G.add_edge(('a', 'b')) ## line 17391 ## sage: G.automorphism_group() ## line 17392 ## Permutation Group with generators [('a','b')] sage: D = DiGraph( { 0:[1], 1:[2], 2:[3], 3:[4], 4:[0] } ) ## line 17397 ## sage: D.automorphism_group() ## line 17398 ## Bliss fatal error: Internal error  unknown splitting heuristics Aborting!
comment:92 Changed 6 years ago by
Volker,
have you reinstalled bliss? There is a patch that has to be applied to bliss before this works and the patch was introduced in this branch.
Best,
Jernej
comment:93 Changed 6 years ago by
Just recompiled and its still there. Actually its always dying in a slightly different spot:
sage: g = digraphs.Circuit(5) ## line 11558 ## sage: g.is_circulant(certificate = True) ## line 11559 ## Bliss fatal error: Internal error  unknown splitting heuristics Aborting!
comment:94 Changed 6 years ago by
Wow that's bad. Just to be sure, the patch applied (the one in pkgs/bliss/patches) is the following?
 bliss0.72/graph.cc 20110512 15:29:46.000000000 +0200 +++ /tmp/bliss0.72/graph.cc 20150128 13:40:42.289179859 +0100 @@ 1920,6 +1920,7 @@ Digraph::Digraph(const unsigned int nof_vertices) { vertices.resize(nof_vertices); + sh = shs_f; }
comment:95 followup: ↓ 98 Changed 6 years ago by
$ patch=patches/digraph_heuristic.patch $ patch n p1 <"$patch" patch: **** Only garbage was found in the patch input.
comment:96 Changed 6 years ago by
Hm. Question. Why don't I get this error when I issue sage f bliss?
comment:97 Changed 6 years ago by
Oops, n is not dryrun in patch.
The problem is that you first "cd src" and then iterate over "patches/*.patch". Which is then empty.
comment:98 in reply to: ↑ 95 Changed 6 years ago by
Replying to vbraun:
$ patch=patches/digraph_heuristic.patch $ patch n p1 <"$patch" patch: **** Only garbage was found in the patch input.
What exactly is causing this error? The patch was created with
diff Naur old new > patch.txt
comment:99 Changed 6 years ago by
The "only garbage" message is because of the "n".
comment:100 Changed 6 years ago by
Okay, so the patch actually looks fine if manually apply it, but sage f bliss says
can't find file to patch at input line 3
how do I actually specify this file? Where are the sources expected to be?
comment:101 Changed 6 years ago by
As I said in comment:97, the problem is that you first "cd src" and then iterate over "patches/*.patch". Which is the wrong path when you are in "src"
comment:102 Changed 6 years ago by
Volker,
this is the actual error I get after fixing the "cd src" issue. Specifically
**************************************************** can't find file to patch at input line 3 Perhaps you used the wrong p or strip option? The text leading up to this was:   bliss0.72/graph.cc 20110512 15:29:46.000000000 +0200 +++ /tmp/bliss0.72/graph.cc 20150130 11:41:02.211921044 +0100
comment:103 Changed 6 years ago by
For starters, why is bliss0.72/graph.cc one directory deep but /tmp/bliss0.72/graph.cc two directories deep? Do your diffs against identical directory trees. Then strip the right number of directory levels with the p
comment:104 Changed 6 years ago by
 Commit changed from 09ec0494fa9b2e6f4b9dd9154a570cdd04cfb594 to 5ef441aeca37ec354b0a6a8b423583add44395b1
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
5ef441a  Fixed patching of bliss

comment:105 Changed 6 years ago by
Can someone take a look if this now makes sense?
Doing sage f bliss and testing the graph module passes OK for me.
comment:106 Changed 6 years ago by
Here it crashes with the usual error message. Does that work on your computer ?
sage: digraphs.DeBruijn(3,1).is_circulant(certificate = True) Bliss fatal error: Internal error  unknown splitting heuristics Aborting!
comment:107 Changed 6 years ago by
Weird.
sage: digraphs.DeBruijn(3,1).is_circulant(certificate = True) (True, [(3, [0, 1, 2])])
comment:108 Changed 6 years ago by
Could you please check if this new modification that I pushed actually patches bliss for you?
comment:109 Changed 6 years ago by
The patching works fine. I added grep "sh = shs_f;" A 5 B 5 graph.cc
right at the end of the 'for patch in' loop in spkginstall, and I see:
Digraph::Digraph(const unsigned int nof_vertices) { vertices.resize(nof_vertices); sh = shs_f; }
I also don't understand why it would work on your computer and not on mine.
Nathann
comment:110 Changed 6 years ago by
I have now pulled the latest branch, installed bliss and everything works fine. The above example as well as sage t generic_graph.py o_O
I have no idea what's going on at this point.
comment:111 Changed 6 years ago by
Same with sage t l optional=sage,bliss graph/
for the whole folder ?
Nathann
comment:112 Changed 6 years ago by
Yes! I only get three errors. One is the depreciaton warning from Tutte poly and two are weird errors of the type
********************************************************************** File "sage/src/sage/graphs/generic_graph.py", line 17448, in sage.graphs.generic_graph.GenericGraph.? Failed example: A1.is_isomorphic(A2) # optional  bliss Expected: True # optional  bliss Got: True **********************************************************************
comment:113 Changed 6 years ago by
Can you try on somebody else's computer, or on some ssh machine ?
Nathann
comment:114 Changed 6 years ago by
Nathann,
sorry for the delay. Was computing something on all external machines and did want to stop to compile sage.
I have now tested this on another machine (fetch stuff with git install bliss sage t on generic_graph.py and graph.py) and it works well.
Also
sage: digraphs.DeBruijn(3,1).is_circulant(certificate = True) (True, [(3, [0, 1, 2])])
So I have no idea why the error is still occurring for you.
Best,
Jernej
comment:115 Changed 6 years ago by
I am recompiling Sage from scratch to see what happens when I reinstall this afterwards.
Nathann
comment:116 Changed 6 years ago by
Okay. I made a 'make distclean' on a machine on which Sage crashed with this line
sage: digraphs.DeBruijn(3,1).is_circulant(certificate = True)
I remove the bliss package, then ran 'make' then installed bliss again, and now it works. Volker? Could you do the same thing on your machine to see if it solves the problem too?
Nathann
comment:117 Changed 6 years ago by
What do you mean by "remove the package"? If you need to recompile (e.g. because of different patches) then you must bump the patch level in the packageversion.txt
comment:118 Changed 6 years ago by
Okay. This branch now works on my laptop, and on my office's computer. Here is what I did:
make distclean
rm upstream/bliss0.72.tar.bz2
 apply the branch
make
sage f bliss
make
And now it works.
I have no clue what the problem was, however. And of course now I don't know how to reproduce the bug anymore XD
Nathann
comment:119 Changed 6 years ago by
 Commit changed from 5ef441aeca37ec354b0a6a8b423583add44395b1 to b270ce66315ccc8c87b97a4e6bc6a754d11c941d
Branch pushed to git repo; I updated commit sha1. New commits:
b270ce6  trac #17464: Rebase on 6.6.beta2

comment:120 followup: ↓ 121 Changed 6 years ago by
Do you think we can accept this then?
comment:121 in reply to: ↑ 120 Changed 6 years ago by
Do you think we can accept this then?
Not yet. First, I think I saw somewhere that the documentation did not build, and this must be fixed. Because of some http link.
Then we must figure out what happened, for even if a distclean makes the trick something fishy is going on in the building process (Volker may know). Unless we find what it is and fix it, everybody will have to do a make distclean
in order to have it work, just like we did.
Nathann
comment:122 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:123 Changed 6 years ago by
You need to bump the packageversion.txt to 0.72.p1, otherwise the build system does't know that anything changed and will not recompile bliss (and, therefore, your patch will not be used).
comment:124 Changed 6 years ago by
Volker: the bug still happened when running 'sage f bliss'. Isn't that a contradiction ?
comment:125 followup: ↓ 126 Changed 6 years ago by
Which bug do you mean? There are clearly multiple ones. I'll be happy to look if you don't have any obvious bugs open any more.
comment:126 in reply to: ↑ 125 Changed 6 years ago by
Hello Volker,
Which bug do you mean? There are clearly multiple ones. I'll be happy to look if you don't have any obvious bugs open any more.
Well, the 'main' bug that we had was this 'undefined heuristic' poblem which caused crashes. As I reported above, running a 'make distclean' and reinstalling everything solves it, and now this branch passes all tests on my computer.
I would be tempted to switch it to 'positive review', but that would produce errors on everybody's computer unless they *also* run this make distclean! If you say that this would be solved by changing the version number, then let us do that and switch it to 'positive review'
What worries me is that I do not understand why changing the version number would have any effect that forcing a reinstall through 'sage f bliss' did not have. I tried it, long before trying 'make distclean', and it had no effect.
What do you think we should do ?
Nathann
comment:127 Changed 6 years ago by
 Status changed from needs_review to needs_work
You need to bump the packageversion.txt to 0.72.p1, otherwise the build system does't know that anything changed and will not recompile bliss (and, therefore, your patch will not be used).
comment:128 Changed 6 years ago by
 Commit changed from b270ce66315ccc8c87b97a4e6bc6a754d11c941d to 7b07c7a57bad9f3644c88c7f3f875008d6d3ec98
comment:129 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:130 Changed 6 years ago by
 Status changed from needs_review to positive_review
Hello!
First of all thank you for pushing this last bit!!
I've glanced at the changes, tested the relevant modules with t and checked if sage docbuild reference html gives any errors related to this change.
All of the above looks good so I am giving this a positive review. In case you need something else to be checked let me know.
Best,
Jernej
comment:131 Changed 6 years ago by
 Status changed from positive_review to needs_work
Conflicts with #18145
comment:132 Changed 6 years ago by
This ticket, in positive review since two weeks, has to be rebased on a ticket created two days ago?....
You are not being fair.
Nathann
comment:133 Changed 6 years ago by
Jeroen asked me to merge it first, usually they are merged in ascending order.
comment:134 Changed 6 years ago by
 Commit changed from 7b07c7a57bad9f3644c88c7f3f875008d6d3ec98 to 7902e5f82eb6ab925fcca62ecb7eb81c19544661
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
c98e78d  Merge commit '7d1b5f8ca56180ca2d7044453707c619ef17b51a' into HEAD

c683c19  Add PARI documentation

4b07161  Better format links

9f710a2  Merge commit '4b071619a00e667d3452a73229de43f231dfe662' into HEAD

41755fe  Reorganize building of Sage library and autogenerated files

3510d45  Minor review fixes

e56aeb2  Cythonize optional extensions

7366bbf  trac #17464: Merged with #18145

e9639c2  trac #17464: Add bliss to module_list.py

7902e5f  trac #18107: Broken doctest

comment:135 Changed 6 years ago by
 Commit changed from 7902e5f82eb6ab925fcca62ecb7eb81c19544661 to 44d8462ffc5bff9086c5f408542100b5580c031d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
44d8462  trac #17164: Broken doctest

comment:136 Changed 6 years ago by
 Status changed from needs_work to positive_review
comment:137 Changed 6 years ago by
 Status changed from positive_review to needs_work
[graphs ] /Users/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.py:docstring of sage.graphs.generic_graph.GenericGraph.automorphism_group:25: ERROR: Unknown target name: "http://www.tcs.tkk.fi/software/bliss/index.html". [graphs ] /Users/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.py:docstring of sage.graphs.generic_graph.GenericGraph.canonical_label:33: ERROR: Unknown target name: "http://www.tcs.tkk.fi/software/bliss/index.html". [graphs ] /Users/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.py:docstring of sage.graphs.generic_graph.GenericGraph.is_isomorphic:13: ERROR: Unknown target name: "http://www.tcs.tkk.fi/software/bliss/index.html". Error building the documentation. Traceback (most recent call last): File "/Users/buildslavesage/slave/sage_git/build/src/doc/common/builder.py", line 1626, in <module> getattr(get_builder(name), type)() File "/Users/buildslavesage/slave/sage_git/build/src/doc/common/builder.py", line 292, in _wrapper getattr(get_builder(document), 'inventory')(*args, **kwds) File "/Users/buildslavesage/slave/sage_git/build/src/doc/common/builder.py", line 503, in _wrapper x.get(99999) File "/Users/buildslavesage/slave/sage_git/build/local/lib/python/multiprocessing/pool.py", line 558, in get raise self._value OSError: [graphs ] /Users/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.py:docstring of sage.graphs.generic_graph.GenericGraph.automorphism_group:25: ERROR: Unknown target name: "http://www.tcs.tkk.fi/software/bliss/index.html".
comment:138 Changed 6 years ago by
 Commit changed from 44d8462ffc5bff9086c5f408542100b5580c031d to 35e7862195ee22f314848fee7e4196f3b84d3fa2
Branch pushed to git repo; I updated commit sha1. New commits:
35e7862  trac #17464: Broken doc

comment:139 Changed 6 years ago by
 Commit changed from 35e7862195ee22f314848fee7e4196f3b84d3fa2 to 9d708203dd3236f3c192faab6b573799fa5c1c32
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
9d70820  trac #17464: Broken doc

comment:140 Changed 6 years ago by
 Status changed from needs_work to positive_review
comment:141 Changed 6 years ago by
 Dependencies changed from #17552 to #17552, #18145
comment:142 Changed 6 years ago by
 Status changed from positive_review to needs_work
sage t long src/sage/combinat/designs/incidence_structures.py ********************************************************************** File "src/sage/combinat/designs/incidence_structures.py", line 1498, in sage.combinat.designs.incidence_structures.IncidenceStructure.automorphism_group Failed example: G Expected: Permutation Group with generators [(2,3)(4,5), (2,4)(3,5), (1,2)(4,6), (0,1)(4,5)] Got: Permutation Group with generators [(2,3)(4,5), (2,4)(3,5), (1,2,3)(4,5,6), (1,6)(2,5,4,3), (0,1)(2,3)] ********************************************************************** 1 item had failures: 1 of 11 in sage.combinat.designs.incidence_structures.IncidenceStructure.automorphism_group [287 tests, 1 failure, 3.88 s]
comment:143 Changed 6 years ago by
Good news:
sage: g1=PermutationGroup([[(2,3),(4,5)], [(2,4),(3,5)], [(1,2),(4,6)], [(0,1),(4,5)]]) sage: g2=PermutationGroup([[(2,3),(4,5)], [(2,4),(3,5)], [(1,2,3),(4,5,6)], [(1,6),(2,5,4,3)], [(0,1),(2,3)]]) sage: g1==g2 True
comment:144 Changed 6 years ago by
 Commit changed from 9d708203dd3236f3c192faab6b573799fa5c1c32 to 61307f9ead3de81ab69713d4707fa7f04c01cd2a
comment:145 Changed 6 years ago by
 Commit changed from 61307f9ead3de81ab69713d4707fa7f04c01cd2a to 54b0865d4837861321e3cb9dacf5fc648a2ebfe5
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
54b0865  trac #17464: A wrong labelling was returned

comment:146 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:147 followup: ↓ 148 Changed 6 years ago by
Is bliss making random choices during the computation? There is no need for nondeterministic choices in graph automorphisms, I'm sure. Patch it out and/or setting the seed might be a better fix in the long run.
comment:148 in reply to: ↑ 147 Changed 6 years ago by
Hello,
Is bliss making random choices during the computation? There is no need for nondeterministic choices in graph automorphisms, I'm sure.
A permutation group can have different sets of generators, and that's the trouble here: Sage and Nauty do not obtain the same. The groups are equal, however, as illustrated above.
Patch it out and/or setting the seed might be a better fix in the long run.
There was a real bug in there. I fixed it, and sent an email to Jernej hoping that he can take a look at it soon.
Nathann
comment:149 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:150 Changed 6 years ago by
 Status changed from positive_review to needs_work
comment:151 Changed 6 years ago by
 Commit changed from 54b0865d4837861321e3cb9dacf5fc648a2ebfe5 to e403f16cdb4e158c0533992c5588188dea46cd11
Branch pushed to git repo; I updated commit sha1. New commits:
e403f16  trac #17464: broken doctests on (different architecture + bliss)

comment:152 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:153 Changed 6 years ago by
Here it is. Some doctests were displaying canonical labellings, and of course bliss and Sage compute different ones. I changed the doctests to make them more 'anonymous'.
Nathann
comment:154 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:155 Changed 6 years ago by
 Branch changed from public/bliss to e403f16cdb4e158c0533992c5588188dea46cd11
 Resolution set to fixed
 Status changed from positive_review to closed
comment:156 Changed 6 years ago by
 Commit e403f16cdb4e158c0533992c5588188dea46cd11 deleted
sage t src/sage/graphs/generic_graph.py ********************************************************************** File "src/sage/graphs/generic_graph.py", line 17773, in sage.graphs.generic_graph.GenericGraph.? Failed example: A1.is_isomorphic(A2) # optional  bliss Expected: True # optional  bliss Got: True ********************************************************************** File "src/sage/graphs/generic_graph.py", line 18179, in sage.graphs.generic_graph.GenericGraph.is_isomorphic Failed example: G.is_isomorphic(graphs.GeneralizedPetersenGraph(5,2),algorithm='bliss')# optional  bliss Exception raised: Traceback (most recent call last): File "/usr/local/src/sagegit/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 496, in _run self.compile_and_execute(example, compiler, test.globs) File "/usr/local/src/sagegit/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 858, in compile_and_execute exec(compiled, globs) File "<doctest sage.graphs.generic_graph.GenericGraph.is_isomorphic[43]>", line 1, in <module> G.is_isomorphic(graphs.GeneralizedPetersenGraph(Integer(5),Integer(2)),algorithm='bliss')# optional  bliss File "/usr/local/src/sagegit/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.py", line 18306, in is_isomorphic from sage.graphs.bliss import is_isomorphic ImportError: cannot import name is_isomorphic ********************************************************************** File "src/sage/graphs/generic_graph.py", line 18483, in sage.graphs.generic_graph.GenericGraph.? Failed example: s1 == s2 # optional  bliss Expected: True # optional  bliss Got: True **********************************************************************
comment:157 Changed 6 years ago by
O_o
New commits:
Cython wrapper example
trac #17464: First attempt at integrating bliss into sage