a1 = true b2 = false c3 = a1 or b2the third equation defining c3 uses definitions of a1 and b2.
Your Equation code now reads lines, and parses them as:
lhs "=" (token)+where lhs is an identifier and tokens are identifiers, truth values, or boolean operators. 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 graph has 3 nodes: a1, b2 and c3, and 2 edges (a1 --> c3) and (b2 --> c3). It is implemented as an ArrayList of 3 adjacency lists, one for source a1, one for source b2, and one for source c3. The adjacency list for a1 contains c3, and the adjacency list for b2 contains c3. The inDegrees for a1 and b2 are both 0, while the inDegree for c3 is 2. Here is the DepGraph object for these three equations:
0: AdjList source: a1, inDegree: 0, destinations: [c3] 1: AdjList source: b2, inDegree: 0, destinations: [c3] 2: AdjList source: c3, 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, b2]
For example, when analyzing and topological sorting the input file with the equations given above, the following output is generated by EquationDriver:
next line: a1 = true next line: b2 = false next line: c3 = a1 or b2 Dependence Graph: 3 nodes, 2 edges 0: AdjList source: a1, inDegree: 0, destinations: [c3] 1: AdjList source: b2, inDegree: 0, destinations: [c3] 2: AdjList source: c3, inDegree: 2, destinations: [] Evaluation order of equations: [a1, b2] [c3]
Work with the following codes:
TokenIter.java, use or fix your iterator TokenIter from P4.
Driver.java is provided,
don't change this code. The 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:
// line parses a line: LHS "=" RHS
// LHS = identifier
// RHS = ( token )+
// add LHS entry to depGraph
// for all identifiers x in RHS, add edge x->LHS in graph
public void line(DepGraph depGraph) throws GraphException
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
}
Make sure you put ***java** files in your jar (not class files).