I'm trying to implement a BFS to find all prerequisites required before a certain course can be taken. My public List<Node> computeAllPrereqs(String courseName) method is where my code is messing up. Can someone look at my method and help me find the issue? I figured the finish node would be none, because my the courses in my graph all lead to none. The graph is not cyclic.
This is the text file that I'm passing into the constructor, the first column is the course and followed by the course are its prerequisites:
CS1 None
CS2 CS1
CS3 CS2
CS4 CS1
CS5 CS3 CS4
CS6 CS2 CS4
.
public class Graph {
private Map<String, Node> graph;
public Graph(String filename) throws FileNotFoundException {
// open the file for scanning
File file = new File(filename);
Scanner in = new Scanner(file);
// create the graph
graph = new HashMap<String, Node>();
// loop over and parse each line in the input file
while (in.hasNextLine()) {
// read and split the line into an array of strings
// where each string is separated by a space.
Node n1, n2;
String line = in.nextLine();
String[] fields = line.split(" ");
for(String name: fields){
if (!graph.containsKey(fields[0]))
{
n1 = new Node(name);
graph.put(name, n1);
}
else{
n2 = new Node(name);
graph.get(fields[0]).addNeighbor(n2);
}
}
}
in.close();
}
public List<Node> computeAllPrereqs(String courseName){
// assumes input check occurs previously
Node startNode;
startNode = graph.get(courseName);
// prime the dispenser (queue) with the starting node
List<Node> dispenser = new LinkedList<Node>();
dispenser.add(startNode);
// construct the predecessors data structure
Map<Node, Node> predecessors = new HashMap<Node,Node>();
// put the starting node in, and just assign itself as predecessor
predecessors.put(startNode, startNode);
// loop until either the finish node is found, or the
// dispenser is empty (no path)
while (!dispenser.isEmpty()) {
Node current = dispenser.remove(0);
if (current == new Node(null)) {
break;
}
// loop over all neighbors of current
for (Node nbr : current.getNeighbors()) {
// process unvisited neighbors
if(!predecessors.containsKey(nbr)) {
predecessors.put(nbr, current);
dispenser.add(nbr);
}
}
}
return constructPath(predecessors, startNode, null);
}
private List<Node> constructPath(Map<Node,Node> predecessors,
Node startNode, Node finishNode) {
// use predecessors to work backwards from finish to start,
// all the while dumping everything into a linked list
List<Node> path = new LinkedList<Node>();
if(predecessors.containsKey(finishNode)) {
Node currNode = finishNode;
while (currNode != startNode) {
path.add(0, currNode);
currNode = predecessors.get(currNode);
}
path.add(0, startNode);
}
return path;
}
}
Here's the node class I used to make the nodes and neighbors in the graph:
public class Node {
/*
* Name associated with this node.
*/
private String name;
/*
* Neighbors of this node are stored as a list (adjacency list).
*/
private List<Node> neighbors;
public Node(String name) {
this.name = name;
this.neighbors = new LinkedList<Node>();
}
public String getName() {
return name;
}
public void addNeighbor(Node n) {
if(!neighbors.contains(n)) {
neighbors.add(n);
}
}
public List<Node> getNeighbors() {
return new LinkedList<Node>(neighbors);
}
@Override
public String toString() {
String result;
result = name + ": ";
for(Node nbr : neighbors) {
result = result + nbr.getName() + ", ";
}
// remove last comma and space, or just spaces in the case of no neighbors
return (result.substring(0, result.length()-2));
}
@Override
public boolean equals(Object other) {
boolean result = false;
if (other instanceof Node) {
Node n = (Node) other;
result = this.name.equals(n.name);
}
return result;
}
@Override
public int hashCode() {
return this.name.hashCode();
}
}
Here's my test class:
public class Prerequisite {
/**
* Main method for the driver program.
*
* @param args the name of the file containing the course and
* prerequisite information
*
* @throws FileNotFoundException if input file not found
*/
public static void main(String[] args) throws FileNotFoundException {
// Check for correct number of arguments
if(args.length != 1) {
String us = "Usage: java Prerequisite <input file>";
System.out.println(us);
return;
}
// create a new graph and load the information
// Graph constructor from lecture notes should
// be modified to handle input specifications
// for this lab.
Graph graph = new Graph(args[0]);
// print out the graph information
System.out.println("Courses and Prerequisites");
System.out.println("=========================");
System.out.println(graph);
// ASSUMPTION: we assume there are no cycles in the graph
// Part I:
// compute how many (and which) courses must be taken before it is
// possible to take any particular course
System.out.println("How many courses must I take "
+ "before a given course?!?!?");
for(String name : graph.getAllCourseNames()) {
List<Node> allPrereqs = graph.computeAllPrereqs(name);
System.out.print(String.valueOf(allPrereqs.size()));
System.out.print(" courses must be taken before " + name + ": ");
for(Node el : allPrereqs) {
System.out.print(el.getName() + " ");
}
System.out.println();
}
}
When I run this test my output is:
0 courses must be taken before CS1:
0 courses must be taken before CS3:
0 courses must be taken before CS2:
0 courses must be taken before CS5:
0 courses must be taken before CS4:
0 courses must be taken before CS6:
it should be:
0 courses must be taken before CS1:
2 courses must be taken before CS3: CS1 CS2
1 courses must be taken before CS2: CS1
4 courses must be taken before CS5: CS1 CS3 CS2 CS4
1 courses must be taken before CS4: CS1
3 courses must be taken before CS6: CS1 CS2 CS4
I know I'm posting a lot of code but I don't want to have to edit in more code in later if it is needed to help fix my bug.
