2. Read TSPLIB sections

A TSPLIB file has keyword/value headers followed by a coordinate or edge-weight section. The headers can come in any order, which is what sections is for. This step builds a reader for EUC_2D coordinates, then compares it with the full TSPLIB library reader.

All commands run from the repository root. Start with DIMACS CNF if captures and repeats are new to you.

Read keyword/value headers

Each sections arm has a line pattern. An ordinary arm must match once; optional allows it to be absent. Each arm still permits at most one match. The patterns below accept both DIMENSION:3 and DIMENSION : 3 because pattern spacing beside punctuation can be empty.

comment "COMMENT"
sections until "EOF" {
  "NAME : {name:rest}" optional
  "DIMENSION : {n:2..46340}"
  "EDGE_WEIGHT_TYPE : {edge_weight_type:word}"
}

COMMENT A small coordinate instance
EDGE_WEIGHT_TYPE:EUC_2D
NAME : triangle
DIMENSION : 3
EOF

iris read site/examples/tutorial/tsplib-headers.iris site/examples/tutorial/tsplib-headers.txt --dzn

edge_weight_type = "EUC_2D";
name = "triangle";
n = 3;

rest captures the remaining matching text, including spaces within a name. word captures one word. Entry order follows the order in which the arms execute, so edge_weight_type appears before name in this output.

The EOF token ends sections and is consumed. Sections also end at actual end of input; until "EOF" does not require the token to appear. Required arms are checked when sections end. See sections in the Specification.

Add the coordinates

An arm’s body can read subsequent input. The NODE_COORD_SECTION body reads n triples: a node ID, an x coordinate and a y coordinate. The dimension must have been read before this body runs. Sections accept arms in any order, but they do not postpone a body until the names it uses are defined.

comment "COMMENT"
sections until "EOF" {
  "NAME : {name:rest}" optional
  "DIMENSION : {n:2..46340}"
  "EDGE_WEIGHT_TYPE : {edge_weight_type:word}"
  "NODE_COORD_SECTION" {
    repeat n {
      node: int
      x: float
      y: float
    }
  }
}
check edge_weight_type == "EUC_2D" "this reader requires EUC_2D coordinates"
check x >= -1e9 && x <= 1e9 && y >= -1e9 && y <= 1e9 "coordinates must be between -1e9 and 1e9"

NAME : triangle
EDGE_WEIGHT_TYPE : EUC_2D
DIMENSION:3
NODE_COORD_SECTION
1 0 0
2 3 0
3 3 4
EOF

iris read site/examples/tutorial/tsplib-coordinates.iris site/examples/tutorial/tsplib-coordinates.txt --dzn

name = "triangle";
edge_weight_type = "EUC_2D";
n = 3;
node = [1, 2, 3];
x = [0.0, 3.0, 3.0];
y = [0.0, 0.0, 4.0];

The repeat produces three parallel arrays. Coordinates are floats even when the input spells them as integers. The checks require the supported distance type and bound both coordinate columns. In the coordinate check, x and y denote fields of the same record, so they are checked together for every node.

This reader stores node IDs without requiring consecutive numbering. Use index 1 instead of node: int when a format requires exactly 1, 2, 3, … and you do not need to retain the IDs. See index statements and checks.

Finish with the library reader

The library supports coordinate and explicit matrix instances. It makes the payload arms optional, then checks which payload the declared edge-weight type requires. defined guards names whose arms may not have run. An omitted edge-weight type defaults to EXPLICIT; an omitted matrix layout defaults to FULL_MATRIX when the weight section runs.

format tsplib

comment "COMMENT"
sections until "EOF" {
  "NAME : {name:rest}" optional
  "TYPE : {type:word}" optional
  "DIMENSION : {n:2..46340}"
  "EDGE_WEIGHT_TYPE : {edge_weight_type:word}" optional
  "EDGE_WEIGHT_FORMAT : {edge_weight_format:word}" optional
  "NODE_COORD_TYPE : {node_coord_type:word}" optional
  "DISPLAY_DATA_TYPE : {display_data_type:word}" optional
  "NODE_COORD_SECTION" optional {
    repeat n {
      node: int
      x: float
      y: float
    }
  }
  "EDGE_WEIGHT_SECTION" optional {
    if !defined(edge_weight_format) {
      let edge_weight_format = "FULL_MATRIX"
    }
    weight[n][n]: 0..gecode.int_max / n layout edge_weight_format
  }
  "DISPLAY_DATA_SECTION" optional {
    repeat n {
      display_node: int
      display_x: float
      display_y: float
    }
  }
}
if !defined(edge_weight_type) {
  let edge_weight_type = "EXPLICIT"
}

if edge_weight_type == "EXPLICIT" {
  check defined(weight) "no EDGE_WEIGHT_SECTION"
  check size(weight) == n "edge weights do not match DIMENSION"
} else {
  check edge_weight_type == "EUC_2D" ||
    edge_weight_type == "CEIL_2D" ||
    edge_weight_type == "ATT" ||
    edge_weight_type == "GEO"
    "EDGE_WEIGHT_TYPE must be EXPLICIT, EUC_2D, CEIL_2D, ATT, or GEO"
  check defined(x) "no NODE_COORD_SECTION"
  check size(x) == n "coordinates do not match DIMENSION"
  check x >= -1e9 && x <= 1e9 && y >= -1e9 && y <= 1e9 "coordinates must be between -1e9 and 1e9"
}

NAME : handmade-euc-2d-five
TYPE : TSP
DIMENSION : 5
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_TYPE : TWOD_COORDS
NODE_COORD_SECTION
1 0 0
2 3 0
3 3 4
4 0 4
5 1.5 2
EOF

iris read formats/tsplib/tsplib.iris formats/tsplib/cases/euc-2d-five/input.txt --dzn

name = "handmade-euc-2d-five";
'type' = "TSP";
n = 5;
edge_weight_type = "EUC_2D";
node_coord_type = "TWOD_COORDS";
node = [1, 2, 3, 4, 5];
x = [0.0, 3.0, 3.0, 0.0, 1.5];
y = [0.0, 0.0, 4.0, 4.0, 2.0];

The data contains coordinates. The host computes distances for EUC_2D, CEIL_2D, ATT or GEO; the reader spec does not perform that conversion. The library page also shows explicit weights and a missing weight-section failure. The Specification defines matrix layouts.

Continue with job shop records and checks, or read the sections guide for repeated and missing headers.