![]() |
AuD
Lecture 'Algorithmen und Datenstrukturen' (code examples)
|
Undirected graph that is defined implicitly by a regular 2d grid. More...
Classes | |
class | Cell |
Cell in a Grid2 . More... | |
class | CompareCellDistanceFromIndex |
comparator for {#link aud.PriorityQueue} compares Cell#d | |
class | CompareCellEstimatedDistanceFromIndex |
comparator for {#link aud.PriorityQueue} compares Cell#f | |
Public Member Functions | |
Grid2 () | |
construct an empty grid, use read_file or setup More... | |
Grid2 (String filename) | |
construct grid by calling read_file More... | |
void | read_file (String filename) |
read file and treat contents as cells, calls setup More... | |
void | setup (String[] lines) |
setup grid from string: create contents as grid cells More... | |
void | setup (String text) |
setup from multi-line string, e.g., EXAMPLE More... | |
int | num_rows () |
get number of rows More... | |
int | num_columns () |
get number of columns More... | |
int | size () |
get total number of cells More... | |
int | cell_index (int i, int j) |
get cell index from coordinates More... | |
int | get_row (int _index) |
get row from cell index More... | |
int | get_column (int _index) |
get columns from cell index More... | |
Cell | cell (int i, int j) |
get cell (i,j) More... | |
int[] | neighbors (int index) |
get neighbors of cell index (4-neighborhood) More... | |
int | find_first (char value) |
find first cell in grid with value @endiliteral More... | |
void | display () |
display current grid More... | |
void | reset_cells () |
reset all cells to default state but keep their values More... | |
void | dfs_recursive (int s) |
recusive DFS More... | |
void | dfs_iterative (int s0) |
iterative DFS More... | |
void | bfs (int s0) |
BFS. More... | |
void | dijkstra (int s0, int s1) |
Dijkstra. More... | |
void | astar (int s0, int s1) |
A*. More... | |
void | backtrack (int s) |
backtrack and display path to source More... | |
Static Public Member Functions | |
static void | main (String[] args) |
Public Attributes | |
int | delay = 100 |
delay in display in milliseconds More... | |
Static Public Attributes | |
static final String | EXAMPLE |
example grid (argument to setup More... | |
Protected Member Functions | |
int[] | neighbors_from_tunnels (int index) |
get neighbors of index from tunnels More... | |
int[] | create_tunnels_for (Cell cell) |
create tunnels for specified entry at cell More... | |
boolean | create_all_tunnels () |
create all tunnels (preprocess) More... | |
Static Protected Member Functions | |
static void | usage () |
print help message and exit More... | |
Undirected graph that is defined implicitly by a regular 2d grid.
The graph is defined by 4-neighborhoods (north,east,south,west) on a 2-dimensional grid. You can imagine the grid as a "pixel image" with each pixel represented as a Grid2.Cell
.
For this graph, we don't use the aud.graph.AbstractGraph
interface.
We use simple "ASCII images" for input and visualization. Note that the output uses ANSI escape codes for displaying colors. Colors will be displayed correctly only on a "command window" with a terminal emulation. This is typically provided by any Unix terminal. (It will not work with the standard Windows command prompt cmd.exe
! Use the -no-color
option in this case.)
Definition at line 38 of file Grid2.java.
construct an empty grid, use read_file
or setup
Definition at line 120 of file Grid2.java.
Referenced by aud.example.grid.Grid2.main().
aud.example.grid.Grid2.Grid2 | ( | String | filename | ) |
construct grid by calling read_file
Definition at line 123 of file Grid2.java.
References aud.example.grid.Grid2.read_file().
void aud.example.grid.Grid2.astar | ( | int | s0, |
int | s1 | ||
) |
A*.
Definition at line 538 of file Grid2.java.
References aud.example.grid.Grid2.create_all_tunnels(), aud.PriorityQueue< T >.push(), and aud.example.grid.Grid2.size().
Referenced by aud.example.grid.Grid2.main().
void aud.example.grid.Grid2.backtrack | ( | int | s | ) |
backtrack and display
path to source
Definition at line 596 of file Grid2.java.
void aud.example.grid.Grid2.bfs | ( | int | s0 | ) |
BFS.
Definition at line 436 of file Grid2.java.
References aud.Queue< T >.enqueue().
Referenced by aud.example.grid.Grid2.main().
Cell aud.example.grid.Grid2.cell | ( | int | i, |
int | j | ||
) |
get cell (i,j)
Definition at line 193 of file Grid2.java.
Referenced by aud.example.grid.Grid2.create_tunnels_for(), and aud.example.grid.Grid2.neighbors_from_tunnels().
int aud.example.grid.Grid2.cell_index | ( | int | i, |
int | j | ||
) |
get cell index from coordinates
Definition at line 179 of file Grid2.java.
|
protected |
create all tunnels (preprocess)
Definition at line 280 of file Grid2.java.
Referenced by aud.example.grid.Grid2.astar().
|
protected |
create tunnels for specified entry at cell
Definition at line 257 of file Grid2.java.
References aud.example.grid.Grid2.cell(), and aud.example.grid.Grid2.Cell.is_tunnel().
void aud.example.grid.Grid2.dfs_iterative | ( | int | s0 | ) |
iterative DFS
Definition at line 409 of file Grid2.java.
References aud.Stack< T >.push().
Referenced by aud.example.grid.Grid2.main().
void aud.example.grid.Grid2.dfs_recursive | ( | int | s | ) |
recusive DFS
Definition at line 391 of file Grid2.java.
Referenced by aud.example.grid.Grid2.main().
void aud.example.grid.Grid2.dijkstra | ( | int | s0, |
int | s1 | ||
) |
Dijkstra.
Definition at line 463 of file Grid2.java.
References aud.PriorityQueue< T >.push(), and aud.example.grid.Grid2.size().
Referenced by aud.example.grid.Grid2.main().
void aud.example.grid.Grid2.display | ( | ) |
display current grid
Definition at line 331 of file Grid2.java.
References aud.util.Terminal.cls(), and aud.util.Terminal.instance.
Referenced by aud.example.grid.Grid2.main().
int aud.example.grid.Grid2.find_first | ( | char | value | ) |
find first cell in grid with value @endiliteral
Definition at line 317 of file Grid2.java.
References aud.example.grid.Grid2.size().
Referenced by aud.example.grid.Grid2.main().
int aud.example.grid.Grid2.get_column | ( | int | _index | ) |
get columns from cell index
Definition at line 189 of file Grid2.java.
Referenced by aud.example.grid.Grid2.neighbors().
int aud.example.grid.Grid2.get_row | ( | int | _index | ) |
get row from cell index
Definition at line 185 of file Grid2.java.
Referenced by aud.example.grid.Grid2.neighbors().
|
static |
Definition at line 627 of file Grid2.java.
References aud.example.grid.Grid2.astar(), aud.example.grid.Grid2.bfs(), aud.example.grid.Grid2.delay, aud.example.grid.Grid2.dfs_iterative(), aud.example.grid.Grid2.dfs_recursive(), aud.example.grid.Grid2.dijkstra(), aud.example.grid.Grid2.display(), aud.example.grid.Grid2.EXAMPLE, aud.example.grid.Grid2.find_first(), aud.example.grid.Grid2.Grid2(), aud.util.Terminal.instance, aud.example.grid.Grid2.read_file(), aud.example.grid.Grid2.setup(), aud.example.grid.Grid2.size(), and aud.example.grid.Grid2.usage().
int[] aud.example.grid.Grid2.neighbors | ( | int | index | ) |
get neighbors of cell index
(4-neighborhood)
Definition at line 197 of file Grid2.java.
References aud.example.grid.Grid2.get_column(), and aud.example.grid.Grid2.get_row().
|
protected |
get neighbors of index
from tunnels
Definition at line 238 of file Grid2.java.
References aud.example.grid.Grid2.cell().
int aud.example.grid.Grid2.num_columns | ( | ) |
int aud.example.grid.Grid2.num_rows | ( | ) |
void aud.example.grid.Grid2.read_file | ( | String | filename | ) |
read file and treat contents as cells, calls setup
Definition at line 128 of file Grid2.java.
References aud.example.grid.Grid2.setup().
Referenced by aud.example.grid.Grid2.Grid2(), and aud.example.grid.Grid2.main().
void aud.example.grid.Grid2.reset_cells | ( | ) |
reset all cells to default state but keep their values
Definition at line 382 of file Grid2.java.
References aud.example.grid.Grid2.size().
void aud.example.grid.Grid2.setup | ( | String | text | ) |
setup from multi-line string, e.g., EXAMPLE
Definition at line 167 of file Grid2.java.
References aud.example.grid.Grid2.setup().
void aud.example.grid.Grid2.setup | ( | String[] | lines | ) |
setup grid from string: create contents as grid cells
Definition at line 147 of file Grid2.java.
Referenced by aud.example.grid.Grid2.main(), aud.example.grid.Grid2.read_file(), and aud.example.grid.Grid2.setup().
int aud.example.grid.Grid2.size | ( | ) |
get total number of cells
Definition at line 176 of file Grid2.java.
Referenced by aud.example.grid.Grid2.astar(), aud.example.grid.Grid2.dijkstra(), aud.example.grid.Grid2.find_first(), aud.example.grid.Grid2.main(), and aud.example.grid.Grid2.reset_cells().
|
staticprotected |
print help message and exit
Definition at line 610 of file Grid2.java.
Referenced by aud.example.grid.Grid2.main().
int aud.example.grid.Grid2.delay = 100 |
delay in display
in milliseconds
Definition at line 60 of file Grid2.java.
Referenced by aud.example.grid.Grid2.main().
|
static |
example grid (argument to setup
Definition at line 49 of file Grid2.java.
Referenced by aud.example.grid.Grid2.main().