shortest_path

type AStarPqItem[W g.Weight] struct {
	// ID of the node this item refers to
	Id g.NodeId
	// minimum distance from source node to this node (g-value)
	Distance W
	// priority of this item in the heap (f-value)
	Priority W
	// predecessor node of this item in the search tree
	Predecessor g.NodeId
	// contains filtered or unexported fields
}

type AStarPriorityQueue[W g.Weight] []*AStarPqItem[W]

type AStarRouter[N any, E g.IWeightedHalfEdge[W], W g.Weight] struct {
	Graph     g.Graph[N, E]
	Heuristic Heuristic[W]
}

type AltHeuristic[W g.Weight] struct {
	LandmarkDistancesCollection map[g.NodeId]LandmarkDistances[W]

	// dynamic attributes
	Source g.NodeId // source node of the current search: updated via Init
	Target g.NodeId // target node of the current search: updated via Init

	ActiveLandmarks []LandmarkDistances[W]
}

type ArcFlagAStarRouter[N g.Partitioner, E g.IFlaggedHalfEdge[W], W g.Weight] struct {
	Graph     g.Graph[N, E]
	Transpose g.Graph[N, E]

	Heuristic Heuristic[W]
}

type ArcFlagRouter[N g.Partitioner, E g.IFlaggedHalfEdge[W], W g.Weight] struct {
	Graph g.Graph[N, E]
}

type BenchmarkResult struct {
	TimeDistribution   []float64 `json:"times"`
	PqPopsDistribution []int     `json:"pq-pops"`
}

type BenchmarkSummary struct {
	Runs   int     // number of executions
	Time   float64 // average execution time [ms]
	PqPops int     // average number of Pop() operations on priority queue
}

type Benchmarker[W g.Weight] struct {
	NodeRange g.NodeId
	Router    Router[W]
	Result    BenchmarkResult
}

type BiDijkstraRouter[N any, E g.IWeightedHalfEdge[W], W g.Weight] struct {
	Graph     g.Graph[N, E]
	Transpose g.Graph[N, E]

	MaxInitializerValue W
}

type BidirectionalAStarRouter[N any, E g.IWeightedHalfEdge[W], W g.Weight] struct {
	Graph     g.Graph[N, E]
	Transpose g.Graph[N, E]

	ForwardHeuristic  Heuristic[W]
	BackwardHeuristic Heuristic[W]

	MaxInitializerValue W
}

type BidirectionalArcFlagRouter[N g.Partitioner, E g.IFlaggedHalfEdge[W], W g.Weight] struct {
	Graph     g.Graph[N, E]
	Transpose g.Graph[N, E]

	MaxInitializerValue W
}

type DijkstraPqItem[W g.Weight] struct {
	// ID of the node this item refers to
	Id g.NodeId
	// priority of this item in the heap
	Priority W
	// predecessor node of this item in the search tree
	Predecessor g.NodeId
	// contains filtered or unexported fields
}

type DijkstraPriorityQueue[W g.Weight] []*DijkstraPqItem[W]

type DijkstraRouter[N any, E g.IWeightedHalfEdge[W], W g.Weight] struct {
	Graph g.Graph[N, E]
}

type Heuristic[W g.Weight] interface {
	// Init initializes the heuristic with the source and the target node id of the next search.
	// The Init method must be called before any search by the search algorithm.
	Init(source g.NodeId, target g.NodeId)
	// Evaluate computes the value of the heuristic at node with ID=id.
	Evaluate(id g.NodeId) W
}

type LandmarkDistances[W g.Weight] struct {
	Landmark g.NodeId // node ID of the landmark
	From     []W      // stores the length of shortest paths from L to every node
	To       []W      // stores the length of shortest paths from every node to L
}

type Router[W g.Weight] interface {
	// Route computes the shortest path from the source node to the target node of the underlying graph.
	//
	// The search space of the algorithm's execution is reported iff recordSearchSpace is true.
	// Note that recording the search space will decrease the performance of Route significantly.
	Route(source, target g.NodeId, recordSearchSpace bool) ShortestPathResult[W]
}

type ShortestPathResult[W g.Weight] struct {
	// Length stores the length of the shortest path between the source and the target node.
	// The value of Length is set to -1 iff such a path does not exist.
	Length W
	// Path is a slice of NodeId values that describe the shortest path from the source to the target node.
	// The slice is empty iff such a path does not exist.
	Path []g.NodeId
	// PqPops reports the number of Pop() operations on the priority queue during the shortest path computation.
	PqPops int
	// SearchSpace reports the search space of the algorithm by enumerating all processed node IDs.
	// The slice is ordered by the time the nodes were settled.
	// Shortest path algorithms should usually not record the search space for performance reasons.
	// SearchSpace is 'nil' iff the algorithm has been instructed not to record the search space.
	SearchSpace []g.NodeId
}

type ShortestPathToAllResult[W g.Weight] struct {
	// Lengths stores the length of the shortest path from the source node to each node and -1 if such a path does not exist.
	Lengths []W
	// Predecessers store the predecessor node of each node on a shortest path starting at the source node and -1 if such a path does not exist.
	Predecessors []g.NodeId
	// PqPops reports the number of Pop() operations on the priority queue during the one-to-all shortest path computation.
	PqPops int
}

type ShortestPathTreeNode struct {
	// Id is the root element of this search tree and refers to a Node ID in the graph on which Dijkstra's algorithm has been applied.
	Id g.NodeId
	// Children is a list of pointers to subtrees, each referring to a node that is reached on a shortest path from the source node via this node (ID=Id).
	Children []*ShortestPathTreeNode
	// Visited is a boolean flag to mark nodes that have already been visited while traversing the search graph.
	// Caution: It is not possible to make use of this flag for more than one traversal (without resetting it).
	Visited bool
}

type ShortestPathTreePqItem[W g.Weight] struct {
	// ID of the node this item refers to
	Id g.NodeId
	// priority of this item in the heap
	Priority W
	// list of predecessor nodes of this item in the search tree
	Predecessors []g.NodeId
	// contains filtered or unexported fields
}

type ShortestPathTreePriorityQueue[W g.Weight] []*ShortestPathTreePqItem[W]

type TwoLevelArcFlagRouter[N g.TwoLevelPartitioner, E g.ITwoLevelFlaggedHalfEdge[W], W g.Weight] struct {
	Graph g.Graph[N, E]
}