V
- the vertex type; often Coord
public class Algorithms<V>
extends java.lang.Object
Graph
are defined here, with some specific cases in subclasses.
The most-frequently-used algorithm here is probably findShortestPath(Object, Object, ArrayList, Heuristic)
,
or some overload of it; this is a standard A-Star algorithm backed by a priority queue that is very fast. Somewhat
surprisingly, it doesn't need indices like gdx-ai's IndexedAStarPathFinder needs, and this makes the code easier to
use. There's a good amount of other useful algorithms here, like detectCycle()
and various non-A-Star search
methods, like breadthFirstSearch(Object, int, int)
and depthFirstSearch(Object, int, int)
.
Modifier and Type | Method and Description |
---|---|
Graph<V> |
breadthFirstSearch(V v)
Perform a breadth first search starting from the specified vertex.
|
Graph<V> |
breadthFirstSearch(V v,
int maxVertices,
int maxDepth)
Perform a breadth first search starting from the specified vertex.
|
Graph<V> |
depthFirstSearch(V v)
Perform a depth first search starting from the specified vertex.
|
Graph<V> |
depthFirstSearch(V v,
int maxVertices,
int maxDepth)
Perform a depth first search starting from the specified vertex.
|
boolean |
detectCycle()
Checks whether there are any cycles in the graph using depth first searches.
|
double |
findMinimumDistance(V start,
V target)
Find the length of the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
|
java.util.ArrayList<V> |
findShortestPath(V start,
V target)
Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
|
boolean |
findShortestPath(V start,
V target,
java.util.ArrayList<V> path,
Heuristic<V> heuristic)
Find the shortest path between the start and target vertices, using the A* search algorithm with the provided
heuristic, and implemented with a priority queue.
|
java.util.ArrayList<V> |
findShortestPath(V start,
V target,
Heuristic<V> heuristic)
Find the shortest path between the start and target vertices, using the A* search algorithm with the provided heuristic, and implemented with a priority queue.
|
int |
lastRunID()
Gets the identifier for the last run of an algorithm; this should mostly be usable internally, but may be useful
when different runs have affected a graph and a
Node.lastRunID may need to be checked against this. |
public java.util.ArrayList<V> findShortestPath(V start, V target)
start
- the starting vertextarget
- the target vertexpublic java.util.ArrayList<V> findShortestPath(V start, V target, Heuristic<V> heuristic)
start
- the starting vertextarget
- the target vertexpublic boolean findShortestPath(V start, V target, java.util.ArrayList<V> path, Heuristic<V> heuristic)
start
- the starting vertextarget
- the target vertexpath
- the list of vertices to which the path vertices should be addedpublic double findMinimumDistance(V start, V target)
start
- the starting vertextarget
- the target vertexpublic Graph<V> breadthFirstSearch(V v, int maxVertices, int maxDepth)
v
- the vertex at which to start the searchmaxVertices
- the maximum number of vertices to process before terminating the searchmaxDepth
- the maximum edge distance (the number of edges in a shortest path between vertices) a vertex should have to be
considered for processing. If a vertex has a distance larger than the maxDepth, it will not be added to the
returned graphGraph.getVertices()
and Graph.getEdges()
.public Graph<V> breadthFirstSearch(V v)
v
- the vertex at which to start the searchGraph.getVertices()
and Graph.getEdges()
.public Graph<V> depthFirstSearch(V v, int maxVertices, int maxDepth)
v
- the vertex at which to start the searchmaxVertices
- the maximum number of vertices to process before terminating the searchmaxDepth
- the maximum edge distance (the number of edges in a shortest path between vertices) a vertex should have to be
considered for processing. If a vertex has a distance larger than the maxDepth, it will not be added to the
returned graphGraph.getVertices()
and Graph.getEdges()
.public Graph<V> depthFirstSearch(V v)
v
- the vertex at which to start the searchGraph.getVertices()
and Graph.getEdges()
.public boolean detectCycle()
public int lastRunID()
Node.lastRunID
may need to be checked against this.Copyright © Eben Howard 2012–2022. All rights reserved.