[Nauty] Questions - Generating graph families
Brendan McKay
Brendan.McKay at anu.edu.au
Sun Jul 16 12:12:14 AEST 2023
Hi Diego,
The tools for doing exactly this are not present, but it is a suitable
candidate
for the PRUNE/DEGPRUNE feature of geng.c because the property is inherited
by induced subgraphs.
Make a file diego.c like this:
-------------------------------------------------------
#include "gtools.h"
boolean diego(graph *g, int n, int maxn)
/* Return TRUE if it can be determined that every descendant
will have 3 or more vertices of degree >= 3. */
{
int i,numbig;
if (POPCOUNT(g[n-1]) < 3) return FALSE;
numbig = maxn - n + 1;
if (numbig > 2) return TRUE;
for (i = n-1; --i >= 0; )
{
if (POPCOUNT(g[i]) > 2) ++numbig;
if (numbig > 2) return TRUE;
}
return FALSE;
}
-------------------------------------------------------
Now compile like this:
gcc -o diego -O3 -march=native -DMAXN=WORDSIZE -DWORDSIZE=32 -DPREPRUNE=diego geng.c diego.c nautyW1.a
The program diego now has all the features of geng except that the
output is restricted to those graphs with at most two vertices of degree
> 2.
The idea with a pruning function is that returning TRUE causes this
graph and all its descendants to be discarded. This example uses the
fact that the latest vertex added (vertex n-1 here) is a vertex of
maximum degree in this subgraph. (This does NOT imply that the vertices
are in non-decreasing order of degree.)
For example, "diego 18" makes 1500591 graphs in 110 seconds, and "diego
-c 18" makes 281579 connected graphs in the same time. My tests were
very brief so use with care.
These graphs have a rather simple structure and making them directly
would be much faster, at the cost of more complicated programming.
Brendan.
On 15/7/2023 9:30 am, Diego J wrote:
> *Good morning,*
>
> I am using nauty and traces software to generate families of graphs. I need
> to generate a family with maximum of 2 vertices of degree greater than or
> equal to 3, which I don't know if it's possible. I would like everyone's
> help.
>
> Diego.
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty
More information about the Nauty
mailing list