Parris Studios

So in my previous post a year ago. My graphing was actually based around small cases. Cases where verticies and edges could be represented as objects; however, in the real world this completely not optimal and does not work…

Dijkstra’s

**
 * This method performs a breadth first search. It will color all nodes,
 * list discovery times, and specify the discovery node. This can be used
 * information can then be accessed from the graph class.
 * @param startNode
 * The Vertex at which to start the search
 */
 private void dijsktra(int sx, int sy, int ex, int ey){
 int height = this.allNodes.length;
 int width = this.allNodes[0].length;
 nodes = new Node[height][width];
 PriorityQueue<Node> q = new PriorityQueue<Node>(10000);
 q.offer(new Node(sx,sy,1,null,0,-1));
 out:
 while(!q.isEmpty()){
 Node u = q.poll();
 for (int i=0; i<dy.length;i++){
 int x = u.x+dx[i];
 int y = u.y+dy[i];
 if (x >= 0 && x < width && y >= 0 && y < height && allNodes[y][x] != 'x'){
 Node a = new Node(x,y,1,u,u.weightFromStart+direction(i),i);
 if(Math.abs(a.weightFromStart-u.weightFromStart)>epsilon){
 if (nodes[y][x]!=null && a.compareTo(nodes[y][x])==1){
 q.remove(nodes[y][x]);
 nodes[y][x] = a;
 q.offer(a);
 }
 else if (nodes[y][x]==null){
 nodes[y][x] = a;
 q.offer(a);
 }
 }
 }
 }
 }
 }

Breadth First:

char label may have been assignment specific. I don’t remember what it is for. I believe it is just the label I wanted to mark things with.

private static void bfs(int starti, int startj, char label){
 int height = maze.length;
 int width = maze[0].length;
 //set color
 discovery[starti][startj][3]=1;
 //set discovery time
 discovery[starti][startj][2]=0;
 //create queue
 ArrayBlockingQueue<Integer[]> q = new ArrayBlockingQueue<Integer[]>(10000);
 Integer[] a = {starti,startj};
 q.offer(a);
 while(!q.isEmpty())
 {
 Integer[] u = q.poll();
 for (int i=0;i<dx.length;i++){
 if ((u[0]+dx[i]<height && u[1]+dy[i]<width)&&(((u[0]+dx[i]>=0 && u[1]+dy[i]>=0)&&(maze[u[0]+dx[i]][u[1]+dy[i]]!='x'&&maze[u[0]][u[1]]!='x'))&&discovery[u[0]+dx[i]][u[1]+dy[i]][3]==0)){
 //color
 discovery[u[0]+dx[i]][u[1]+dy[i]][3] = 1;
 //disc time
 discovery[u[0]+dx[i]][u[1]+dy[i]][2] = discovery[u[0]][u[1]][2] + 1;
 //pi
 discovery[u[0]+dx[i]][u[1]+dy[i]][0] = u[0];
 discovery[u[0]+dx[i]][u[1]+dy[i]][1] = u[1];
 //update queue
 Integer[] b = {u[0]+dx[i],u[1]+dy[i]};
 q.offer(b);
 }
 }
 discovery[u[0]][u[1]][3] = 2;
 if (maze[u[0]][u[1]]!='x')
 maze[u[0]][u[1]] = label;
 }
 }

Actually I don’t have depth first, but it is pretty similar. I am just you could figure it out !

Maybe I will include Kruskals and Prims sometime. I have those coded too. Hope this helps someone.