Thank you for your help with my project! It is much appreciated!

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. You'll also 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:

Tab separated.

# prefixes comment lines.

Lines look like , e.g., 120 , which indicates that character1 can be represented as the number characterID1. IDs are just

integers.

-data-components.txt (ASCII formatted) stores edges:

Tab separated.

# prefixes comment lines

Lines look like , e.g., 92 73, which indicates that character1 is a component of character2.

In terms of programming, you will need to:

-Create a new class called BetterDiGraph that implements the EditableDiGraph interface. See the interface file for details.

-Create a new class called IntuitiveTopological that implements the TopologicalSort interface.

Use BetterDiGraph to store the graph.

-Instead of using DFS to find a topological sort, implement the following algorithm: "IntuitiveTopological". This algorithm works as follows: look at your graph, pick out a node with in-degree zero, add it to the topological ordering, and remove it from the graph. This process repeats until the graph is empty.

-Make sure to check for cycles before trying to generate a topological sort of the graph!

-Complete the main method in BaseMain.java. It should:

-Load data-kanji.txt, use it to populate a hashtable that maps IDs to characters, and add the IDs as nodes in the graph.

-Load data-components.txt, and use it to add edges to the graph being built.

-Create an IntuitiveTopological object, and use it to sort the graph.

-Display the characters in the ordering. Note that topological sort will produce a list of a IDs - you'll need to take the IDs and uses them to look up the correct character in the hashtable you populated earlier.

-Add support for visualizing the graph that you generate. Most likely this will take the form of using a graph library such as GraphViz to render an image for the data you load. An example might look like the image attached below. You shouldnt have to import anything other than java.util.LinkedList, java.util.HashMap, java.util.NoSuchElementException, java.io.*, or whatever you use for the graph (GraphViz, etc.)

There is a sample output attached below also that contains the characters in the default order from the file, and the order resulting from a topological sort. Note that your

topological sort may be in a slightly different order than is shown below. The key is that simpler characters are shown before the more complicated characters that are

built from them.

Supplied 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

un: original: W+? Sorted: +-,, BUILD SUCCESSFUL (total time: 0 seconds)