Input Files

Beyond Brute Force uses standard input formats shared by multiple project problems.

The course-provided support code reads these files and converts each input into the representation passed to your algorithm.

You need to understand the formats well enough to inspect supplied instances and create your own test cases, but you are not expected to write the low-level parsing code yourself.

Each invocation of src/solve.py processes one problem instance.

Instance Names

Unless an explicit identifier is supplied on the command line, an instance is identified by the name of its input file without the filename extension.

For example:

tests/example-01.txt

has the instance identifier:

example-01

The directory containing the file is not part of the identifier.

The identifier may be overridden using the --instance option described on the Program Interface page.

Unweighted Graph Files

Several project problems use simple, unweighted graphs.

The standard text representation begins with two integers:

n m

where:

• n is the number of vertices; and
• m is the number of edges.

Vertices are numbered consecutively beginning with 0:

The next m lines each contain two integers identifying the endpoints of one edge.

For example:

5 6
0 1
0 2
1 2
2 3
2 4
3 4

describes a graph with five vertices and six edges.

For an undirected graph, endpoint order is not significant. Thus:

0 2

and

2 0

describe the same edge.

Unless a problem specification explicitly states otherwise, graph instances are simple:

• self-loops are not permitted; and
• parallel edges are not permitted.

The supplied reader will report malformed input rather than silently changing the graph.

Text edge-list files use the .txt filename extension.

graph6 Files

Some experimental graph collections will be produced using Brendan McKay’s geng program.

geng represents graphs using the graph6 format.

Course-provided support code will decode graph6 instances into the same internal graph representation used for ordinary unweighted edge-list files. Your solving algorithms therefore do not need to know which representation was used to store the original graph.

You are not expected to implement graph6 encoding or decoding.

A .g6 input file passed to src/solve.py contains one graph6 instance.

When geng is used to generate many graphs, the provided experimental tools may separate its output into individual instances before invoking your solver.

Creating Your Own Test Instances

You are expected to create additional test cases while developing and evaluating your algorithms.

For an unweighted graph instance:

1. choose the number of vertices;
2. choose the edges;
3. place the correct values of n and m on the first line; and
4. place one edge on each subsequent line.

For example:

4 3
0 1
1 2
2 3

represents a path on four vertices.

Creating your own instances is useful for testing:

• very small graphs whose answers can be determined by hand;
• boundary cases;
• disconnected graphs;
• graphs containing isolated vertices; and
• graph structures that you expect to be especially easy or difficult for an algorithm.

Supplied and Gradescope Test Instances

Checkpoint instructions may include public test instances whose expected answers are known.

These files are provided so that you can test your implementation before submitting it.

Gradescope may also use additional test instances that are not included in the public collection. Hidden tests will follow the same documented input formats and assumptions as the public instances.

Your implementation should therefore solve the documented problem rather than depend on particular supplied test files.

Additional Input Formats

Some project problems require additional information that cannot be represented by an unweighted edge list. For example, Traveling Salesperson instances require edge weights.

Additional shared formats will be documented on this page as they are defined, rather than being independently redefined on each problem specification page.