[Nauty-list] accept only graphs with subgraphs isomorphic to predefined subset

Gregory Puleo gpuleo at gmail.com
Wed Oct 23 06:57:05 EST 2013


Although, on closer reading of your message: while this may solve the
problem of how to do your initialization, I'm not sure that the algorithm
you described will have the effect you want. While it will indeed "accept
only graphs with subgraphs isomorphic to predefined subset", it will also
reject lots of graphs that *do* have such subgraphs, if the subgraph is not
generated in the first 11 vertices.

For illustration, suppose I want to reject all graphs without K_2 as an
induced subgraph; clearly, I should only reject the empty graph, but many
nonempty graphs will have an empty n=2 subgraph; in fact, after a quick
test it seems that only the complete graph has K_2 as its n=2 subgraph.

Is this the intended behavior?

-Greg


On Tue, Oct 22, 2013 at 2:42 PM, Gregory Puleo <gpuleo at gmail.com> wrote:

> It looks like the ideal solution here is to use the GENG_MAIN preprocessor
> variable, do the initialization in your own main function, and then call
> GENG_MAIN from there. From geng.c:
>
> CALLING FROM A PROGRAM
>
>    It is possible to call geng from another program instead of using it
>    as a stand-alone program.  The main requirement is to change the name
>    of the main program to be other than "main".  This is done by defining
>    the preprocessor variable GENG_MAIN.  You might also like to define
>    OUTPROC to be the name of a procedure to receive the graphs. To call
>    the program you need to define an argument list argv[] consistent with
>    the usual one; don't forget that argv[0] is the command name and not
>    the first argument.  The value of argc is the number of strings in
>    argv[]; that is, one more than the number of arguments.  See the
>    sample program callgeng.c.
>
> -Greg
>
>
> On Tue, Oct 22, 2013 at 2:03 PM, Hoy, Robert <rshoy at usf.edu> wrote:
>
>> Hi, everybody.  I want to define a set G of about 1600 subgraphs at the m
>> = 11 level such that the PRUNE function of geng rejects all n = 11
>> subgraphs that are not isomorphic to any of the graphs in the set G.
>>
>> The (very) slow way to do this is to read the graphs in from a file each
>> time PRUNE is called for n = 11, but obviously I don't want to do that.
>>  Instead I want to read them in only once, i.e. at the beginning of the
>> geng program, e.g. something like
>>
>> geng.c:
>>
>> graph myset[1645];
>>
>> appropriategengfunction {
>> /* fill myset by reading from file */
>> }
>>
>> where "appropriategengfunction" is called when geng starts up, and
>> prune.c can access my set via something
>>
>> extern graph myset[1645];
>>
>> (and then prune.c will do the appropriate pruning)
>>
>> =========
>>
>> Any tips on how to do this?  I'm not sure what the "appropriate" geng
>> function would be, or even whether it's in geng.c rather than (say) nauty.c.
>>
>> Any help would be greatly appreciated.
>>
>> Thanks,
>> Rob
>>
>> Robert Hoy
>> Assistant Professor of Physics
>> University of South Florida
>> 813-974-0063
>>
>>
>>
>> _______________________________________________
>> Nauty-list mailing list
>> Nauty-list at cs.anu.edu.au
>> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
>>
>
>
>
> --
> Gregory Puleo
> http://www.math.uiuc.edu/~puleo/
>



-- 
Gregory Puleo
http://www.math.uiuc.edu/~puleo/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20131022/4b1f3946/attachment.html 


More information about the Nauty mailing list