Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

In this project, you are asked to design, implement, and test an abstract data type (ADT) graph in its prototype. It can include frequently used

In this project, you are asked to design, implement, and test an abstract data type (ADT) graph in its prototype. It can include frequently used algorithms, such as DFS, BFS, and so on. In this project, you are required to implement topological ordering algorithm only, which is based on DFS. Other algorithms can be extended in the future. In order to output the sequence of the courses, you need a sorting algorithm, which will put the courses in the order according to their post visiting numbers

I REALLY NEED HELP DEFINING THE MAIN CLASS, here is what I have so far:

CourseGrap.java:

package Project2;

import java.io.BufferedReader;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.IOException;

import java.util.ArrayList;

import java.util.Map;

import java.util.TreeMap;

public class CourseGraph {

//private String course_name;

private String course_symbol;

private Map> rev_graph;//this is reverse

private Map> graph_ori;

private ArrayList allKey;

//

private Integer[] preVisited;

private Integer[] postVisited;

private Boolean[] visited;

private final int numOfCourse = 31;

private int num;

//Constructor

public CourseGraph() {

this.course_symbol = "";

rev_graph = new TreeMap>();

graph_ori = new TreeMap>();

allKey = new ArrayList();

preVisited = new Integer[numOfCourse];

postVisited = new Integer[numOfCourse];

visited = new Boolean[numOfCourse];

for(int a = 0; a < numOfCourse; a++) {

preVisited[a] = 0;

postVisited[a] = 0;

visited[a] = false;

}

num = 0;

}

//Returns all the keys

public ArrayList getAllKey() {

ArrayList string = new ArrayList();

for(String key : rev_graph.keySet())

string.add(key);

return string;

}

//Returns values(ArrayList) of key(String) from the HashMap

public ArrayList getvaluelist(String key) {

ArrayList a = new ArrayList();

for(String x : rev_graph.get(key)) {

a.add(x);

}

return a;

}

//Reads from the file and stores individual lines in an ArrayList

public void initialize(String myFileName) {

//create arraylist of lines

ArrayList lines = new ArrayList();

String line;

try {

// FileReader reads text files in the default encoding.

FileReader fileReader = new FileReader(myFileName);

// Always wrap FileReader in BufferedReader.

BufferedReader bufferedReader = new BufferedReader(fileReader);

while((line = bufferedReader.readLine()) != null) {

lines.add(line);// add lines to ArrayList of lines

}

System.out.println();

System.out.println("!!!!!!!!!!DONE READING FILE!!!!!!!!!!");

System.out.println();

// Always close files.

bufferedReader.close();

} catch (FileNotFoundException ex) {

System.out.println("Unable to open file '" + myFileName + "'");

} catch (IOException ex) {

System.out.println("Error reading file '" + myFileName + "'");

}

//after reading file, start to split each line by calling split method

for(String s : lines) {

splitLine(s);

}

}

// split method to split each line into course names and pre reqs

public void splitLine(String line) {

ArrayList prerequsite = new ArrayList();

//Splits each line into course and course pre reqs

if(line.contains("(")) {

String array[] = line.split("\\(|\\)");

course_symbol = array[0].substring(0, 9);

String list = array[1];

//if more than 1 pre req, add other prereqs to the ArrayList

if(list.contains(",")) {

String m[] = list.split(",");

for(int i = 0; i < m.length; i++) {

if(m[i].charAt(0) != ' ') {

prerequsite.add(m[i]);

} else {

m[i] = m[i].substring(1, m[i].length());

prerequsite.add(m[i]);

}

}

} else

prerequsite.add(list);

} else {

course_symbol = line.substring(0, 9);

}

//Add the key(course_symbol) and value(prerequsite) to the rev_graph

rev_graph.put(course_symbol, prerequsite);

setOriGraph();

}

//set original rev_graph with prereqs

public void setOriGraph() {

//Adds courses prereqs to an array list then put it in the map

for(String x : rev_graph.keySet()) {

ArrayList oriVal = new ArrayList();

for(String s : rev_graph.keySet()) {

if(getvaluelist(s).contains(x))

oriVal.add(s);

}

graph_ori.put(x, oriVal);

}

}

//DFS

public void dfs() {

//set all visit false and store all key set in array

// assign false for all visited elements

allKey = getAllKey();

for(int i = 0; i < allKey.size(); i++)

visited[i] = false;

//go through every key in the rev_graph

for(int i = 0; i < allKey.size(); i++) {

if(!visited[i])

//explore the values of the key[i]

explore(allKey.get(i), graph_ori.get(allKey.get(i)));

}

}

//Explore

public void explore(String key, ArrayList values) {

//get the number of that key with this values as values

int a = allKey.indexOf(key);

visited[a] = true;

preVisited[a] = ++num;

for(int j = 0; j < values.size(); j++) {

//get index of value[j] in allKey;

int k = allKey.indexOf(values.get(j));

//get the class name that have this value as prerequisite

if(visited[k] == false) {

explore(values.get(j), graph_ori.get(values.get(j)));

}

}

postVisited[a] = ++num;

}

//Previsit

public void previsit() {

System.out.println("preVisited");

System.out.println(this.preVisited);

}

//Postvisit

public void postvisit() {

System.out.println("postVisited");

System.out.println(this.postVisited);

}

//Selection sorting algorithm to sort previsit, postvisit, and keys from highest to lowest

public void selectionSort() {

for(int i = 0; i < numOfCourse; i++) {

int max = i;

for(int j = i; j < numOfCourse; j++)

if(postVisited[max] < postVisited[j])

max = j;

int tem = postVisited[i];

postVisited[i] = postVisited[max];

postVisited[max] = tem;

tem = preVisited[i];

preVisited[i] = preVisited[max];

preVisited[max] = tem;

String temKey = allKey.get(i);

allKey.set(i, allKey.get(max));

allKey.set(max, temKey);

}

for(int i = 0; i < numOfCourse; i++) {

System.out.print(preVisited[i] + ", ");

}

System.out.println(" Sorted post Visited");

for(int i = 0; i < numOfCourse; i++) {

System.out.print(postVisited[i] + ", ");

}

System.out.println();

System.out.print(allKey);

}

//Run the DFS and prints original graph

public void printOri() {

for(String key : graph_ori.keySet()) {

System.out.println(key + graph_ori.get(key));

}

}

//prints previsit and post visited order then sorts them by calling the selectionSort method

public void print() {

System.out.println(rev_graph);

for(int i = 0; i < numOfCourse; i++) {

System.out.print(preVisited[i] + ", ");

}

System.out.println(" post Visited");

for(int i = 0; i < numOfCourse; i++) {

System.out.print(postVisited[i] + ", ");

}

selectionSort();

}

}

courses.txt:

MATH 1390 COLLEGE ALGEBRA MATH 1591 Calculus I (MATH 1390) MATH 2330 Discrete Mathematics (MATH 1591, CSCI 1470) MATH 3320 Linear Algebra (MATH 2330) CSCI 1470 COMPUTER SCIENCE I (MATH 1390) CSCI 1480 COMPUTER SCIENCE II (CSCI 1470) CSCI 2320 DATA STRUCTURES (CSCI 1480) CSCI 2440 ASSEMBLY LANGUAGE AND COMPUTER ORGANIZATION (CSCI 1480) CSCI 3190 SOCIAL IMPLICATIONS OF TECHNOLOGY (CSCI 2320) CSCI 3330 ALGORITHMS (CSCI 2320, MATH 2330) CSCI 3335 NETWORKING (CSCI 2320) CSCI 3345 HUMAN-COMPUTER INTERACTION (CSCI 2320) CSCI 3350 FILE STRUCTURES (CSCI 2320) CSCI 3360 DATABASE SYSTEMS (CSCI 2320) CSCI 3370 PRINCIPLES OF PROGRAMMING LANGUAGES (CSCI 2320) CSCI 3380 COMPUTER ARCHITECTURE (CSCI 2440) CSCI 3381 OBJECT-ORIENTED SOFTWARE DEVELOPMENT WITH JAVA (CSCI 2320) CSCI 3385 ARTIFICIAL INTELLIGENCE (CSCI 2320) CSCI 4300 OPERATING SYSTEMS (CSCI 2440, CSCI 3330) CSCI 4310 INTRODUCTION TO SCIENTIFIC COMPUTING (CSCI 2320, MATH 1591,MATH 3320) CSCI 4315 INFORMATION SECURITY (CSCI 3330) CSCI 4320 COMPILER CONSTRUCTION (CSCI 3370) CSCI 4340 INTRODUCTION TO PARALLEL PROGRAMMING (CSCI 2440, CSCI 3330) CSCI 4345 INTRODUCTION TO REAL-TIME SYSTEM CONCEPTS AND IMPLEMENTATION (CSCI 4300) CSCI 4350 COMPUTER GRAPHICS (CSCI 2320, MATH 3320) CSCI 4353 INTRODUCTION TO MULTIMEDIA COMPUTING (CSCI 3330) CSCI 4355 DISTRIBUTED OBJECT COMPUTING (CSCI 3335) CSCI 4365 WEB TECHNOLOGY (CSCI 3330) CSCI 4370 DATA MINING (CSCI 3360) CSCI 4390 THEORY OF COMPUTATION (CSCI 2320, MATH 2330) CSCI 4490 SOFTWARE ENGINEERING (CSCI 3381)

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Multidimensional Array Data Management In Databases

Authors: Florin Rusu

1st Edition

1638281483, 978-1638281481

More Books

Students also viewed these Databases questions

Question

10.

Answered: 1 week ago