public class DefaultGraph extends UndirectedGraph<Coord> implements java.io.Serializable
UndirectedGraph
of Coord vertices where all connections have cost 1. This should be
initialized with a 2D (rectangular) char array using the map convention where '#'
is a wall and anything else
is passable.
Constructor and Description |
---|
DefaultGraph()
No-op no-arg constructor, present for
Serializable ; if you use this you must call init(char[][])
or init(char[][], boolean) before using the DefaultGraph. |
DefaultGraph(char[][] map)
Builds a DefaultGraph from a 2D char array that uses
'#' to represent any kind of inaccessible cell, with
all other chars treated as walkable. |
DefaultGraph(char[][] map,
boolean eightWay)
Builds a DefaultGraph from a 2D char array that uses
'#' to represent any kind of inaccessible cell, with
all other chars treated as walkable. |
Modifier and Type | Method and Description |
---|---|
Graph<Coord> |
breadthFirstSearch(Coord coord)
Perform a breadth first search starting from the specified vertex.
|
Graph<Coord> |
breadthFirstSearch(Coord coord,
int maxVertices,
int maxDepth)
Perform a breadth first search starting from the specified vertex.
|
Graph<Coord> |
depthFirstSearch(Coord coord)
Perform a depth first search starting from the specified vertex.
|
Graph<Coord> |
depthFirstSearch(Coord coord,
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(Coord start,
Coord target)
Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
|
Graph<Coord> |
findMinimumWeightSpanningTree()
Find a minimum weight spanning tree using Kruskal's algorithm.
|
java.util.ArrayList<Coord> |
findShortestPath(Coord start,
Coord target)
Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
|
boolean |
findShortestPath(Coord start,
Coord target,
java.util.ArrayList<Coord> path,
Heuristic<Coord> 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<Coord> |
findShortestPath(Coord start,
Coord target,
Heuristic<Coord> 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.
|
void |
init(char[][] map)
Re-initializes a DefaultGraph from a 2D char array that uses
'#' to represent any kind of inaccessible
cell, with all other chars treated as walkable. |
void |
init(char[][] map,
boolean eightWay)
Re-initializes this DefaultGraph from a 2D char array that uses
'#' to represent any kind of inaccessible
cell, with all other chars treated as walkable. |
char[] |
show()
Creates a 1D char array (which can be passed to
String.valueOf(char[]) ) filled with a grid made of the
vertices in this Graph and their estimated costs, if this has done an estimate. |
addConnection, algorithms, createNew, getEdge, isDirected, obtainEdge, removeConnection
addConnection, addEdge, addEdge, addVertex, addVertices, connectionExists, contains, edgeExists, getEdge, getEdgeCount, getEdges, getEdges, getNode, getNodes, getVertices, removeAllEdges, removeAllVertices, removeEdge, removeEdge, removeNode, removeVertex, removeVertices, size, sortEdges, sortVertices
public DefaultGraph()
Serializable
; if you use this you must call init(char[][])
or init(char[][], boolean)
before using the DefaultGraph.public DefaultGraph(char[][] map)
'#'
to represent any kind of inaccessible cell, with
all other chars treated as walkable. This only builds connections along cardinal directions.map
- a 2D char array where '#'
represents an inaccessible area (such as a wall) and anything else is walkablepublic DefaultGraph(char[][] map, boolean eightWay)
'#'
to represent any kind of inaccessible cell, with
all other chars treated as walkable. If eightWay
is true, this builds connections along diagonals as well
as along cardinals, but if eightWay
is false, it only builds connections along cardinal directions.map
- a 2D char array where '#'
represents an inaccessible area (such as a wall) and anything else is walkableeightWay
- if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connectionspublic void init(char[][] map)
'#'
to represent any kind of inaccessible
cell, with all other chars treated as walkable. This only builds connections along cardinal directions.map
- a 2D char array where '#'
represents an inaccessible area (such as a wall) and anything else is walkablepublic void init(char[][] map, boolean eightWay)
'#'
to represent any kind of inaccessible
cell, with all other chars treated as walkable. If eightWay
is true, this builds connections along
diagonals as well as along cardinals, but if eightWay
is false, it only builds connections along cardinal
directions.map
- a 2D char array where '#'
represents an inaccessible area (such as a wall) and anything else is walkableeightWay
- if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connectionspublic Graph<Coord> findMinimumWeightSpanningTree()
public java.util.ArrayList<Coord> findShortestPath(Coord start, Coord target)
start
- the starting vertextarget
- the target vertexpublic java.util.ArrayList<Coord> findShortestPath(Coord start, Coord target, Heuristic<Coord> heuristic)
start
- the starting vertextarget
- the target vertexheuristic
- typically predefined in Heuristic
, this determines how the optimal path will be estimatedpublic boolean findShortestPath(Coord start, Coord target, java.util.ArrayList<Coord> path, Heuristic<Coord> heuristic)
start
- the starting vertextarget
- the target vertexpath
- the list of vertices to which the path vertices should be addedpublic double findMinimumDistance(Coord start, Coord target)
start
- the starting vertextarget
- the target vertexpublic Graph<Coord> breadthFirstSearch(Coord coord, int maxVertices, int maxDepth)
coord
- 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<Coord> breadthFirstSearch(Coord coord)
coord
- the vertex at which to start the searchGraph.getVertices()
and Graph.getEdges()
.public Graph<Coord> depthFirstSearch(Coord coord, int maxVertices, int maxDepth)
coord
- 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<Coord> depthFirstSearch(Coord coord)
coord
- the vertex at which to start the searchGraph.getVertices()
and Graph.getEdges()
.public boolean detectCycle()
public char[] show()
String.valueOf(char[])
) filled with a grid made of the
vertices in this Graph and their estimated costs, if this has done an estimate. Each estimate is rounded to the
nearest int and only printed if it is 4 digits or less; otherwise this puts '####' in the grid cell. This is a
building-block for toString() implementations that may have debugging uses as well.Copyright © Eben Howard 2012–2022. All rights reserved.