Documentation
¶
Index ¶
- Constants
- func DeleteIndexInt(ints []int, index int) []int
- func GetDistanceToEdgeForHeap(a interface{}) float64
- func IndexOfEdge(edges []CircuitEdge, edge CircuitEdge) int
- func IndexOfVertex(vertices []CircuitVertex, vertex CircuitVertex) int
- func IsBetween(val float64, testA float64, testB float64) bool
- func IsEdgeCloser(v CircuitVertex, candidateEdge CircuitEdge, currentEdge CircuitEdge) bool
- func Length(circuit []CircuitVertex) float64
- func MergeEdgesByIndex(edges []CircuitEdge, vertexIndex int) (updatedEdges []CircuitEdge, detachedEdgeA CircuitEdge, ...)
- func MergeEdgesByVertex(edges []CircuitEdge, vertex CircuitVertex) (updatedEdges []CircuitEdge, detachedEdgeA CircuitEdge, ...)
- func MergeEdgesCopy(edges []CircuitEdge, vertex CircuitVertex) (updatedEdges []CircuitEdge, detachedEdgeA CircuitEdge, ...)
- func MergeEdgesList(edges *list.List, vertex CircuitVertex) (detachedEdgeA CircuitEdge, detachedEdgeB CircuitEdge, mergedLink *list.Element)
- func MoveVertex(edges []CircuitEdge, vertex CircuitVertex, edge CircuitEdge) (updatedEdges []CircuitEdge, mergedEdge CircuitEdge, splitEdgeA CircuitEdge, ...)
- func SplitEdgeList(edges *list.List, edgeToSplit CircuitEdge, vertexToAdd CircuitVertex) *list.Element
- type Circuit
- type CircuitEdge
- func FindClosestEdge(vertex CircuitVertex, currentCircuit []CircuitEdge) CircuitEdge
- func FindClosestEdgeList(vertex CircuitVertex, currentCircuit *list.List) CircuitEdge
- func SplitEdge(edges []CircuitEdge, edgeToSplit CircuitEdge, vertexToAdd CircuitVertex) (updatedEdges []CircuitEdge, edgeIndex int)
- func SplitEdgeCopy(edges []CircuitEdge, edgeToSplit CircuitEdge, vertexToAdd CircuitVertex) (updated []CircuitEdge, edgeIndex int)
- type CircuitVertex
- func DeduplicateVerticesNoSorting(vertices []CircuitVertex) []CircuitVertex
- func DeleteVertex(vertices []CircuitVertex, index int) []CircuitVertex
- func DeleteVertexCopy(vertices []CircuitVertex, toDelete CircuitVertex) []CircuitVertex
- func FindFarthestPoint(target CircuitVertex, points []CircuitVertex) CircuitVertex
- func InsertVertex(vertices []CircuitVertex, index int, vertex CircuitVertex) []CircuitVertex
- type Deduplicator
- type Deletable
- type DistanceToEdge
- type Equal
- type Heap
- func (h *Heap) AnyMatch(predicate func(x interface{}) bool) bool
- func (h *Heap) Clone() *Heap
- func (h *Heap) Delete()
- func (h *Heap) DeleteAll(shouldDelete func(x interface{}) bool) []interface{}
- func (h *Heap) GetValues() []interface{}
- func (h *Heap) Heapify()
- func (h *Heap) Len() int
- func (h *Heap) Less(i int, j int) bool
- func (h *Heap) Peek() interface{}
- func (h *Heap) Pop() interface{}
- func (h *Heap) PopHeap() interface{}
- func (h *Heap) Push(x interface{})
- func (h *Heap) PushAll(x ...interface{})
- func (h *Heap) PushAllFrom(other *Heap)
- func (h *Heap) PushHeap(x interface{})
- func (h *Heap) ReplaceAll(replaceFunction func(x interface{}) interface{})
- func (h *Heap) String() string
- func (h *Heap) Swap(i int, j int)
- func (h *Heap) TrimN(numberToRetain int)
- type PerimeterBuilder
Constants ¶
const Threshold = 0.0000001
Threshold defines how close two values can be and still be considered identical (e.g. for de-duplicating points).
Variables ¶
This section is empty.
Functions ¶
func DeleteIndexInt ¶
DeleteIndexInt removes the int at the specified index in the supplied array, and returns the updated array. This may update the supplied array, so it should be updated with the returned array.
func GetDistanceToEdgeForHeap ¶
func GetDistanceToEdgeForHeap(a interface{}) float64
GetDistanceToEdgeForHeap is used to retrieve the Distance field from a DistanceToEdge in a heap, so that DistanceToEdges can be sorted from closest to farthest.
func IndexOfEdge ¶
func IndexOfEdge(edges []CircuitEdge, edge CircuitEdge) int
IndexOfEdge returns the index (starting at 0) of the edge in the array. If the edge is not in the array, -1 will be returned.
func IndexOfVertex ¶
func IndexOfVertex(vertices []CircuitVertex, vertex CircuitVertex) int
IndexOfVertex returns the index (starting at 0) of the vertex in the array. If the vertex is not in the array, -1 will be returned.
func IsBetween ¶
IsBetween returns true if 'val' is between (inclusive) the two values 'testA' and 'testB'
func IsEdgeCloser ¶
func IsEdgeCloser(v CircuitVertex, candidateEdge CircuitEdge, currentEdge CircuitEdge) bool
IsEdgeCloser returns true if the candidate edge is closer than the current closest edge.
func Length ¶
func Length(circuit []CircuitVertex) float64
Length returns the total length of the circuit (including the return to the start).
func MergeEdgesByIndex ¶
func MergeEdgesByIndex(edges []CircuitEdge, vertexIndex int) (updatedEdges []CircuitEdge, detachedEdgeA CircuitEdge, detachedEdgeB CircuitEdge)
MergeEdgesByIndex combines the edges so that the attached vertex at the specified index is no longer used in the edges. The vertexIndex is the index of the edge starting with the vertex to detach in the edges array. After merging: - the replacement edge is stored in vertexIndex-1 (or the last entry if vertexIndex is 0), - the edge at vertexIndex is removed,
- the length of updatedEdges is one less than edges.
This may update the supplied array, so it should be updated with the returned array. In addition to returning the updated array, this also returns the two detached edges.
func MergeEdgesByVertex ¶
func MergeEdgesByVertex(edges []CircuitEdge, vertex CircuitVertex) (updatedEdges []CircuitEdge, detachedEdgeA CircuitEdge, detachedEdgeB CircuitEdge, mergedEdge CircuitEdge)
MergeEdgesByVertex combines the edges so that the supplied vertex is no longer used in the edges. The array of edges must be ordered so that the 0th edge starts with the 0th vertex in the GetAttachedVertices array, the 1st edge starts with the 1st vertex, and so on. If the supplied vertex is not in the array of edges, or there are too few edges (less than 2), the array will be returned unmodified (with nil for the other variables). After successfully merging: - the merged edge replaces the edge ending with the supplied vertex in the array, - the edge starting with the supplied vertex is removed from the array,
- the length of updatedEdges is one less than edges.
This may update the supplied array, so it should be updated with the returned array. In addition to returning the updated array, this also returns the two detached edges and the merged edge.
func MergeEdgesCopy ¶
func MergeEdgesCopy(edges []CircuitEdge, vertex CircuitVertex) (updatedEdges []CircuitEdge, detachedEdgeA CircuitEdge, detachedEdgeB CircuitEdge, mergedEdge CircuitEdge)
MergeEdgesCopy combines the edges so that the supplied vertex is no longer used in the edges. After successfully merging: - the merged edge replaces the edge ending with the supplied vertex in the array, - the edge starting with the supplied vertex is removed from the array,
- the length of updatedEdges is one less than edges.
This does not modify the supplied array, so it is safe to use with algorithms that clone the edges array into multiple circuits. In addition to returning the updated array, this also returns the two detached edges and the merged edge.
func MergeEdgesList ¶
func MergeEdgesList(edges *list.List, vertex CircuitVertex) (detachedEdgeA CircuitEdge, detachedEdgeB CircuitEdge, mergedLink *list.Element)
MergeEdgesList combines the edges so that the supplied vertex is no longer used in the linked list of edges. In addition to updating the linked list, this also returns the two detached edges and the linked list element for the merged edge. If the vertex is not presed in the list of edges, it will be unmodified and nil will be returned.
func MoveVertex ¶
func MoveVertex(edges []CircuitEdge, vertex CircuitVertex, edge CircuitEdge) (updatedEdges []CircuitEdge, mergedEdge CircuitEdge, splitEdgeA CircuitEdge, splitEdgeB CircuitEdge)
MoveVertex removes an attached vertex from its current location and moves it so that it splits the supplied edge. The vertices adjacent to the vertex's original location will be merged into a new edge. This may update the supplied array, so it should be updated with the returned array. In addition to returning the updated array, this also returns the merged edge and the two edges at the vertex's new location. If the vertex or edge is not in the circuit, this will return the original, unmodified, array and nil for the edges. Complexity: MoveVertex is O(N)
func SplitEdgeList ¶
func SplitEdgeList(edges *list.List, edgeToSplit CircuitEdge, vertexToAdd CircuitVertex) *list.Element
SplitEdgeList replaces the supplied edge with the two edges that are created by adding the supplied vertex to the edge. This requires the supplied edge to exist in the linked list of circuit edges. If it does not exist, the linked list will remain unchanged, and nil will be returned. If it does exist, this will update the linked list, and return the newly added element in the linked list.
Types ¶
type Circuit ¶
type Circuit interface {
// FindNextVertexAndEdge determines the next vertex to add to the circuit, along with which edge it should be added to.
// For example, in the ClosestGreedy algorithm this returns the vertex and edge with the minimum distance increase.
// This should return (nil,nil) when the circuit is complete.
FindNextVertexAndEdge() (CircuitVertex, CircuitEdge)
// GetAttachedVertices returns all vertices that have been added to the circuit (either as part of BuildPerimeter or Update).
// This returns them in the order they should be traversed as part of the circuit (ignoring any unattached vertices).
GetAttachedVertices() []CircuitVertex
// GetLength returns the length of the circuit (at the current stage of processing).
GetLength() float64
// GetUnattachedVertices returns the set of vertices that have not been added to the circuit yet. (all of these points are internal to the perimeter)
GetUnattachedVertices() map[CircuitVertex]bool
// Update adds the supplied vertex to circuit by splitting the supplied edge and creating two edges with the supplied point as the common vertex of the edges.
Update(vertexToAdd CircuitVertex, edgeToSplit CircuitEdge)
}
Circuit provides an abstract representation of a set of points (locations, vertices) for the TSP solver to interact with. This allows it to ignore whether the implementation is a set of N-dimensional points, a graph, or any other representation of points.
type CircuitEdge ¶
type CircuitEdge interface {
Equal
fmt.Stringer
// DistanceIncrease returns the difference in length between the edge
// and the two edges formed by inserting the vertex between the edge's start and end.
// For example, if start->end has a length of 5, start->vertex has a length of 3,
// and vertex->end has a length of 6, this will return 4 (i.e. 6 + 3 - 5)
DistanceIncrease(vertex CircuitVertex) float64
// GetEnd returns the ending point of this edge.
GetEnd() CircuitVertex
// GetLength returns the distance between the start and end vertices.
GetLength() float64
// GetStart returns the starting point of this edge.
GetStart() CircuitVertex
// Intersects checks if the two edges go through at least one identical point.
// Note: Edges may share multiple points if they are co-linear, or in the use-case of graphs.
Intersects(other CircuitEdge) bool
// Merge creates a new edge starting from this edge's start vertex and ending at the supplied edge's end vertex.
Merge(CircuitEdge) CircuitEdge
// Split creates two new edges "start-to-vertex" and "vertex-to-end" based on this edge and the supplied vertex.
Split(vertex CircuitVertex) (CircuitEdge, CircuitEdge)
}
CircuitVertex provides an abstract representation of an edge for the TSP solver to interact with.
func FindClosestEdge ¶
func FindClosestEdge(vertex CircuitVertex, currentCircuit []CircuitEdge) CircuitEdge
FindClosestEdge finds, and returns, the edge that is the closest to this vertex.
func FindClosestEdgeList ¶
func FindClosestEdgeList(vertex CircuitVertex, currentCircuit *list.List) CircuitEdge
FindClosestEdgeList finds, and returns, the edge that is the closest to this vertex in the supplied linked list.
func SplitEdge ¶
func SplitEdge(edges []CircuitEdge, edgeToSplit CircuitEdge, vertexToAdd CircuitVertex) (updatedEdges []CircuitEdge, edgeIndex int)
SplitEdge replaces the supplied edge with the two edges that are created by adding the supplied vertex to the edge. This may update the supplied array, so it should be updated with the returned array. If the supplied edge does not exist, the array will be returned unchanged, along with an index of -1. If the supplied edge does exist, this will return the updated array and the index of the replaced edge (which becomes the index of the first new edge, the index of the second new edge is always that index+1).
func SplitEdgeCopy ¶
func SplitEdgeCopy(edges []CircuitEdge, edgeToSplit CircuitEdge, vertexToAdd CircuitVertex) (updated []CircuitEdge, edgeIndex int)
SplitEdgeCopy replaces the supplied edge with the two edges that are created by adding the supplied vertex to the edge. This does not modify the supplied array, so it is safe to use with algorithms that clone the edges array into multiple circuits. If the supplied edge does not exist, the array will be returned unchanged, along with an index of -1. If the supplied edge does exist, this will return the updated array and the index of the replaced edge (which becomes the index of the first new edge, the index of the second new edge is always that index+1).
type CircuitVertex ¶
type CircuitVertex interface {
Equal
fmt.Stringer
// DistanceTo returns the distance between the two vertices; this should always be a positive number.
DistanceTo(other CircuitVertex) float64
// EdgeTo creates a new CircuitEdge from this point (start) to the supplied point (end).
EdgeTo(end CircuitVertex) CircuitEdge
}
CircuitVertex provides an abstract representation of a single point (location, vertex) for the TSP solver to interact with.
func DeduplicateVerticesNoSorting ¶
func DeduplicateVerticesNoSorting(vertices []CircuitVertex) []CircuitVertex
DeduplicateVerticesNoSorting is an O(n*n) algorithm for deduplicating an array of vertices, and returning a copy of the array containing only the unique vertices. This function does not modify the supplied array of vertices. Note 1: the order that vertices are encountered in an array matters for deduplication, for example:
- Given vertices A, B, and C.
- A and B are within model.Threshold of each other, as are B and C, but A and C are not.
- If A or C is encountered first, both A and C will be included in the output.
- However, if B is encountered first, only B will be in the output.
Note 2: This should be used in situations where a hash map (O(n)) or sorting the array (O(n*log(n))) would be insufficient, for example:
- Sorting 3D vertices can result in duplicate entries in the output, due to having to sort by Y or Z first.
- If we sort by Y first, it is possible to have a point that matches in X and Y and is significantly different in Z in between points that match in X, Y, and Z.
- If vertices A and C are effectively equal, and vertex B has the same X and Y, but a significantly different Z, it could be sorted between A and C, preventing A and C from deduplicating.
func DeleteVertex ¶
func DeleteVertex(vertices []CircuitVertex, index int) []CircuitVertex
DeleteVertex removes the vertex at the specified index in the supplied array, and returns the updated array. This may update the supplied array, so it should be updated with the returned array. This version of delete vertex should not be used if the array may get cloned or is a clone.
func DeleteVertexCopy ¶
func DeleteVertexCopy(vertices []CircuitVertex, toDelete CircuitVertex) []CircuitVertex
DeleteVertexCopy returns a copy of the supplied array with the specified vertex removed. This does not modify the supplied array, so it is safe to use with algorithms that clone the vertex array.
func FindFarthestPoint ¶
func FindFarthestPoint(target CircuitVertex, points []CircuitVertex) CircuitVertex
FindFarthestPoint finds the vertex in the array that is farthest from the supplied target vertex.
func InsertVertex ¶
func InsertVertex(vertices []CircuitVertex, index int, vertex CircuitVertex) []CircuitVertex
InsertVertex inserts the supplied vertex at the specified index, 0-based. If the index is greater than the last index in the array, the vertex will be appended to the end of the array. This may modify the supplied array, so it should be updated with the returned array.
type Deduplicator ¶
type Deduplicator func([]CircuitVertex) []CircuitVertex
Deduplicator is a function that takes in an array of vertices, and returns a copy of the array without duplicate points.
type Deletable ¶
type Deletable interface {
Delete()
}
Deletable should be implemented by any struct that needs to be cleaned up (to prevent resource leaks).
type DistanceToEdge ¶
type DistanceToEdge struct {
Vertex CircuitVertex
Edge CircuitEdge
Distance float64
}
DistanceToEdge is used to cache the distance (typically the distance increase) from a vertex to an edge.
func (*DistanceToEdge) HasVertex ¶
func (h *DistanceToEdge) HasVertex(x interface{}) bool
HasVertex returns true if the supplied interface is another DistanceToEdge, and it has the same Vertex as this DistanceToEdge. If is used to remove other DistanceToEdges from a heap after the vertex in this DistanceToEdge was attached to its edge.
func (*DistanceToEdge) String ¶
func (h *DistanceToEdge) String() string
String converts the DistanceToEdge to a json string.
type Equal ¶
type Equal interface {
// Equals should return true if this object is equal to the supplied object.
Equals(other interface{}) bool
}
Equal defines a boolean comparison method.
type Heap ¶
type Heap struct {
// contains filtered or unexported fields
}
Heap is a min heap that implements heap.Interface. It provides the methods PushHeap and PopHeap, so that clients don't need to use the heap package. It also provides methods for cloning the heap, deleting items from the heap based on a condition function, and peeking at the head of the heap.
func NewHeap ¶
NewHeap creates a new, empty, min Heap with the supplied function for computing the value used to order the heap.
func (*Heap) AnyMatch ¶
AnyMatch checks if any items in the heap match the supplied predicate, and returns true if any item does. This method will return true as soon as any matching item is found. If the heap is empty, this method will return false. The complexity is O(n) due to needing to potentially check all the items in the heap.
func (*Heap) Clone ¶
Clone creates a copy of the Heap, so that items can be added or removed from one heap without affecting the other heap. The complexity is O(n) due to needing to copy all the items in the heap.
func (*Heap) Delete ¶
func (h *Heap) Delete()
Delete cleans up this heap by: unsetting the value function (since it may reference the object containing the heap), deleting all entries in the heap that implement Deletable, and clearing the backing array.
func (*Heap) DeleteAll ¶
DeleteAll creates a copy of the heap, only containing items that match the supplied condition; this modifies the original heap. This returns all items that were deleted in an array. "shouldDelete" needs to return true if the item should be deleted, false if it should be included in the copy. The complexity is O(n) due to needing to check each entry for inclusion, then re-heapifying the remaining data.
func (*Heap) GetValues ¶
func (h *Heap) GetValues() []interface{}
GetValues returns all items in the heap. If any of the items in the heap (or the array) are modified, Heapify() should be called on this heap.
func (*Heap) Heapify ¶
func (h *Heap) Heapify()
Heapify ensures that the heap is ordered correctly. The complexity is O(n) per heap.Init().
func (*Heap) Len ¶
Len retrieves the number of items, without modifying the heap. The complexity is O(1).
func (*Heap) Less ¶
Less is required by heap.Interface and is used to compare items in the heap when sorting the heap. The complexity is O(1).
func (*Heap) Peek ¶
func (h *Heap) Peek() interface{}
Peek retrieves the minimum value from the heap, without modifying the heap. The complexity is O(1).
func (*Heap) Pop ¶
func (h *Heap) Pop() interface{}
Pop is required by heap.Interface, and is used by the heap package. PopHeap should be used instead of Pop to remove an item from the heap, since this will not re-order the remaining heap.
func (*Heap) PopHeap ¶
func (h *Heap) PopHeap() interface{}
PopHeap removes the next item from the heap (based the minimum value of any item when the configured value function is applied). This wraps heap.Pop so that clients don't need to be familiar with the heap package, and only need to use this class. The complexity is O(log n).
func (*Heap) Push ¶
func (h *Heap) Push(x interface{})
Push is required by heap.Interface, and is used by the heap package. PushHeap or PushAll should be used instead of Push to add a new item to the heap, since this will not update the location of the new item to the correct position in the heap.
func (*Heap) PushAll ¶
func (h *Heap) PushAll(x ...interface{})
PushAll adds all the supplied elements to the heap. The complexity is O(n), where n is the number elements already in the heap + the number of elements in the supplied array.
func (*Heap) PushAllFrom ¶
PushAllFrom adds all the entries in the supplied heap to this heap. The complexity is O(n), where n is the number elements already in the heap + the number of elements in the supplied array.
func (*Heap) PushHeap ¶
func (h *Heap) PushHeap(x interface{})
PushHeap adds the supplied item to the heap at the correct location. This wraps heap.Push so that clients don't need to be familiar with the heap package, and only need to use this class. The complexity is O(log n).
func (*Heap) ReplaceAll ¶
func (h *Heap) ReplaceAll(replaceFunction func(x interface{}) interface{})
ReplaceAll creates a copy of the heap, using the supplied function to replace items in the heap; this modifies the original heap. "replaceFunction" should return one of the following:
- nil or an empty array if the item should be excluded,
- the original item if it should be retained unchanged,
- a single item that should replace the original item, or
- an array with one or more items that should replace the original item.
The complexity is O(n) due to needing to check each entry for replacement, then re-heapifying the updated data.
type PerimeterBuilder ¶
type PerimeterBuilder func(verticesArg []CircuitVertex) (edges []CircuitEdge, unattached map[CircuitVertex]bool)
PerimeterBuilder creates an initial circuit, using the minimum vertices required to fully enclose the other (interior) vertices. For example, when using 2-D points, this constructs a convex polygon such that all points are either vertices or inside the polygon. This returns the perimeter as an array of edges, and a map of unattached vertices.
Source Files