Solving a Color Maze using DFS

The project involves solving a color maze using DFS algorithm in Java. The graph used is a unidirectional graph with vertices representing colors and edges representing direction. The DFS algorithm is a recursive graph algorithm that uses backtracking to search all nodes from the root to the final vertex. The code reads a file containing color inputs and traverses through the inputs to find the shortest path to the blues eye.

Report: Solving a color Maze using DFS.
The projects involved reading a file from the local machine that contains a set of color inputs
(Red and blue) with direction. The start color determines the choice of the predecessor color and
so on until the blues eye is reached. We chose to use java since it is simple and easy to
understand when it comes to algorithms and solving graphical questions.
First the programs reads a file and scans through the file line by line traversing through the
inputs to find the shortest line from the root to the last end, that is, the blues eye.
The program reads the inputs and puts them into an array List where it transverses the point
using DFS algorithm to find the shortest path. The DFS algorithm when searching for a node
moves down to the end of the tree, if it doesn’t find the node, it backtracks to search for the node
in the next tree branch. The process continues until it finds the node, hence DFS is a recursive
algorithm since it can visit a specific node more than one time. But marks the visited nodes so as
not to go back again in the reverse direction.
What type of graph did you use for the problem and how did you construct the graph
(what do the vertices, edges, etc. correspond to)?
This is unidirectional graph – this is because the colors point are not placed in a specific order
and the algorithm searches in different directions until it finds the eye.
There also exist loops as it tries in the algorithm.
A vertex represents the color while the edges represent the direction that the color heads.

Which algorithm did you use? Describe it in pseudocode.
The pseudocode for DFS is shown below. Depth first search is a recursive graph algorithm that
uses backtracking that searches all nodes from the root to the final vertex and if it finds a
deadlock it backtracks.
DFS(graph,rootVertex)
//using a stack-S
S.push(rootVertex)
rootVertex is visited and hence it should be marked
while(S is not empty)
//remove the vertex and visit the next vertex
Vertex = S.top()
S.pop()
For all neighbours w of Vertex in Graph graph:
If w is not visited
S.push(w)
Mark w as visited.

Code:
package com.ken;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class ColorsMaze {
private final Map<Integer, Set<Integer>> adjList = new HashMap();
/**
* The main constructor reading Colormaze file.
*/
public ColorsMaze(File colorFile) throws FileNotFoundException{

try (Scanner scan = new Scanner(colorFile)) {
while (scan.hasNextInt()) {
int node1 = scan.nextInt();
int node2 = scan.nextInt();
this.connect(node1, node2);
this.connect(node2, node1);
}
}
}
/**
* unidirectional connection from node1 to node2.
*/
private void connect(int node1, int node2) {
if (!this.adjList.containsKey(node1)) {
this.adjList.put(node1, new HashSet());
}
this.adjList.get(node1).add(node2);
}
public String toString() {
StringBuilder s = new StringBuilder();
for (Map.Entry<Integer, Set<Integer>> adj : this.adjList.entrySet()) {
int from = adj.getKey();

Set<Integer> to = adj.getValue();
s.append(from).append(" connected to ").append(to).append('\n');
}
return s.toString();
}
public Iterable<Integer> getadjList(int node) {
return Collections.unmodifiableSet(adjList.get(node));
}
public List<String> readCharacters() {
List<String> colors = new ArrayList();
// The name of the file to open.
String fileName = "C:\\java\\input.txt";
// This will reference one line at a time
String line = null;
try {
// FileReader reads text files in the default encoding.
FileReader fileReader = new FileReader(fileName);
// Always wrap FileReader in BufferedReader.
BufferedReader bufferedReader = new BufferedReader(fileReader);

while ((line = bufferedReader.readLine()) != null) {
colors.add(line);
System.out.println(line);
}
// Always close files.
bufferedReader.close();
} catch (FileNotFoundException ex) {
ex.printStackTrace();
} catch (IOException ex) {
ex.printStackTrace();
}
return colors;
}
public static void main(String ...args) throws FileNotFoundException{
Scanner scanFile = new Scanner(System.in);
String file = scanFile.nextLine();
ColorsMaze m = new ColorsMaze(new File(file));
}

}
References
1. ANDRÁSFAI, B.: Introductory Graph Theory. The Institute of Physics (1978)
2. ANDRÁSFAI, B.: Graph Theory: Flows, Matrices. The Institute of Physics (1991)
3. BANG-JENSEN, J. & GUTIN, G.: Digraphs: Theory, Algorithmsand Applications.Springer–
Verlag (2002)
4. BOLLOBÁS, B.: Modern Graph Theory. Springer–Verlag (2002)
5. CHRISTOFIDES, N.: Graph Theory. An Algorithmic Approach. Academic Press (1975)
6. DIESTEL, R.: Graph Theory. Springer–Verlag (2005)
7. DOLAN, A. & ALDOUS, J.: Networks and Algorithms. An Introductory Approach. Wiley
(1999)