Opened 5 years ago

Closed 2 years ago

#21313 closed enhancement (duplicate)

allow <Graph>.is_isomorphic() use bliss and/or nauty

Reported by: dimpase Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: jmantysalo Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Currently is_isomorphic for graphs is using the default Sage's implementation. Bliss and nauty are typically faster, so it should be possible to use them too.

Change History (6)

comment:1 Changed 5 years ago by jmantysalo

  • Cc jmantysalo added

Please note that currently is_package_installed() is slow because we changed it to use pip.

comment:2 follow-up: Changed 3 years ago by dcoudert

  • Milestone changed from sage-7.4 to sage-8.1

Don't know how to do that but it would be very nice.

comment:3 in reply to: ↑ 2 Changed 3 years ago by jmantysalo

Replying to dcoudert:

Don't know how to do that but it would be very nice.

It seems that we can read the graph to dreadnaut in some format, propably by string given by graph6_string() and the use the commands for it to get the result. At least that should work. For bliss we alreade have some support in .pyx-file.

comment:4 Changed 3 years ago by dimpase

  • Milestone changed from sage-8.1 to sage-feature

comment:5 Changed 3 years ago by dimpase

note that there are Python bindings for nauty here: https://web.cs.dal.ca/~peter/software/

(they are somewhat lacking features, but the C part might be useful).

comment:6 Changed 2 years ago by jdemeyer

  • Milestone changed from sage-feature to sage-duplicate/invalid/wontfix
  • Resolution set to duplicate
  • Status changed from new to closed

There is a bliss implementation since #17464 and nauty is handled by #25506.

Note: See TracTickets for help on using tickets.