a=12 b=23 c=a*a+bthe third equation defining c uses a and b.
Your Equation code reads lines, and parses them as:
lhs "=" (token)+where lhs is an identifier and tokens are identifiers, numbers, or operators, as in P4. A dependence graph, a DepGraph object, contains an ArrayList of adjacency lists, AdjList objects. An AdjList contains a source, an inDegree, and an ArrayList of destinations.
For each identifier x in the right hand side, an edge x --> lhs is created in the dependence graph. So, for the 3 equations above the dependence has 3 nodes: a, b and c, and 2 edges (a --> c) and (b --> c). It is implemented as an ArrayList of 3 adjacency lists, one for source a, one for source b, and one for source c. The adjacency list for a contains c, and the adjacency list for b contains c. The inDegrees for a and b are both 0, while the inDegree for c is 2. Here is the DepGraph object for these three equations:
0: AdjList source: a, inDegree: 0, destinations: [c] 1: AdjList source: b, inDegree: 0, destinations: [c] 2: AdjList source: c, inDegree: 2, destinations: []
After the input lines have been read, and the dependence graph has been created, the order of evaluation of the equations will be determined by a topological sort method, topoPrint(), in DepGraph. The topoPrint method implements the forward topological sort method, described in the Graph 2 lecture nodes. It is based on inDegrees, and prints lines containing all left hand sides of the equations that can be evaluated, ***in the order that the left hand sides were defined*** and thus entered into the dependence graph.
For each line, the identifiers are to be printed as an ArrayList of Strings: e.g. [a1, bbc]
For example, when analyzing and topological sorting this input file, the following output is generated (by EquationDriver, see below):
next line: m = 1*2 next line: h = m*m + 15 next line: r = h*2 next line: s = (m-r)*(m+r) next line: b = 5000 next line: n = b-h next line: Dependence Graph: 6 nodes, 6 edges 0: AdjList source: m, inDegree: 0, destinations: [h, s] 1: AdjList source: h, inDegree: 1, destinations: [r, n] 2: AdjList source: r, inDegree: 1, destinations: [s] 3: AdjList source: s, inDegree: 2, destinations: [] 4: AdjList source: b, inDegree: 0, destinations: [n] 5: AdjList source: n, inDegree: 2, destinations: [] Evaluation order of equations: [m, b] [h] [r, n] [s]
Work with the following codes:
TokenIter.java, use or fix your iterator TokenIter from P4.
EquationDriver.java is provided,
don't change this code. The equation driver initializes the dependence graph,
and repeatedly reads lines from a file, creates a TokenIterator and a next Equation, and calls the line
method of the Equation class. After all input lines have been read, EquationDriver calls the topoPrint method
in DepGraph, which topologically sorts and prints the evaluation order of the equations.
Equation.java replaces Equation from P4.
The line method in equation must now, for each identifier x in the right hand side expression, add
an edge x --> lhs in the dependence graph.
DepGraph.java, GraphException.java and AdjList.java are used for the dependence graph.
Start from the code you worked on in recitation R11. Your
main job is to implement the topoPrint method in DepGraph:
public void topoPrint() throws GraphException{
// copy all inDegrees to temporary inDegrees, as these will be decremented to zero
// repeat
// 1. find sources with temporary inDegree 0 (making sure only new ones are found, see step 3)
// 2. print these on one line in definition order in format [SOURCE1, SOURCE2, ... , SOURCEn]
// 3. decrement the temporary inDegree of all successors of the sources found above
}
Use the Checkin webserver to exercise and submit your code. Submit a P5.jar file containing TokenIter.java, DepGraph.java, AdjList.java, Equation.java **ONLY**.
Make sure you put ***java** files in your jar (not class files).