Demo and validation tool for the RingDecomposerLib library. More...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "RDLtesting.h"
#include "TestDemo.h"
#include "TestValidate.h"

Detailed Description

Demo and validation tool for the RingDecomposerLib library.

This tool can be used for demo output and for testing/validation.

Demo output

Start the tool with

Test demo <filename>

The program will output the ring topology calculated by the library. The input file must be in DIMACS format as described below.

Validation

Start the tool with

Test validate <filename> [<timeout>]

The program will compare the relevant cycles to the cycles present in the input file. Furthermore the URFs will be validated, i.e. calculated with an independent exponential algorithm (definition of the URFs). The same procedure is applied to the SSSR (verify it's a cycle base). A number of consistency tests is executed to ensure integrity and robustness. See the file test/README for a descriptions of the test files.

The input file must be in DIMACS format as described below. A number of interesting example graphs are in the folder test.

The parameter timeout is optional and specifies a timeout in seconds for the exponential URF validation and the SSSR validation algorithm. (Timeouts are failures!)

File format

The input file format is a (modified) DIMACS graph format. See folder test for example files. Graph format specification:

First line:

p <number of nodes> <number of edges> [<nof cycles>]

with <nof cycles> optional.

Then the edges of the graph follow

e <node1> <node2>

If <nof cycles> was specified, then the relevant cycles of the graph are listed:

r <ring id> <ring size> <node1> <node2>

<ring id> and <ring size> are repeated for each edge of the graph as specified by <node1> and <node2>.