latest version

1 files changed, 292 insertions, 0 deletions

diff --git a/graph-checker/nauty/README_24 b/graph-checker/nauty/README_24
new file mode 100644
index 0000000..35feb62
--- /dev/null
+++ b/graph-checker/nauty/README_24
@@ -0,0 +1,292 @@
+README file for nauty 2.4 
+This file is only of historical interest as this version is very old.
+
+Brendan McKay, bdm@cs.anu.edu.au
+
+------------------------------------------------------------
+
+The most recent distribution of nauty can be found at
+http://cs.anu.edu.au/~bdm/nauty .
+
+The manual nug.pdf is available at that site and is also included
+in the distribution package.
+
+Note that nauty is copyright but free to use for most purposes.
+The details are in the file nauty.h.
+
+The code in the file planarity.c (used by the planarg program)
+is copyright to the Magma project. 
+
+------------------------------------------------------------
+
+INSTALLATION.
+
+The first step is to unpack the archive.  On Unix-ish systems
+you can use one of these commands:
+
+   tar xzf nauty24.tar.gz
+or
+   gunzip -c nauty24.tar.gz | tar xf -
+
+This will write all the files into the subdirectory nauty24.
+Go to that directory.
+
+If you have a working shell, and make, you can run
+   ./configure
+followed by
+   make all
+to compile nauty for your system.
+
+If that succeeds without problem, you will have have the
+program dreadnaut ready to run.
+
+If you have problems during compilation, it may be that the
+configuration scripts are inadequate for your system.  Usually it
+is because of some missing system header, incompatible typedef,
+or similar.  Please send the details to the author.
+
+If you don't have a shell or make, manually edit the files nauty.h,
+naututil.h and gtools.h as distributed.  The parts between the lines
+======= near the start are the main things to look at.  After this
+manual editing, you can use makefile as a guide to compilation.
+
+Programs which use an older version of nauty need to be
+recompiled (** not just relinked **). Make sure they use the
+DEFAULTOPTIONS_GRAPH or DEFAULTOPTIONS_SPARSEGRAPH macro to define
+the fields of the options parameter.
+
+See below for compiling on a PC under DJGPP.
+
+If you are using Windows in an environment that needs Windows line
+endings (which is a configuration option in Cygwin, for example),
+then you might prefer to use nauty24.zip rather than
+nauty24.tar.gz.
+
+------------------------------------------------------------
+
+TESTING.
+
+After compiling nauty successfully, it is recommended that you run
+the included test programs.  The simplest way is
+    make checks
+
+------------------------------------------------------------
+
+MAILING LIST.
+
+There is a mailing list for announcements and discussion about
+nauty and related topics.  You can subscribe at
+http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
+
+------------------------------------------------------------
+
+OTHER FILES IN THE PACKAGE.
+
+A few additional goodies are included.
+
+sumlines.c  -  This is a program designed to digest the outputs from
+  multiple runs of a program (such as a computation split into multiple
+  parts).  Lines matching given patterns can be counted and checked,
+  and numbers appearing in them can be accumulated.  Instructions appear
+  in the source file.  See the option GMP near the head of the program
+  before trying to compile.
+
+naugroup.h, naugroup.c  -  These define procedures for exhaustively
+  listing a group found by nauty.  This is done in a space-efficient way.
+  A sample program appears in nautyex3.c, but so far there is no
+  complete documentation.
+
+------------------------------------------------------------
+
+DJGPP.
+
+The Unix-like environment DJGPP can be used to run nauty and gtools on
+DOS/Win computers.  DJGPP is available at http://www.delorie.com/djgpp .
+The program shortg does not work since DJGPP does not provide a working
+pipe() system call.  Using the bash shell is recommended.  In DOS,
+Windows NT and early Windows editions, you will need to convert all
+long file names to the 8+3 limits.  Thanks to Guenter Sterntenbrink
+for helping with this.
+
+If configure gives an error message similar to this:
+   can not guess host type: you must specify one
+then try
+   ./configure --host=i686
+or use i586 for Pentium 2.  If all of those fail, try
+   ./configure --host=unknown
+
+------------------------------------------------------------
+
+Making 32-bit executables on 64-bit Linux systems.
+
+(In bash or sh:)
+CFLAGS=-m32 CXXFLAGS=-m32 LDFLAGS=-m32 ./configure
+make clean; make
+
+This requires the libraries ia32-libs and libc6-dev-i386.
+
+------------------------------------------------------------
+
+RECENT CHANGES.
+
+Here we list substantive changes made since the first 2.2 release.
+
+Nov 16, 2002:  Replaced rng.c after communication with Don Knuth.
+  The previous version had a bug (mine!) when there was no explicit
+  initialization done by the user.  It appears the error had no
+  impact on nauty (which only uses rng.c for the "s" command in
+  dreadnaut, and for genrang, but both always initialize).
+  No change to the nauty version number but beta=2.
+
+Nov 18, 2000:  Adjusted the makefile and countg/testg to work in
+  the DOS/Win environment DJGPPP (see the previous section).
+
+May 1, 2003:  Fixed PRUNE feature of genbg.
+
+May 3, 2003:  Added utility directg for making all orientations of graphs.
+
+Oct 4, 2003:  Added options -a, -Z, -d, -z to genbg.  Also, the -l
+              (canonical label) option now preserves the colouring.
+
+Nov 17, 2003: Renamed INFINITY to NAUTY_INFINITY since many C header
+              libraries define INFINITY.  If INFINITY is not defined by
+              the system, you can still use it.
+
+Nov 19, 2003: Added program biplabg to relabel bipartite graphs with the
+              colour classes contiguous.
+
+Feb 13, 2004: Revised C options for solaris on pentium
+
+Mar 1, 2004:  dretog knows !...\n type of comment
+
+May 7, 2004:  geng can be called from another program (see instructions
+              in geng.c.)
+
+May 29, 2004: added definition of SETWORD_FORMAT used to write a setword
+              with printf( ) - see nauty.h
+
+Sep 11, 2004: Added utility multig for making multigraphs based on
+              provided simple graphs; similar to directg
+
+Oct 16, 2004: To avoid problems caused by system-dependent handling of
+              external declarations, nauty() no longer accepts NULL as
+              the value of options.dispatch.  To get the previous
+              behaviour, use the value &graph_dispatch.  This will be
+              handled automatically if programs calling nauty use
+              DEFAULTOPTIONS to declare options and are recompiled.
+              Even better is to use DEFAULTOPTIONS_GRAPH.
+
+May 5, 2005:  A bug in the writing of sparse6 was found and fixed.
+              This is procedure ntos6() in gtools.c, which is invoked
+              by writes6().  The bug could only happen if all the
+              following are true:
+              1.  n = 2, 4, 8 or 16 (for n=2, only if the graph has loops)
+              2.  Vertex n-2 has non-zero degree, but vertex n-1 has
+                  zero degree.
+              These conditions never happen for graphs generated by
+              geng or genbg, nor for regular graphs or connected graphs,
+              nor for graphs canonically labelled by nauty (except maybe
+              with some unusual vertex colouring or invariant).
+              If the conditions do happen, the buggy routine may
+              (with some probability) add a spurious loop to vertex n-1.
+
+              In the package is a utility checks6:
+
+              Usage: checks6 [-w] [infile [outfile]]
+              Check a file of graphs, optionally write corrected version
+              -w  Write corrected graphs (default is not to write)
+
+------now we start version 2.3 (not released) and 2.4------
+
+Nov 10, 2004: Use faster routine getc_unlocked() for reading graphs if
+              available.  It can make a surprising difference.
+
+Nov 17, 2004: If putenv() or setenv() are available, we set LC_COLLATE to
+              "C" before executing "sort" in shortg.  This should alleviate
+	      collation issues with sort.  However, note that many
+              utilities use the locale these days so you are advised to
+	      have LC_COLLATE defined to be "C" always when you are dealing
+              with files of graphs.
+
+              Six counters in statsblk became "unsigned long" instead of
+              "long".  nauty doesn't actually use these, but we might as
+              well give them twice as long before they overflow.
+
+Nov 24, 2004: Made geng faster for generating trees.  The output labelling
+              may be different from before.  A very much faster tree
+              generator is in the works.
+
+Jan 17, 2005: Added two items to dispatch vectors:
+               init   : used for initialising something at the start
+              cleanup : used for doing something at the end, such as
+                        freeing space allocated by init()
+              See the manual for calling sequences.
+
+May 20, 2005: Update graph6 and sparse6 formats to allow much large sizes.
+              The limit is now 68719476735 vertices (best of luck getting
+              close to that!).
+
+Nov 12, 2005: Changed NAUTY_INFINITY to 2^30+2 in BIGNAUTY case
+
+2006 various: Procedures for sparse graphs implemented.
+
+              New program planarg to test for planarity and find
+              planar embeddings:   planarg -help  for details.
+	      The planarity code was written by Paulette Lieby for the
+              Magma project and used with permission.
+
+	      labelg got -S to use sparse graphs.
+              genbg -N changed to genbg -n (only Gordon uses this).
+              genrang gained -R switch for regular graphs in text format.
+              gtools.c has code for reading and writing planarcode.
+              listg got a compile time option to select "Matrix" or
+                 "array" for Maple output.
+              pickg/countg got -T for counting triangles
+
+	      Better configuration for MacOSX.
+
+Nov 22, 2006: Removed usertcellproc from options.  Greater functionality
+              is now available using the new targetcell field in the
+              dispatch vector.  The u8 command has gone from dreadnaut.
+
+              Changed bestcell to targetcell in dispatch vector.
+
+Nov 29, 2006: Added extraoptions field (currently unused) to optionblk
+
+Dec 9, 2006:  Added an invariant adjacencies_sg(), recommended for digraphs
+              when using sparse representation.
+
+Dec 10, 2006: Remove BIGNAUTY, whose usefulness has passed.  Now the types
+	      shortish and permutation are synonymous with int always.
+              The limit on the number of vertices is 2^30 unless int
+              has only 16 bits (still any of them around?) in which
+              case it is 2^15-3. Programs previously linked with
+              files like nautyB.o can now be linked with nauty.o.
+              Alternatively, "make bigs" will create files like
+              nautyB.o by copying.
+
+June 26, 2007:  Fixed an error in  listg -s  reported by Evan Heidtmann.
+
+July 12, 2007:  Added -f option to directg.
+
+Aug 14, 2007:  Added -i,-I,-K options to shortg, parallel to labelg.
+              Since -k is used in labelg in place of -I, changed labelg
+              to use -I also, with -k remaining as an undocumented
+              compatibility feature.
+
+Aug-Sep 2007: Minor things:
+              * naututil-h.in now defines CPUTIME=0.0 as a last resort
+              * gtools.c now implements EDGECODE (not used anywhere yet)
+              * fixed definition of SG_FREE in nausparse.h (not used)
+              * geng favours space over time for n > 28 
+
+Oct 14, 2007: Added -T switch to shortg to specify scratch directory.
+
+Mar 3, 2008:  Fixed makefile for compilation in a 64-bit environment.
+
+Oct 11, 2008: Added -l and -m to genrang
+
+Nov 29, 2008: Slightly improved -c for geng and genbg
+              Added tournament generator gentourng.
+
+Mar 3, 2009:  Added -V to directg.