Answered step by step
Verified Expert Solution
Question
1 Approved Answer
I really appreciate your help! The extra credit would also really help if possible! Code: *****BaseMain.java***** /** * Program for generating kanji component dependency order
I really appreciate your help! The extra credit would also really help if possible! 
In this assignment, you will implement an editable graph data structure and a new algorithm for finding the topological sort of a graph Our goal will be to load two data files, and print out a topological order for the characters that they list. Attached to this post are a base file and two interfaces. Further down the BlackBoard page, you'll find a PDF describing the Java implementation of hashtables (you may find it useful), and a visualization of the dependencies in the data files. The data is formatted as follows data-kanji.txt (UTF-8 formatted) stores nodes e Tab separated * # prefixes comment lines. Lines look like Code:
*****BaseMain.java*****
/**
* Program for generating kanji component dependency order via topological sort.
*
* @author (your name), Acuna
* @version (version)
*/
public class BaseMain {
/**
* Entry point for testing.
* @param args the command line arguments
*/
public static void main(String[] args) {
//TODO: implement this
//Freebie: this is one way to load the UTF8 formated character data.
//BufferedReader indexReader = new BufferedReader(new InputStreamReader(new FileInputStream(new File("data-kanji.txt")), "UTF8"));
}
}
*****TopologicalSort.java*****
/**
* Interface for classes providing a topological sort of a digraph.
*
* @author Sedgewick and Wayne, Acuna
*/
public interface TopologicalSort
{
/**
* Returns an iterable object containing a topological sort.
* @return a topological sort.
*/
public Iterable order();
/**
* Returns true if the graph being sorted is a DAG, false otherwise.
* @return is graph a DAG
*/
public boolean isDAG();
}
*****EditableDiGraph.java*****
import java.util.NoSuchElementException;
/**
* Implements an editable graph with sparse vertex support.
*
* @author Acuna
*/
public interface EditableDiGraph {
/**
* Adds an edge between two vertices, v and w. If vertices do not exist,
* adds them first.
*
* @param v source vertex
* @param w destination vertex
*/
void addEdge(int v, int w);
/**
* Adds a vertex to the graph. Does not allow duplicate vertices.
*
* @param v vertex number
*/
void addVertex(int v);
/**
* Returns the direct successors of a vertex v.
*
* @param v vertex
* @return successors of v
*/
Iterable getAdj(int v);
/**
* Number of edges.
*
* @return edge count
*/
int getEdgeCount();
/**
* Returns the in-degree of a vertex.
* @param v vertex
* @return in-degree.
* @throws NoSuchElementException exception thrown if vertex does not exist.
*/
int getIndegree(int v) throws NoSuchElementException;
/**
* Returns number of vertices.
* @return vertex count
*/
int getVertexCount();
/**
* Removes edge from graph. If vertices do not exist, does not remove edge.
*
* @param v source vertex
* @param w destination vertex
*/
void removeEdge(int v, int w);
/**
* Removes vertex from graph. If vertex does not exist, does not try to
* remove it.
*
* @param v vertex
*/
void removeVertex(int v);
/**
* Returns iterable object containing all vertices in graph.
*
* @return iterable object of vertices
*/
Iterable vertices();
/**
* Returns true if the graph contains at least one vertex.
*
* @return boolean
*/
boolean isEmpty();
/**
* Returns true if the graph contains a specific vertex.
*
* @param v vertex
* @return boolean
*/
boolean containsVertex(int v);
}
*****data-components.txt*****
#src dst
92 73
76 73
5 17
76 17
78 18
15 18
106 19
78 20
106 20
76 21
18 21
78 96
76 95
76 97
92 26
78 26
78 109
115 109
92 77
108 94
106 94
78 30
99 30
106 31
30 31
99 71
30 71
78 88
15 116
78 37
99 84
37 84
76 119
92 40
76 98
40 98
112 83
78 83
115 118
92 89
92 113
108 113
89 113
92 100
113 100
76 48
78 51
92 51
92 110
78 110
106 110
76 335
335 4
92 4
335 3
101 750
86 2
750 2
15 1
90 1
76 79
15 114
114 87
76 85
114 85
15 57
88 117
91 59
99 111
114 111
59 120
111 120
78 75
76 65
106 80
78 72
37 82
68 82
116 93
99 93
*****data-kanji.txt*****
#heisignum kanji
120
119
118
117
116
115
114
113
112
111
110
109
108
#107 (boring node with in+out degree = 0)
106
#105
#104
#
#
101
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
#81
80
79
78
77
76
75
#74
73
72
71
#70
#63
48
30
#33
19
5
68
26
20
51
65
#6
15
17
#34
750
335
#50
#62
31
21
#49
40
59
18
57
37
# - algorithm design
1
2
3
4
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Conceptual Database Design An Entity Relationship Approach
Authors: Carol Batini, Stefano Ceri, Shamkant B. Navathe
1st Edition
