graph

package
v0.0.0-...-cb48014 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 27, 2022 License: MIT Imports: 7 Imported by: 0

Documentation

Index

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) Delete 

func (g *Graph) Delete()

func (*Graph) GetVertices 

func (g *Graph) GetVertices() []*GraphVertex

func (*Graph) String 

func (g *Graph) String() string

type GraphEdge 

type GraphEdge struct {
	// contains filtered or unexported fields
}

func (*GraphEdge) Delete 

func (e *GraphEdge) Delete()

func (*GraphEdge) DistanceIncrease 

func (e *GraphEdge) DistanceIncrease(vertex model.CircuitVertex) float64

func (*GraphEdge) Equals 

func (e *GraphEdge) Equals(other interface{}) bool

func (*GraphEdge) GetEnd 

func (e *GraphEdge) GetEnd() model.CircuitVertex

func (*GraphEdge) GetLength 

func (e *GraphEdge) GetLength() float64

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)

func (*GraphEdge) String 

func (e *GraphEdge) String() string

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
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.