logo CodeStepByStep logo


Language/Type: C++ graphs collections
Related Links:
Author: Marty Stepp (on 2016/06/16)

Write a function named popular that accepts a reference to a BasicGraph as a parameter and returns a Set of pointers to all vertexes in that graph that are "popular" by the following definition. Suppose that the graph represents users on a social network such as Facebook. A vertex represents a user, and a directed edge from A to B represents the fact that user A "likes" user B, or is "friends" with B. The weight of the edge represents how much A "likes" B.

A user v is "popular" if all of the following conditions are met:

  • At least 2 other users "like" v.
  • More users "like" v than v "likes" other users. (More arrows are coming in than going out.)
  • The combined weight of all "likes" toward v is more than the combined outbound weight of all the edges to other users that v "likes". (More total edge weight is coming in than going out.)

For example, in the graph below, vertex B is "popular" because vertexes A, C, and E "like" him with a combined weight of 3+2+4=9, while he "likes" only vertex E with a weight of 4. For this particular example graph, your function would return the set of vertexes representing {B, F, G}.

Constraints: You may not construct any auxiliary collections to solve this problem, other than the Set to return; but you may create as many simple variables as you like. You should not modify the state of the graph passed in. You may assume that the graph's state is valid at the start of the call.

     3       2     
 A ----> B <---- C
 |       ^       |
2|       |       |
 |       |4      |2
 V   5   V   1   V
 D ----> E <---> F
 |       |
1|       |4
 |       |
 V   3   V          2
 G <---- H       I ---> J
Type your solution here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.