Coverage for moptipyapps / tsp / known_optima.py: 77%

1""" 

2A set of tools to load known optima in the TSPLib format. 

3 

4The TSPLib provides benchmark instances for the Traveling Salesperson 

5Problem (TSP). We provide a subset of these instances with up to 2000 cities 

6as resources in :mod:`~moptipyapps.tsp.instance`. Additionally, TSPLib 

7provides the optimal solutions for a subset of these instances. Within this 

8module here, we provide methods for reading the optimal solution files 

9in the TSPLib format. We also include as resources the optimal solutions to 

10the instances that our package provide as resources as well. 

11 

12You can get the list of instance names for which the optimal tours are 

13included in this package via :func:`list_resource_tours` and then load a tour 

14from a resource via :func:`opt_tour_from_resource`. If you want to read a tour 

15from an external file that obeys the TSPLib format, you can do so via 

16:func:`opt_tour_from_file`. 

17 

181. Gerhard Reinelt. TSPLIB - A Traveling Salesman Problem Library. 

19 *ORSA Journal on Computing* 3(4):376-384. November 1991. 

20 https://doi.org/10.1287/ijoc.3.4.376. 

21 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ 

222. Gerhard Reinelt. *TSPLIB95.* Heidelberg, Germany: Universität 

23 Heidelberg, Institut für Angewandte Mathematik. 1995. 

24 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf 

25""" 

26 

27from typing import Final, TextIO, cast 

28 

29import moptipy.utils.nputils as npu 

30import numpy as np 

31from pycommons.io.path import Path, file_path 

32from pycommons.types import check_to_int_range, type_error 

33 

34from moptipyapps.tsp.tsplib import open_resource_stream 

35 

36#: the set of known optimal tours 

37_TOURS: Final[tuple[str, ...]] = ( 

38 "a280", "att48", "bayg29", "bays29", "berlin52", "brg180", "ch130", 

39 "ch150", "cn11", "eil101", "eil51", "eil76", "fri26", "gr120", "gr202", 

40 "gr24", "gr48", "gr666", "gr96", "kroA100", "kroC100", "kroD100", 

41 "lin105", "pcb442", "pr1002", "pr76", "rd100", "st70", "tsp225", 

42 "ulysses16", "ulysses22") 

43 

44 

45def _from_stream(stream: TextIO) -> np.ndarray: 

46 """ 

47 Read an optimal tour from a stream. 

48 

49 :param stream: the text stream 

50 :return: the tour 

51 """ 

52 nodes: list[int] = [] 

53 in_tour: bool = False 

54 done_nodes: set[int] = set() 

55 max_node: int = -1 

56 

57 for the_line in stream: 

58 if not isinstance(the_line, str): 

59 raise type_error(the_line, "line", str) 

60 line = the_line.strip().upper() 

61 if len(line) <= 0: 

62 continue 

63 if line == "TOUR_SECTION": 

64 in_tour = True 

65 continue 

66 if line in {"-1", "EOF"}: 

67 break 

68 if in_tour: 

69 for node_str in line.rsplit(): 

70 node = check_to_int_range( 

71 node_str, "node", 1, 1_000_000_000_000) 

72 if node in done_nodes: 

73 raise ValueError(f"encountered node {node} twice") 

74 done_nodes.add(node) 

75 max_node = max(max_node, node) 

76 nodes.append(node - 1) 

77 if len(nodes) != max_node: 

78 raise ValueError( 

79 f"expected {max_node} nodes, got {len(nodes)} instead.") 

80 return np.array(nodes, npu.int_range_to_dtype(0, max_node - 1)) 

81 

82 

83def opt_tour_from_file(path: str) -> np.ndarray: 

84 """ 

85 Read a known optimal tour from a file. 

86 

87 :param path: the path to the file 

88 :return: the tour 

89 """ 

90 file: Final[Path] = file_path(path) 

91 with file.open_for_read() as stream: 

92 try: 

93 return _from_stream(cast("TextIO", stream)) 

94 except (TypeError, ValueError) as err: 

95 raise ValueError(f"error when parsing file {file!r}") from err 

96 

97 

98def opt_tour_from_resource(name: str) -> np.ndarray: 

99 """ 

100 Load an optimal tour from a resource. 

101 

102 >>> np.array2string(opt_tour_from_resource("ulysses16")) 

103 '[ 0 13 12 11 6 5 14 4 10 8 9 15 2 1 3 7]' 

104 

105 >>> np.array2string(opt_tour_from_resource("cn11")) 

106 '[ 0 2 3 6 9 10 5 8 7 1 4]' 

107 

108 :param name: the name string 

109 :return: the optimal tour 

110 """ 

111 if not isinstance(name, str): 

112 raise type_error(name, "name", str) 

113 with open_resource_stream(f"{name}.opt.tour") as stream: 

114 return _from_stream(stream) 

115 

116 

117def list_resource_tours() -> tuple[str, ...]: 

118 """ 

119 Get a tuple of the names of the optimal tours in the resources. 

120 

121 >>> list_resource_tours() 

122 ('a280', 'att48', 'bayg29', 'bays29', 'berlin52', 'brg180', 'ch130', \ 

123'ch150', 'cn11', 'eil101', 'eil51', 'eil76', 'fri26', 'gr120', 'gr202', \ 

124'gr24', 'gr48', 'gr666', 'gr96', 'kroA100', 'kroC100', 'kroD100', 'lin105', \ 

125'pcb442', 'pr1002', 'pr76', 'rd100', 'st70', 'tsp225', 'ulysses16', \ 

126'ulysses22') 

127 

128 :return: the tuple 

129 """ 

130 return _TOURS