代写program、代写R编程设计

日期：2023-05-05 10:42

[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> GetSteps (int uin,

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<std::string>&

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<std::string>{ "128", "173" }) 6

CountGroups(std::vector<std::string>{ "128", "124", "173" }) 3

*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