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

Collaboration diagram for aud.example.grid.Grid:

Classes
class	Cell
	Cell in a `Grid`. More...

class	CompareCellDistanceFromIndex
	comparator for {#link aud.PriorityQueue} compares `Cell#d`

class	CompareCellEstimatedDistanceFromIndex
	comparator for {#link aud.PriorityQueue} compares `Cell#f`

Public Member Functions
	Grid ()
	construct an empty grid, use `read_file` or `setup` More...

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

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 Grid.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 33 of file Grid.java.

Constructor & Destructor Documentation

◆ Grid() [1/2]

aud.example.grid.Grid.Grid ( )

construct an empty grid, use read_file or setup

Definition at line 115 of file Grid.java.

115{}

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

Here is the caller graph for this function:

◆ Grid() [2/2]

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

construct grid by calling read_file

Definition at line 118 of file Grid.java.

                               {
    read_file(filename);
  }

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

Here is the call graph for this function:

Member Function Documentation

◆ astar()

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

A*.

Definition at line 507 of file Grid.java.

                                   {
 
    PriorityQueue<Integer> open=
      new PriorityQueue<Integer>
      (size(),new CompareCellEstimatedDistanceFromIndex(this));
 
    open.push(s0);
    ++num_opened_;
    cell_[s0].color=Terminal.CYAN;  // start processing
    cell_[s0].d=0.0;
    cell_[s0].f=estimate_distance(s0,s1); // initial guess
    display();
 
    while (!open.is_empty()) {
      int s=open.pop();
 
      for (int t : neighbors(s))
        if (cell_[t].is_free()) {
 
          double distance=cell_[s].d+weight(s,t);
 
          double priority = distance + estimate_distance(t,s1);
 
          if (Double.isInfinite(cell_[t].d)) {
 
            assert(!open.contains(t));
 
            cell_[t].color=Terminal.CYAN; // start processing
            cell_[t].p=s;
            cell_[t].d=distance;
            cell_[t].f=priority;
 
            open.push(t);
            ++num_opened_;
          }
          else if (cell_[t].d>distance && open.contains(t)) {
            cell_[t].color=Terminal.YELLOW; // got updated
            cell_[t].p=s;
            cell_[t].d=distance;
            cell_[t].f=priority;
 
            open.lower(t); // adapt priority queue to new, lower priority
          }
        }
 
      cell_[s].color=Terminal.MAGENTA;
      display();
 
      if (s==s1) {
        backtrack(s);
        break;
      }
    }
  }

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ backtrack()

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

backtrack and display path to source

Definition at line 563 of file Grid.java.

                               {
    assert(cell_[s].p>=0);
    double d=cell_[s].d;
    while (s>=0) {
      cell_[s].color=Terminal.GREEN;
      s=cell_[s].p;
      display();
    }
    Terminal.instance.out.println("distance = "+d);
    if (num_opened_>0)
      Terminal.instance.out.println("examined "+num_opened_+" cells in total");
  }

◆ bfs()

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

BFS.

Definition at line 422 of file Grid.java.

                          {
    Queue<Integer> open=new Queue<Integer>();
 
    open.enqueue(s0);
    cell_[s0].color=Terminal.CYAN;  // start processing
    cell_[s0].d=0.0;
    display();
 
    while (!open.is_empty()) {
      int s=open.dequeue();
 
      for (int t : neighbors(s)) {
        if (cell_[t].color==Terminal.WHITE && cell_[t].is_free()) {
 
          cell_[t].color=Terminal.CYAN; // start processing
          cell_[t].d=cell_[s].d+weight(s,t);
          cell_[t].p=s;
 
          open.enqueue(t);
        }
      }
      cell_[s].color=Terminal.MAGENTA;
      display();
    }
  }

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cell()

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

get cell (i,j)

Definition at line 188 of file Grid.java.

                                {
    return cell_[cell_index(i,j)];
  }

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

Here is the caller graph for this function:

◆ cell_index()

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

get cell index from coordinates

Definition at line 174 of file Grid.java.

                                     {
    assert(0<=i && i<num_rows_);
    assert(0<=j && j<num_columns_);
    return i*num_columns_+j;
  }

◆ create_tunnels_for()

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

protected

create tunnels for specified entry at cell

Definition at line 252 of file Grid.java.

                                                {
    assert cell.is_tunnel() : "expect tunnel entry";
    // count ...
    int n=0;
    for (int i=0;i<cell_.length;++i) {
      if (cell_[i].value == cell.value)
        ++n;
    }
    int[] nhd = new int[n];
 
    // ... save
    tunnels_.insert(cell.value, nhd);
 
    // .. and copy
    n=0;
    for (int i=0;i<cell_.length;++i) {
      if (cell_[i].value == cell.value)
        nhd[n++] = i;
    }
    return nhd;
  }

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

Here is the call graph for this function:

◆ dfs_iterative()

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

iterative DFS

Definition at line 395 of file Grid.java.

                                    {
    Stack<Integer> open=new Stack<Integer>();
 
    open.push(s0);
    cell_[s0].color=Terminal.CYAN;  // start processing
    cell_[s0].d=0.0;
    display();
 
    while (!open.is_empty()) {
      int s=open.pop();
 
      for (int t : neighbors(s)) {
        if (cell_[t].color==Terminal.WHITE && cell_[t].is_free()) {
 
          cell_[t].color=Terminal.CYAN; // start processing
          cell_[t].d=cell_[s].d+weight(s,t);
          cell_[t].p=s;
 
          open.push(t);
        }
      }
      cell_[s].color=Terminal.MAGENTA;
      display();
    }
  }

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfs_recursive()

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

recusive DFS

Definition at line 377 of file Grid.java.

                                   {
    cell_[s].color=Terminal.CYAN; // start processing s0
    cell_[s].d=0.0;
    display();
    for (int t : neighbors(s)) {
      if (cell_[t].color==Terminal.WHITE && cell_[t].is_free()) {
 
        cell_[t].d=cell_[s].d+weight(s,t);
        cell_[t].p=s;
 
        dfs_recursive(t);
      }
    }
    cell_[s].color=Terminal.MAGENTA; // done with s0
    display();
  }

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

Here is the caller graph for this function:

◆ dijkstra()

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

Dijkstra.

Definition at line 449 of file Grid.java.

                                      {
 
    PriorityQueue<Integer> open=
      new PriorityQueue<Integer>(size(),new CompareCellDistanceFromIndex(this));
 
    open.push(s0);
    ++num_opened_;
    cell_[s0].color=Terminal.CYAN;  // start processing
    cell_[s0].d=0.0;
    display();
 
    while (!open.is_empty()) {
      int s=open.pop();
 
      for (int t : neighbors(s))
        if (cell_[t].is_free()) {
 
          double priority=cell_[s].d+weight(s,t);
 
          if (Double.isInfinite(cell_[t].d)) {
 
            assert(!open.contains(t));
 
            cell_[t].color=Terminal.CYAN; // start processing
            cell_[t].p=s;
            cell_[t].d=priority;
 
            open.push(t);
            ++num_opened_;
          }
          else if (cell_[t].d>priority && open.contains(t)) {
            cell_[t].color=Terminal.YELLOW; // got updated
            cell_[t].p=s;
            cell_[t].d=priority;
 
            open.lower(t); // adapt priority queue to new, lower priority
          }
        }
 
      cell_[s].color=Terminal.MAGENTA;
      display();
 
      if (s==s1) {
        backtrack(s);
        break;
      }
    }
  }

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ display()

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

display current grid

Definition at line 317 of file Grid.java.

                        {
    Terminal term=Terminal.instance;
 
    term.cls(frame_++==0);
    term.fg(Terminal.BLACK);
    term.hideCursor();
 
    for (int i=0;i<num_rows();++i) {
 
      for (int j=0;j<num_columns();++j) {
        Cell c=cell(i,j);
 
        term.bg(c.is_free() ? c.color : Terminal.BLUE);
 
        char ch=c.value=='\000' ? ' ' : c.value;
 
        // display characters for colors
        if (term.dumb() && ch==' ') {
          switch (c.color) {
          case Terminal.RED:     ch='&'; break;
          case Terminal.BLUE:    ch='@'; break;
          case Terminal.GREEN:   ch='$'; break;
          case Terminal.YELLOW:  ch='~'; break;
          case Terminal.CYAN:    ch='*'; break;
          case Terminal.MAGENTA: ch='.'; break;
          case Terminal.BLACK:   ch='%'; break;
          case Terminal.WHITE:
          default: break;
          }
        }
        else if (show_parent_) {
          if (i>0 && c.p==cell_index(i-1,j)) ch='↓';
          else if (i<num_rows_ && c.p==cell_index(i+1,j)) ch='↑';
          else if (j>0 && c.p==cell_index(i,j-1)) ch='→';
          else if (j<num_columns_ && c.p==cell_index(i,j+1)) ch='←';
        }
 
        term.out.print(ch);
      }
      term.out.println();
    }
    term.showCursor();
    term.reset();
 
    term.out.flush();
    try {
      Thread.sleep(delay);
    } catch (InterruptedException e) {}
  }

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_first()

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

find first cell in grid with value @endiliteral

Returns: cell index or exit program.

Definition at line 303 of file Grid.java.

                                    {
    for (int i=0;i<size();++i)
      if (cell_[i].value==value)
        return i;
 
    Terminal.instance.reset();
    System.err.println("Could not find a cell with value='"+value+"'.");
    System.exit(-1);
 
    return -1;
  }

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_column()

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

get columns from cell index

Definition at line 184 of file Grid.java.

                                    {
    return _index%num_columns_;
  }

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

Here is the caller graph for this function:

◆ get_row()

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

get row from cell index

Definition at line 180 of file Grid.java.

                                 {
    return _index/num_columns_;
  }

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

Here is the caller graph for this function:

◆ main()

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

static

Definition at line 594 of file Grid.java.

                                         {
 
    Runtime.getRuntime().addShutdownHook(new Thread() {
        @Override public void run() {
          // make sure we are leaving cleanly on SIGINT
          Terminal.instance.reset();
          Terminal.instance.showCursor();
          Terminal.instance.out.flush();
        }
      });
 
 
    Grid g=new Grid();
 
    // prcess argumentys
    String method="dfs";
    char start='A', destination='A';
 
    for (int i=0;i<args.length;++i) {
      if (args[i].compareTo("-g")==0) {
        g.read_file(args[++i]);
        if (g.size()==0) {
          System.err.println("error: grid is empty");
          System.exit(-1);
        }
      }
      else if (args[i].compareTo("-m")==0)
        method=args[++i];
      else if (args[i].compareTo("-s")==0)
        start=args[++i].charAt(0);
      else if (args[i].compareTo("-d")==0)
        destination=args[++i].charAt(0);
      else if (args[i].compareTo("-delay")==0)
        g.delay=Integer.parseInt(args[++i]);
      else if (args[i].compareTo("-p")==0)
        g.show_parent_=true;
      else if (args[i].compareTo("-no-color")==0)
        Terminal.instance=new Terminal(false);
      else if (args[i].compareTo("-color")==0)
        Terminal.instance=new Terminal(true);
      else if (args[i].compareTo("-show")==0)
        method=null;
      else
        usage();
    }
 
    if (g.size()==0)
      g.setup(EXAMPLE); // use default grid
 
    g.display();
 
    if (method==null) // show only
      System.exit(0);
 
    // find source node (or exit)
    int s0=g.find_first(start);
 
    // find destination node if given (or exit)
    int s1=(destination!=start ? g.find_first(destination) : -1);
 
    if (method.compareTo("dfs")==0)
      g.dfs_recursive(s0);
    else if (method.compareTo("idfs")==0)
      g.dfs_iterative(s0);
    else if (method.compareTo("bfs")==0)
      g.bfs(s0);
    else if (method.compareTo("dijkstra")==0)
      g.dijkstra(s0,s1);
    else if (method.compareTo("astar")==0) {
      if (s1<0) {
        System.err.println("A* requires destination, use '-d'");
        System.exit(-1);
      }
      g.astar(s0,s1);
    }
    else
      usage();
 
  }

Here is the call graph for this function:

◆ neighbors()

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

get neighbors of cell index (4-neighborhood)

Definition at line 192 of file Grid.java.

                                    {
    int i=get_row(index);
    int j=get_column(index);
    int north=-1,east=-1,south=-1,west=-1, k=0;
 
    // if (i>0)              { north=cell_index(i-1,j); ++k; }
    // if (j<num_columns_-1) { east =cell_index(i,j+1); ++k; }
    // if (i<num_rows_-1)    { south=cell_index(i+1,j); ++k; }
    // if (j>0)              { west =cell_index(i,j-1); ++k; }
 
    // equivalent but more efficient:
    if (i>0)              { north=index-num_columns_; ++k; }
    if (j<num_columns_-1) { east =index+1;            ++k; }
    if (i<num_rows_-1)    { south=index+num_columns_; ++k; }
    if (j>0)              { west =index-1;            ++k; }
 
    int[] nhd=new int[k];
    k=0;
 
    int[] tunnel_nhd = neighbors_from_tunnels(index);
    if (tunnel_nhd.length > 1) {
      // copy tunnels to nhd, but filter this cell index
      nhd=new int[nhd.length + tunnel_nhd.length-1];
      for (int n=0;n<tunnel_nhd.length;++n) {
        if (tunnel_nhd[n] != index) {
          nhd[k++] = tunnel_nhd[n];
        }
      }
    }
 
    if (north>=0) nhd[k++]=north;
    if (east>=0)  nhd[k++]=east;
    if (south>=0) nhd[k++]=south;
    if (west>=0)  nhd[k++]=west;
 
    return nhd;
  }

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

Here is the call graph for this function:

◆ neighbors_from_tunnels()

int[] aud.example.grid.Grid.neighbors_from_tunnels ( int index )

protected

get neighbors of index from tunnels

Definition at line 233 of file Grid.java.

                                                    {
    Cell cell = cell_[index];
 
    if (!cell.is_tunnel())
      return new int[0];
 
    if (tunnels_ == null)
      tunnels_ = new aud.HashMap<Character,int[]>();
 
    int[] nhd = tunnels_.find(cell.value);
 
    if (nhd == null) {
      nhd = create_tunnels_for(cell);
    }
 
    return nhd;
  }

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

Here is the call graph for this function:

◆ num_columns()

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

get number of columns

Definition at line 169 of file Grid.java.

169{ return num_columns_; }

◆ num_rows()

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

get number of rows

Definition at line 167 of file Grid.java.

167{ return num_rows_; }

◆ read_file()

void aud.example.grid.Grid.read_file ( String filename )

read file and treat contents as cells, calls setup

Definition at line 123 of file Grid.java.

                                         {
    StringBuilder sb=new StringBuilder();
    try {
      FileReader fr=new FileReader(filename);
      BufferedReader in=new BufferedReader(fr);
      String line;
      while ((line=in.readLine())!= null) {
        sb.append(line);
        sb.append("\n");
      }
    } catch (Exception e) {
      System.err.println("error while reading '"+filename+"'");
      System.err.println(e.toString());
      System.exit(-1);
    }
    setup(sb.toString());
  }

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ reset_cells()

void aud.example.grid.Grid.reset_cells ( )

reset all cells to default state but keep their values

Definition at line 368 of file Grid.java.

                            {
    for (int i=0;i<size();++i) {
      Cell c=cell_[i];
      cell_[i]=new Cell();
      cell_[i].value=c.value;
    }
  }

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

Here is the call graph for this function:

◆ setup() [1/2]

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

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

Definition at line 162 of file Grid.java.

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

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

Here is the call graph for this function:

◆ setup() [2/2]

void aud.example.grid.Grid.setup ( String[] lines )

setup grid from string: create contents as grid cells

Definition at line 142 of file Grid.java.

                                    {
    num_rows_=lines.length;
    num_columns_=0;      // find maximum number of columns
    for (String line : lines) {
      num_columns_=(num_columns_<line.length() ? line.length() : num_columns_);
    }
 
    cell_=new Cell[size()];
    for (int i=0;i<size();++i)
      cell_[i]=new Cell();
 
    int i=0;
    for (String line : lines) {
      for (int j=0;j<line.length();++j) {
        cell(i,j).value=line.charAt(j);
      }
      ++i;
    }
  }

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

Here is the caller graph for this function:

◆ size()

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

get total number of cells

Definition at line 171 of file Grid.java.

171{ return num_rows_*num_columns_; }

Referenced by aud.example.grid.Grid.astar(), aud.example.grid.Grid.dijkstra(), aud.example.grid.Grid.find_first(), aud.example.grid.Grid.main(), and aud.example.grid.Grid.reset_cells().

Here is the caller graph for this function:

◆ usage()

static void aud.example.grid.Grid.usage ( )

staticprotected

print help message and exit

Definition at line 577 of file Grid.java.

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

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

Here is the caller graph for this function:

Member Data Documentation

◆ delay

int aud.example.grid.Grid.delay = 100

delay in display in milliseconds

Definition at line 55 of file Grid.java.

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

◆ EXAMPLE

final String aud.example.grid.Grid.EXAMPLE

static

Initial value:

=
    "+-+         +----- --------+    +----+\n"+
    "| |  +------+----- ---+    |         |\n"+
    "|           |  A      |    |    |    |\n"+
    "| |  +------+----- ---+    |    |\n"+
    "+-+         |                   +----+\n"+
    "            +----- --------+\n"+
    "\n"+
    "                                          +\n"

example grid (argument to setup

Definition at line 44 of file Grid.java.

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

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

Grid.java

Classes

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Protected Member Functions

Static Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ Grid() [1/2]

◆ Grid() [2/2]

Member Function Documentation

◆ astar()

◆ backtrack()

◆ bfs()

◆ cell()

◆ cell_index()

◆ create_tunnels_for()

◆ dfs_iterative()

◆ dfs_recursive()

◆ dijkstra()

◆ display()

◆ find_first()

◆ get_column()

◆ get_row()

◆ main()

◆ neighbors()

◆ neighbors_from_tunnels()

◆ num_columns()

◆ num_rows()

◆ read_file()

◆ reset_cells()

◆ setup() [1/2]

◆ setup() [2/2]

◆ size()

◆ usage()

Member Data Documentation

◆ delay

◆ EXAMPLE