Introduction
代写Precedence Network，在工程改进中很常见的网络拓扑图，计算节点时间的时候比较烧脑一点。
When preparing a plan for a software development project, the project is broken down into a set of tasks (or activities) with dependencies between these tasks. The tasks and dependencies form what is called a precedence network, with the tasks represented by nodes in the network and the dependencies by directed arcs between pairs of nodes. If the duration of each task is estimated, the minimum duration for the whole software development project can be calculated from the precedence network. Some of the tasks may be able to be started later or take longer than estimated without increasing the overall duration of the project, but if other tasks are started late or take longer than estimated, they will delay the project as a whole. The tasks that will delay the project are called critical tasks, and the path through the network formed by these tasks is called the critical path.
In our modelling of a precedence network each task will be represented by a node with the attributes:
- An identifier or name (a string)
- The estimated duration of the task (an integer)
- The earliest start time - the calculated earliest time a tasks can start based on the predecessor tasks that must be completed before this task can commence (an integer)
- The latest start time - the calculated latest time a task can start without delaying the successor tasks that depend on this tasks (an integer)
- The earliest finish time - the calculated earliest start time plus the estimated duration (an integer)
- The latest finish time - the calculated latest start time plus the duration (an integer)
- The float associated with the task - the difference between the latest start time and the earliest start time, which is the maximum time available to either delay the start of the task or to spend more time on the task (an integer)
- The activity span of the task - the difference between latest start time and the earliest start time, which gives the maximum time period over which the task can be completed (an integer)
- A description of the task (a string)
In this assignment we are only going to keep track of the first seven of these attributes.
To create the precedence network you need to specify:
- The tasks (their ID’s)
- The tasks that must be completed before a task can start - the list of predecessor tasks
- The estimated duration for the task.
At least one task must not have any predecessors - a requirement for a valid precedence network. You can have more than one task without predecessors - in this case some of the algorithms for manipulating a precedence network are simplified by add in a dummy ‘starting task’ with zero duration that is then set as the predecessor of these tasks. Similarly adding a dummy ‘last task’ can simplify some algorithms for predecessor networks.
We will assume in this assignment that the precedence network has a single starting tasks (without predecessors) and a single ending node (without successors).
As an example, consider the project with the following eight tasks, associated dependencies and durations:
| Id | Predecessors | Duration |
|---|---|---|
| A | None | 8 |
| B | A | 15 |
| C | A | 30 |
| D | A | 30 |
| E | B,C | 20 |
| F | D | 10 |
| G | E,F | 10 |
| H | G | 12 |
To calculate the critical tasks, we need to calculate, for each task, the earliest start, earliest finish, latest finish, latest start, and float. This requires two passes across the network.
The first pass is from left to right (from starting task to ending task):
- For the starting task, the earliest start is set to zero. Add the duration to the earliest start to get the earliest finish.
- Then, going from left to right, the earliest start of a node is the maximum of the earliest finish values of its predecessor nodes. The earliest finish for a node is the earliest start of the node plus the duration.
The second pass is from right to left:
- For the last task, the latest finish is set to the earliest finish, the latest start is the earliest start and the float is set to zero.
- Moving from right to left, the latest finish for a task is set to the smallest latest start of the successor nodes of the task, the latest start for the task is set to the latest finish minus the duration, and the float to the difference between the latest start and earliest start.
The critical tasks are the tasks that have float of zero. Note that the first and last tasks are critical tasks, and that there is at least one path of critical tasks through the network - the critical path(s).
For the example project given above, the critical tasks are A, C, E, G and H.
This assignment is concerned with calculating the critical tasks for a precedence network. You will be given C++ classes to represent the precedence network, but you must implement the algorithms to calculate the critical tasks.
In this first assignment you are given the class structures required to implement the assignment - a design for the solution - and you must provide code to implement this design. In the next assignment you will need to design the class structures as well as implement the classes.
Representing the Precedence network
In this assignment you will represent the precedence network using two classes
class Task
This class contains information about a single task (the name, duration, earliest start, earliest finish, latest start, latest finish and float), along with a list of predecessor tasks and a list of successor tasks.
class Network
This class is an abstraction of the network as a whole, allowing tasks and precedence relationships to be added to the network, and the critical tasks to be calculated.
You are given specifications for these two classes. These class specifications have fairly extensive comments that should be considered part of the assignment specification. You need to complete and test these classes. The testing code is provided - you can use this testing code during the development of your solution to this assignment, as it provides a framework for running your solution and the testing provides feedback on errors in your solution. The testing code all marks the assignment - it produces a HTML page with feedback and a mark. You can run this marking framework as many times as you like before submitting your solution.
As a note, in the design of the Task and Network classes, some methods that shoud be hidden are made public in the class specifications to make the marking of the assignment easier. You must not change the visibility of any fields or methods of the Task or Network classes. Similarly, you must not change the signature of the methods of the two classes, as this will also create problems with the marking code. You will submit only the Task and Network classes. The assignment will be marked with original copies of the marking code, so any changes you make to the provided marking code will not be present when your assignment is marked. However, during development of your solution, you can make changes to the marking code - typically commenting out some of the calls to the marking classes - to allow you to use the marking code before you have implemented all the methods of the Task and Network classes.
The Marking Program
Your assignment will be marked automatically. The marking program that will both test and mark your assignment code will be made available to you. The program generates a web page with the results of the marking along with the details of the marking scheme. The marks for the assignment are divided equally between the classes Task and Network.
You may run the marking program as many times as you wish while developing your solution.
When the submitted assignment is marked, you will receive zero marks for code that does not compile and run.
All files for the marking program are available for download from the course web site. There is on-line documentation for the classes in the marking program and for the Network and Task classes. This documentation is generated by Doxygen from the comments embedded in the header and source files (similar to JavaDoc).
The assignment will be marked with original copies of the marking classes and the Task.h and Network.h files. The only code that you will be asked to submit are the Task.cpp and Network.cpp files, so your final submission should work with original copies of all of the remaining files. The files Task.cpp and Network.cpp already have all the #include’s that you need to get them to work.
The files provided are:
- markAssignment.cpp
This has a main() method to start the program running. This program expects as the name of the file containing your name, student ID and student email address as the only command line parameter when it runs. If you don’t provide a command line parameter, the program assumes your details are in “details.txt” in the directory from which the program runs. - The class Marking - Marking.h and Marking.cpp
This class coordinates the marking and writes the output to a file and to standard output. - The class NetworkMarks - NetworkMarks.h and NetworkMarks.cpp
This class contains the code to mark the Network class. - The class TaskMarks - TaskMarks.h and TaskMarks.cpp
This class contains the code to mark the Task class. - The class NetworkException - NetworkException.h and NetworkException.cpp
This provides an exception class that can be thrown when there is problem detected by the code in the class Network. - The class TaskException - TaskException.h and TaskException.cpp
This class provides an exception that is thrown when there is problem in the Task class. - The class TestOutput - TestOutput.h and TestOutput.cpp
This class writes to a report file and to standard output. - A small set of utility functions that are used in the classes - utils.h and utils.cpp.
- The class Task - Task.h and Task.cpp
This is one of the classes you are required to complete for the assignment by providing the body for a number of methods of the class. - The class Network - Network.h and Network.cpp
This is one of the classes you are required to complete for the assignment by providing the body for a number of methods of the class.
The assignment should be developed with a C++11 compliant compiler as it uses some C++ 11 features. The marking program should work with any C++11 compliant compiler. Your assignment will be marked with a C++11 compliant compiler.
Getting the Marking program to run
You need to be systematic in the way you add code to the Task.cpp and Network.cpp files to get the marking program to work and to finish the assignment.
- As the files Task.cpp and Network.cpp have code removed from methods, including ‘return’ statements, the first thing you should do is to add in a return statement with a return value of the correct type.
Some methods return more complicated types and you will need to work out how to return a simple value of the appropriate type to get the method working.
For some methods, such as simple ‘getter’ methods, you may be able to return the correct value at this stage (see 4. below). - Next get the constructors working. But be aware that the testing of the constructors may make use of ‘getter’ methods (see 4. below), so you may need to do some of these methods early as well.
- Move onto the copy constructor and the assignment operator.
- Next add code for ‘getter’ methods - methods that return information stored in the class. These are usually one line of code - you may have done some in steps 1 and 2 above.
- Now add in code for any ‘setter’ methods - that set the value of information stored in the class. These are often just one line of code.
- Finally start work on the more complicated methods that require you to manipulate the data in the class object. Start with the easiest ones first - for example, in the Network class, do addTask() and addDependency() before trying to do the rest.
Once you get the marking program running it should provide you with reasonable feedback about the problems it finds. You can run the marking program as many times as you like to try to get your code working.
Remember - don’t change the marking program (other than to comment out calls to some tests until you have a first cut of the code for methods being tested) as your code will be compiled and run with unchanged code for all files except for the Task.cpp and Network.cpp files that you provide.
The Details.txt file and Running your code
You need to also submit a file details.txt that contains (each on their own line) your name, your student ID and your email address. The program will read this file and use the information to customise the report it generates, and to set the name of the report. The marking report is written to a file with the name part your student ID and with extension .html.
The report file will need to have in the same directory the file containing the Uni logo and name: “ajs_clip_image001.gif”.
Depending on the development environment you are using for coding, you may need to specify the directory in which the program will run, and to ensure that the files details.txt and ajs_clip_imamge001.gif are in that directory.