[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