Documentation
¶
Index ¶
- func BuildPerimiter(vertices []model.CircuitVertex) (circuitEdges []model.CircuitEdge, ...)
- func ToCircuitVertexArray(g []*GraphVertex) []model.CircuitVertex
- type Graph
- type GraphEdge
- func (e *GraphEdge) Delete()
- func (e *GraphEdge) DistanceIncrease(vertex model.CircuitVertex) float64
- func (e *GraphEdge) Equals(other interface{}) bool
- func (e *GraphEdge) GetEnd() model.CircuitVertex
- func (e *GraphEdge) GetLength() float64
- func (e *GraphEdge) GetPath() []*GraphVertex
- func (e *GraphEdge) GetStart() model.CircuitVertex
- func (e *GraphEdge) Intersects(other model.CircuitEdge) bool
- func (e *GraphEdge) Merge(other model.CircuitEdge) model.CircuitEdge
- func (e *GraphEdge) Split(vertex model.CircuitVertex) (model.CircuitEdge, model.CircuitEdge)
- func (e *GraphEdge) String() string
- type GraphGenerator
- type GraphVertex
- func (v *GraphVertex) AddAdjacentVertex(other *GraphVertex, distance float64)
- func (v *GraphVertex) Delete()
- func (v *GraphVertex) DeletePaths()
- func (v *GraphVertex) DistanceTo(other model.CircuitVertex) float64
- func (start *GraphVertex) EdgeTo(end model.CircuitVertex) model.CircuitEdge
- func (v *GraphVertex) Equals(other interface{}) bool
- func (v *GraphVertex) GetAdjacentVertices() map[*GraphVertex]float64
- func (v *GraphVertex) GetId() string
- func (v *GraphVertex) GetPaths() map[model.CircuitVertex]*GraphEdge
- func (start *GraphVertex) InitializePaths()
- func (v *GraphVertex) String() string
- type StringVertex
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BuildPerimiter ¶
func BuildPerimiter(vertices []model.CircuitVertex) (circuitEdges []model.CircuitEdge, unattachedVertices map[model.CircuitVertex]bool)
BuildPerimiter produces the smallest convex perimeter that can encompass all the vertices in the supplied array. This returns both the edges comprising the convex perimeter and the set of unattached (interior) vertices. This will panic if any of the vertices in the array are not of type GraphVertex.
func ToCircuitVertexArray ¶
func ToCircuitVertexArray(g []*GraphVertex) []model.CircuitVertex
Types ¶
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
func NewGraph ¶
func NewGraph(vertices []*GraphVertex) *Graph
func (*Graph) GetVertices ¶
func (g *Graph) GetVertices() []*GraphVertex
type GraphEdge ¶
type GraphEdge struct {
// contains filtered or unexported fields
}
func (*GraphEdge) DistanceIncrease ¶
func (e *GraphEdge) DistanceIncrease(vertex model.CircuitVertex) float64
func (*GraphEdge) GetEnd ¶
func (e *GraphEdge) GetEnd() model.CircuitVertex
func (*GraphEdge) GetPath ¶
func (e *GraphEdge) GetPath() []*GraphVertex
func (*GraphEdge) GetStart ¶
func (e *GraphEdge) GetStart() model.CircuitVertex
func (*GraphEdge) Intersects ¶
func (e *GraphEdge) Intersects(other model.CircuitEdge) bool
func (*GraphEdge) Merge ¶
func (e *GraphEdge) Merge(other model.CircuitEdge) model.CircuitEdge
func (*GraphEdge) Split ¶
func (e *GraphEdge) Split(vertex model.CircuitVertex) (model.CircuitEdge, model.CircuitEdge)
type GraphGenerator ¶
type GraphGenerator struct { // EnableAsymetricDistances (it true, default false) allows the graph to have different edge lengths from A to B than B to A // (e.g. to simulate different routes between two locations due to one-way streets). EnableAsymetricDistances bool // EnableUnidirectionalEdges (if true, default false) allows the graph to have an edge from node A to B, without a corresponding edge from B to A. // All vertices will have paths to all other vertices, even if this is enabled. EnableUnidirectionalEdges bool // MaxEdges determines the maximum number of edges each vertex can have. // This must be greater than or equal to MinEdges, and this must be at least 2. MaxEdges uint8 // MinEdges determines the minimum number of edge each vertex should have. // This must be at least 1. MinEdges uint8 // NumVertices determines the number of vertices to generate. // This must be at least 3. NumVertices uint32 // Seed is used to initialize the random algorithm. // This should be used to reproduce the same graph across multiple tests. // If this is nil, a seed will be automatically generated. Seed *int64 }
func (*GraphGenerator) Create ¶
func (gen *GraphGenerator) Create() *Graph
type GraphVertex ¶
type GraphVertex struct {
// contains filtered or unexported fields
}
func NewGraphVertex ¶
func NewGraphVertex(id string) *GraphVertex
func (*GraphVertex) AddAdjacentVertex ¶
func (v *GraphVertex) AddAdjacentVertex(other *GraphVertex, distance float64)
func (*GraphVertex) Delete ¶
func (v *GraphVertex) Delete()
func (*GraphVertex) DeletePaths ¶
func (v *GraphVertex) DeletePaths()
func (*GraphVertex) DistanceTo ¶
func (v *GraphVertex) DistanceTo(other model.CircuitVertex) float64
func (*GraphVertex) EdgeTo ¶
func (start *GraphVertex) EdgeTo(end model.CircuitVertex) model.CircuitEdge
EdgeTo creates a new GraphEdge from the start vertex to the end vertex. Its complexity is O(n*log(n)), due to needing to find the optimal path, which potentially involves checking each vertex in the graph, which are sorted by distance from the start vertex, for early escape. If a path cannot be created from the start vertex to the end vertex nil will be returned (the graph is asymmetric, so it is possible to connect only one way).
func (*GraphVertex) Equals ¶
func (v *GraphVertex) Equals(other interface{}) bool
func (*GraphVertex) GetAdjacentVertices ¶
func (v *GraphVertex) GetAdjacentVertices() map[*GraphVertex]float64
func (*GraphVertex) GetId ¶
func (v *GraphVertex) GetId() string
func (*GraphVertex) GetPaths ¶
func (v *GraphVertex) GetPaths() map[model.CircuitVertex]*GraphEdge
func (*GraphVertex) InitializePaths ¶
func (start *GraphVertex) InitializePaths()
InitializePaths sets up the map of the most efficient edges from this vertex to all other vertices in the graph. Its complexity is O(n*e*log(n*e)), where n is the number of nodes and e is the average number of edges off of each node.
We only visit each node once, however for each node we add each of its connected nodes to a heap to find the shortest path to the next unvisited node.
func (*GraphVertex) String ¶
func (v *GraphVertex) String() string
type StringVertex ¶
type StringVertex struct {
// contains filtered or unexported fields
}