[Nauty-list] genbg vs. geng

[Brendan McKay]

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
> >