- patch from the upstream allowing to link to libnauty.so: https://github.com/polymake/polymake/issues/10#issuecomment-906184045
- updated to fix a testsuite regression: https://forum.polymake.org/viewtopic.php?f=10&p=3838#p3838

commit 3d5f15812247c37e1821d30a24e69acc308bc54b
Author: Benjamin Lorenz <lorenz@math.tu-berlin.de>
Date:   Tue Aug 24 21:20:40 2021 +0200

    bundled/nauty: add support for libnauty installation to configuration
    
    in addition to bundled and source-dir
    
    without any options this will try to run a test-program and fall back
    to the bundled nauty if that fails.

--- bundled/nauty/apps/graph/src/GraphIso.cc.orig	2021-05-18 08:50:05 UTC
+++ bundled/nauty/apps/graph/src/GraphIso.cc
@@ -29,8 +29,8 @@
 #define set nauty_set
 #define permutation nauty_permutation
 
-#include <nauty.h>
-#include <naututil.h>
+#include <nauty/nauty.h>
+#include <nauty/naututil.h>
 #include <memory>
 
 namespace {
--- bundled/nauty/apps/graph/src/build_flags.pl.orig	2021-05-18 08:50:05 UTC
+++ bundled/nauty/apps/graph/src/build_flags.pl
@@ -1,6 +1,6 @@
 # input for generate_ninja_targets.pl
 
-my $foreign_src = $ConfigFlags{'bundled.nauty.NautySrc'};
+my $foreign_src = $ConfigFlags{'bundled.nauty.NautySrc'} ne "bundled" && $ConfigFlags{'bundled.nauty.NautySrc'};
 my $nauty_src = $foreign_src ? '${bundled.nauty.NautySrc}' : '${root}/bundled/nauty/external/nauty';
 my $generated_dir = '${buildroot}/staticlib/nauty';
 my @generated_headers = qw( nauty.h naututil.h gtools.h );
@@ -9,17 +9,21 @@ my @generated_out = map { "$generated_dir/$_" } @gener
 my $include_generated = ($foreign_src && grep { -f "$foreign_src/$_" } @generated_headers)
                         ? join(" ", map { "-include $_" } @generated_out)
                         : "-I$generated_dir";
+my $nauty_inc = $ConfigFlags{'bundled.nauty.NautySrc'}
+                ? " -I$generated_dir -I$nauty_src"
+                : "";
 
-( CXXFLAGS => "-DBIGNAUTY -I$generated_dir -I$nauty_src",
+( 'GraphIso.cc' => $nauty_inc,
 
-  GENERATED => {
-    out => "@generated_out", in => "@generated_in",
-    command => "cd $generated_dir; CC=\"\${CC}\" CFLAGS=\"\${CFLAGS}\" $nauty_src/configure --quiet >/dev/null 2>/dev/null; rm -f makefile",
-  },
-
-  staticlib => {
-    SOURCEDIR => $nauty_src,
-    SOURCES => [ qw(naugraph.c naurng.c nausparse.c nautaux.c nautil.c nautinv.c naututil.c nauty.c rng.c schreier.c) ],
-    CFLAGS => "-DBIGNAUTY $include_generated -I$nauty_src",
-  }
+  $ConfigFlags{'bundled.nauty.NautySrc'}
+  ? ( GENERATED => {
+        out => "@generated_out", in => "@generated_in",
+        command => "cd $generated_dir; CC=\"\${CC}\" CFLAGS=\"\${CFLAGS}\" $nauty_src/configure --quiet >/dev/null 2>/dev/null; rm -rf makefile nauty; ln -s . nauty",
+      },
+      staticlib => {
+        SOURCEDIR => $nauty_src,
+        SOURCES => [ qw(naugraph.c naurng.c nausparse.c nautaux.c nautil.c nautinv.c naututil.c nauty.c rng.c schreier.c) ],
+        CFLAGS => "$include_generated -I$nauty_src",
+      } )
+  : ()
 )
--- bundled/nauty/support/configure.pl.orig	2021-05-18 08:50:05 UTC
+++ bundled/nauty/support/configure.pl
@@ -14,19 +14,19 @@
 #  GNU General Public License for more details.
 #-------------------------------------------------------------------------------
 
-@conf_vars=qw( NautySrc );
+@conf_vars=qw( NautySrc CXXFLAGS LDFLAGS LIBS );
 
 sub allowed_options {
    my ($allowed_options, $allowed_with)=@_;
-   @$allowed_with{ qw( nauty-src ) }=();
+   @$allowed_with{ qw( nauty-src nauty ) }=();
 }
 
 
 sub usage {
-   print STDERR "  --with-nauty-src=PATH  Source directory of nauty.\n",
-                "                         By default polymake will use the bundled nauty source files,\n",
-                "                         for the minimal tarball this option allows using a custom\n",
-                "                         directory containing the nauty sources.\n";
+   print STDERR "                         By default polymake will use the bundled nauty source files,\n",
+                "                         these options allow using a custom nauty source or installation:\n",
+                "  --with-nauty-src=PATH  Source directory of nauty.\n",
+                "  --with-nauty=PATH      Installation prefix of nauty.\n";
 }
 
 sub check_nauty {
@@ -36,17 +36,101 @@ sub check_nauty {
 
 sub proceed {
    my ($options)=@_;
-   my $nautysrc;
-   if (defined ($nautysrc=$options->{"nauty-src"})) {
-      check_nauty($nautysrc) or
-         die "Specified nauty source directory invalid, could not find 'nauty-h.in'.";
-      $NautySrc = $nautysrc;
-   } elsif (!check_nauty()) {
+   my $nauty_path;
+   my $nauty_src;
+   my $nautyver;
+   $NautySrc = "bundled";
+   if (defined ($nauty_path=$options->{nauty}) && $nauty_path ne "bundled") {
+      my $nauty_inc="$nauty_path/include";
+      my $nauty_lib=Polymake::Configure::get_libdir($nauty_path, "nauty");
+      unless (-f "$nauty_inc/nauty/nauty.h"
+              && ( -f "$nauty_lib/libnauty.$Config::Config{dlext}"
+                   || -f "$nauty_lib/libnauty.a" ) ) {
+         die "Invalid installation location of nauty library: header file nauty/nauty.h and/or library libnauty.$Config::Config{dlext} / libnauty.a not found\n";
+      }
+      $LDFLAGS.=" -Wl,-rpath,$nauty_lib"
+         if $nauty_path !~ m|^/usr$| && -f "$nauty_lib/libnauty.$Config::Config{dlext}";
+      $CXXFLAGS = "-I$nauty_inc";
+      $LDFLAGS = "-L$nauty_lib";
+      undef $NautySrc;
+   } elsif (defined ($nauty_src=$options->{"nauty-src"}) && $nauty_src ne "bundled") {
+      check_nauty($nauty_src) or
+         die "Specified nauty source directory invalid, could not find 'nauty-h.in' in $nauty_src.";
+      $NautySrc = "$nauty_src";
+   }
+
+   if (!$nauty_src && $nauty_path ne "bundled" && $options->{prereq} ne ".none.") {
+      # compile test-program, soft-fail
+      my $testcode = <<'---';
+// simplified example from nautyex1.c from the nauty source
+
+#define MAXN 1000    /* Define this before including nauty.h */
+#include <nauty/nauty.h>
+#include <iostream>
+
+int
+main(int argc, char *argv[])
+{
+    graph g[MAXN*MAXM];
+    int lab[MAXN],ptn[MAXN],orbits[MAXN];
+    static DEFAULTOPTIONS_GRAPH(options);
+    statsblk stats;
+    int n = 5;
+    int m = 1;
+    int v;
+
+    options.writeautoms = FALSE;
+
+    /* The following optional call verifies that we are linking
+       to compatible versions of the nauty routines.            */
+
+    nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
+    EMPTYGRAPH(g,m,n);
+    for (v = 0; v < n; ++v)  ADDONEEDGE(g,v,(v+1)%n,m);
+
+    densenauty(g,lab,ptn,orbits,&options,&stats,m,n,NULL);
+    std::cout << "VERSION " << NAUTYVERSIONID << std::endl;
+
+    exit(0);
+}
+---
+      my $error=Polymake::Configure::build_test_program($testcode, LIBS => "-lnauty", CXXFLAGS => "$CXXFLAGS", LDFLAGS => "$LDFLAGS");
+
+      if ($? == 0) {
+         my $message=Polymake::Configure::run_test_program();
+         if ($?) {
+            check_nauty() and !defined($nauty_path) or
+               die "Could not run a test program checking for nauty library.\n",
+                   "The complete error log follows:\n\n$message\n",
+                   "Please investigate the reasons and fix the installation.\n";
+         } else {
+            ($nautyver) = $message =~ /VERSION (\d+)/;
+            my $nautymin = 25000; # version*10000
+            if ($nautyver < $nautymin) {
+               check_nauty() and !defined($nauty_path) or
+                  die "Your nauty version $nautyver is too old, at least version $nautymin is required.\n";
+            } else {
+               undef $NautySrc;
+            }
+         }
+      } else {
+         check_nauty() and !defined($nauty_path) or
+            die "Could not compile a test program checking for nauty.\n",
+                "The most probable reasons are that the library is installed at a non-standard location,\n",
+                "is not configured to build a shared module, or missing at all.\n",
+                "The complete error log follows:\n\n$error\n",
+                "Please install the library and specify its location using --with-nauty option, if needed.\n";
+      }
+   }
+
+   if ($NautySrc eq "bundled" && !check_nauty()) {
       die "Bundled nauty directory seems to be missing, to use the nauty interface\n",
           "with the minimal tarball please specify a nauty source directory\n",
-          "via --with-nauty-src=PATH.";
+          "via --with-nauty-src=PATH, or a nauty installation with --with-nauty=PATH.";
+   } elsif (!defined($NautySrc)) {
+      $LIBS = "-lnauty";
    }
 
-   return $NautySrc ? "$NautySrc" : "bundled";
+   return $NautySrc ? "source: $NautySrc" : ("version $nautyver @ ".($nauty_path//"system"));
 }