import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import fti.ti.sda.GraphNodeSDA;

public class GraphExamples {

	public static void main(String[] args) {
		// membuat Node yang ada dalam graf
		GraphNodeSDA<Character> nodeA = new GraphNodeSDA<>('A');
		GraphNodeSDA<Character> nodeB = new GraphNodeSDA<>('B');
		GraphNodeSDA<Character> nodeC = new GraphNodeSDA<>('C');
		GraphNodeSDA<Character> nodeD = new GraphNodeSDA<>('D');
		GraphNodeSDA<Character> nodeE = new GraphNodeSDA<>('E');
		// membuat hubungan antar Node
		nodeA.addAdjecentNode(nodeB);
		nodeA.addAdjecentNode(nodeC);
		nodeB.addAdjecentNode(nodeA);
		nodeB.addAdjecentNode(nodeC);
		nodeB.addAdjecentNode(nodeD);
		nodeB.addAdjecentNode(nodeE);
		nodeC.addAdjecentNode(nodeA);
		nodeC.addAdjecentNode(nodeB);
		nodeC.addAdjecentNode(nodeE);
		nodeD.addAdjecentNode(nodeB);
		nodeE.addAdjecentNode(nodeB);
		nodeE.addAdjecentNode(nodeC);
		
		// mengimplementasikan Breadth First Search
		System.out.print("BFS: ");
		Queue<GraphNodeSDA<Character>> queue = new LinkedList<>();
		queue.add(nodeA); // Node awal
		// baca isi queue sampai kosong
		while(!queue.isEmpty()) {
			// baca Node yang disimpan dalam queue
			GraphNodeSDA<Character> node = queue.poll();
			// pastikan bahwa node belum pernah dikunjungi
			if(!node.isVisited()) {
				System.out.print(node.getData() + ", "); // cetak isi node
				// baca seluruh node tetangga 
				LinkedList<GraphNodeSDA<Character>> tetangga = 
						node.getAdjecentNodes();
				// masukkan seluruh tetangga dalam queue
				queue.addAll(tetangga); 
				node.visited(); // tandai bahwa node sudah dikunjungi
			}
		}
		
		// reset visited 
		nodeA.resetVisited(); nodeB.resetVisited(); nodeC.resetVisited();
		nodeD.resetVisited(); nodeE.resetVisited();
		
		// mengimplementasikan Depth First Search
		System.out.print("\nDFS: ");
		Stack<GraphNodeSDA<Character>> stack = new Stack<>();
		stack.push(nodeA); // node awal
		// baca isi stack sampai kosong
		while(!stack.isEmpty()) {
			// baca Node yang disimpan dalam stack
			GraphNodeSDA<Character> node = stack.pop(); 
			// pastikan bahwa node belum pernah dikunjungi
			if(!node.isVisited()) {
				System.out.print(node.getData() + ", "); // cetak isi node
				// baca seluruh node tetangga 
				LinkedList<GraphNodeSDA<Character>> tetangga = 
						node.getAdjecentNodes();
				// masukkan seluruh tetangga dalam queue
				stack.addAll(tetangga); 
				node.visited(); // tandai bahwa node sudah dikunjungi
			}
		}
	}

}