## Graph Theory, Breadth First Search, Depth First Search

(UPDATED ON NOV 10th, 2008) – fixed a bug

(UPDATED ON Dec 16th, 2008) – fixed a bug

Here are some pretty slick algorithms (in my opinion haha) for a Graph Theory Assignment I had recently. I see plenty of ways to optimize the code, but I had to finish the project. Depth first search was stripped of its time detection stuff… They could be easily added. Just find some psuedo code :)! The javadoc on depth first search sucks by the way…. sorry haha. Below is the definition of the project:

You will be given a graph (in incoming adjacency list format, as specified later) as input. The vertices of the graph again represent a list of tasks, and an incoming edge represents a task which must be performed before the current one. Furthermore, each task has an (integer) time associated with it, representing the amount of time needed to complete the task.

The goal is to compute the minimum time needed to complete the entire project represented by the graph. The assumption is that, if you have two tasks which do not (directly or indirectly) depend on each other, these tasks can be performed simultaneously, in the time required for the longer of the two tasks.

Input: Given a filename as a command line argument, the first line of the input file will be a number representing the number of vertices in the graph. If you are given number *n*, it will be followed by *n* more lines before the end of the file. For the *i*= the 2nd through *n+1*st lines of the file, the first number represents the time needed for the *i*th vertex, and each integer after that represents a prerequisite vertex. Numbers on a line are separated by a single space. (Vertices are numbered 1 through *n*.)

Output: If the problem has no cycle, you are to output *n+1* integers, one per line. The first *n* numbers represent the earliest possible starting times for each of the n vertices (in order of the vertices, not of their starting times). The last number is the total minimum time needed to complete the task. If the input graph DOES have a cycle, you just output the number -1 (only one line of output). You should write your output to System.out.

Example: Suppose the file has the following input:

5

4 4 5

5

14 2

2 3

17 2

Then the correct output is:

22

0

5

19

5

26

Here, task 2 goes first, starting at time 0. When it completes at time 5, the two tasks which depend on it (tasks 3 and 5) begin. Task 3 completes at time 19, which allows task 4 to start at time 19, and it completes at time 21. However, task 5 doesn’t complete until time 22, at which point task 1 can begin. It finishes (along with the whole project) at time 26.

Below is the code:

import java.util.*; import java.io.*; /** * A Graph contains edges and verticies (nodes). This class will allow you * to add edges and nodes to your graph using the insert command and also * allow you to check how long it would take to reach a task. Also in that * process it will allow you to see if the graph or part of a graph has a * cycle. * @author Parris */ public class MinCompletion { /** * @param args the command line arguments */ public static void main(String[] args) { MinCompletion g = new MinCompletion(); g.run(args); } /** * Non-static version of main. * @param args */ public void run(String[] args){ // remove when submitting //args = new String[1]; //args[0] = "input1.txt"; for (int i = 0; i < args.length; i++) { try { Graph g = new Graph(); ArrayList theLines = new ArrayList(); File aFile = new File(args[i]); Scanner aScanner = new Scanner(aFile); //kill the first line, pointless.... aScanner.nextLine(); //Scan file add lines to theLines while(aScanner.hasNextLine()) theLines.add(aScanner.nextLine()); //For each line create a new Node, and remove the weight from //the line for (int j=0;j { Scanner bScanner = new Scanner(theLines.get(j)); g.insert(bScanner.nextInt()); String theNewString = ""; while(bScanner.hasNextInt()) theNewString += bScanner.nextInt() + " "; theLines.set(j, theNewString); } //go through each line and add the edges for (int j=0; j { ArrayList preReqEdges = new ArrayList(); Scanner cScanner = new Scanner(theLines.get(j)); //go through each string, each number is connecting 2 nodes while(cScanner.hasNextInt()) { preReqEdges.add(cScanner.nextInt()); } //System.out.println(preReqEdges.toString()); if (preReqEdges.size()!=0) g.connectNodes(j, preReqEdges); } //find max times for everything ArrayList largestTimes = new ArrayList(); boolean minusOneExists = false; for (int j=0; j { largestTimes.add(g.findTime(j)); if (largestTimes.get(largestTimes.size()-1)==-1) minusOneExists = true; else System.out.println( largestTimes.get(largestTimes.size()-1)); } if (!minusOneExists) { //-1 since this program is working off a 0 index Node largestNode = g.allNodes.get(g.findIndex(largestTimes)-1); System.out.println(largestNode.weight+g.findMax(g.findPathTimes(0, g.allNodes.get(i),largestTimes))); } else System.out.println(-1); } catch (Exception e) { System.out.println("Could not process the file: " +e); } } } class Graph { ArrayList allEdges; ArrayList allNodes; /** * Initializes the Graph */ public Graph(){ allEdges = new ArrayList(); allNodes = new ArrayList(); } /** * Returns the Number of Verticies in the graph * @return * The Number of Verticies in the Graph */ public int getNumberOfVerticies() { return allNodes.size(); } /** * Returns the Number of Edges in the graph * @return * The Number of Edges in the Graph */ public int getNumberOfEdges() { return allEdges.size(); } /** * This class creates a new Node based on the specified edge. * @param n * The weight of the new vertex */ public void insert(int n) { // first add the new node allNodes.add(new Node(n)); } /** * Will create edges and connect Nodes in this graph * @param preReqNodes * An ArrayList of integers which represent nodes that * are prerequistes of the new Node with weight n */ public void connectNodes(int destNode, ArrayList preReqNodes) { if (preReqNodes.size()!=0) { //System.out.println("connect "+preReqNodes.toString()+" and " +destNode); ArrayList allNewEdges = new ArrayList(); for (int i=0; i { //make a new edge, the source is the preReqNodes.get(i), the dest is //preReqNodes Edge a = new Edge(allNodes.get(preReqNodes.get(i)-1), allNodes.get(destNode)); //we must add this edge to the source node and to our compiled list allNodes.get(preReqNodes.get(i)-1).addEdge(a); allNodes.get(destNode).addEdge(a); allNewEdges.add(a); } //add all edges to the node and to the allEdge list if(allNewEdges.size()>0) { allNodes.get(destNode).addEdges(allNewEdges); allEdges.addAll(allNewEdges); } } } /** * This method will find how long it takes to process a vertex * @param n * Is the index of the vertex for which to find length of it's prerequisites * @return * The Length of time of a vertex's prerequisites */ public int findTime(int n){ if (!this.cycleExists(allNodes.get(n))) { ArrayList pathLengths = findPathTimes(0,allNodes.get(n), new ArrayList()); for(int i=0;i pathLengths.set(i, pathLengths.get(i)-allNodes.get(n).getWeight()); //System.out.println(pathLengths.toString()); return findMax(pathLengths); } else return -1; } /** * Finds all path times that exist in all branches. Recurses through all * paths. * @param time * Expects the starting amount of time. Assume 0. * @param n * The starting Node * @param pathLengths * The arraylist which stores the finished Path Lengths * @return * Returns the path lengths in an ArrayList */ private ArrayList findPathTimes(int time, Node n, ArrayList pathLengths){ boolean hasASource = false; for (Edge e : n.getConnectedEdges()) { if(!e.getSource().equals(n)) { hasASource = true; } } if (hasASource) { for (Edge e: n.getConnectedEdges()) { if (!e.getSource().equals(n)) findPathTimes(time+n.getWeight(),e.getSource(), pathLengths); } } else { pathLengths.add(time+n.getWeight()); } return pathLengths; } /** * This method checks to see if a cycle exists using breadth first search * @param startNode * The Vertex at which to start the search * @return * A Boolean value "false" will be return if there is no cycle. Otherwise * true will be returned. */ private boolean cycleExists(Node startNode){ return this.depthFirstSearch(startNode); } /** * 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 breadthFirstSearch(Node startNode) { this.cleanNodes(); int discoveryTime = 1; startNode.setColor(1); startNode.setDiscoveryTime(0); PriorityQueue q = new PriorityQueue(); q.offer(startNode); while(!q.isEmpty()) { Node u = q.poll(); for(Edge v : u.getConnectedEdges()) { //the adj edges, verticies are white, and not the vertex itself //the color it grey and put them in the queue if(v.getDest().getColor()==0 &amp;&amp; !v.getDest().equals(u)) { v.getDest().setColor(1); v.getDest().setDiscoveryTime(discoveryTime); v.getDest().setPi(u); q.offer(v.getDest()); } else if(v.getSource().getColor()==0 &amp;&amp; !v.getSource().equals(u)) { v.getSource().setColor(1); v.getSource().setDiscoveryTime(discoveryTime); v.getSource().setPi(u); q.offer(v.getSource()); } } discoveryTime++; u.setColor(0); } } /** * Uses DFS on the starting node. * @param n * DFS on the starting node. * @return * A boolean value, true if cycle is there, false if not. */ private boolean depthFirstSearch(Node n) { Node startNode = n; this.cleanNodes(); boolean isCycle = false; for (Node d : allNodes) { d.setColor(0); d.pi = null; } for (Node d : allNodes) { if (d.color == 0) { isCycle = this.depthFirstSearchVisit(n,isCycle,startNode); } } return isCycle; } /** * Using DFS the startingNode is visiting its Dest node. * @param n * The node we start with. * @param foundCycle * Boolean true if cycle, false otherwise. * @param startNode * Uses the starting node of DFS * @return * foundCycle */ private boolean depthFirstSearchVisit(Node n,boolean foundCycle, Node startNode) { n.setColor(1); for (Edge e : n.getConnectedEdges()) { if(e.getDest().color == 0 &amp;&amp; !e.getDest().equals(n)) { e.getDest().setPi(n); return depthFirstSearchVisit(e.getDest(),foundCycle,startNode); } else if (e.getDest().equals(startNode)&amp;&amp;!n.equals(startNode)) { //there is a cycle foundCycle = true; } } n.setColor(2); return foundCycle; } /** * Initializes nodes for running any graph algorithm on them. Cleans * the color, discovery time, finishing time, and discovery node variables. */ private void cleanNodes() { for(Node n : allNodes) { n.setColor(0); n.setDiscoveryTime(-1); n.setFinishingTime(-1); n.setPi(null); } } /** * Returns the max number in a ArrayList * @param numbers * An Array List of numbers * @return * The Biggest number */ private int findMax(ArrayList numbers) { int theMax = 0; for (Integer n: numbers) if (theMax theMax = n; return theMax; } /** * Returns the index for the max number in a ArrayList * @param numbers * An Array List of numbers * @return * The index of the biggest number */ private int findIndex(ArrayList numbers) { int theMax = 0; for (int i=0; i if (theMax theMax = i; return theMax; } } /** * The Edge class is protected. Only this class may access it. * An Edge object will connect 2 nodes together. One will be the source * the other will be the destination. */ class Edge { private Node dest; private Node source; /** * Initiallizes an edge * @param source * The source of Edge of type Node * @param dest * The Destination of the Edge of type Node */ protected Edge(Node source, Node dest) { this.source = source; this.dest = dest; } /** * Checks to see if an Edge is equal to another edge * @param e * Edge for which to compare * @return * True if these 2 edges are equal */ public boolean equals(Edge e) { // if this source and dest are equal to e's source // and dest then this edge is equal. if (this.getSource().equals(e.getSource()) &amp;&amp; this.getDest().equals(e.getDest())) return true; else return false; } /** * Returns the node which is identified as the Destination of this * Edge * @return * The Destination of type Node */ protected Node getDest() { return dest; } /** * Returns the node which is identified as the source of this * Edge * @return * The Source of type Node */ protected Node getSource() { return source; } /** * Returns some useful preformated string representing this Edge * @return * String representing this Edge */ public String toString() { return "Edge "+ "Destination " + dest + "Source " + source; } } class Node { ArrayList connectedEdges = new ArrayList(); int weight; /* * A Node can have 3 colors signifying if it is processed, visited or * not yet seen. This is used to find a cycle or possibly for depth * first search also. * 0 = white, undiscovered * 1 = grey, discovered but not processed, * 2 = black, discovered and processed */ int color; int discoveryTime; int finishingTime; Node pi; // the node discovers it /** * Initializes a node * @param weight * The Weight of a node, of type integer */ protected Node(int weight) { this.weight = weight; } /** * Checks to see if another node is equal by comparing weight, and what * edges it has. It may be possible to not override this method from the * standard equals class. Simply checking the hash may have been * sufficient * @param n * The Node n, for which to check equality. * @return * True if the 2 nodes are equal otherwise false. */ public boolean equals(Node n) { // if this node's weight is equal to n's weight // and all the edges of the 2 nodes are the same // then these nodes are equal if(this.getWeight() == n.getWeight() &amp;&amp; this.getConnectedEdges().equals(n.getConnectedEdges())) return true; else return false; } /** * Returns a list of all connected edges. * @return * An ArrayList of Stereotpe Edge which represents all connected edges */ protected ArrayList getConnectedEdges() { return connectedEdges; } /** * Adds all edges within a collection * @param allEdges * An ArrayList of Edges to add. */ protected void addEdges(ArrayList allEdges) { this.connectedEdges.addAll(allEdges); } /** * Adds a single edge to this Node * @param anEdge * Adds an Edge to this Node */ protected void addEdge(Edge anEdge) { this.connectedEdges.add(anEdge); } /** * 0 = white, discovered and unprocessed * 1 = grey, discovered but not processed * 2 = black, discovered and processed * @param color * The color to set this node of type int (0,1,2) as defined previously */ public void setColor(int color) { this.color = color; } /** * Set this discovery time * @param discoveryTime * Set the time at which this node was discovered */ public void setDiscoveryTime(int discoveryTime) { this.discoveryTime = discoveryTime; } /** * Set this finishing time * @param finishingTime * The time at which this node finishing processing */ public void setFinishingTime(int finishingTime) { this.finishingTime = finishingTime; } /** * Set this discovery node * @param pi * The node that discovers this node */ public void setPi(Node pi) { this.pi = pi; } /** * Gets this nodes discovery time * @return * the time at which this node was discovered */ public int getDiscoveryTime() { return discoveryTime; } /** * Gets this nodes finishing time * @return * the time at which this node was finished */ public int getFinishingTime() { return finishingTime; } /** * Gets the node that discovered this node * @return * the node that discovered this node */ protected Node getPi() { return pi; } /** * 0 = white, discovered and unprocessed * 1 = grey, discovered but not processed * 2 = black, discovered and processed * @return color * The color of this node of type int (0,1,2) as defined previously */ public int getColor() { return this.color; } /** * Returns the weight also known as processing time in this case. * @return * Weight of type int */ public int getWeight() { return weight; } /** * Returns some useful preformated string representing this Node * @return * String representing this Node */ public String toString() { return "This Node has Value: " + this.getWeight(); } } }

### Leave a Reply

You must be logged in to post a comment.