package algs13;

import algs41.Graph;

import algs41.GraphGenerator;

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) {

return -1; // 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) {

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() );

}

}