The To-do's in the SocialCircles class
// Exercise 4.1.3 (Solution published at http://algs4.cs.princeton.edu/) package algs41; import stdlib.*; import algs13.Bag; /** * The
Graphclass 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"><>(); } } /** * 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=""> 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.="" *="">
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");="" }="" }="" package="" homework;="" import="" java.util.arrays;="" import="" algs41.graph;="" import="" algs41.graphgenerator;="" import="" stdlib.*;="" **="" *="" class="" socialcircles="" version="" 1.0="" *="" *="" computes="" several="" 'social="" circle'="" (graph)="" characteristics="" *="" terms:="" the="" popularity="" of="" a="" vertex="" is="" simply="" its="" degree="" *="" vertices="" are="" 'friends'="" if="" they="" are="" connected="" *="" *="" tocompute:="" (each="" characteristic="" is="" defined="" in="" the="" corresponding="" functions="" below)="" *="" *="" numberoftrios="" *="" maxbalancefactor="" *="" indirectpopularity="" *="" socialstatus="" *="" numberofmostunbalancedfriendships="" *="" *="" there="" are="" two="" levels="" to="" this="" assignment.="" *="" b-level="" *="" complete="" the="" methods="" marked="" todo.="" *="" a-level="" *="" complete="" todo-a="" in="" the="" method:="" *="" *="" you="" may="" add="" additional="" instance="" methods="" to="" the="" socialcircles="" class="" to="" faciliate="" completing="" the="" todos="" *="" you="" may="" not="" add="" any="" additional="" instance="" variables="" to="" the="" socialcircles="" class="" *="" you="" may="" not="" change="" the="" graph="" 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)="" *="" or="" create="" small="" simpleconnected="" graphs="" using="" the="" graphgenerator="" class="" (view="" with="" graphviz?)="" and="" verify="" your="" functions="" *="" compute="" the="" correct="" values="" *="" */="" public="" class="" socialcircles="" {="" private="" int="" numberoftrios;="" the="" results="" of="" the="" computations="" are="" stored="" private="" int[]="" indirectpopularity;="" in="" these="" instance="" variables.="" private="" int="" maxbalancefactor;="" the="" values="" of="" the="" variables="" may="" be="" accessed="" by="" clients="" using="" private="" int="" numberofmostunbalancedfriendships;="" the="" corresponding="" 'accessor'="" functions="" below.="" private="" int="" []="" socialrank;="" accessor="" functions="" public="" int="" getindirectpopularity(int="" v)="" {="" getindirectpopularity="" of="" vertex="" v="" return="" indirectpopularity[v];="" }="" public="" int="" getnumberoftrios()="" {="" return="" numberoftrios;="" }="" public="" int="" getmaxbalancefactor()="" {="" return="" maxbalancefactor;="" }="" public="" int="" getnumberofmostunblanancedfriendships()="" {="" return="" numberofmostunbalancedfriendships;="" }="" public="" int="" getsocialrank(int="" v)="" {="" get="" getsocialrank="" of="" vertex="" v="" return="" socialrank[v];="" }="" ---end="" accessors="" **="" *="" degree="" *="" *="" suggestion.="" copy="" the="" degree="" function="" (or="" see="" if="" you="" can="" write="" it="" from="" scratch)="" from="" the="" textbook.="" *="" you="" may="" find="" it="" a="" useful="" utility="" function="" for="" your="" functions="" */="" public="" static="" int="" degree(graph="" g,="" int="" v)="" {="" int="" degree="0;" for(int="" w="" :="" g.adj(v))="" degree++;="" return="" degree;="" }="" **="" *="" 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)="" {="" int="" u="0," v,="" w;="" for(int="" i="" :="" g.adj(u))="" stdout.println("yes");="" numberoftrios="-1;" todo="" 1="" fix="" this="" }="" **="" *="" determineindirectpopularity="" *="" *="" concept:="" people="" accrue="" social="" status="" from="" the="" people="" they="" associate="" with.="" *="" and="" while="" an="" individual="" may="" not="" be="" 'popular',="" they="" may="" achieve="" some="" level="" *="" of="" popularity="" -="" indirectly="" -="" through="" the="" popularity="" of="" their="" friends.="" this="" *="" is="" the="" notion="" of="" 'indirectpopularity'="" *="" *="" for="" each="" vertex="" v,="" determine="" the="" maximum="" popularity="" of="" its="" friends="" *="" *="" the="" indirectpopularity="" of="" a="" vertex="" with="" no="" friends="" is="" 0="" *="" *="" store="" the="" answer="" in="" indirectpopularity[v]="" */="" private="" void="" determineindirectpopularity(graph="" g)="" {="" for="" (int="" v="0;" v="">< g.v();="" v++="" )="" indirectpopularity[v]="-1;" 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)="" {="" for="" (int="" v="0;" v="">< g.v();="" v++)="" {="" socialrank[v]="-1;" todo="" 3="" fix="" this="" }="" }="" **="" *="" blanancedfriendships="" *="" *="" say="" the="" 'balancefactor'="" of="" a="" friendship="" is="" the="" difference="" between="" the="" two="" friends'="" *="" popularities.="" if="" two="" friends="" have="" the="" same="" popularity,="" then="" the="" balancefactor="" would="" *="" be="" 0.="" if="" one="" of="" the="" friends="" had="" n="" total="" friends="" and="" the="" other="" had="" 1,="" then="" the="" *="" balancefactor="" would="" be="" n-1="" -="" it="" would="" be="" a="" 'lopsided'="" friendship="" *="" *="" the="" maxbalancefactor="" for="" a="" graph="" is="" the="" largest="" balancefactor="" for="" the="" graph="" *="" (note="" it="" would="" always="" be="">=0) * * B-Level: * determine the maximum balanceFactor for the graph. * store the answer in the maxBalanceFactor instance variable * * A-Level * * determine the number of 'friendships' for which the balanceFactor is largest for the graph * store the answer in the numberOfMostUnbalancedFriendships instance variable * * this level is optional. if you choose NOT to complete it, simply leave the assignment * statement to numberOfMostUnbalancedFriendships as given below. * * Example: if all vertices have the same number of friends, then all popularites would be the same * so all balanceFactors would be 0 - the maxBalanceFactor would be 0 * * A-Level: since all balanceFactors are the same, * all friendships would have the maximum balanceFactor