Opened 6 years ago

Closed 6 years ago

#21704 closed defect (fixed)

bliss does not support multiple edges

Reported by: jaanos Owned by:
Priority: major Milestone: sage-7.5
Component: graph theory Keywords: bliss, multiedges
Cc: ncohen, azi, jmantysalo Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 2c56c67 (Commits, GitHub, GitLab) Commit: 2c56c678c33b1eff778df68f7b15666a3d69a5f1
Dependencies: Stopgaps:

Status badges

Description (last modified by tscrim)

Example (with bliss installed):

sage: G = Graph(':C_kQ')
sage: G.automorphism_group(algorithm='bliss').order()
8
sage: G.automorphism_group(algorithm='sage').order()
4

This ticket changes the default behaviour so the 'sage' algorithm is used by default when dealing with multiedges, and an error is raised if 'bliss' is given explicitly. Similar situation for canonical_label.

Change History (11)

comment:1 Changed 6 years ago by jaanos

Cc: ncohen azi added
Component: PLEASE CHANGEgraph theory
Description: modified (diff)
Keywords: bliss multiedges added
Status: newneeds_info
Type: PLEASE CHANGEdefect

comment:2 Changed 6 years ago by jmantysalo

Cc: jmantysalo added

Should be easy to implement the first option. Let's make that to correct the bug, and later think about second option as an optimization.

comment:3 Changed 6 years ago by jmantysalo

Branch: u/jmantysalo/bliss_ignores_multiple_edges_when_computing_the_automorphism_group

comment:4 Changed 6 years ago by jmantysalo

Authors: Jori Mäntysalo
Commit: 8f9d64157bf8db1d14f7d761fb6fa47465a56093
Status: needs_infoneeds_review

I also reformat docstring slightly.


New commits:

8f9d641Disable 'bliss' for multiedged graphs.

comment:5 Changed 6 years ago by tscrim

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

I've posted an issue on our version of upstream: https://github.com/mkoeppe/bliss/issues/2. So a good followup would be to actually do the fix directly in our fork of bliss.

comment:6 Changed 6 years ago by jaanos

Thanks for the patch. By the way, after closer inspection, it seems that bliss does not support multiple edges after all, even when given in a file.

comment:7 Changed 6 years ago by jaanos

Description: modified (diff)
Status: positive_reviewneeds_work

I've changed the description to match the actual status. Also, I'm setting this to needs_work since the canonical_label method also needs to be updated.

comment:8 Changed 6 years ago by jaanos

Branch: u/jmantysalo/bliss_ignores_multiple_edges_when_computing_the_automorphism_groupu/jaanos/bliss_ignores_multiple_edges_when_computing_the_automorphism_group

comment:9 Changed 6 years ago by jaanos

Commit: 8f9d64157bf8db1d14f7d761fb6fa47465a560932c56c678c33b1eff778df68f7b15666a3d69a5f1
Status: needs_workneeds_review

OK, done, so we're back to needs_review.


New commits:

2c56c67Disable 'bliss' also for canonical labels of multiedged graphs

comment:10 Changed 6 years ago by tscrim

Description: modified (diff)
Status: needs_reviewpositive_review
Summary: bliss ignores multiple edges when computing the automorphism groupbliss does not support multiple edges

comment:11 Changed 6 years ago by vbraun

Branch: u/jaanos/bliss_ignores_multiple_edges_when_computing_the_automorphism_group2c56c678c33b1eff778df68f7b15666a3d69a5f1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.