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

Milestone 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.

Weighted Graph Files

Traveling Salesperson uses complete, undirected weighted graphs. The standard weighted edge-list format begins with:

n m

followed by m lines of the form:

u v weight

For example:

4 6
0 1 8
0 2 5
0 3 9
1 2 6
1 3 4
2 3 7

Weights are nonnegative integers. As with unweighted graphs, vertices are numbered from 0 through n-1, self-loops are not permitted, and parallel edges are not permitted.

A Traveling Salesperson instance must describe a complete graph, so every pair of distinct vertices must have a weight. For an n-vertex TSP instance, there are therefore

undirected edges.

TSPLIB-Style TSP Files

The course reader also supports a subset of TSPLIB-style symmetric TSP files. Files with a .tsp extension (including .tsp.gz) are detected automatically.

The supported coordinate format is:

TYPE: TSP
DIMENSION: n
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 x1 y1
2 x2 y2
...
EOF

TSPLIB node labels are conventionally numbered 1 through n. The course reader converts them to the 0-based vertex IDs used by the project API. Edge weights are computed using the standard TSPLIB EUC_2D rounding rule.

You are not expected to implement TSPLIB parsing or distance conversion. Your algorithm receives the same course-provided weighted-graph representation regardless of whether the input came from an explicit weighted edge list or a TSPLIB coordinate file.

Course-Generated Random TSP Files

Some large TSP benchmarks use a compact course-generated format instead of storing all $O(n^2)$ edge weights explicitly. These files use TSPLIB-style headers with:

EDGE_WEIGHT_TYPE: BBF_RANDOM_UNIFORM
BBF_RANDOM_SEED: ...
BBF_WEIGHT_MIN: ...
BBF_WEIGHT_MAX: ...

The course support code uses this metadata to generate the complete weighted graph deterministically. The same file therefore produces the same edge weights on every run without requiring a large explicit edge list.

You are not expected to generate or parse this format yourself. Treat these instances exactly like other weighted TSP instances through the course-provided weighted-graph interface described on the Program Interface page.