AuD
Lecture 'Algorithmen und Datenstrukturen' (code examples)
aud.example.grid.Grid2 Class Reference

Undirected graph that is defined implicitly by a regular 2d grid. More...

+ Collaboration diagram for aud.example.grid.Grid2:

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...
 

Detailed Description

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.

Constructor & Destructor Documentation

◆ Grid2() [1/2]

construct an empty grid, use read_file or setup

Definition at line 120 of file Grid2.java.

120{}

Referenced by aud.example.grid.Grid2.main().

+ Here is the caller graph for this function:

◆ Grid2() [2/2]

aud.example.grid.Grid2.Grid2 ( String  filename)

construct grid by calling read_file

Definition at line 123 of file Grid2.java.

123 {
124 read_file(filename);
125 }
void read_file(String filename)
read file and treat contents as cells, calls setup
Definition: Grid2.java:128

References aud.example.grid.Grid2.read_file().

+ Here is the call graph for this function:

Member Function Documentation

◆ astar()

void aud.example.grid.Grid2.astar ( int  s0,
int  s1 
)

A*.

Definition at line 538 of file Grid2.java.

538 {
539
540 create_all_tunnels(); // May fail if there are any tunnels, and they were not initialized!
541
542 PriorityQueue<Integer> open=
543 new PriorityQueue<Integer>
544 (size(),new CompareCellEstimatedDistanceFromIndex(this));
545
546 open.push(s0);
547 ++num_opened_;
548 cell_[s0].color=Terminal.CYAN; // start processing
549 cell_[s0].d=0.0;
550 cell_[s0].f=estimate_distance(s0,s1); // initial guess
551 display();
552
553 while (!open.is_empty()) {
554 int s=open.pop();
555
556 for (int t : neighbors(s))
557 if (cell_[t].is_free()) {
558
559 double distance=cell_[s].d+weight(s,t);
560
561 double priority = distance + estimate_distance(t,s1);
562
563 if (Double.isInfinite(cell_[t].d)) {
564
565 assert(!open.contains(t));
566
567 cell_[t].color=Terminal.CYAN; // start processing
568 cell_[t].p=s;
569 cell_[t].d=distance;
570 cell_[t].f=priority;
571
572 open.push(t);
573 ++num_opened_;
574 }
575 else if (cell_[t].d>distance && open.contains(t)) {
576 cell_[t].color=Terminal.YELLOW; // got updated
577 cell_[t].p=s;
578 cell_[t].d=distance;
579 cell_[t].f=priority;
580
581 open.lower(t); // adapt priority queue to new, lower priority
582 }
583 }
584
585 cell_[s].color=Terminal.MAGENTA;
586 display();
587
588 if (s==s1) {
589 backtrack(s);
590 break;
591 }
592 }
593 }
int color
indexed color, see Terminal
Definition: Grid2.java:89
double f
priority used by A* (distance + estimated distance to destination
Definition: Grid2.java:93
int p
index of parent cell
Definition: Grid2.java:95
double d
distance to source
Definition: Grid2.java:91
int size()
get total number of cells
Definition: Grid2.java:176
boolean create_all_tunnels()
create all tunnels (preprocess)
Definition: Grid2.java:280
void display()
display current grid
Definition: Grid2.java:331
void backtrack(int s)
backtrack and display path to source
Definition: Grid2.java:596
int[] neighbors(int index)
get neighbors of cell index (4-neighborhood)
Definition: Grid2.java:197

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().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ backtrack()

void aud.example.grid.Grid2.backtrack ( int  s)

backtrack and display path to source

Definition at line 596 of file Grid2.java.

596 {
597 assert(cell_[s].p>=0);
598 double d=cell_[s].d;
599 while (s>=0) {
600 cell_[s].color=Terminal.GREEN;
601 s=cell_[s].p;
602 display();
603 }
604 Terminal.instance.out.println("distance = "+d);
605 if (num_opened_>0)
606 Terminal.instance.out.println("examined "+num_opened_+" cells in total");
607 }

◆ bfs()

void aud.example.grid.Grid2.bfs ( int  s0)

BFS.

Definition at line 436 of file Grid2.java.

436 {
437 Queue<Integer> open=new Queue<Integer>();
438
439 open.enqueue(s0);
440 cell_[s0].color=Terminal.CYAN; // start processing
441 cell_[s0].d=0.0;
442 display();
443
444 while (!open.is_empty()) {
445 int s=open.dequeue();
446
447 for (int t : neighbors(s)) {
448 if (cell_[t].color==Terminal.WHITE && cell_[t].is_free()) {
449
450 cell_[t].color=Terminal.CYAN; // start processing
451 cell_[t].d=cell_[s].d+weight(s,t);
452 cell_[t].p=s;
453
454 open.enqueue(t);
455 }
456 }
457 cell_[s].color=Terminal.MAGENTA;
458 display();
459 }
460 }

References aud.Queue< T >.enqueue().

Referenced by aud.example.grid.Grid2.main().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ cell()

Cell aud.example.grid.Grid2.cell ( int  i,
int  j 
)

get cell (i,j)

Definition at line 193 of file Grid2.java.

193 {
194 return cell_[cell_index(i,j)];
195 }
int cell_index(int i, int j)
get cell index from coordinates
Definition: Grid2.java:179

Referenced by aud.example.grid.Grid2.create_tunnels_for(), and aud.example.grid.Grid2.neighbors_from_tunnels().

+ Here is the caller graph for this function:

◆ cell_index()

int aud.example.grid.Grid2.cell_index ( int  i,
int  j 
)

get cell index from coordinates

Definition at line 179 of file Grid2.java.

179 {
180 assert(0<=i && i<num_rows_);
181 assert(0<=j && j<num_columns_);
182 return i*num_columns_+j;
183 }

◆ create_all_tunnels()

boolean aud.example.grid.Grid2.create_all_tunnels ( )
protected

create all tunnels (preprocess)

Definition at line 280 of file Grid2.java.

280 {
281 boolean has_tunnels = false;
282 for (int i=0;i<cell_.length;i++) {
283 has_tunnels = has_tunnels || (neighbors_from_tunnels(i).length>0);
284 }
285 return has_tunnels;
286 }
int[] neighbors_from_tunnels(int index)
get neighbors of index from tunnels
Definition: Grid2.java:238

Referenced by aud.example.grid.Grid2.astar().

+ Here is the caller graph for this function:

◆ create_tunnels_for()

int[] aud.example.grid.Grid2.create_tunnels_for ( Cell  cell)
protected

create tunnels for specified entry at cell

Definition at line 257 of file Grid2.java.

257 {
258 assert cell.is_tunnel() : "expect tunnel entry";
259 // count ...
260 int n=0;
261 for (int i=0;i<cell_.length;++i) {
262 if (cell_[i].value == cell.value)
263 ++n;
264 }
265 int[] nhd = new int[n];
266
267 // ... save
268 tunnels_.insert(cell.value, nhd);
269
270 // .. and copy
271 n=0;
272 for (int i=0;i<cell_.length;++i) {
273 if (cell_[i].value == cell.value)
274 nhd[n++] = i;
275 }
276 return nhd;
277 }
Value insert(Key key, Value value)
insert key-value pair
Definition: HashMap.java:260
char value
the value that is displayed
Definition: Grid2.java:78
boolean is_tunnel()
letters a-z denote entries to tunnels: e.g., all 'a' are connected
Definition: Grid2.java:86
Cell cell(int i, int j)
get cell (i,j)
Definition: Grid2.java:193

References aud.example.grid.Grid2.cell(), and aud.example.grid.Grid2.Cell.is_tunnel().

+ Here is the call graph for this function:

◆ dfs_iterative()

void aud.example.grid.Grid2.dfs_iterative ( int  s0)

iterative DFS

Definition at line 409 of file Grid2.java.

409 {
410 Stack<Integer> open=new Stack<Integer>();
411
412 open.push(s0);
413 cell_[s0].color=Terminal.CYAN; // start processing
414 cell_[s0].d=0.0;
415 display();
416
417 while (!open.is_empty()) {
418 int s=open.pop();
419
420 for (int t : neighbors(s)) {
421 if (cell_[t].color==Terminal.WHITE && cell_[t].is_free()) {
422
423 cell_[t].color=Terminal.CYAN; // start processing
424 cell_[t].d=cell_[s].d+weight(s,t);
425 cell_[t].p=s;
426
427 open.push(t);
428 }
429 }
430 cell_[s].color=Terminal.MAGENTA;
431 display();
432 }
433 }

References aud.Stack< T >.push().

Referenced by aud.example.grid.Grid2.main().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ dfs_recursive()

void aud.example.grid.Grid2.dfs_recursive ( int  s)

recusive DFS

Definition at line 391 of file Grid2.java.

391 {
392 cell_[s].color=Terminal.CYAN; // start processing s0
393 cell_[s].d=0.0;
394 display();
395 for (int t : neighbors(s)) {
396 if (cell_[t].color==Terminal.WHITE && cell_[t].is_free()) {
397
398 cell_[t].d=cell_[s].d+weight(s,t);
399 cell_[t].p=s;
400
401 dfs_recursive(t);
402 }
403 }
404 cell_[s].color=Terminal.MAGENTA; // done with s0
405 display();
406 }
void dfs_recursive(int s)
recusive DFS
Definition: Grid2.java:391

Referenced by aud.example.grid.Grid2.main().

+ Here is the caller graph for this function:

◆ dijkstra()

void aud.example.grid.Grid2.dijkstra ( int  s0,
int  s1 
)

Dijkstra.

Definition at line 463 of file Grid2.java.

463 {
464
465 PriorityQueue<Integer> open=
466 new PriorityQueue<Integer>(size(),new CompareCellDistanceFromIndex(this));
467
468 open.push(s0);
469 ++num_opened_;
470 cell_[s0].color=Terminal.CYAN; // start processing
471 cell_[s0].d=0.0;
472 display();
473
474 while (!open.is_empty()) {
475 int s=open.pop();
476
477 for (int t : neighbors(s))
478 if (cell_[t].is_free()) {
479
480 double priority=cell_[s].d+weight(s,t);
481
482 if (Double.isInfinite(cell_[t].d)) {
483
484 assert(!open.contains(t));
485
486 cell_[t].color=Terminal.CYAN; // start processing
487 cell_[t].p=s;
488 cell_[t].d=priority;
489
490 open.push(t);
491 ++num_opened_;
492 }
493 else if (cell_[t].d>priority && open.contains(t)) {
494 cell_[t].color=Terminal.YELLOW; // got updated
495 cell_[t].p=s;
496 cell_[t].d=priority;
497
498 open.lower(t); // adapt priority queue to new, lower priority
499 }
500 }
501
502 cell_[s].color=Terminal.MAGENTA;
503 display();
504
505 if (s==s1) {
506 backtrack(s);
507 break;
508 }
509 }
510 }

References aud.PriorityQueue< T >.push(), and aud.example.grid.Grid2.size().

Referenced by aud.example.grid.Grid2.main().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ display()

void aud.example.grid.Grid2.display ( )

display current grid

Definition at line 331 of file Grid2.java.

331 {
332 Terminal term=Terminal.instance;
333
334 term.cls(frame_++==0);
335 term.fg(Terminal.BLACK);
336 term.hideCursor();
337
338 for (int i=0;i<num_rows();++i) {
339
340 for (int j=0;j<num_columns();++j) {
341 Cell c=cell(i,j);
342
343 term.bg(c.is_free() ? c.color : Terminal.BLUE);
344
345 char ch=c.value=='\000' ? ' ' : c.value;
346
347 // display characters for colors
348 if (term.dumb() && ch==' ') {
349 switch (c.color) {
350 case Terminal.RED: ch='&'; break;
351 case Terminal.BLUE: ch='@'; break;
352 case Terminal.GREEN: ch='$'; break;
353 case Terminal.YELLOW: ch='~'; break;
354 case Terminal.CYAN: ch='*'; break;
355 case Terminal.MAGENTA: ch='.'; break;
356 case Terminal.BLACK: ch='%'; break;
357 case Terminal.WHITE:
358 default: break;
359 }
360 }
361 else if (show_parent_) {
362 if (i>0 && c.p==cell_index(i-1,j)) ch='↓';
363 else if (i<num_rows_ && c.p==cell_index(i+1,j)) ch='↑';
364 else if (j>0 && c.p==cell_index(i,j-1)) ch='→';
365 else if (j<num_columns_ && c.p==cell_index(i,j+1)) ch='←';
366 }
367
368 term.out.print(ch);
369 }
370 term.out.println();
371 }
372 term.showCursor();
373 term.reset();
374
375 term.out.flush();
376 try {
377 Thread.sleep(delay);
378 } catch (InterruptedException e) {}
379 }
int delay
delay in display in milliseconds
Definition: Grid2.java:60
int num_rows()
get number of rows
Definition: Grid2.java:172
int num_columns()
get number of columns
Definition: Grid2.java:174

References aud.util.Terminal.cls(), and aud.util.Terminal.instance.

Referenced by aud.example.grid.Grid2.main().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ find_first()

int aud.example.grid.Grid2.find_first ( char  value)

find first cell in grid with value @endiliteral

Returns
cell index or exit program.

Definition at line 317 of file Grid2.java.

317 {
318 for (int i=0;i<size();++i)
319 if (cell_[i].value==value)
320 return i;
321
322 Terminal.instance.reset();
323 System.err.println("Could not find a cell with value='"+value+"'.");
324 System.exit(-1);
325
326 return -1;
327 }

References aud.example.grid.Grid2.size().

Referenced by aud.example.grid.Grid2.main().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ get_column()

int aud.example.grid.Grid2.get_column ( int  _index)

get columns from cell index

Definition at line 189 of file Grid2.java.

189 {
190 return _index%num_columns_;
191 }

Referenced by aud.example.grid.Grid2.neighbors().

+ Here is the caller graph for this function:

◆ get_row()

int aud.example.grid.Grid2.get_row ( int  _index)

get row from cell index

Definition at line 185 of file Grid2.java.

185 {
186 return _index/num_columns_;
187 }

Referenced by aud.example.grid.Grid2.neighbors().

+ Here is the caller graph for this function:

◆ main()

static void aud.example.grid.Grid2.main ( String[]  args)
static

Definition at line 627 of file Grid2.java.

627 {
628
629 Runtime.getRuntime().addShutdownHook(new Thread() {
630 @Override public void run() {
631 // make sure we are leaving cleanly on SIGINT
632 Terminal.instance.reset();
633 Terminal.instance.showCursor();
634 Terminal.instance.out.flush();
635 }
636 });
637
638
639 Grid2 g=new Grid2();
640
641 // prcess argumentys
642 String method="dfs";
643 char start='A', destination='A';
644
645 for (int i=0;i<args.length;++i) {
646 if (args[i].compareTo("-g")==0) {
647 g.read_file(args[++i]);
648 if (g.size()==0) {
649 System.err.println("error: grid is empty");
650 System.exit(-1);
651 }
652 }
653 else if (args[i].compareTo("-m")==0)
654 method=args[++i];
655 else if (args[i].compareTo("-s")==0)
656 start=args[++i].charAt(0);
657 else if (args[i].compareTo("-d")==0)
658 destination=args[++i].charAt(0);
659 else if (args[i].compareTo("-delay")==0)
660 g.delay=Integer.parseInt(args[++i]);
661 else if (args[i].compareTo("-p")==0)
662 g.show_parent_=true;
663 else if (args[i].compareTo("-no-color")==0)
664 Terminal.instance=new Terminal(false);
665 else if (args[i].compareTo("-color")==0)
666 Terminal.instance=new Terminal(true);
667 else if (args[i].compareTo("-show")==0)
668 method=null;
669 else
670 usage();
671 }
672
673 if (g.size()==0)
674 g.setup(EXAMPLE); // use default grid
675
676 g.display();
677
678 if (method==null) // show only
679 System.exit(0);
680
681 // find source node (or exit)
682 int s0=g.find_first(start);
683
684 // find destination node if given (or exit)
685 int s1=(destination!=start ? g.find_first(destination) : -1);
686
687 if (method.compareTo("dfs")==0)
688 g.dfs_recursive(s0);
689 else if (method.compareTo("idfs")==0)
690 g.dfs_iterative(s0);
691 else if (method.compareTo("bfs")==0)
692 g.bfs(s0);
693 else if (method.compareTo("dijkstra")==0)
694 g.dijkstra(s0,s1);
695 else if (method.compareTo("astar")==0) {
696 if (s1<0) {
697 System.err.println("A* requires destination, use '-d'");
698 System.exit(-1);
699 }
700 g.astar(s0,s1);
701 }
702 else
703 usage();
704
705 }
static final String EXAMPLE
example grid (argument to setup
Definition: Grid2.java:49
Grid2()
construct an empty grid, use read_file or setup
Definition: Grid2.java:120
static void usage()
print help message and exit
Definition: Grid2.java:610

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().

+ Here is the call graph for this function:

◆ neighbors()

int[] aud.example.grid.Grid2.neighbors ( int  index)

get neighbors of cell index (4-neighborhood)

Definition at line 197 of file Grid2.java.

197 {
198 int i=get_row(index);
199 int j=get_column(index);
200 int north=-1,east=-1,south=-1,west=-1, k=0;
201
202 // if (i>0) { north=cell_index(i-1,j); ++k; }
203 // if (j<num_columns_-1) { east =cell_index(i,j+1); ++k; }
204 // if (i<num_rows_-1) { south=cell_index(i+1,j); ++k; }
205 // if (j>0) { west =cell_index(i,j-1); ++k; }
206
207 // equivalent but more efficient:
208 if (i>0) { north=index-num_columns_; ++k; }
209 if (j<num_columns_-1) { east =index+1; ++k; }
210 if (i<num_rows_-1) { south=index+num_columns_; ++k; }
211 if (j>0) { west =index-1; ++k; }
212
213 int[] nhd=new int[k];
214 k=0;
215
216 int[] tunnel_nhd = neighbors_from_tunnels(index);
217 if (tunnel_nhd.length > 1) {
218 // copy tunnels to nhd, but filter this cell index
219 nhd=new int[nhd.length + tunnel_nhd.length-1];
220 for (int n=0;n<tunnel_nhd.length;++n) {
221 if (tunnel_nhd[n] != index) {
222 nhd[k++] = tunnel_nhd[n];
223 }
224 }
225 }
226
227 if (north>=0) nhd[k++]=north;
228 if (east>=0) nhd[k++]=east;
229 if (south>=0) nhd[k++]=south;
230 if (west>=0) nhd[k++]=west;
231
232 return nhd;
233 }
int get_row(int _index)
get row from cell index
Definition: Grid2.java:185
int get_column(int _index)
get columns from cell index
Definition: Grid2.java:189

References aud.example.grid.Grid2.get_column(), and aud.example.grid.Grid2.get_row().

+ Here is the call graph for this function:

◆ neighbors_from_tunnels()

int[] aud.example.grid.Grid2.neighbors_from_tunnels ( int  index)
protected

get neighbors of index from tunnels

Definition at line 238 of file Grid2.java.

238 {
239 Cell cell = cell_[index];
240
241 if (!cell.is_tunnel())
242 return new int[0];
243
244 if (tunnels_ == null)
245 tunnels_ = new aud.HashMap<Character,int[]>();
246
247 int[] nhd = tunnels_.find(cell.value);
248
249 if (nhd == null) {
251 }
252
253 return nhd;
254 }
Implementation of an unordered map based on a hash table.
Definition: HashMap.java:31
Value find(Key key)
find value for key @endiliteral
Definition: HashMap.java:281
int[] create_tunnels_for(Cell cell)
create tunnels for specified entry at cell
Definition: Grid2.java:257
AuD lecture: Data structures, algorithms, examples.
Definition: A234Tree.java:1

References aud.example.grid.Grid2.cell().

+ Here is the call graph for this function:

◆ num_columns()

int aud.example.grid.Grid2.num_columns ( )

get number of columns

Definition at line 174 of file Grid2.java.

174{ return num_columns_; }

◆ num_rows()

int aud.example.grid.Grid2.num_rows ( )

get number of rows

Definition at line 172 of file Grid2.java.

172{ return num_rows_; }

◆ read_file()

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.

128 {
129 StringBuilder sb=new StringBuilder();
130 try {
131 FileReader fr=new FileReader(filename);
132 BufferedReader in=new BufferedReader(fr);
133 String line;
134 while ((line=in.readLine())!= null) {
135 sb.append(line);
136 sb.append("\n");
137 }
138 } catch (Exception e) {
139 System.err.println("error while reading '"+filename+"'");
140 System.err.println(e.toString());
141 System.exit(-1);
142 }
143 setup(sb.toString());
144 }
void setup(String[] lines)
setup grid from string: create contents as grid cells
Definition: Grid2.java:147

References aud.example.grid.Grid2.setup().

Referenced by aud.example.grid.Grid2.Grid2(), and aud.example.grid.Grid2.main().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ reset_cells()

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.

382 {
383 for (int i=0;i<size();++i) {
384 Cell c=cell_[i];
385 cell_[i]=new Cell();
386 cell_[i].value=c.value;
387 }
388 }

References aud.example.grid.Grid2.size().

+ Here is the call graph for this function:

◆ setup() [1/2]

void aud.example.grid.Grid2.setup ( String  text)

setup from multi-line string, e.g., EXAMPLE

Definition at line 167 of file Grid2.java.

167 {
168 setup(text.split("\\n"));
169 }

References aud.example.grid.Grid2.setup().

+ Here is the call graph for this function:

◆ setup() [2/2]

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.

147 {
148 num_rows_=lines.length;
149 num_columns_=0; // find maximum number of columns
150 for (String line : lines) {
151 num_columns_=(num_columns_<line.length() ? line.length() : num_columns_);
152 }
153
154 cell_=new Cell[size()];
155 for (int i=0;i<size();++i)
156 cell_[i]=new Cell();
157
158 int i=0;
159 for (String line : lines) {
160 for (int j=0;j<line.length();++j) {
161 cell(i,j).value=line.charAt(j);
162 }
163 ++i;
164 }
165 }

Referenced by aud.example.grid.Grid2.main(), aud.example.grid.Grid2.read_file(), and aud.example.grid.Grid2.setup().

+ Here is the caller graph for this function:

◆ size()

int aud.example.grid.Grid2.size ( )

get total number of cells

Definition at line 176 of file Grid2.java.

176{ return num_rows_*num_columns_; }

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().

+ Here is the caller graph for this function:

◆ usage()

static void aud.example.grid.Grid2.usage ( )
staticprotected

print help message and exit

Definition at line 610 of file Grid2.java.

610 {
611 System.err.println
612 ("java aud.example.graph.TraversalExample "+
613 "[-g file] [-m method] [-s s0] [-d s1] [-v N]\n"+
614 " -g FILE read grid from FILE\n"+
615 " -m METHOD traversal {dfs,idfs,bfs,dijkstra,astar}\n"+
616 " -p show parent cell by an arrow (requires color)\n"+
617 " -s START start node (one character, default: 'A')\n"+
618 " -d DESTINATION destination node for A* (default: none)\n"+
619 " -delay MILLISECONDS set delay after each step\n"+
620 " -no-color don't use ANSI codes\n"+
621 " -color force use of ANSI codes (requires terminal emulation)\n"+
622 " -show display initial grid and exit"
623 );
624 System.exit(-1);
625 }

Referenced by aud.example.grid.Grid2.main().

+ Here is the caller graph for this function:

Member Data Documentation

◆ delay

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().

◆ EXAMPLE

final String aud.example.grid.Grid2.EXAMPLE
static
Initial value:
=
"+-+ +----- --------+ +----+\n"+
"| | +------+----- ---+ | |\n"+
"| | A | | | |\n"+
"| | +------+----- ---+ | |\n"+
"+-+ | +----+\n"+
" +----- --------+\n"+
"\n"+
" +\n"

example grid (argument to setup

Definition at line 49 of file Grid2.java.

Referenced by aud.example.grid.Grid2.main().


The documentation for this class was generated from the following file: