Source code for tsplib95.parser

# -*- coding: utf-8 -*-
import collections


VALUE_TYPES = {
    'NAME': str,
    'TYPE': str,
    'COMMENT': str,
    'DIMENSION': int,
    'CAPACITY': int,
    'EDGE_WEIGHT_TYPE': str,
    'EDGE_WEIGHT_FORMAT': str,
    'EDGE_DATA_FORMAT': str,
    'NODE_COORD_TYPE': str,
    'DISPLAY_DATA_TYPE': str,
}


[docs]class ParsingError(Exception): """Error raised when a given file cannot be parsed. This indicates the file does not conform to the standard TSPLIB95 file format. """ def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.line = None
class Stream: def __init__(self, lines): self.lines = iter(lines) self.line = self._get_next() def __next__(self): self.line = self._get_next() return self.line def _get_next(self): try: line = '' while not line: line = next(self.lines).strip() except StopIteration: return None return line def get_next_tour(sequence): tour = [] while sequence: index = sequence.pop(0) if index == -1: if sequence == [-1]: sequence.pop(0) return tour tour.append(index) raise ParsingError('all tours must end with -1') def read_integer_sequence(stream): while True: try: yield from map(int, stream.line.split()) next(stream) except (ValueError, AttributeError): break def split_kv(line): k, v = line.split(':', 1) return k.strip(), v.strip() def parse(text): stream = Stream(text.splitlines()) data = {} try: transition = start while transition: transition = transition(data, stream) except ParsingError as e: e.line = stream.line raise return data def start(data, stream): next(stream) return process_line def finish(data, stream): return None def process_line(data, stream): if stream.line is None or stream.line == 'EOF': return finish if ':' in stream.line: return process_key_value else: return process_key def process_key_value(data, stream): key, value = split_kv(stream.line) try: parser = VALUE_TYPES[key] except KeyError: raise ParsingError(f'{key} is not a valid keyword') data[key] = parser(value) next(stream) return process_line def process_key(data, stream): key = stream.line next(stream) key_parsers = { 'NODE_COORD_SECTION': parse_node_coords, 'DEPOT_SECTION': parse_depots, 'DEMAND_SECTION': parse_demands, 'EDGE_DATA_SECTION': parse_edge_data, 'FIXED_EDGES_SECTION': parse_fixed_edges, 'DISPLAY_DATA_SECTION': parse_display_data, 'TOUR_SECTION': parse_tours, 'EDGE_WEIGHT_SECTION': parse_edge_weights, } try: return key_parsers[key] except KeyError: raise ParsingError(f'{key} is not a valid keyword') def parse_node_coords(data, stream): section = data['NODE_COORD_SECTION'] = collections.OrderedDict() while True: if stream.line is None: break index, *reals = stream.line.split() try: index = int(index) except ValueError: break if len(reals) not in (2, 3): raise ParsingError('node coords must be 2d or 3d') coord = tuple(map(float, reals)) section[index] = coord next(stream) return process_line def parse_depots(data, stream): section = data['DEPOT_SECTION'] = [] while True: if stream.line is None: raise ParsingError('depot section must end with -1') try: depot = int(stream.line) except ValueError: raise ParsingError('not a valid depot') if depot == -1: break section.append(depot) next(stream) next(stream) return process_line def parse_demands(data, stream): section = data['DEMAND_SECTION'] = {} while True: if stream.line is None: break try: index, demand = stream.line.split() except ValueError: break try: index, demand = int(index), int(demand) except ValueError: break section[index] = demand next(stream) return process_line def parse_edge_data(data, stream): edge_format = data['EDGE_DATA_FORMAT'] return { 'EDGE_LIST': parse_edge_list, 'ADJ_LIST': parse_adj_list, }[edge_format] def parse_edge_list(data, stream): section = data['EDGE_DATA_SECTION'] = [] while True: if stream.line is None: raise ParsingError('edge lists must end with a -1') try: u, v = stream.line.split() except ValueError: break try: edge = int(u), int(v) except ValueError: raise ParsingError('not a valid edge') section.append(edge) next(stream) if stream.line != '-1': raise ParsingError('edge lists must end with a -1') next(stream) return process_line def parse_adj_list(data, stream): section = data['EDGE_DATA_SECTION'] = collections.OrderedDict() while True: if stream.line is None: raise ParsingError('entire adjacency list must end with a -1') *values, end = stream.line.split() if end != '-1': raise ParsingError('adjacency list must end with a -1') if not values: break node, *neighbors = map(int, values) section[node] = neighbors next(stream) next(stream) return process_line def parse_fixed_edges(data, stream): section = data['FIXED_EDGES_SECTION'] = [] while True: if stream.line is None: raise ParsingError('fixed edges must end with a -1') try: u, v = stream.line.split() except ValueError: break try: edge = int(u), int(v) except ValueError: raise ParsingError('fixed edges must be two integer ' 'coordinate indicies') section.append(edge) next(stream) if stream.line != '-1': raise ParsingError('fixed edges must end with a -1') next(stream) return process_line def parse_display_data(data, stream): section = data['DISPLAY_DATA_SECTION'] = collections.OrderedDict() while True: if stream.line is None: break index, *reals = stream.line.split() try: index = int(index) except ValueError: break if len(reals) not in (2, 3): raise ParsingError('display data must be either 2d or 3d') coord = tuple(map(float, reals)) section[index] = coord next(stream) return process_line def parse_tours(data, stream): section = data['TOUR_SECTION'] = [] sequence = list(read_integer_sequence(stream)) while sequence: tour = get_next_tour(sequence) section.append(tour) return process_line def parse_edge_weights(data, stream): data['EDGE_WEIGHT_SECTION'] = list(read_integer_sequence(stream)) return process_line