Package ghidra.graph.algo

Class DijkstraShortestPathsAlgorithm.OneSourceToAll

java.lang.Object

ghidra.graph.algo.DijkstraShortestPathsAlgorithm.OneSourceToAll

Enclosing class:

DijkstraShortestPathsAlgorithm<V,E extends GEdge<V>>

protected class DijkstraShortestPathsAlgorithm.OneSourceToAll
extends java.lang.Object

A class representing all optimal paths from a given source to every other (reachable) vertex in the graph This is the workhorse of path computation, and implements Dijkstra's Shortest Path algorithm from one source to all destinations. We considered using JUNG to store the graph and compute the paths, but we could not, because we would like to find all paths having the optimal distance. If there are ties, JUNG's implementation chooses one arbitrarily; we would like all tied paths.

Field Summary

Fields

Change	Modifier and Type	Field	Description
NEW	protected java.util.Map<V,java.util.Set<E>>	bestIns
NEW	protected DynamicValueSortedTreeMap<V,java.lang.Double>	queueByDistance
NEW	protected V	source
NEW	protected java.util.Map<V,java.lang.Double>	visitedDistance

Constructor Summary

Constructors

Change	Modifier	Constructor	Description
	protected	OneSourceToAll(V src)	Compute the shortest paths from a given vertex to all other reachable vertices in the graph

Method Summary

Change	Modifier and Type	Method	Description
NEW	protected boolean	addOrUpdate(V dest, double newDist)	Update the record for the given destination with a new offer of shortest distance If either the record doesn't exist yet, or the new offer beats the current best, then a new record is created and replaces the current record.
	protected void	addPathsTo(java.util.Collection<java.util.Deque<E>> paths, V dst)	Add the shortest paths from the source to the given destination into the given collection This is used internally to recover the shortest paths
	protected void	addPathsTo(java.util.Collection<java.util.Deque<E>> paths, V prev, java.util.Deque<E> soFar)	Add the shortest paths from source to a given intermediate, continuing along a given path to the final destination, into the given collection This is a recursive method for constructing the shortest paths overall.
NEW	java.util.Collection<java.util.Deque<E>>	computeOptimalPathsTo(V dst)	Recover the shortest paths from the source to the given destination, if it is reachable
	protected void	fill()	Compute paths, building out the graph until all reachable vertices have been visited
NEW	protected void	fillStep(V from, double dist)	Perform one iteration of Dijskstra's path finding algorithm

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

queueByDistance NEW

protected final DynamicValueSortedTreeMap<V,java.lang.Double> queueByDistance

visitedDistance NEW

protected final java.util.Map<V,java.lang.Double> visitedDistance

bestIns NEW

protected final java.util.Map<V,java.util.Set<E extends GEdge<V>>> bestIns

source NEW

protected final V source

Constructor Detail

OneSourceToAll

protected OneSourceToAll(V src)

Compute the shortest paths from a given vertex to all other reachable vertices in the graph

Parameters:

src - the source (seed) vertex

Method Detail

computeOptimalPathsTo NEW

public java.util.Collection<java.util.Deque<E>> computeOptimalPathsTo(V dst)

Recover the shortest paths from the source to the given destination, if it is reachable

Parameters:

dst - the destination

Returns:

a collection of the shortest paths from source to destination, or the empty set

addPathsTo

protected void addPathsTo(java.util.Collection<java.util.Deque<E>> paths,
                          V dst)

Add the shortest paths from the source to the given destination into the given collection This is used internally to recover the shortest paths

Parameters:

paths - a place to store the recovered paths

dst - the destination

addPathsTo

protected void addPathsTo(java.util.Collection<java.util.Deque<E>> paths,
                          V prev,
                          java.util.Deque<E> soFar)

Add the shortest paths from source to a given intermediate, continuing along a given path to the final destination, into the given collection This is a recursive method for constructing the shortest paths overall. Assuming the given path from intermediate to final destination is the shortest, we can show by induction, the computed paths from source to destination are the shortest.

Parameters:

paths - a place to store the recovered paths

prev - the intermediate destination

soFar - a (shortest) path from intermediate to final destination

addOrUpdate NEW

protected boolean addOrUpdate(V dest,
                              double newDist)

Update the record for the given destination with a new offer of shortest distance If either the record doesn't exist yet, or the new offer beats the current best, then a new record is created and replaces the current record. If present, the list of best inbound edges is cleared -- because they all correspond to a distance that has just been beat. The node is also added and/or moved forward in the queue of unvisited vertices. If the record exists, and the new offer ties the current offer, nothing happens, but the method still returns true, since the corresponding inbound edge could be optimal. If the record's current best beats the offer, nothing happens, and the method returns false, indicating the inbound edge is definitely not optimal.

Parameters:

dest - the destination whose record to update

newDist - the distance offer

Returns:

true iff the offer is equal to or better than the record's current best

fill

protected void fill()

Compute paths, building out the graph until all reachable vertices have been visited

fillStep NEW

protected void fillStep(V from,
                        double dist)

Perform one iteration of Dijskstra's path finding algorithm

Parameters:

from - the vertex to visit for this iteration