* Complete the methods marked ToDo.

package CSC301SP18Homework;

import algs41.Graph;

import algs41.GraphGenerator;

import qs.a.w;

import stdlib.*;

/**

* class Friendship version 1.0

*

* computes several 'friendship' related values for a graph

*

* numberOfTrios: the number of groups of 3 vertices (u,v,w) which are all directly connected to each other

* indirectPopularity: for a vertex v, its indirect popularity is the maximum degree of all the nodes adjacent to v

* averageNumberOfFriends: see below

* socialRank: The social rank of a vertex v is: the number of nodes in the graph

* that have more friends than v does

* a lower number implies higher social 'status'

*

* Complete the methods marked ToDo.

*

* You may add additional instance methods to the Friendship class to faciliate completing the ToDos

* You may NOT add any additional instance variables to the Friendship class

* You may use basic Java arrays, however you may NOT use any additional data structures without permission (e.g. queue)

*

* Note: you are free to change main; we will test your class using a different driver.

* Some test graphs (with answers) are included in main; you are encouraged to create additional test graphs

* using the textbook file format ( see data/tinyG.txt for an example)

*

*/

public class Friendship {

private int numberOfTrios; // the results of the computations are stored

private int[] indirectPopularity; // in these instance variables.

private double averageNumberOfFriends; // the values of the variables may be accessed using

private int [] socialRank; // the corresponding 'accessor' functions below.

public int indirectPopularity(int v) { // accessor functions

return indirectPopularity[v];

}

public int numberOfTrios() {

return numberOfTrios;

}

public double averageNumberOfFriends() {

return averageNumberOfFriends;

}

public int socialRank(int v) {

return socialRank[v];

}

// ---end accessors

/**

* degree

*

* Suggestion. copy the degree function from the textbook.

* you may find it a useful utility function for your functions

*/

private int degree(Graph G, int v) {

int degree = 0;

// if (int w : G.adj(v)){

// degree ++;

// }

return degree; // fix this if you want to use it

}

/**

* CountNumberOfTrios

*

* determine how many groups of 3 vertices (u,v,w) are directly to connected to each other

* Each group should be counted only one time.

*

* the functions stores the computed result in the numberOfTrios instance variable

*/

private void countNumberOfTrios(Graph G) {

// if u, v, w are marked

// numberOfTrios ++

numberOfTrios = -1; // ToDo 1 fix this

}

/**

* determineIndirectPopularity

*

* for each vertex v, determine the maximum popularity of its friends

* store the answer in indirectPopularity[v]

*

*/

private void determineIndirectPopularity(Graph G) {

// ToDo 2 fix this

}

/**

* socialRank

*

* for each vertex v, determine how many vertices have degree higher than v

* "how many people are more popular than V?"

* store the answer in socialRank[v]

*/

private void determineSocialRank(Graph G) {

// ToDo 3 fix this

}

/**

* determineAverageNumberOfFriends

*

* Each vertex has some number of friends.

* Determine the average number of friends over all vertices

* store the answer in: averageNumberOfFriends

*/

private void determineAverageNumberOfFriends(Graph G) {

averageNumberOfFriends = -1; // ToDo 4 fix this

}

// the constructor instantiates all instance variables and

// calls methods to compute their values for the input graph G

// nothing for you to change here

public Friendship(Graph G) {

indirectPopularity = new int[G.V()];

socialRank = new int[G.V()];

countNumberOfTrios(G);

determineIndirectPopularity(G);

determineSocialRank(G);

determineAverageNumberOfFriends(G);

}

// test client

//

// use this test client to test your friendship class

// to perform a test, select an input graph by commenting it "in" and the others "out" below

public static void main(String[] args) {

// the answers for each graph given below are included in a comment in the right margin

// in order: # trios, indirect popularity, average social rank, average # of friends

In in = new In("data/tinyG.txt" );

Graph G = GraphGenerator.fromIn (in); // 2; varies from 1-4; 4; 2

//Graph G =GraphGenerator.complete(4); // 4; all 3; 0; 3

//Graph G = GraphGenerator.cycle(8); // 0; all 2; 0, 2

//Graph G = GraphGenerator.binaryTree(15); // 0; all 3; 4; 1.87

//Graph G = GraphGenerator.random(50, 1000); // answer may vary due to randomness

// ballpark: 11000; 50's; 23; 40

// StdOut.println(G); // uncomment to have the graph adj-list printed

// G.toGraphviz ("g.png"); // uncomment to get a picture of the graph

// create the Friendship instance using the graph G

Friendship community = new Friendship(G);

// display the results computed by the Friendship instance

StdOut.format("The number of trios is %d ", community.numberOfTrios());

StdOut.format("Indirect popularity Table ");

for (int v=0; v < G.V(); v++) {

StdOut.format(" vertex %3d : %3d ", v, community.indirectPopularity(v));

}

// determine the average social rank

int sum=0;

for (int v=0; v < G.V(); v++) {

sum+= community.socialRank(v);

}

double averageSocialRank = sum / G.V();

StdOut.format("The average social rank is %5.2f ", averageSocialRank);

StdOut.format("The average number of friends is %5.2f ", community.averageNumberOfFriends() );

}

}

XXXXXX THIS IS THE GRAPH CLASS XXXXXXXXXXXX

// Exercise 4.1.3 (Solution published at http://algs4.cs.princeton.edu/)

package algs41;

import stdlib.*;

import algs13.Bag;

/**

* The Graph class represents an undirected graph of vertices

* named 0 through V-1.

* It supports the following operations: add an edge to the graph,

* iterate over all of the neighbors adjacent to a vertex.

* Parallel edges and self-loops are permitted.

*

* For additional documentation, see Section 5.1 of

* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

*/

public class Graph {

private final int V;

private int E;

private final Bag[] adj;

/**

* Create an empty graph with V vertices.

*/

@SuppressWarnings("unchecked")

public Graph(int V) {

if (V < 0) throw new Error("Number of vertices must be nonnegative");

this.V = V;

this.E = 0;

this.adj = new Bag[V];

for (int v = 0; v < V; v++) {

adj[v] = new Bag<>();

}

}

/**

* Return the number of vertices in the graph.

*/

public int V() { return V; }

/**

* Return the number of edges in the graph.

*/

public int E() { return E; }

/**

* Add the undirected edge v-w to graph.

* @throws java.lang.IndexOutOfBoundsException unless both 0 <= v < V and 0 <= w < V

*/

public void addEdge(int v, int w) {

if (v < 0 || v >= V) throw new IndexOutOfBoundsException();

if (w < 0 || w >= V) throw new IndexOutOfBoundsException();

E++;

adj[v].add(w);

adj[w].add(v);

}

/**

* Return the list of neighbors of vertex v as in Iterable.

* @throws java.lang.IndexOutOfBoundsException unless 0 <= v < V

*/

public Iterable adj(int v) {

if (v < 0 || v >= V) throw new IndexOutOfBoundsException();

return adj[v];

}

/**

* Returns the degree of vertex {@code v}.

*

* @param v the vertex

* @return the degree of vertex {@code v}

* @throws IllegalArgumentException unless {@code 0 <= v < V}

*/

public int degree(int v) {

if (v < 0 || v >= V) throw new IndexOutOfBoundsException();

return adj[v].size();

}

/**

* Return a string representation of the graph.

*/

public String toString() {

StringBuilder s = new StringBuilder();

String NEWLINE = System.getProperty("line.separator");

s.append(V + " vertices, " + E + " edges " + NEWLINE);

for (int v = 0; v < V; v++) {

s.append(v + ": ");

for (int w : adj[v]) {

s.append(w + " ");

}

s.append(NEWLINE);

}

return s.toString();

}

/**

* Save a graphviz representation of the graph.

* See graphviz.org.

*/

public void toGraphviz(String filename) {

GraphvizBuilder gb = new GraphvizBuilder ();

for (int v = 0; v < V; v++) {

gb.addNode (v);

boolean showSelfLoop = false;

for (int w : adj[v]) {

if (v < w) // only once each edge

gb.addEdge (v, w);

if (v == w) {

showSelfLoop = !showSelfLoop;

if (showSelfLoop)

gb.addEdge (v, w);

}

}

}

gb.toFileUndirected (filename);

}

/**

* Test client.

*/

public static void main(String[] args) {

//args = new String [] { "data/tinyCG.txt" };

args = new String [] { "data/tinyG.txt" };

//args = new String [] { "20", "40" };

Graph G;

if (args.length == 1) {

In in = new In(args[0]);

G = GraphGenerator.fromIn (in);

} else {

int V = Integer.parseInt (args[0]);

int E = Integer.parseInt (args[1]);

G = GraphGenerator.simple(V, E);

}

StdOut.println(G);

G.toGraphviz ("g.png");

}

}