Some Java projects

PROJECT 1: Forming graphs. Listing prerequisites. Detecting cycles in the graph.

The following is a Java that I completed yesterday i.e. on January 20th (2002). I found it interesting & decided to put it on the web. This was an assignment for my Algorithms (CS 341) course. It was just submitted today so I'm not sure how correct this solution was, although I tried to test & make sure that it works well.

For the next stage of this program, I'd like to actually make a Java applet that runs on the web. It would actually show as the vectors & hashtables are being filled. It would also show the Depth-first search taking place. I think it'd be exciting to see those details. But for now, I'm just putting the "raw" code. It runs from a Console window.

1) Use the Makefile to compile the program by typing in make, or javac CycleFind.java
2) Next step is to run the file, which is done in either of the following two ways:
        Usage:   java CycleFind -prereq <coursename> <inputfile>
          java CycleFind -find <inputfile>

Goals of the program:

• Program a graph data structure & perform operations on it
• Implement the Depth-first Search algorithm
• Adapt the DFS algorithm to find cycles in directed graphs
• Assume valid input
  

Brief Explanation:

Two main things done by the program is that if we choose the "-prereq" option then it will list all the courses that require the given course to be taken. If "-find" option is chosen then the program checks for cycles in the graph. If there is a cycle then it displays the cycle else it displays "No cycle found" message. See bottom of the page for sample input files & their output.

The program models relationships between courses that one might need to take. Also note that there is a directed graph, where a directed edge exists from node A to node B if course B has course A as a prerequisite (i.e. course A must be taken before course B). For example, if CS341 requires both CS240 and Math239 as prerequisites, this can be shown this way:

The program also tests for such cycles in any such graph. If we ever find an edge from an active node to another active node, the program stops, and the directed cycle is printed out.

Input:

• Text file that follows a specified format.
• There is a set of lines, each with the name of one course on them. Note that for simplicity, course names are one word long, with no spaces. Then, there is a line which consists of a single hyphen. Then, there is a set of lines representing prerequisite relationships, with one such relationship per line. Thecourse that is a prerequisite is first, then there is a space, then the course for which the first course is a prerequisite.
• Sample Input file:

CS240
Math239
CS341
-
CS240 CS341
Math239 CS341

Output:

• General formal: course 1 -> course 2 -> course 3 -> course 4 -> ... -> course 1
• For example, if the input consists of:
      CS360
      CS341
      Math239
      CS370
      -
      CS360 CS341
      CS370 CS360
      Math239 CS370
      Math239 CS341
      CS341 Math239
• Then the output might be: (It might also print this cycle in another order, or another cycle altogether.)

CS341 -> Math239 -> CS341

• If the graph has no cycles, the output should be:
          No cycle detected.

Java Code

• Note that the actual files have a *.txt at the end. To actually compile the files, rename them to *.java
• CycleFind.java
• Node.java
• Graph.java
• Makefile
• Test files: test1    test2    test3    test4    test5

Testing screen shot for the files above:

Home 

Page updated on: 19-Feb-2002 03:40 PM