Overview
The researchers at the department of computer science have requested the development of an application software forA goal hierarchy
A goal hierarchy is a variation on the concept of AND/OR trees. An AND/OR tree is useful for representing solution of problems that can be solved by decomposing them into a set of smaller problems. An AND/OR tree is a rooted tree, where all nodes have exactly one parent node except the root. The nodes with no offspring are called leaves. Siblings can be grouped into AND groups (default) or placed in an OR group.A goal hierarchy is similar to AND/OR trees except that nodes can be influenced by other elements. These can be other nodes in the tree or the source of the influence may be anonymous. To maintain the treeness of this structure, the influences are shown as directed edges with a different color, font, or thickness. The following figure shows an example goal hierarchy.
As can be seen in the diagram, inner nodes are shown using circles, while leaf nodes are shown as boxes. Each node has a label and a description (not shown). An arc over the edges connecting a parent to its children indicates that an OR grouping of those edges. The external influences are shown using directed edges (with a red color).
The goal hierarchy is used to determine the value or level of satisficication of a goal. For example, the root goal is satisfied if both goals A1 and B1 are satisfied and one of C1 and D1 is satisfied. Furthermore, the root goal has a negative anonymous external influence with the value e2 that can affect its satisfiability. Similarly, the goal A1 is satisfied if A21 and A22 are satisfied. The goal B1 is satisfied if the leaf M3 is satisfied. The goal C1 is satisfied if both C2 and M7 are satisfied. The goal D1 is satisfied if one of M8 or D2 is satisfied and so on.
Goal evaluation
One approach to determining the satisfiability is use of binary values (e.g. true, false). In this case, the goal A21 is satisfied (or evaluates to true) if M0 is true. Similarly, the goal C2 is satisfied (or evaluates to true) if at least one of M4, M5, M6 is true. The root R is satisfied if A1 and B2 are satisfied and at least one of C1 or C1 is satisfied.The binary values are insufficient for our goal hierarchy. Instead we use values between 0 and 100. Now we can define a goal satisfied if its values has reached a level between 0 and 100 (e.g. 90).
In this application, only leaf nodes have values. These values are computed externally by querying a database. Based on the values of the leaf nodes and an associated weight for each node, we propagate these up to the root of the tree using the following mechanism.
- If a goal has only one child, which is a leaf, then its value is its child's value. For example, the value of A21 is the value of M0.
If a goal has multiple children that are grouped in an AND, then its value is the average of its children. For example, the value of A22 is the average of the values of leaf nodes M1 and M2. Similarly, the value of A1 is the average of the values of the nodes A21 and A22.If a goal has multiple children that are grouped in an AND, then its value is the weighted average of its children. In other words, each node has a weight factor associated with it. The weight factor, w is a positive integer (i.e. w > 0). For example, if the weight of M1 is w1 and the weight of M2 is w2, then the value of A22 is computed as
((M1 * w1) + (M2 * w2)) / (w1 + w2) Similarly, if the weight of A21 is w21 and the weight of A22 is w22, then the value of A1 is the weighted average of the A21 and A22 or((A21 * w21) + (A22 * w22)) / (w21 + w22) If a goal has multiple children that are grouped in an OR, then its value is the maximum of the value of its children. For example, the value of C2 is the maximum value of M4, M5, M6. Similarly, the value of D1 is the maximum value of the leaf nodes M8 and D2 (whose value is the average value of the leaf nodes M9 and M10).If a goal has multiple children that are grouped in an OR, then its value is the value of the child whose weighted value is greater than other children. For example, if the weights of M4, M5, and M6 are w4, w5, and w6 respectively, and (M4 * w4) is greater than (M5 * w5), and (M6 * w6), then the value of C2 is M4 (not M4 * w4). Similarly, if the weight of M8 is w8 and the weight of D2 is w2, then the value of D1 is the maximum weighted value of the leaf nodes M8 and D2 or the maximum of (M8 * w8), (D2 * w2). Note that the value of D2 is the weighted average value of the leaf nodes M9 and M10.
- If a goal has multiple children some of which are grouped in OR
groups and others in an AND, its value is computed as:
Computer the value of each OR group first. For example, to compute the value of R, compute the value of the OR group of C1 and D1, which is the maximum of the two. Call this value V1.Compute the value of each OR group first. For example, to compute the value of R, compute the value of the OR group of C1 and D1, which is the maximum of the value of C1 times its weight and D1 times its weight. Call this value V1.
Compute the weighted average value of last part with other nodes in the AND group. For example, to compute the value of R, we find the average of the values of A1, B1, and V1.Compute the weighted average value of last part with other nodes in the AND group. For example, to compute the value of R, we find the weighted average of the values of A1, B1, and V1.
More formally, if G1 and G2 are nodes in the goal hierarchy, and V(G1) and V(G2) represent their respective values, we have:
More formally, if G1 and G2 are nodes in the goal hierarchy, and V(G1) and V(G2) represent their respective values, and w1 and w2 are their respective weights, we have:- V (G1 AND G2 AND G3 ... AND Gn)= V(G1) + V(G2) + V(G3) + ... V(Gn) ) /n
- V (G1 OR G2 OR G3 ... OR Gm)= MAX ( V(G1),V(G2),V(G3),...,V(Gm) )
- V (G1 AND (G2 OR G3)) = AVG (V(G1), (MAX (V(G2),V(G3))))
If a goal has a positive/negative external influence, then the value of the influence is added/subtracted from the value of that goal. For example, the value of R with its influence is its value without influence minus e2. Similarly, the value of goal A1 with its influence is its value without influence plus e1. The value of goal C1 is its values plus the value of D2.
Example
In the example provided, the value of Node R is computed as:V(R) = ( V(A1) * wA1 + V(B1) * wB1 + V(C1) * wC1 ) / (wA1 + wB1 + wC1) -e2
Similarly, the value of C1 can be computed:
V(C1) = ( V(C2) * wC2 + V(M7) * wM7 ) / (wC2 + wM7) + V(D2)
And, the value of C2 is computed as:
V(C2) = V(M4)
Charting values
The values of the goals in a hierarchy change with time. As such, we need to store the values of all goals according to the date that they were computed. These values together depict a curve showing the progress of the values of a goal over time. The figure below shows the values of a goal against time (X axis).
Such a chart provides a means of monitoring the changes of a goal's value. To improve the monitoring process we use two other curves. First, we add an estimated line which is a linear projection of the value of a goal based on its value at the current time and its value at a point in the past (e.g. start time). In other words, the estimated line goes through two points: the first sample and the most recent sample. We also create an ideal curve, which depicts how we think the values will change. To draw this curve, we determine the start and the end times. We estimate the values of each goal at these times and the times in between. Connecting these values creates an ideal curve. In its simplest form, the ideal curve is a line connecting the values of a goal at the start and the end times. The figure below shows the values of the above goal plus an ideal line (green) and an estimated line (yellow).
These curves enable us to see the ideal progress in the values of a goal versus its real progress against time. The estimated determines that future value of a goal, if its value progresses as it has done so far.
Functional requirements
Textual representation
The goal hierarchy should be represented textually using XML (ideally complying to GXL). This enables a researcher to create a textual representation of a goal hierarchy that can be used by the application to render and manipulate. Similarly, as we gather values for leaf nodes, they must be stored as XML documents to be used by the application for charting and estimating as described in section "Charting values".Furthermore, if a goal hierarchy is created using the GUI component of the application, the result should be stored as an XML document. The application must be able to save a goal hierarchy as an XML document and read the same document and create the exact same goal hierarchy.Each node must be associated with a label, consisting of at most 8 characters, a description, consisting of at most 256 character, a unique identifier, a positive integer (32bits), for searching purposes, and a weight factor. Neither Labels nor descriptions need be unique. Descriptions can be null but labels must not. Furthermore, labels cannot begin with a white space. If a label beings with a white space, the leading white space must be removed.
In case of errors, if using the batch mode, the application should provide a line number and terminate the loading without applying any changes.
Graphics
Given a valid XML document representing a goal hierarchy, the application must create a visual representation of it similar to the example provided in section "A goal hierarchy". In other words, a graph where leaf nodes are drawn as boxes, inner nodes as circles, connecting edges as straight line, and external influences as directed edges. The diagram must show the label and the unique id of each node inside the circle or box. The most recent value of each node, must also be shown (with the default value of 0).If an XML document is not valid, the application must print the line number and terminate gracefully.
Goal value computation
The user can manually enter the values of each leaf node interactively. Upon entering the value of a leaf node, the application should compute the values of inner nodes. For example, in the diagram in the section "A goal hierarchy", if the user enters a value for the leaf node M0, then the application must re-compute all values of goal A21,A1, and R.The user
can similarlycreates an XML document containing all the values for the leaf nodes and direct the application to read them in batch. In this case, the diagram should be updated only after all values are re-computed. In case of batch processing, any missing values for a leaf node is to be assumed 0.External influences have a default value of 0 unless specified by the user. The values of an external influence must have identical sign to its definition, otherwise, an error occurs. The application must print the number of the last line and terminate gracefully.
Ideal curve creation
To establish an ideal curve, the user enters two dates indicating the start and end dates of monitoring. For each goal, the user can provide a set of points representing a date and a value for that particular goal representing the ideal curve. (These dates must be between the start and end dates.) These points define the ideal curve.The application must maintain the values of the ideal curve for search and query explained later. These points can be entered
interactively orusing a batch system (via an XML file). If a user does not provide an ideal curve for a goal, the application should create an ideal line between the start and end points by default.Creation of charts
Upon request by the user, the application must create a chart of values for a goal. This chart must depict the ideal curve, the real curve, and an estimated line for that goal.Drill down and query
The user can specify a tolerance level for each goal. (The default is 10 percent.) When a goal falls below its ideal curve by its tolerance level, then the user can request a search for all its children that have fallen below their ideal curve by their tolerance level. This search can recursively continue all the way to the leaf nodes (drill down).Here are a list queries that must be supported:
- A user may also request the value of a specific goal using its unique id.
- A user may request the label or description of a goal using its unique id.
- A user may request the value of goals that match a label (full match).
- A user may request a list of goals that have fallen below their ideal curves by their respective tolerance level.
Graph manipulation
The user should be able to create and edit a goal hierarchy interactively. In particular, the user should be able to create nodes, connect them together via a parent-child edge, group siblings into OR groups, or create external influences. Finally, the user can save the hierarchy as an XML document.
Non-functional requirements
Client-server architecture or web-based access
The application must be structured as a client-server. Multiple clients should be able to connect to the server, create diagrams, and compute their values. Ideally, the architecture should be web-based using the Netscape/Mozilla web browsers.Graph rendering speed
Typical goal hierarchies have between 50 and 150 nodes. As such, the speed of generating the diagram of a goal hierarchy should be no more than 10 seconds, with the average time around 5 seconds. Furthermore, the time taken to create a chart using a batch loading should be no more than 15 seconds, with the average time around 8 seconds.All the specified numbers are based on the execution of the application on ECF facility.
Resource consumption
The amount of memory available in our environment vary greatly. As such, the amount of memory consumption should be restricted to the default values provided by Java Virtual Machine.Programming languages and other supports
Due to diversity of platforms, the application must be implemented using Java. XML (and ideally GXL) are to be used for textual representations.Maintainability, understandability, and modifiability
Upon completion of your project, all project documents and source codes must be delivered for evaluation. An acceptance criteria is ease of evolving your applications. As such, your application must comply with following criteria:- No method should exceed 200 lines
including commentsexcluding comments (using wc -l). - The class hierarchy should have a depth less than or equal to 5 levels.
- Names of classes and packages must be English words. Names that have more than one word, should be catenated using the underscore character.
The McCabe complexity of each method must be less than or equal to 20. The average McCabe complexity of methods in a class should less than or equal to 20.- All documentation must be created using JavaDoc.
- All public methods must have a brief description as what they do and what their assumptions are (if any).
- No method should exceed 200 lines
Resources
XML and related technologies
For XML related technologies, visit www.w3.org. For a description of GXL, visit www.gupro.de/GXL.Java and related technologies
For information on Java, visit java.sun.com and java.sun.com/products/servlet.Frequently asked questions
Post your questions on the course newsgroup. Responses will be posted on course web page