Opened 5 years ago

Closed 4 years ago

Last modified 4 years ago

#17464 closed enhancement (fixed)

Computing the automorphism group of a graph with Bliss

Reported by: azi Owned by:
Priority: major Milestone: sage-6.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 5 years ago by azi

  • Branch set to u/azi/bliss
  • Commit set to 3f4553d1cb40c8d2dbfd55bdef4323877c0b4321
  • Status changed from new to needs_info

New commits:

d29d083Cython wrapper example
3f4553dtrac #17464: First attempt at integrating bliss into sage

comment:2 Changed 5 years ago by azi

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

  1. I want any comments and suggestions if its going in the right direction(to avoid later rewrites :D)
  2. 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.
  3. 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()?
  4. 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??

Last edited 5 years ago by azi (previous) (diff)

comment:3 Changed 5 years ago by git

  • Commit changed from 3f4553d1cb40c8d2dbfd55bdef4323877c0b4321 to f8dcb7e4ffca76715b478ada498be1714e0f38f1

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

f8dcb7etrac #17464: Added module_list as well

comment:4 Changed 5 years ago by ncohen

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 non-sage 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 bliss-version.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 follow-up: Changed 5 years ago by azi

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 ; follow-up: Changed 5 years ago by 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

Nathann

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

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 5 years ago by azi

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 over-thinking 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 ; follow-up: Changed 5 years ago by azi

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 5 years ago by ncohen

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 5 years ago by ncohen

  • Branch changed from u/azi/bliss to public/bliss
  • Commit f8dcb7e4ffca76715b478ada498be1714e0f38f1 deleted

comment:12 Changed 5 years ago by git

  • Commit set to f8e2618b7b644a6bee364379405485a5c8468418

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

343b145trac #17552: Initial attempt at creating a SPKG for bliss
0e2d04ftrac #17552: review
b353d5ftrac #17552: Reviewing the review
6239deatrac #17552: Added copying of headers to the include dir
7cb683ctrac #17552: Added move of "kqueue.hh" header to local/include
2222588Cython wrapper example
9d56af3trac #17464: First attempt at integrating bliss into sage
85ef58ctrac #17464: Added module_list as well
696590ctrac #17464: few modifications to the bliss wrapper
f8e2618trac #17464: spliting graph/digraph creating function

comment:13 Changed 5 years ago by azi

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: t2-t1
37.43013310432434
sage: t1 = time() ; A = G.automorphism_group(); t2 = time() # uses 50% of RAM
sage: t2-t1
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 5 years ago by ncohen

Looks good ! I'm eager to use this in my hypergraph computations :-PPPP

Nathann

comment:15 Changed 5 years ago by ncohen

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 follow-up: Changed 5 years ago by azi

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: t2-t1
0.15731596946716309
sage: t1 = time() ; A = G.automorphism_group(); t2 = time()
....... indefinitely..............

comment:17 Changed 5 years ago by azi

  • Branch changed from public/bliss to public/bliss2
  • Commit changed from f8e2618b7b644a6bee364379405485a5c8468418 to 152b2eb748fa36b4306ac12d13433c6e9b741be3
  • Status changed from needs_info to needs_work

New commits:

48805f5Cython wrapper example
95dcb37trac #17464: First attempt at integrating bliss into sage
50eb67ftrac #17464: Added module_list as well
076a55etrac #17464: few modifications to the bliss wrapper
ebba1aetrac #17464: spliting graph/digraph creating function
3e0caa8trac #17552: Added move of "kqueue.hh" header to local/include
7fe9974trac #17522: idk
152b2ebtrac #17464: Working version of bliss wrapper including isomorphism testing and computation of canonical forms.

comment:18 Changed 5 years ago by azi

Oh wow what a mess again...

comment:19 Changed 5 years ago by azi

  • Branch changed from public/bliss2 to public/bliss
  • Commit changed from 152b2eb748fa36b4306ac12d13433c6e9b741be3 to f8e2618b7b644a6bee364379405485a5c8468418

New commits:

7cb683ctrac #17552: Added move of "kqueue.hh" header to local/include
2222588Cython wrapper example
9d56af3trac #17464: First attempt at integrating bliss into sage
85ef58ctrac #17464: Added module_list as well
696590ctrac #17464: few modifications to the bliss wrapper
f8e2618trac #17464: spliting graph/digraph creating function

comment:20 Changed 5 years ago by azi

Reverted back to the public/bliss branch, apparently I've pushed some old unrelated nonsesne...

comment:21 Changed 5 years ago by git

  • Commit changed from f8e2618b7b644a6bee364379405485a5c8468418 to 3c37cb81e7bfbc58f953035054dd4c30d0750880

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

3c37cb8trac #17464: First workable version of bliss

comment:22 Changed 5 years ago by azi

I think this last pushed branch should be good.

comment:23 Changed 5 years ago by ncohen

  • Dependencies set to #17552

comment:24 in reply to: ↑ 16 ; follow-up: Changed 5 years ago by 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

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 ; follow-up: Changed 5 years ago by azi

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

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

Last edited 5 years ago by azi (previous) (diff)

comment:26 in reply to: ↑ 25 ; follow-up: Changed 5 years ago by ncohen

Yoooooo !

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

  1. 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 5 years ago by azi

Replying to ncohen:

Yoooooo !

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

  1. 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 follow-up: Changed 5 years ago by azi

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 ; follow-up: Changed 5 years ago by 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

Nathann

comment:30 in reply to: ↑ 29 Changed 5 years ago by azi

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 5 years ago by azi

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 5 years ago by git

  • Commit changed from 3c37cb81e7bfbc58f953035054dd4c30d0750880 to cad441ec9fcfa114fc481411e949557845c45ab5

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

cad441etrac #17464: Added documentation and some cleanups

comment:33 follow-up: Changed 5 years ago by azi

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

Last edited 5 years ago by azi (previous) (diff)

comment:34 in reply to: ↑ 33 ; follow-up: Changed 5 years ago by 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 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/spkg-install file and the patches/ folder. The corresponding doc is there:

http://www.sagemath.org/doc/developer/packaging.html#patching-sources

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 one-line 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 ; follow-up: Changed 5 years ago by azi

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 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/spkg-install file and the patches/ folder. The corresponding doc is there:

http://www.sagemath.org/doc/developer/packaging.html#patching-sources

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 one-line 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 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from cad441ec9fcfa114fc481411e949557845c45ab5 to 6679f16ab3db644a285ed8706eafa587eafee4a3

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

6679f16trac #17464: Added calls from generic_graph to bliss

comment:38 follow-up: Changed 5 years ago by azi

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 ; follow-up: Changed 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from 6679f16ab3db644a285ed8706eafa587eafee4a3 to aed44e8dd39982907467b6e0d699f9def062f1af

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

aed44e8trac #17464: Made some changes as reviewer suggested

comment:41 in reply to: ↑ 39 ; follow-up: Changed 5 years ago by azi

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 keyword algorithm 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, and is_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 ; follow-up: Changed 5 years ago by ncohen

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 5 years ago by git

  • 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 ; follow-up: Changed 5 years ago by azi

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 ; follow-up: Changed 5 years ago by 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>

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 ; follow-up: Changed 5 years ago by azi

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 5 years ago by ncohen

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 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from 1d7afae64c538d1a6a0ffdec31275a65969f2068 to a539b9953f9d8ccbbda67fc5b60a9372079a3eaf

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a539b99trac #17464: Graph automorphism groups through bliss

comment:50 Changed 5 years ago by ncohen

  • 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)

Last edited 5 years ago by ncohen (previous) (diff)

comment:51 Changed 5 years ago by git

  • Commit changed from a539b9953f9d8ccbbda67fc5b60a9372079a3eaf to 7e6edd0ecf50e7d75876b619a9495c8f57b92971

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

7e6edd0trac #17464: Make IncidenceStructure.automorphism_group call Graph.automorphism_group

comment:52 follow-up: Changed 5 years ago by ncohen

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 is automorphism_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 with is_isomorphic (or canonical_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 of enumerate(G). We have this standard in other places that when vertices are turned into integers, it is done using the ordering of G.vertices().

Tell me what you think ! I would be glad to have this into Sage soon ;-)

Nathann

comment:53 Changed 5 years ago by git

  • Commit changed from 7e6edd0ecf50e7d75876b619a9495c8f57b92971 to 60018569126f690eda0b417f5fec1485904c59ed

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

6001856trac #17464: Additional documentation

comment:54 in reply to: ↑ 52 ; follow-up: Changed 5 years ago by azi

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 is automorphism_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 with is_isomorphic (or canonical_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 of enumerate(G). We have this standard in other places that when vertices are turned into integers, it is done using the ordering of G.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/efficiently-converting-a-bijection-to-cycle-notation

Nathann

comment:55 in reply to: ↑ 54 ; follow-up: Changed 5 years ago by 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.

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/efficiently-converting-a-bijection-to-cycle-notation

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 5 years ago by ncohen

btw: the doc does not compile on my computer because of some broken link

Nathann

comment:57 in reply to: ↑ 55 ; follow-up: Changed 5 years ago by azi

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/efficiently-converting-a-bijection-to-cycle-notation

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 ; follow-up: Changed 5 years ago by 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.

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 ; follow-up: Changed 5 years ago by azi

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

  1. Leave out the is_isomorphic thing
  2. Find a workaround for the digraph thing.

and then we are almost done?

Best,

Jernej

comment:60 in reply to: ↑ 59 Changed 5 years ago by ncohen

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

  1. Leave out the is_isomorphic thing
  2. Find a workaround for the digraph thing.

and then we are almost done?

Right !

Nathann

comment:61 Changed 5 years ago by git

  • Commit changed from 60018569126f690eda0b417f5fec1485904c59ed to 97bb760e17aefff7c9004bcad17409627d94e99d

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

97bb760Added correct fix for digraph's missing heuristic

comment:62 Changed 5 years ago by azi

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 follow-up: Changed 5 years ago by azi

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 5 years ago by ncohen

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 follow-up: Changed 5 years ago by azi

Ohh I didn't notice you included that. I think this new fix does it. All tests pass now.

comment:66 Changed 5 years ago by git

  • Commit changed from 97bb760e17aefff7c9004bcad17409627d94e99d to 9a84f54d2877fa89083dfade62c5ff243f4bca31

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

9a84f54Fixed test cases so that all tests pass.

comment:67 in reply to: ↑ 65 Changed 5 years ago by ncohen

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 5 years ago by ncohen

sage -t --long tutte_polynomial.py  # 2 doctests failed

comment:69 Changed 5 years ago by git

  • Commit changed from 9a84f54d2877fa89083dfade62c5ff243f4bca31 to 2942c3136ffad17f490b55cd83421c70c05ff46a

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

2942c31Removed is_isomorphic

comment:70 Changed 5 years ago by azi

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 5 years ago by git

  • Commit changed from 2942c3136ffad17f490b55cd83421c70c05ff46a to 2018dbc040e23bfafc873af17adc75f699a175cc

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

2018dbcFixed error related to the new way of computing automorphisms.

comment:72 follow-up: Changed 5 years ago by azi

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 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from 2018dbc040e23bfafc873af17adc75f699a175cc to cac03d7f9ce6ee3de47ad48f46a9118fb0c72083

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

cac03d7Made sure canonical labels are computed with Sage's algorithm

comment:75 follow-up: Changed 5 years ago by azi

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 5 years ago by ncohen

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 5 years ago by ncohen

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 follow-up: Changed 5 years ago by azi

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 ; follow-up: Changed 5 years ago by 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.

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 ; follow-up: Changed 5 years ago by azi

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 5 years ago by git

  • Commit changed from cac03d7f9ce6ee3de47ad48f46a9118fb0c72083 to c68235bf3c18d02dbfa17c92578f70a71a251b32

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

c68235bRemoved (trivial) doctest complicating bliss integration

comment:82 Changed 5 years ago by git

  • Commit changed from c68235bf3c18d02dbfa17c92578f70a71a251b32 to acdbae661e84bad3953dd6260d2edb2aeb9719ea

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

f5efca9trac #17464: Merged with 6.5.beta6
acdbae6trac #17464: Review

comment:83 in reply to: ↑ 80 Changed 5 years ago by ncohen

  • Authors set to Jernej Azarija
  • 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 5 years ago by git

  • Commit changed from acdbae661e84bad3953dd6260d2edb2aeb9719ea to b03b2b90d27d1511f111730dfcb8eb7eba7b54fa

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b03b2b9trac #17464: Review

comment:85 Changed 5 years ago by azi

  • Status changed from needs_review to positive_review

comment:86 Changed 5 years ago by azi

Thanks for helping pushing this through.I hope all is set now.

Best,

Jernej

comment:87 Changed 5 years ago by ncohen

Eeeeeeeeeeeeexcellent ! ;-)

Nathann

comment:88 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

Documentation doesn't build

comment:89 Changed 5 years ago by git

  • Commit changed from b03b2b90d27d1511f111730dfcb8eb7eba7b54fa to 09ec0494fa9b2e6f4b9dd9154a570cdd04cfb594

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

09ec049trac #17464: Broken doc

comment:90 Changed 5 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:91 Changed 5 years ago by vbraun

  • 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 5 years ago by azi

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 5 years ago by vbraun

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 5 years ago by azi

Wow that's bad. Just to be sure, the patch applied (the one in pkgs/bliss/patches) is the following?

--- bliss-0.72/graph.cc	2011-05-12 15:29:46.000000000 +0200
+++ /tmp/bliss-0.72/graph.cc	2015-01-28 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 follow-up: Changed 5 years ago by vbraun

$ patch=patches/digraph_heuristic.patch
$ patch -n -p1 <"$patch" 
patch: **** Only garbage was found in the patch input.

comment:96 Changed 5 years ago by azi

Hm. Question. Why don't I get this error when I issue sage -f bliss?

comment:97 Changed 5 years ago by vbraun

Oops, -n is not dry-run 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 5 years ago by azi

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 5 years ago by vbraun

The "only garbage" message is because of the "-n".

comment:100 Changed 5 years ago by azi

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 5 years ago by vbraun

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 5 years ago by azi

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:
--------------------------
|--- bliss-0.72/graph.cc	2011-05-12 15:29:46.000000000 +0200
|+++ /tmp/bliss-0.72/graph.cc	2015-01-30 11:41:02.211921044 +0100

comment:103 Changed 5 years ago by vbraun

For starters, why is bliss-0.72/graph.cc one directory deep but /tmp/bliss-0.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 5 years ago by git

  • Commit changed from 09ec0494fa9b2e6f4b9dd9154a570cdd04cfb594 to 5ef441aeca37ec354b0a6a8b423583add44395b1

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

5ef441aFixed patching of bliss

comment:105 Changed 5 years ago by azi

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 5 years ago by ncohen

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 5 years ago by azi

Weird.

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

comment:108 Changed 5 years ago by azi

Could you please check if this new modification that I pushed actually patches bliss for you?

comment:109 Changed 5 years ago by ncohen

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 spkg-install, 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

Last edited 5 years ago by ncohen (previous) (diff)

comment:110 Changed 5 years ago by azi

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.

Last edited 5 years ago by azi (previous) (diff)

comment:111 Changed 5 years ago by ncohen

Same with sage -t -l --optional=sage,bliss graph/ for the whole folder ?

Nathann

comment:112 Changed 5 years ago by azi

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 5 years ago by ncohen

Can you try on somebody else's computer, or on some ssh machine ?

Nathann

comment:114 Changed 4 years ago by azi

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 4 years ago by ncohen

I am recompiling Sage from scratch to see what happens when I reinstall this afterwards.

Nathann

comment:116 Changed 4 years ago by ncohen

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 4 years ago by vbraun

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 package-version.txt

comment:118 Changed 4 years ago by ncohen

Okay. This branch now works on my laptop, and on my office's computer. Here is what I did:

  • make distclean
  • rm upstream/bliss-0.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 4 years ago by git

  • Commit changed from 5ef441aeca37ec354b0a6a8b423583add44395b1 to b270ce66315ccc8c87b97a4e6bc6a754d11c941d

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

b270ce6trac #17464: Rebase on 6.6.beta2

comment:120 follow-up: Changed 4 years ago by azi

Do you think we can accept this then?

comment:121 in reply to: ↑ 120 Changed 4 years ago by ncohen

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 4 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:123 Changed 4 years ago by vbraun

You need to bump the package-version.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 4 years ago by ncohen

Volker: the bug still happened when running 'sage -f bliss'. Isn't that a contradiction ?

comment:125 follow-up: Changed 4 years ago by vbraun

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 4 years ago by ncohen

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 4 years ago by vbraun

  • Status changed from needs_review to needs_work

You need to bump the package-version.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 4 years ago by git

  • Commit changed from b270ce66315ccc8c87b97a4e6bc6a754d11c941d to 7b07c7a57bad9f3644c88c7f3f875008d6d3ec98

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

7048e6atrac #17464: Merged with 6.6.rc0
7b07c7atrac #17464: Merge and package version update

comment:129 Changed 4 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:130 Changed 4 years ago by azi

  • 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 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Conflicts with #18145

comment:132 Changed 4 years ago by ncohen

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 4 years ago by vbraun

Jeroen asked me to merge it first, usually they are merged in ascending order.

comment:134 Changed 4 years ago by git

  • Commit changed from 7b07c7a57bad9f3644c88c7f3f875008d6d3ec98 to 7902e5f82eb6ab925fcca62ecb7eb81c19544661

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

c98e78dMerge commit '7d1b5f8ca56180ca2d7044453707c619ef17b51a' into HEAD
c683c19Add PARI documentation
4b07161Better format links
9f710a2Merge commit '4b071619a00e667d3452a73229de43f231dfe662' into HEAD
41755feRe-organize building of Sage library and auto-generated files
3510d45Minor review fixes
e56aeb2Cythonize optional extensions
7366bbftrac #17464: Merged with #18145
e9639c2trac #17464: Add bliss to module_list.py
7902e5ftrac #18107: Broken doctest

comment:135 Changed 4 years ago by git

  • Commit changed from 7902e5f82eb6ab925fcca62ecb7eb81c19544661 to 44d8462ffc5bff9086c5f408542100b5580c031d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

44d8462trac #17164: Broken doctest

comment:136 Changed 4 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:137 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work
[graphs   ] /Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/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/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/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/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/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/buildslave-sage/slave/sage_git/build/src/doc/common/builder.py", line 1626, in <module>
    getattr(get_builder(name), type)()
  File "/Users/buildslave-sage/slave/sage_git/build/src/doc/common/builder.py", line 292, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/Users/buildslave-sage/slave/sage_git/build/src/doc/common/builder.py", line 503, in _wrapper
    x.get(99999)
  File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
OSError: [graphs   ] /Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/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 4 years ago by git

  • Commit changed from 44d8462ffc5bff9086c5f408542100b5580c031d to 35e7862195ee22f314848fee7e4196f3b84d3fa2

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

35e7862trac #17464: Broken doc

comment:139 Changed 4 years ago by git

  • Commit changed from 35e7862195ee22f314848fee7e4196f3b84d3fa2 to 9d708203dd3236f3c192faab6b573799fa5c1c32

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9d70820trac #17464: Broken doc

comment:140 Changed 4 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:141 Changed 4 years ago by jdemeyer

  • Dependencies changed from #17552 to #17552, #18145

comment:142 Changed 4 years ago by vbraun

  • 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 4 years ago by ncohen

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 4 years ago by git

  • Commit changed from 9d708203dd3236f3c192faab6b573799fa5c1c32 to 61307f9ead3de81ab69713d4707fa7f04c01cd2a

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

e86dff3trac #17464: Merged with beta0
61307f9trac #17464: A wrong labelling was returned

comment:145 Changed 4 years ago by git

  • Commit changed from 61307f9ead3de81ab69713d4707fa7f04c01cd2a to 54b0865d4837861321e3cb9dacf5fc648a2ebfe5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

54b0865trac #17464: A wrong labelling was returned

comment:146 Changed 4 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:147 follow-up: Changed 4 years ago by vbraun

Is bliss making random choices during the computation? There is no need for non-deterministic 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 4 years ago by ncohen

Hello,

Is bliss making random choices during the computation? There is no need for non-deterministic 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 4 years ago by azi

  • Status changed from needs_review to positive_review

comment:150 Changed 4 years ago by azi

  • Status changed from positive_review to needs_work

comment:151 Changed 4 years ago by git

  • Commit changed from 54b0865d4837861321e3cb9dacf5fc648a2ebfe5 to e403f16cdb4e158c0533992c5588188dea46cd11

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

e403f16trac #17464: broken doctests on (different architecture + bliss)

comment:152 Changed 4 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:153 Changed 4 years ago by ncohen

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 4 years ago by azi

  • Status changed from needs_review to positive_review

comment:155 Changed 4 years ago by vbraun

  • Branch changed from public/bliss to e403f16cdb4e158c0533992c5588188dea46cd11
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:156 Changed 4 years ago by jdemeyer

  • 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/sage-git/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/usr/local/src/sage-git/local/lib/python2.7/site-packages/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/sage-git/local/lib/python2.7/site-packages/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 4 years ago by ncohen

O_o

Note: See TracTickets for help on using tickets.