Digraphs icon indicating copy to clipboard operation
Digraphs copied to clipboard

Speed up `OnDigraphs` for a digraph and a permutation

Open ChrisJefferson opened this issue 6 years ago • 3 comments

This came up from some code which was heavily using digraphs. this almost doubled the speed of the algorithm, as it turns out these GAP-level checks were dominating the run-time of OnDigraphs.

  • Instead of checking if the permutation fixes the vertices, check if it is the identity (which is much cheaper, although catches less cases)

  • Do not check explictly if the permutation maps the vertices of the graph to itself, do the mapping then check afterwards.

ChrisJefferson avatar Oct 28 '19 14:10 ChrisJefferson

Another solution is that we could create some NC versions of functions that are particularly performance-critical, including OnDigraphsNC.

wilfwilson avatar Oct 28 '19 14:10 wilfwilson

@ChrisJefferson I know this is a bit late (sorry) but I intend to come up with a resolution for this soon that keeps the performance improvement.

wilfwilson avatar Mar 03 '21 20:03 wilfwilson

Stale pull request message

github-actions[bot] avatar Jan 07 '22 01:01 github-actions[bot]