代写CS 128 | [MP11] Illini Book
- 首页 >> Algorithm 算法[MP11] Illini Book
Grading
Your [MP] Illini Book score is Checkpoint + Due Date = max 100 pts
— If you do not submit anything by the initial checkpoint deadline, the most you can get on this assignment is
90%.
Checkpoint I (10 pts)
You must submit by 23:59 Champaign local time on Tuesday, Apr. 25, and score at least 10% to earn full
10 points.
If you do not score at least 10% before this deadline, you will receive 0 points.
You will submit to Illini Book - Checkpoint for this 10 points.
WARNING You are alloted 20 penalty-free checkpoint submission attempts, which will expire after
checkpoint deadline.
Due Date (90 pts)
You must pass ALL test cases correctly to earn full 90 pts.
If your code does not pass all of our test cases, these 90 pts will be prorated → 90 pts * (% what you
earned / 100%).
WARNING You are alloted 20 penalty-free deadline submission attempts. Additional attempts are
available with 5 point penalty per submission (cumulative) until available credit reaches 0.
Submission Limit Is Imposed! WARNING
Submission limit is imposed for this MP following the schema speci?ed above (same as last week's).
We do not count submissions that did not compile as a submission.
After using up 20 penalty-free deadline submission attempts, you will be able to submit additional times,
but with 5 points deduction per submission attempt (meaning the available credit goes 85, 80, 75, ... 15,
This assignment is due Thursday, April 27, 2023 at 23:59 CDT. See the syllabus for our late policy.
Howdy, Yiwei!
CS 128 | [MP11] Illini Book
1 of 8
10, 5, 0).
If you start early and utilize both checkpoint allotments and deadline allotments..
Extra credit deadline
You must submit by 23:59 Champaign local time on Wednesday, Apr. 26, and score 100% on the entire
assignment to earn 5% extra credit for a total of 105%. You are not eligible for this if you missed the
checkpoint.
Please review the syllabus for more information about this opportunity.
Background
A young entrepreneur in your RHET 105 class has approached you with an idea that they claim is “the next big
thing!” Since you are a rockstar CS 128 student, you’ve been tasked with building IlliniBook—a way to ?nd and
connect with fellow Illini based on shared interests.
The app should not only know who is connected to whom, but also how they are connected. When two people
are directly connected, they have a label on their relationship, represented by a std::string. This relationship
can be a club, activity, class, job, etc.
You don’t want to deal with fancy things like “databases” and “the cloud” just yet, so all users have their
information stored in two di?erent .csv ?les.
After processing peoples’ pro?les, you’ll need to be able to check if two people are related (directly and
indirectly) and check if two people are related through a speci?c relationship type. You should also be able to
and the number of groups in your social network!
The Illini Book Constructor
In the IlliniBook Constructor, you are supposed to read from two CSV ?les:
The ?rst CSV ?le provides a list of UINs as integer values:
1 UIN (int)
2 UIN_1
3 UIN_2
4 ...
5 UIN_N
The second CSV ?le provides a list of relationships in a format that looks like this:
1 UIN_A,UIN_B,Relationship (int, int, std::string)
2 UIN_A_1,UIN_B_1,Work
3 UIN_A_2,UIN_B_2,Sports
4 ...
5 UIN_A_N,UIN_B_N,relation_N
For emphasis, the UINs are signed integer values (including 0).
Note: we will not include headers in the csv ?le. Please see the example section of this writeup for more
example.
Howdy, Yiwei!
CS 128 | [MP11] Illini Book
2 of 8
With the paths to these ?les provided to your constructor, construct an IlliniBook class that implements the
functions outlined in the following section. How you store this information is completely up to you.
Assignment
Your job is to implement the functions in the table below. Make sure the functions follow the speci?cations
listed.
Each node represents a single person (with the unique uin). Each edge represents a single relationship. If you
are asked to return node/nodes, then you are actually asked to return UIN/UINs.
Function Speci?cation
Public:
IlliniBook(const std::string&
people_fpath, const std::string&
relations_fpath)
Constructor (see above)
IlliniBook(const IlliniBook& rhs) Deleted
IlliniBook& operator=(const
IlliniBook& rhs)
Deleted
~IlliniBook() Destructor
Depending on your design choices, either mark it as default or
provide implementation.
bool AreRelated(int uin_1, int
uin_2) const
Returns true if and only if there exists a path between node uin_1
and node uin_2 (i.e. there exists direct or indirect relationships
between 2 people connected by any activity).
bool AreRelated(int uin_1, int
uin_2, const std::string&
relationship) const
Returns true if and only if there exists a path between node uin_1
and node uin_2 where all edges in the path are relationship (i.e.
there exists direct or indirect relationships between 2 people
connected by the speci?ed relationship).
int GetRelated(int uin_1, int uin_2)
const
Returns the length* of the shortest path between node uin_1 and
node uin_2 (i.e. shortest length between person1 and person2) if
such path exists; otherwise, return -1.
int GetRelated (int uin_1, int
uin_2, const std::string&
relationship)
Returns the length* of the shortest path between node with uin_1
and node with uin_2 where all edges in the path are relationship
(i.e. shortest length between person1 and person2 for the only
given relationship) if such path exists; otherwise, return -1.
std::vector
int n) const
Returns a vector of all UINs that have a shortest path of n from the
given uin. Ensure that you do not have any duplicate elements in
Howdy, Yiwei!
CS 128 | [MP11] Illini Book
3 of 8
Function Speci?cation
this vector..
size_t CountGroups () const Return the number of connected components in the graph (i.e. the
number of groups who are connected by ANY activity).
size_t CountGroups(const
std::string& relationship) const
Return the number of connected components in the graph after
edges in the graph are ?ltered: only consider edges relationship.
size_t CountGroups(const
std::vector
relationships) const
Return the number of connected components in the graph after
edges in the graph are ?ltered: only consider edges in
relationships.
* The "length from A to B" is equivalent to the "distance travelled", and is de?ned as the number of edges
traversed to get to B from A.
Assumptions
For the purposes of this MP, you can assume the following about CSVs:
All UINs in the ?rst CSV are unique
All pairs of UINs in the second CSV are unique
All UINs in the second CSV are contained in the ?rst CSV
Any person will never relationed to themselves.
There is at most one relationship between two people. (e.g. the second CSV ?le won’t claim that Person A
and Person B are connected by both Basketball and CS128.)
All relationships are symmetric (e.g. if A is related to B by relationship R, then B is also related to A by R.)
You can assume the following about parameters:
people_fpath and relations_fpath are valid
uin_1 != uin_2
uin, uin_1, uin_2 are contained in the ?rst csv
There are no duplicate elements in relationships
n >= 1
relationships.size() >= 1
You CANNOT assume the following:
relationship or elements in relationships are contained in the second csv (relation csv)
If a relationship is not contained in the second csv, you should ignore it.
Example
Consider the following input:
persons.csv
1 1
Howdy, Yiwei!
CS 128 | [MP11] Illini Book
Here is the corresponding graph where the value on the node is the corresponding UIN and the value on the
edge is the corresponding relationship.
Howdy, Yiwei!
CS 128 | [MP11] Illini Book
5 of 8
Invocation Return
AreRelated(1, 2) true
AreRelated(3, 2) true
AreRelated(1, 9) false
AreRelated(1, 2, "128") true
AreRelated(1, 2, "124") false
AreRelated(1, 6, "128") true
AreRelated(1, 6, "124") true
GetRelated(1, 2) 1
GetRelated(3, 2) 2
GetRelated(1, 9) -1
GetRelated(1, 2, "128") 1
GetRelated(1, 2, "124") -1
GetRelated(1, 6, "128") 2
GetRelated(1, 6, "124") 1
GetSteps(1, 1) { 2, 3, 6 }
GetSteps(1, 2) { 7, 8 }
GetSteps(1, 3) { }
GetSteps(9, 1) { }
CountGroups() 3
CountGroups("128") 6
CountGroups("124") 6
CountGroups("173") 10
CountGroups(std::vector
CountGroups(std::vector
*Order does not matter
Constraints
Member variables: There are no required member variables for the IlliniBook, but you are encouraged to
add member variables in IlliniBook (e.g. for the purpose of store graph representation).
Compilation ?ags: Your program must compile without warnings/errors when compiled with: clang++
using the -std=c++20 and the following ?ags -Wall -Wextra -Werror -pedantic
Allowed headers: Only the following header ?les are allowed to be #included in your solution ?les
*
*
Howdy, Yiwei!
CS 128 | [MP11] Illini Book
6 of 8
"illini_book.hpp" "utilities.hpp" "fstream" "list" "map" "queue" "set" "string" "utility"
"vector"
Autograder Tests
Memory Tests
Since the decision of how to implement this is completely up to you (including which library/data structure to
use, etc), memory test points are not awarded if you pass the memory tests. However, you will get penalized
for not passing memory tests.
i.e.
If you decide to not use free store anywhere in your code, or if you use free store but has no memory
issues, memory leak tests have no e?ect on your grade (0 out of 0 awarded).
If you decide to use free store and your code causes memory leaks, you will get penalized (0 out of ~insert
positive number~ awarded).
Clang-Tidy Checks
For this MP, we are implementing the same policy for clang-tidy as memory checks. There is no point value for
passing. However, you will get penalized for not passing the test.
Tips
Compiling
A completed Makefile is not provided to you. You may want to create one.
"Unable to write" error? If you are writing to a ?le in a folder (for example, obj/hello.o), that folder needs to
exist in the ?rst place (in this example obj folder). Clang will not create a ?le recursively.
Debugging
To use the debugger,
you'll need to create a folder bin (if it does not already exist) in the project root, and
compile the executable to the bin folder with the name exec.
If you end up using a std::map, use the GDB instead of the LLDB to debug your code. LLDB has issues with
debugging code that uses maps, so if you elect to use them in your implementation do not use LLDB.
Traversing the Graph Based on Relationships
You may notice that there are several functions that accept a std::string relationship. The way you would
want to go about this is to imagine a sub-graph of sorts where the only relationship between two people can
be the input std::string argument. We suggest you use a graph to store data where each node represents
one person and each edge represents a relationship.
For instance, in the given graph:
Howdy, Yiwei!
CS 128 | [MP11] Illini Book
7 of 8
If a function is passed "relationship2", then for all practical purposes within the function:
Person0 and Person2 are connected
Person0 and Person1 are not connected
Person1 and Person2 are not connected
For functions that do not have std::string relationship listed as an argument:
Person0 and Person2 are connected
Person0 and Person1 are connected
Person1 and Person2 are connected
Big Hint
You will want to take advantage of a breadth-rst search in this assignment. In addition, I would encourage
you to consider using std::queue to help implement that traversal. Finally, you can record the nodes you've
visited in an std::set; see the insert and contains behaviors.
Howdy, Yiwei!
CS 128 | [MP11] Illini Book
8 of 8