tspreader.go 4.87 KB
Newer Older
1
// =======================================================
CedricPump's avatar
CedricPump committed
2
// read tsp Data saved in Data format of
3
4
5
// Gerhard Reinelt
// Universität Heidelberg
// Institut für Informatik
CedricPump's avatar
CedricPump committed
6
// Data: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/
7
8
9
10
11
12
13
//
// Documentation: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf
//
// Author Cedric Pump, Student, Technische Hochschule Lübeck
// =======================================================


CedricPump's avatar
- init    
CedricPump committed
14
15
16
17
18
19
20
package tspreader

import (
	"bufio"
	"errors"
	"fmt"
	"log"
21
	"math"
CedricPump's avatar
- init    
CedricPump committed
22
23
24
25
26
27
	"os"
	"strconv"
	"strings"
)

type TspSpec struct {
CedricPump's avatar
CedricPump committed
28
29
30
31
32
33
34
	Name             string
	ProblemType      string
	Comment          string
	Dimension        int
	EdgeWeightType   string
	EdgeWeightFormat string
	Data             *TspData
CedricPump's avatar
- init    
CedricPump committed
35
36
37
}

type TspData struct {
CedricPump's avatar
CedricPump committed
38
39
	Datatype string
	Values   *[][] float64
CedricPump's avatar
- init    
CedricPump committed
40
41
}

42
43
44
45
46
// NewTspSpec
// ------------------------------------
// Constructs empty TSP Specification
// ------------------------------------
func NewTspSpec() *TspSpec {
CedricPump's avatar
CedricPump committed
47
	return &TspSpec{Name: "", ProblemType: "TSP", Comment: "", Dimension: 0, EdgeWeightType: "", Data: NewTspData()}
CedricPump's avatar
- init    
CedricPump committed
48
49
}

50
51
52
53
54
// NewTspData
// ------------------------------------
// Constructs empty TSP Specification Data
// ------------------------------------
func NewTspData() *TspData {
CedricPump's avatar
CedricPump committed
55
	return &TspData{Datatype: "EDGE_WEIGHT_SECTION", Values: &[][]float64{}}
CedricPump's avatar
- init    
CedricPump committed
56
57
}

58
59
60
61
// String
// ------------------------------------
// Returns string representation of TSP Specification
// ------------------------------------
CedricPump's avatar
- init    
CedricPump committed
62
func (t TspSpec) String() string {
CedricPump's avatar
CedricPump committed
63
	return fmt.Sprintf("%s [%s] - %s %s %d", t.Name, t.ProblemType, t.EdgeWeightType, t.EdgeWeightFormat, t.Dimension)
64
65
}

66
67
68
69
// String
// ------------------------------------
// Returns string representation of TSP Data
// ------------------------------------
70
func (t TspData) String() string {
CedricPump's avatar
CedricPump committed
71
	return fmt.Sprintf("Datatype: %s", t.Datatype)
CedricPump's avatar
- init    
CedricPump committed
72
73
}

74
75
// Read
// ------------------------------------
CedricPump's avatar
CedricPump committed
76
// Reads TSP Data from .tsp file
77
// ------------------------------------
CedricPump's avatar
- init    
CedricPump committed
78
79
80
81
82
83
84
85
func Read(path string) (*TspSpec, error) {
	file, err := os.Open(path)
	if(err != nil) {
		log.Fatal(err)
		return nil, errors.New("unable to open file")
	}
	scanner := bufio.NewScanner(file)

86
	spec := NewTspSpec()
CedricPump's avatar
- init    
CedricPump committed
87
88
89
	dataLine := -1
	arr := [][]float64{}

90
91
92
	line := ""
	for scanner.Scan() && line != "EOF" {
		line = scanner.Text()
93
94

		// handle Specification Headers
CedricPump's avatar
- init    
CedricPump committed
95
96
97
98
		if strings.Contains(line,":") {
			strs := strings.Split(line, ":")
			switch strings.ReplaceAll(strs[0]," ","") {
			case "NAME": {
CedricPump's avatar
CedricPump committed
99
				spec.Name = strings.ReplaceAll(strs[1]," ","")
100
				break
CedricPump's avatar
- init    
CedricPump committed
101
102
			}
			case "TYPE": {
CedricPump's avatar
CedricPump committed
103
				spec.ProblemType = strings.ReplaceAll(strs[1]," ","")
104
				break
CedricPump's avatar
- init    
CedricPump committed
105
106
			}
			case "COMMENT": {
CedricPump's avatar
CedricPump committed
107
				spec.Comment = strings.ReplaceAll(strs[1]," ","")
108
				break
CedricPump's avatar
- init    
CedricPump committed
109
110
111
112
			}
			case "DIMENSION": {
				i, e := strconv.ParseInt(strings.ReplaceAll(strs[1]," ",""),10,64)
				if(e == nil) {
CedricPump's avatar
CedricPump committed
113
					spec.Dimension = int(i)
CedricPump's avatar
- init    
CedricPump committed
114
				}
115
				break
CedricPump's avatar
- init    
CedricPump committed
116
117
			}
			case "EDGE_WEIGHT_TYPE": {
CedricPump's avatar
CedricPump committed
118
				spec.EdgeWeightType = strings.ReplaceAll(strs[1]," ","")
119
				break
CedricPump's avatar
- init    
CedricPump committed
120
121
			}
			case "EDGE_WEIGHT_FORMAT": {
CedricPump's avatar
CedricPump committed
122
				spec.EdgeWeightFormat = strings.ReplaceAll(strs[1]," ","")
123
				break
CedricPump's avatar
- init    
CedricPump committed
124
125
126
			}
			}
		} else {
127
			// Sace Data as Multi Dimensional Array
CedricPump's avatar
- init    
CedricPump committed
128
			if dataLine == -1 {
CedricPump's avatar
CedricPump committed
129
				spec.Data.Datatype = strings.ReplaceAll(line," ","")
CedricPump's avatar
- init    
CedricPump committed
130
131
132
133
				dataLine++
			} else {
				entries := strings.Split(line, " ")

134
135
				if entries[0] != "EOF" {
					arr = append(arr, []float64{})
CedricPump's avatar
- init    
CedricPump committed
136

137
138
139
140
141
					for _, e := range entries {
						f, err := strconv.ParseFloat(e, 64)
						if err == nil {
							arr[dataLine] = append(arr[dataLine], f)
						}
CedricPump's avatar
- init    
CedricPump committed
142
					}
143
					dataLine++
CedricPump's avatar
- init    
CedricPump committed
144
145
146
147
148
				}
			}
		}

	}
CedricPump's avatar
CedricPump committed
149
	spec.Data.Values = &arr
150

CedricPump's avatar
CedricPump committed
151
	if spec.Data.Datatype != "EDGE_WEIGHT_SECTION" {
152
153
154
		cordToMatrix(spec)
	}

155
	// return specification
CedricPump's avatar
- init    
CedricPump committed
156
157
	return spec, nil
}
158
159

func cordToMatrix(spec *TspSpec)  {
CedricPump's avatar
CedricPump committed
160
	arr := *spec.Data.Values
161
162
	outarr := [][]float64{}

CedricPump's avatar
CedricPump committed
163
164
	switch spec.EdgeWeightType {
	case "EUC_2D":{
165
166
167
168
169
170
171
172
173
174
175
176
177
178
		// entries in euclidean 3d space in form of [index, lat, long]
		// distance calculation for points p1 to p2 with
		// p1 = (x1, y1) and p2 = (x2, y2):
		// d = √[( y2 –  y1)² + ( x1 –  x2)²]
		for i, node1 := range arr{
			outarr = append(outarr, []float64{})
			for _, node2 := range arr {
				dist := math.Sqrt(math.Pow(node1[1] - node2[1],2) + math.Pow(node1[2] - node2[2],2))
				outarr[i] = append(outarr[i], dist)
			}
		}
		break
	}

CedricPump's avatar
CedricPump committed
179
	case "EUC_3D":{
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
		// entries in euclidean 2d space in form of [index, lat, long]
		// distance calculation for points p1 to p2 with
		// p1 = (x1, y1), p2 = (x2, y2) and p3 = (z1, z2):
		// d = d = ((x2 - x1)2 + (y2 - y1)2 + (z2 - z1)2)1/2
		for i, node1 := range arr{
			outarr = append(outarr, []float64{})
			for _, node2 := range arr {
				dist := math.Sqrt(math.Pow(node1[1] - node2[1],2) + math.Pow(node1[2] - node2[2],2) + math.Pow(node1[3] - node2[3],2))
				outarr[i] = append(outarr[i], dist)
			}
			}
			break
		}
	}

CedricPump's avatar
CedricPump committed
195
196
197
198
	spec.Data.Values = &outarr
	spec.Data.Datatype = "EDGE_WEIGHT_SECTION"
	spec.EdgeWeightType = "EXPLICIT"
	spec.EdgeWeightFormat = "FULL_MATRIX"
199
}