讲解 ECS34、C++编程设计辅导
ECS34 WQ24 February 17, 2024
Project 4
1 of 9
Project 4
Due March 11, 2024 at 9:00 PM
You will be working with a partner for this project. This specification is subject to change at any
time for additional clarification.
Desired Outcomes
• Exposure to GoogleTest and Google Mock
• Exposure to Expat XML library
• Exposure to Open Street Map file formats
• Use of git repository
• Exposure to documenting code in Markdown
• An understanding of how to develop Makefiles that build and execute unit tests
• An understanding of delimiter-separated-value files
• An understanding of XML files
• An understanding of Dijkstra’s Algorithm
• An understanding of how to integrate a third-party C library in C++
Project Description
Navigation is a critical to modern society. Once source and destination coordinates are translated
to vertices, the shortest or fastest path can be calculated to route the user to their destination. The
goal of your project is to write a program that will be able to parse an OpenStreetMap (OSM) file
for an area and then to find shortest/fastest routes as fast as possible. Additionally, the goal is to
include multiple methods of transportation (biking vs walking and bus) in your search for fastest
routes. You will be building a program that can find paths, print and save them. You will be
building upon the classes from project 3. Some of the capabilities are extra credit, see the extra
credit section to determine what is required, and what is extra credit.
The CBusSystemIndexer class you will be developing will index the CBusSystem
information provided for ease of lookup of stops and routes. It will be helpful class in developing
some of the later components of the project.
// CBusSystemIndexer member functions
// Constructor for the Bus System Indexer
CBusSystemIndexer(std::shared_ptr bussystem);
// Destructor for the Bus System Indexer
~CBusSystemIndexer();
// Returns the number of stops in the CBusSystem being indexed
std::size_t StopCount() const noexcept;
// Returns the number of routes in the CBusSystem being indexed
std::size_t RouteCount() const noexcept;
ECS34 WQ24 February 17, 2024
Project 4
2 of 9
// Returns the SStop specified by the index where the stops are sorted by
// their ID, nullptr is returned if index is greater than equal to
// StopCount()
std::shared_ptr SortedStopByIndex(std::size_t index) const noexcept;
// Returns the SRoute specified by the index where the routes are sorted by
// their Name, nullptr is returned if index is greater than equal to
// RouteCount()
std::shared_ptr SortedRouteByIndex(std::size_t index) const noexcept;
// Returns the SStop associated with the specified node ID, nullptr is
// returned if no SStop associated with the node ID exists
std::shared_ptr StopByNodeID(TNodeID id) const noexcept;
// Returns true if at least one route exists between the stops at the src and
// dest node IDs. All routes that have a route segment between the stops at
// the src and dest nodes will be placed in routes unordered set.
bool RoutesByNodeIDs(TNodeID src, TNodeID dest,
std::unordered_set > &routes) const noexcept;
// Returns true if at least one route exists between the stops at the src and
// dest node IDs.
bool RouteBetweenNodeIDs(TNodeID src, TNodeID dest) const noexcept;
The CDijkstraPathRouter class you will be developing will implement the
CPathRouter abstract interface. The CDijkstraPathRouter class will find the shortest
path between source and destination vertices if one exists. At the core the shortest path finding
algorithm must utilize Dijkstra’s Algorithm, though you may optimize where available. The vertex
IDs do not have to match the node or stop IDs used by the other classes. You will need to write a
test program for the CDijkstraPathRouter.
// CDijkstraPathRouter member functions
// Constructor for the Dijkstra Path Router
CDijkstraPathRouter();
// Destructor for the Dijkstra Path Router
~CDijkstraPathRouter();
// Returns the number of vertices in the path router
std::size_t VertexCount() const noexcept;
// Adds a vertex with the tag provided. The tag can be of any type.
TVertexID AddVertex(std::any tag) noexcept;
// Gets the tag of the vertex specified by id if id is in the path router.
// A std::any() is returned if id is not a valid vertex ID.
std::any GetVertexTag(TVertexID id) const noexcept;
// Adds an edge between src and dest vertices with a weight of weight. If
// bidir is set to true an additional edge between dest and src is added. If
// src or dest nodes do not exist, or if the weight is negative the AddEdge
// will return false, otherwise it returns true.
bool AddEdge(TVertexID src, TVertexID dest, double weight, bool bidir =
false) noexcept;
ECS34 WQ24 February 17, 2024
Project 4
3 of 9
// Allows the path router to do any desired precomputation up to the deadline
bool Precompute(std::chrono::steady_clock::time_point deadline) noexcept;
// Returns the path distance of the path from src to dest, and fills out path
// with vertices. If no path exists NoPathExists is returned.
double FindShortestPath(TVertexID src, TVertexID dest, std::vector
&path) noexcept;
The CDijkstraTransportationPlanner class you will be developing will implement
the CTransportationPlanner abstract interface. You will build upon the street map, bus
system, bus system indexer, and path router to implement the transportation planner. The
configuration of the transportation system will be provided as a parameter to the constructor.
// CDijkstraTransportationPlanner member functions
// Constructor for the Dijkstra Transportation Planner
CDijkstraTransportationPlanner(std::shared_ptr config);
// Destructor for the Dijkstra Transportation Planner
~CDijkstraTransportationPlanner();
// Returns the number of nodes in the street map
std::size_t NodeCount() const noexcept override;
// Returns the street map node specified by index if index is less than the
// NodeCount(). nullptr is returned if index is greater than or equal to
// NodeCount(). The nodes are sorted by Node ID.
std::shared_ptr SortedNodeByIndex(std::size_t index) const
noexcept override;
// Returns the distance in miles between the src and dest nodes of the
// shortest path if one exists. NoPathExists is returned if no path exists.
// The nodes of the shortest path are filled in the path parameter.
double FindShortestPath(TNodeID src, TNodeID dest, std::vector< TNodeID >
&path) override;
// Returns the time in hours for the fastest path between the src and dest
// nodes of the if one exists. NoPathExists is returned if no path exists.
// The transportation mode and nodes of the fastest path are filled in the
// path parameter.
double FindFastestPath(TNodeID src, TNodeID dest, std::vector< TTripStep >
&path) override;
// Returns true if the path description is created. Takes the trip steps path
// and converts it into a human readable set of steps.
bool GetPathDescription(const std::vector< TTripStep > &path, std::vector<
std::string > &desc) const override;
ECS34 WQ24 February 17, 2024
Project 4
4 of 9
The CTransportationPlannerCommandLine class you will be developing will
implement the command line interface for the transplanner program. The transplanner
program is a command line program that will take in commands and execute what is requested.
// CTransportationPlannerCommandLine member functions
// Constructor for the Transportation Planner Command Line
CTransportationPlannerCommandLine(std::shared_ptr cmdsrc,
std::shared_ptr outsink,
std::shared_ptr errsink,
std::shared_ptr results,
std::shared_ptr planner);
// Destructor for the Transportation Planner Command Line
~CTransportationPlannerCommandLine();
// Processes the commands input to the
bool ProcessCommands();
An example CSV and OSM file set will be provided, the files will be used in project 4. Your tests
should be built with them in mind, but you shouldn’t load the files as part of the tests.
The Makefile you develop needs to implement the following:
• Must create obj directory for object files (if doesn’t exist)
• Must create bin directory for binary files (if doesn’t exist)
• Must compile cpp files using C++17
• Must link string utils and string utils tests object files to make teststrutils executable
• Must link StringDataSource and StringDataSourceTest object files to make
teststrdatasource executable
• Must link FileDataSource, FileDataSink, FileDataFactory and
FileDataSSTest object files to make testfiledatass executable
• Must link StringDataSink and StringDataSinkTest object files to make
teststrdatasink executable
• Must link DSV reader/writer and DSV tests object files to make testdsv executable
• Must link XML reader/writer and XML tests object files to make testxml executable
• Must link KMLWriter and KMLTest object files to make testkml executable
• Must link CSVBusSystem and CSVBusSystem tests object files to make testcsvbs
executable
• Must link OpenStreetMap and OpenStreetMap tests object files to make testosm
executable
• Must link DijkstraPathRouter and DijkstraPathRouter tests object files to
make testdpr executable
• Must link BusSystemIndexer and CSVBusSystemIndexerTest object files to
make testcsvbsi executable
• Must link TransportationPlannerCommandLine and TPCommandLineTest
object files to make testtpcl executable
ECS34 WQ24 February 17, 2024
Project 4
5 of 9
• Must link CSVOSMTransportationPlannerTest,
DijkstraTransportationPlanner and other required object files to make
testtp executable
• Must execute the teststrutils, teststrdatasource, teststrdatasink,
testfiledatass, testdsv, testxml, testcsvbs, testosm, testdpr,
testcsvbsi, testtp, and testtpcl test executables
• Must build the transplanner and speedtest executables once all tests pass
• Must provide a clean that will remove the obj and bin directories
Provided Helper Classes/Tests
• FileDataSource, FileDataSink, and FileDataFactory provide classes for
accessing files/directories as sources/sinks
• StandardDataSource, StandardDataSink, and StandardDataErrorSink
provide classes for accessing standard I/O as sources/sinks
• STransportationPlannerConfig provides a basic implementation for the
configuration interface with the default assumptions
• GeographicUtils provides static methods for calculating distance, bearings, etc. and
will be necessary for calculating the shortest/fastest paths
• KMLWriter and kmlout files provide a class and program that can convert saved paths
into KML files that can be used on google maps
• CSVBusSystemIndexterTest, CSVOSMTransporationPlannerTest,
FileDataSSTest, and TPCommandLineTest provide google tests for much of what
you need to develop
Important Assumptions
• For shortest path assume only follow direction specified in the street map, so you can't go
backward along a "oneway"
• For fastest path, assume can walk both directions regardless of "oneway", bike/bus must
follow "oneway". Also, you cannot bike along paths that specify "bicycle" as "no"
• Assume busses route will take shortest path (don't worry about calculating fastest path)
• Walk speed must be taken from config WalkSpeed function (default is 3mph)
• Bike speed must be taken from config BikeSpeed function (default is 8mph)
• Bus follows speed limit and DefaultSpeedLimit function will provide the assumed
speed limit if the way does not specify it (default is 25 mph)
• You cannot take your bike on the bus, so if you take the bus you must walk to it
• When creating the path description:
o The direction must be based upon beginning point on a street to the end point of
travelling on the street, not the beginning point and the next point
o The direction is listed as along if the street name is known, and toward if the street
name is not known, but the next street is known
o When there are multiple options for taking a bus, the bus that will go the furthest
will be taken. If multiple options are available, the bus with the earliest sorted name
will be taken
ECS34 WQ24 February 17, 2024
Project 4
6 of 9
You must have a docs directory that contains Markdown (.md) files that document the
CPathRouter, CDijkstraPathRouter, CTransportationPlanner,
CDijkstraTransportationPlanner, and
CTransportationPlannerCommandLine classes and their use. The documentation of
each class and function should be consistent. Code examples are excellent for documenting the
use of the developed classes.
You can unzip the given tgz file with utilities on your local machine, or if you upload the file to
the CSIF, you can unzip it with the command:
tar -xzvf proj4given.tgz
You must submit the source file(s), your Makefile, README file, and .git directory in a tgz
archive. Do a make clean prior to zipping up your files so the size will be smaller. You can tar
gzip a directory with the command:
tar -zcvf archive-name.tgz directory-name
A working example can be found on the CSIF in /home/cjnitta/ecs34/transplanner.
Your program is expected to have the same interface as the working example. The full interface
can be listed by typing help after launching the program. A program that can convert saved paths
into KML files has also been provided /home/cjnitta/ecs34/kmlout. Directions of how
to view a KML file in google maps can be found at https://youtu.be/1HqQuHeGa38.
You should avoid using existing source code as a primer that is currently available on the Internet.
You must specify in your readme file any sources of code that you have viewed to help you
complete this project. All class projects will be submitted to MOSS to determine if students have
excessively collaborated. Excessive collaboration, or failure to list external code sources will result
in the matter being referred to Student Judicial Affairs.
Recommended Approach
The recommended approach is as follows:
1. Create a git repository and add your project 3 and provided files.
2. Update your project 3 Makefile to meet the specified requirements. The order of the tests
to be run should the teststrutils, teststrdatasource, teststrdatasink,
testfiledatass, testdsv, testxml, testcsvbs, testosm, testdpr,
testcsvbsi, testtp, and testcl
3. Verify that your string utils, string data source, string data sink, file data source/sink, DSV
reader, DSV writer, XML reader, XML writer, CSV Bus System, OSM, KML writer, tests
all compile, run and pass.
4. Create the files and skeleton functions for BusSystemIndexer.cpp, DijkstraPathRouter.cpp,
DijkstraPathRouterTest.cpp, DijkstraTransportationPlanner.cpp,
TransportationPlannerCommandLine.cpp and transplanner.cpp.
ECS34 WQ24 February 17, 2024
Project 4
7 of 9
5. Write tests for the CDijkstraPathRouter class. Each test you write should fail, make
sure to have sufficient coverage of the possible data input. This will complete the test files
as others will be provided for you.
6. Once tests have been written that fail with the initial skeleton functions, begin writing your
CBusSystemIndexer functions. It should be noted that since the
CBusSystemIndexer, CDijkstraPathRouter, and
CTransportationPlannerCommandLine classes do not rely on one another for
testing, they could potentially be done in any order.
7. Once the CBusSystemIndexer class is complete, begin writing your
CDijkstraPathRouter functions.
8. Once the CDijkstraPathRouter class is complete, begin writing your
CDijkstraTransportationPlanner functions.
NOTE: the GetPathDescription function is extra credit!
9. Once the CDijkstraTransportationPlanner class is complete, begin writing
your CTransportationPlannerCommandLine functions.
10. Once the CTransportationPlannerCommandLine and
CDijkstraTransportationPlanner classes are complete, begin writing the
transplanner program. There will be requirement to parse the command arguments
but setting up of the config to create the CTransportationPlannerCommandLine
is mainly what is needed.
Grading
The point breakdown can be seen in the table below. Make sure your code compiles on the CSIF
as that is where it is expected to run. You will make an interactive grading appointment to have
your assignment graded. You must have a working webcam for the interactive grading
appointment. Project submissions received 24hr prior to the due date/time will received 10% extra
credit. The extra credit bonus will drop off at a rate of 0.5% per hour after that, with no additional
credit being received for submissions within 4hr of the due date/time.
Points Description
10 Has git repository with appropriate number of commits
5 Has Makefile and submission compiles
5 Makefile meets specified requirements
5 Has DijkstraPathRouter google tests that fail with initial skeleton
functions
5 Student DijkstraPathRouter google tests have reasonable coverage
5 Google tests detect errors in instructor buggy code
5 BusSystemIndexer functions pass all tests
5 DijkstraPathRouter pass all student tests
5 DijkstraPathRouter pass all instructor tests
5 DijkstraTransportationPlanner pass all tests (except path description)
5 TransportationPlannerCommandLine pass all tests
5 transplanner fully functional (except print)
5 speedtest fully functional and performs at least at baseline speed
ECS34 WQ24 February 17, 2024
Project 4
8 of 9
10 Code is properly commented with consistent conventions
10 Documentation of classes is consistent and complete
10 Student understands all code they have provided
Extra Credit
There are two opportunities for extra credit on Project 4: Path Description and Speed Performance.
(Up to 25% extra) Path Description
Successfully implement the GetPathDescription function of the
CDijkstraTransportationPlanner class. Must pass all tests, and transplanner
must print the path as the provided version does for the same input.
(Up to 25% extra) Speed Performance
The speed test will test the speed of your CDijkstraTransportationPlanner against the
baseline code. The idea is that your program would be part of a server that would be rebooted daily
and then would handle as many queries as possible. The more queries your program can handle in
a day, the fewer servers that would need to be in operation to handle the daily load. Your program
will have a maximum of 30s to load the data and do any precomputation necessary to start handling
the requests.
A speedtest program has been provide for the baseline (speedtest_baseline) and the
optimized version (speedtest_optimized). The program will output the number of queries
that could be completed in 24hr, it will also output a brief of the path distances/times. A
speedtest.cpp source file that will calculate the number of queries has been provided. Do not
modify the speedtest.cpp when constructing your speedtest program. A verbose listing
of the paths can be created with the --verbose option. Speed comparisons will be done with
compiler optimizations disabled. If your implementation outperforms the baseline
speedtest_baseline, some extra credit will be available. The goal for full extra credit is to
outperform the speedtest_optimized.
Helpful Hints
• Read through the guides that are provided on Canvas
• See http://www.cplusplus.com/reference/, it is a good reference for C++ built in functions
and classes
• Use lenth(), substr(), etc. from the string class whenever possible.
• If the build fails, there will likely be errors, scroll back up to the first error and start from
there.
• You may find the following line helpful for debugging your code:
std::cout<<__FILE__<<" @ line: "<<__LINE__<It will output the line string "FILE @ line: X" where FILE is the source filename and
X is the line number the code is on. You can copy and paste it in multiple places and it will
output that particular line number when it is on it.
ECS34 WQ24 February 17, 2024
Project 4
9 of 9
• Make sure to use a tab and not spaces with the Makefile commands for the target
• make will not warn about undefined variables by default, you may find the
--warn-undefined-variables option very helpful
• The debug option for make can clarify which targets need to be built, and which are not.
The basic debugging can be turned on with the --debug=b option. All debugging can be
turned on with the --debug=a option.
• Make sure to use a.gitignore file to ignore your object files, and output binaries.
• Do not wait to the end to merge with you partner. You should merge your work together
on a somewhat regular basis (or better yet pair program).
• Use CStringDataSource and CStringDataSink to test your reader and writer
classes for DSV and XML.
• You will probably want to use static functions in your classes for the callbacks to the library
calls that require callbacks. The call data (void *) parameter that the functions take and
the callbacks pass back as a parameter, should be this from your object.
• You may find https://www.xml.com/pub/1999/09/expat/index.html helpful for describing
the libexpat functions. You are not going to need to use every function in the Expat library.
• The OSM XML file format is described https://wiki.openstreetmap.org/wiki/OSM_XML.
Though not necessarily important for this project, the tag features are described are
https://wiki.openstreetmap.org/wiki/Map_features.
• Use the --gtest_output=xml:filename to create test results files that can be used
to prevent rerunning tests that have already succeeded.
• Use the --gtest_filter=-Test.Subtest1:Test.Subtest2 to skip google
tests that won’t pass. This can be helpful for skipping say the
CSVOSMTransporationPlanner.PathDescription test that is extra credit.