package graphs;

import base.Colour;
import stacksAndQueues.Queue;
import java.util.ArrayList;

/**
 * Perform Breadth-First Search on a graph. 
 * @author sjc
 *
 */
public class BFS {
	GraphNode[] nodes;
	Integer[][] edges;
	Integer start;
	
	public BFS (GraphNode[] ns, Integer[][] es, Integer sn) {
		nodes = ns;
		edges = es;
		start = sn;
	}
	
	public void search(){
		initialiseStartNode();
		Queue<GraphNode> Q = new Queue<GraphNode>(nodes.length);
		Q.enqueue(nodes[start]);
		while(!Q.isEmpty()){
			GraphNode current = Q.dequeue();
			searchAdjacent(current);
		}
	}
	
	private void searchAdjacent(GraphNode current){
		ArrayList<GraphNode> adj = getAdjacent(current);
		exploreNodes(adj);
		current.colour = Colour.BLACK;
	}
	
	private void exploreNodes(ArrayList<GraphNode> adj){
		// TODO: Implement this
	}
	
	private ArrayList<GraphNode> getAdjacent(GraphNode current){
		ArrayList<GraphNode> adj = new ArrayList<GraphNode>();
		Integer[] edgesFromCurrent = edges[current.value];
		for(int i=0; i<edgesFromCurrent.length; i++){
			Integer edge = edgesFromCurrent[i];
			if(edge == 1){
				adj.add(nodes[i]);
			}
		}
		return adj;
	}
	
	private void initialiseStartNode(){
		GraphNode startnode = nodes[start];
		startnode.colour = Colour.GREY;
		startnode.d = 0;
	}
}

@@ -549,32 +549,45 @@
 archAdjacent
+AndAddToQueue
 (current
 );%0A%09%09%7D%0A%09%7D%0A%09%0A
@@ -570,24 +570,27 @@
 ueue(current
+, Q
 );%0A%09%09%7D%0A%09%7D%0A%09%0A
@@ -609,32 +609,45 @@
 d searchAdjacent
+AndAddToQueue
 (GraphNode curre
@@ -640,32 +640,52 @@
 raphNode current
+, Queue%3CGraphNode%3E Q
 )%7B%0A%09%09ArrayList%3CG
@@ -740,16 +740,28 @@
 odes(adj
+, current, Q
 );%0A%09%09cur
@@ -848,36 +848,339 @@
  adj
-)%7B%0A%09%09// TODO: Implement this
+, GraphNode parent, Queue%3CGraphNode%3E Q)%7B%0A%09%09for(GraphNode current : adj)%7B%0A%09%09%09if(current.colour == Colour.WHITE)%7B%0A%09%09%09%09visitNode(current, parent);%0A%09%09%09%09Q.enqueue(current);%0A%09%09%09%7D%0A%09%09%7D%0A%09%7D%0A%09%0A%09private void visitNode(GraphNode current, GraphNode parent)%7B%0A%09%09current.colour = Colour.GREY;%0A%09%09current.d = parent.d +1;%0A%09%09current.parent = parent;%09%09
 %0A%09%7D%0A

Finished BFS algorithm. Untested