[Nauty] New nauty version limited release

Sterten at aol.com Sterten at aol.com
Fri Oct 22 20:49:01 EST 2004


Brendan:

>Nauty peoples,
>
>A new  version of nauty/gtools can be downloaded from
>     http://cs.anu.edu.au/~bdm/nauty/nauty22.tar.gz
>     http://cs.anu.edu.au/~bdm/nauty/nauty22.zip

shouldn't this be version 2.3  or later ?

>Use the second URL for DOS/Windows and the first for  everything else.
>
>I will wait for problems to be  reported before advertising this
>version on the web page, so if you  have nothing better to do please
>try it out and let me know of even  trivial problems.
>
>--> You should recompile all  programs that call nauty before
>--> concluding that nauty has  problems.

this _is_ some sort of problem.
There are many files, I once  created a batch file (DOS) to compile
them, now I get errors, some are not  compiled (e.g. splay,sumlines),
and there are multiple executables of  different versions. 
Some work, some not. OK, most work, multig.exe  works.
Also, when I make changes to a program, and then there is a new  version,
I might prefer to keep the old version with my changes  instead.
Or an automatic program which transfers my changes to the
new  version.

>=========================multig================================

I  added a line in multig.c:
if(argc<2 ||  argv[1][0]=='/'){printf("\n");printf(HELPTEXT);exit(1);} //## 
this line added  for DOS/Windows by Guenter Stertenbrink

> % multig  --help
>
> Usage: multig [-q] [-u|-T|-G] [-e#|-e#:#]  [-m#] [-f#] [infile [outfile]]
>

the "-" signs are not  necessary, e.g. 
"geng 7 1:20 | multig ue20" is well-defined
instead of  geng 7 1:20 | multig -u -e20

> Read undirected loop-free graphs  and replace their edges with multiple
>  edges in all possible  ways (multiplicity at least 1).
>  Isomorphic multigraphs  derived from the same input are suppressed.
>  If the input  graphs are non-isomorphic then the output graphs are also.
>  
>   -e# | -e#:#  specify a value or range of the  total number of  edges
>                 counting multiplicities
>   -m# maximum edge multiplicity  (minimum is 1)
>   Either -e or -m with a finite maximum  must be given

default could be: maximum multiplicity = n, e.g. if the  multigraph is
a group with 1s on the diagonal. 
BTW. then we have 2 sorts  of isomorphism: as multigraph or as group.
Maybe you can implement this 2nd  sort of isomorphism too ?
And a 3rd isomorphism: when we permute the  multiplicities,
the graphs were also considered  isomorphic

>   -f#  Use the group that fixes the  first # vertices setwise

?

>   -T  use a  simple text output format (nv ne {v1 v2 mult})

I'd like an additional  format with just the n*n numbers of the adjacency
matrix in one  line.

>   -G  like -T but includes group size as  third item (if less than 10^10)
>     The group  size does not include exchange of isolated vertices.

I think, I preferred  it, if it did. 
Or maybe an optional switch : "T+" or "T1"
BTW. I'd like  switches for directg,multig for the number of
sources,sinks,isolated  vertices.

>   -u  no output, just count  them
>   -q  suppress auxiliary  information
>
> This can be used in conjunction with a  source of simple graphs to
> generate nonisomorphic  multigraphs.  I'll give two examples.

...
OK with the  examples.

We could also just feed the complete graph into  multig
E.g.  multiplicities 0..4  is the same as multiplicities  1..5,
so these two are the same :

>geng 5 | multig -u  -m5                                                  
>A geng.exe -d0D4 n=5  e=0-10                                            
>Z 34 graphs generated in 0.00  sec                                           
    
>A multig  -m5u                                                               
    
>Z 34 graphs read from stdin; 533358 multigraphs generated; 2.09  sec         
    

>geng 5 10:10 | multig -u  -m6                                            
>A geng.exe -d0D4 n=5  e=10                                              
>Z 1 graphs generated in 0.00  sec                                            
    
>A multig  -m6u                                                               
    
>Z 1 graphs read from stdin; 533358 multigraphs generated; 9.56  sec          
    

assuming that each multi-digraph has exactly one source and one  sink
(this can be achieved) and that it can have multiple loops,
we have  the 1-1 correspondence via line-digraph with digraphs with 
m vertices and  the property that neighbor-sets are either disjoint or 
coincide.
Would it be  faster to generate these ? Well, when there are many edges
we have many  vertices in the line-digraph  which is not so good.

Suppose a list  of multigraphs and for each multiplicity c a list of numbers 
N_c
Is it  possible to generate all nonisomorphic multigraphs where multiedges  
with
multiplicity c are created in all possible ways with multiplicity from  N_c ?
multig -u -m7   were then the special case N_0=0 and  N_1={1,2,..,7}

>multig cannot presently generate loops.   That will change.

expectation value of duration ? (assuming "never"=10  years or such)

Also, directg can feed multig with graphs.
And then at  last one program geng, which generates multigraphs by default,
but (di)graphs  with appropriate parameters. (or vice versa)


Also, what about one big  executable which contains all programs ?
Call it n.exe or nau.exe (short  name), then e.g. n geng xxxxx
does the same as geng xxxxx etc.
Except  maybe that redirection of input/output is handled directly,
without  pipes.




-------------------
> A.  Generate  all multigraphs on 7 vertices and 20 edges.
>
>% geng 7  1:20 | multig -u -e20
>>A geng -d0D6 n=7  e=1-20
>>Z 1042 graphs generated in 0.00 sec
>>A  multig -ue20:20
>>Z 1042 graphs read from stdin; 28819926  multigraphs generated; 9.92 sec
>
>   geng  generated 1042 simple graphs with from 1 to 20 edges,
>    then multig added multiplicities to the edges so that the  total
>   multiplicity is 20.  Each simple edge gets  multiplicity at least 1.

geng 7 | multig -u -e20    gives  the same.
also  geng 7 21:21 | multig -u -e41     (substract 1 from each multiplicity)
but the latter is much  slower.
Wouldn't it be faster to expand nonedges to multiedges with  multiplicity 0..3
and edges to multiedges with multiplicity 4..7  in all  ways ?



>-------------------
>B.   Generate the 4 x 5 integer matrices with total sum 12
>    and entries {0,1,2,3}.
>
>% genbg 4 5 | multig -m3e12  -f4 -T
>
>The genbg command makes bipartite graphs with  4 vertices of the first
>colour and 5 of the second  colour.

better call them color 0 and color 1 or "with color" and without  color",
since they are not interchangeable.

genbg n n :  2,7,36,317,5624,251610,...
geng n | directg :  1,3,16,218,9608,1540944,...

and that although genbg - matrices can have  1s in the diagonal.
The reason is that with genbg we can exchange rows and  columns,
(but not transpose)
while with geng | directg we can only permute  vertices (rows)
and the columns are permuted accordingly without  freedom.


>The multig command changes each  edge
>to one of {1,2,3} since a limit of 3 is given by -m3.   The parameter
>-e12 says that the total sum of all edges is 12.  

entries in a 4*5 matrix suming to 12, so most entries are zero.
With  sum=30 I would expect that multiplying 0 into {0,1}
and 1 into {2,3} would be  faster ?!

>The -f4 says that
>in considering  isomorphisms the first 4 vertices are not mixed with
>the  others.  (For this application you would normally use -f with  the
>number of vertices in the first class.)

now I understand  the -f  switch

>The parameters of  genbg  can  restrict the structure somewhat; for example
>using -d1:1 will  ensure that no row or column is entirely zero.




Guenter. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20041022/c6a12836/attachment.html 


More information about the Nauty mailing list