#

Clique Hiding Generator

## Source Code

Source code in C
is available here.
## Description

This is the program DELTA used to generate the graphs described in
Camouflaging Independent Sets in Quasi-Random Graphs
by Mark Brockington and Joseph Culberson.
Instructions for compiling are included in the documentation. Here is
a sample run:

tees% GraphGen -g20 -c3 -p0.500 -d0 -s889113

Input file name to write file to: (".b" will be appended)

sample

c Graph Generator

c

c By: Mark Brockington (brock@cs.ualberta.ca)

c and Joe Culberson (joe@cs.ualberta.ca)

c

c Graph Size:20, Clique Size: 3

c Seed:889113, Edge Density: 0.50000

c Depth 0 Hiding

c

c Clique Elements are:

c 19 17 15

c

c Estimated Size of Uncompressed File: 0.0MB

c

p edge 20 92

The file is written in DIMACS compressed format. See Michael Trick's
set of Graph Coloring
Instances.
for a description of this format and for various translation programs.

* NOTE: The graph hides a clique in its present form. * To convert
to an independent set hider, change the code after the line

/* Now, invert the graph to change the ind. set to a clique */

### KNOWN BUGS:

The hidden solution in the output is "off by one"; that is, the hidden
solution values are indexed from 0 to n-1, rather than the DIMACS format
of 1..n. I think it is too late to change this without causing a descrepancy
problem with older versions, and with the DIMACS files.
Joe Culberson

* April 1, 1995 Last Update March 31, 2004. *