[Nauty-list] genbg vs. geng
Brendan McKay
bdm at cs.anu.edu.au
Fri Jun 27 09:02:56 EST 2008
geng -b generates bipartite graphs. All graph isomorphisms
are taken into account.
genbg generates bicoloured graphs with the colours distinguished.
Only colour-preserving isomorphisms are taken into account.
The consequence is that each connected graph generated by geng -b
corresponds to 1 or 2 connected graph generated by genbg. For
disconnected graphs the ratio can be higher than 2.
If you want the general isomorphism used by geng -b but you still
want the vertices labelled in order of a 2-colouring, then filter
the graphs through biplabg.
Brendan.
* Pawel Pralat <pralat at mathstat.dal.ca> [080627 01:45]:
>
> It seems that there is something wrong with `genbg n n':
>
> $ ../../nauty/genbg -c 6 6 > test.txt
> >A ../../nauty/genbg n=6+6 e=11:36 d=1:1 D=6:6 c
> >Z 194203 graphs generated in 0.35 sec
> $ ../../nauty/shortg test.txt
> >A shortg test.txt
> >Z 194203 graphs read from test.txt
> >Z 98621 graphs written to test.txt
>
> P
>
> On Thu, 26 Jun 2008, Pawel Pralat wrote:
>
> >
> > Hi,
> >
> > I needed all connected bipartite graphs on 12 vertices. I used
> > (fortunately?) the following
> >
> > $ ../../nauty/genbg -c 1 11 > 12_vert.txt
> > >A ../../nauty/genbg n=1+11 e=11:11 d=1:1 D=11:1 c
> > >Z 1 graphs generated in 0.00 sec
> > $ ../../nauty/genbg -c 2 10 >> 12_vert.txt
> > >A ../../nauty/genbg n=2+10 e=11:20 d=1:1 D=10:2 c
> > >Z 30 graphs generated in 0.00 sec
> > $ ../../nauty/genbg -c 3 9 >> 12_vert.txt
> > >A ../../nauty/genbg n=3+9 e=11:27 d=1:1 D=9:3 c
> > >Z 853 graphs generated in 0.01 sec
> > $ ../../nauty/genbg -c 4 8 >> 12_vert.txt
> > >A ../../nauty/genbg n=4+8 e=11:32 d=1:1 D=8:4 c
> > >Z 14549 graphs generated in 0.07 sec
> > $ ../../nauty/genbg -c 5 7 >> 12_vert.txt
> > >A ../../nauty/genbg n=5+7 e=11:35 d=1:1 D=7:5 c
> > >Z 98726 graphs generated in 0.25 sec
> > $ ../../nauty/genbg -c 6 6 >> 12_vert.txt
> > >A ../../nauty/genbg n=6+6 e=11:36 d=1:1 D=6:6 c
> > >Z 194203 graphs generated in 0.36 sec
> > $ cat 12_vert.txt | wc -l
> > 308362
> >
> > to get 308362 graphs but my collegue used
> >
> > $ ../../nauty/geng -cbu 12
> > >A ../../nauty/geng -cbd1D11 n=12 e=11-36
> > >Z 212780 graphs generated in 0.55 sec
> >
> > and got a lot less. It seems that geng -cb does not work properly, doesn't
> > it?
> >
> > Cheers,
> > -- Pawel
> >
More information about the Nauty
mailing list