Practice-It

Write a method popular that accepts a Graph<String, String> as a parameter and returns a Set of vertices in that graph that are "popular". Assume 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. 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 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 coming in than going out.)

For example, in the graph below, vertex B is "popular" because vertices 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 method would return the set [B, F, G].

    3       2     
 A ----> B <---- C
 |       ^       |
2|       |       |
 |       |4      |2
 v   5   v   1   v
 D ----> E <---> F
 |       |
1|       |4
 |       |
 v   3   v
 G <---- H       I ---> J

You may assume that the graph and its vertices are not null. Your method should run in at worst O(V²) time where V is the number of vertices in the graph. You may not construct any auxiliary collections to solve this problem, but you may create as many simple variables as you like. You are allowed to call methods on the graph but you should not modify its state. The graph passed to your method implements the following interface:

public interface Graph<V, E> {
    public void addEdge(V v1, V v2);
    public void addEdge(V v1, V v2, E e);
    public void addEdge(V v1, V v2, int weight);
    public void addEdge(V v1, V v2, E e, int weight);
    public void addVertex(V v);
    public void clear();
    public void clearEdges();
    public boolean containsEdge(E e);
    public boolean containsEdge(V v1, V v2);
    public boolean containsPath(List<V> path);
    public boolean containsVertex(V v);
    public int cost(List<V> path);
    public int degree(V v);
    public E edge(V v1, V v2);
    public int edgeCount();
    public Collection<E> edges();
    public int edgeWeight(V v1, V v2);
    public int inDegree(V v);
    public Set<V> inverseNeighbors(V v);
    public boolean isDirected();
    public boolean isEmpty();
    public boolean isReachable(V v1, V v2);         // depth-first search
    public boolean isWeighted();
    public List<V> minimumWeightPath(V v1, V v2);   // Dijkstra's algorithm
    public Set<V> neighbors(V v);
    public int outDegree(V v);
    public void removeEdge(E e);
    public void removeEdge(V v1, V v2);
    public void removeVertex(V v);
    public List<V> shortestPath(V v1, V v2);        // breadth-first search
    public String toString();
    public int vertexCount();
    public Set<V> vertices();
}