The maximum that Chegg will allow me to assign for a single question is 3,000 -

Question

The maximum that Chegg will allow me to assign for a single question is 3,000 - but I recognize that it's a lot of work. If you can complete this for me, I'll post a comment with a second question that you only need to reply to in order to get a further 3,000 points.

The necessary code files to extend AbstractGraph can be found here:

http://www.cs.armstrong.edu/liang/intro9e/html/AbstractGraph.html

http://www.cs.armstrong.edu/liang/intro9e/html/Graph.html

[Question Asked With Image:]

Design SocialGraph, a class for representing and processing social graphs, by extending the abstract class AbstractGraph(link above). In a social graph, the vertices (graph nodes) represent people identified by their names) while the un-directed edges represent the acquaintance relationships between them. Consider the implementation of the following specific methods:

Explanation / Answer

Link to Code

https://www.dropbox.com/s/qlf42qiax4ckm7h/Digits.zip

Code

SocialGraph.java

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

class Triangle {

public int u; // 1st vertex of the triangle

public int v; // 2nd vertex of the triangle

public int w; // 3rd vertex of the triangle

/** Construct an edge for (u, v) */

public Triangle(int u, int v, int w) {

this.u = u;

this.v = v;

this.w = w;

}

  

public String toString()

{

String s = "("+u+" "+v+" "+w+")";

return s;

}

}

public class SocialGraph extends AbstractGraph<String>{

public HashMap<String,Integer> mp;

public HashMap<Integer,String> mprev;

public SocialGraph(ArrayList<String> v, ArrayList<AbstractGraph.Edge> e)

{

super(e,v);

mp = new HashMap<String,Integer>();

for(int i = 0;i<v.size();i++)

{

mp.put(v.get(i), i);

}

}

public SocialGraph(List<String> v, List<AbstractGraph.Edge> e) {

// TODO Auto-generated constructor stub

super(e,v);

mp = new HashMap<String,Integer>();

for(int i = 0;i<v.size();i++)

{

mp.put(v.get(i), i);

}

}

public boolean isConnected()

{

Tree t = dfs(0);

//System.out.println(t.getSearchOrder()+" "+t.getNumberOfVerticesFound()+" "+vertices.size());

return vertices.size() == t.getNumberOfVerticesFound();

}

public double normalizedDegreeOfCentrality(int v)

{

return (double)getDegree(v)/(vertices.size()-1);

}

public double normalizedDegreeOfCentrality(String v)

{

return (double)getDegree(getIndex(v))/(vertices.size()-1);

}

public int numberOfTrianglesIncidentToVertex(int v)

{

List<Integer> nb = getNeighbors(v);

int count=0;

for(int i = 0;i<vertices.size();i++)

{

for(int j = i+1;j<vertices.size();j++)

{

if(nb.contains(i) && nb.contains(j) && getNeighbors(i).contains(j) && i!=j && i!=v && j!=v)

{

//System.out.println(i+" "+j);

count++;

}

}

}

return count;

}

public int numberOfTrianglesIncidentToVertex(String a)

{

int v = getIndex(a);

List<Integer> nb = getNeighbors(v);

int count=0;

for(int i = 0;i<vertices.size();i++)

{

for(int j = i+1;j<vertices.size();j++)

{

if(nb.contains(i) && nb.contains(j) && getNeighbors(i).contains(j) && i!=j && i!=v && j!=v)

{

//System.out.println(i+" "+j);

count++;

}

}

}

return count;

}

public List<Triangle> listOfTrianglesIncidentToVertex(int v)

{

List<Integer> nb = getNeighbors(v);

List<Triangle> tr = new ArrayList<Triangle>();

int count=0;

for(int i = 0;i<vertices.size();i++)

{

for(int j = i+1;j<vertices.size();j++)

{

if(nb.contains(i) && nb.contains(j) && getNeighbors(i).contains(j) && i!=j && i!=v && j!=v)

{

tr.add(new Triangle(v,i,j));

}

}

}

return tr;

}

public List<Triangle> listOfTrianglesIncidentToVertex(String a)

{

int v = getIndex(a);

List<Integer> nb = getNeighbors(v);

List<Triangle> tr = new ArrayList<Triangle>();

int count=0;

for(int i = 0;i<vertices.size();i++)

{

for(int j = i+1;j<vertices.size();j++)

{

if(nb.contains(i) && nb.contains(j) && getNeighbors(i).contains(j) && i!=j && i!=v && j!=v)

{

tr.add(new Triangle(v,i,j));

}

}

}

return tr;

}

public double clusterIndividual(int v)

{

double edgeactual = numberOfTrianglesIncidentToVertex(v);

double edgepotential = getDegree(v)*(getDegree(v)-1)/2.0;

if(edgepotential != 0)

return edgeactual*100.0/edgepotential;

else

return 0.0;

}

public double clusterIndividual(String a)

{

int v = getIndex(a);

double edgeactual = numberOfTrianglesIncidentToVertex(v);

double edgepotential = getDegree(v)*(getDegree(v)-1)/2.0;

if(edgepotential != 0)

return edgeactual*100.0/edgepotential;

else

return 0.0;

}

public double averageClustering()

{

double sum = 0.0;

for(int i = 0;i<vertices.size();i++)

sum+=clusterIndividual(i);

sum=sum/vertices.size();

return sum;

}

public void addVertexAndEdges(String v, List<Integer> e)

{

int n = vertices.size();

addVertex(v);

mp.put(v, n);

for(int i = 0;i<e.size();i++)

addEdge(n, e.get(i));

}

public List<String> depthFirstSearch(int v)

{

Tree t = dfs(v);

List<Integer> in = t.getSearchOrder();

List<String> sn = new ArrayList<String>();

for(int i = 0;i<in.size();i++)

{

String tmp = getVertex((in.get(i)));

sn.add(tmp);

}

return sn;

}

public List<String> depthFirstSearch(String a)

{

int v = getIndex(a);

Tree t = dfs(v);

List<Integer> in = t.getSearchOrder();

List<String> sn = new ArrayList<String>();

for(int i = 0;i<in.size();i++)

{

String tmp = getVertex((in.get(i)));

sn.add(tmp);

}

return sn;

}

public List<String> breadthFirstSearch(int v)

{

Tree t = bfs(v);

List<Integer> in = t.getSearchOrder();

List<String> sn = new ArrayList<String>();

for(int i = 0;i<in.size();i++)

{

String tmp = getVertex((in.get(i)));

sn.add(tmp);

}

return sn;

}

public List<String> breadthFirstSearch(String a)

{

int v = getIndex(a);

Tree t = bfs(v);

List<Integer> in = t.getSearchOrder();

List<String> sn = new ArrayList<String>();

for(int i = 0;i<in.size();i++)

{

String tmp = getVertex((in.get(i)));

sn.add(tmp);

}

return sn;

}

}

TestSocialGraph.java

import java.io.File;

import java.io.FileNotFoundException;

import java.util.*;

public class TestSocialGraph {

public static void test() throws Exception

{

File file = new File("data.txt");

Scanner ip = new Scanner(file);

List<String> v = new ArrayList<String>();

//vertices name

String line = ip.nextLine();

String toks[] = line.split(";");

for(int i = 0;i<toks.length;i++)

v.add(toks[i]);

List<AbstractGraph.Edge> e = new ArrayList<AbstractGraph.Edge>();

line = ip.nextLine();

while(ip.hasNextLine())

{

String l = ip.nextLine();

String tok[] = l.split(" ");

int s = Integer.parseInt(tok[0]);

for(int i = 1;i<tok.length;i++)

e.add(new AbstractGraph.Edge(s,Integer.parseInt(tok[i])));

}

SocialGraph s = new SocialGraph(v,e);

System.out.println(" Graph");

s.printEdges();

System.out.println(" Graph Connectivity");

if(s.isConnected())

System.out.println("Graph is connected");

else

System.out.println("Graph is not connected");

System.out.println(" Normalized Centrality");

for(int i = 0;i<v.size();i++)

{

System.out.println(v.get(i)+" "+s.normalizedDegreeOfCentrality(v.get(i)));

}

System.out.println(" Triangles incident on a vertex");

for(int i = 0;i<v.size();i++)

{

System.out.println(v.get(i)+" "+s.numberOfTrianglesIncidentToVertex(v.get(i))+" "+s.listOfTrianglesIncidentToVertex(v.get(i)));

}

System.out.println(" Individual Clustering");

for(int i = 0;i<v.size();i++)

{

System.out.println(v.get(i)+" "+s.clusterIndividual(v.get(i)));

}

System.out.println(" Average Clustering");

System.out.println(s.averageClustering());

System.out.println(" Depth First Search starting from each vertex");

for(int i = 0;i<v.size();i++)

{

System.out.println(v.get(i)+" "+s.depthFirstSearch(v.get(i)));

}

System.out.println(" Breadth First Search starting from each vertex");

for(int i = 0;i<v.size();i++)

{

System.out.println(v.get(i)+" "+s.breadthFirstSearch(v.get(i)));

}

System.out.println(" Adding an edge i(8) which is neighbour to 3 4 5");

List<Integer> enew = new ArrayList<Integer>();

enew.add(3);

enew.add(4);

enew.add(5);

s.addVertexAndEdges("pratik", enew);

s.printEdges();

}

public static void main(String[] args) throws Exception

{

test();

File file = new File("data.txt");

Scanner ip = new Scanner(file);

Scanner console = new Scanner(System.in);

List<String> v = new ArrayList<String>();

//vertices name

String line = ip.nextLine();

String toks[] = line.split(";");

for(int i = 0;i<toks.length;i++)

v.add(toks[i]);

List<AbstractGraph.Edge> e = new ArrayList<AbstractGraph.Edge>();

line = ip.nextLine();

while(ip.hasNextLine())

{

String l = ip.nextLine();

String tok[] = l.split(" ");

int s = Integer.parseInt(tok[0]);

for(int i = 1;i<tok.length;i++)

e.add(new AbstractGraph.Edge(s,Integer.parseInt(tok[i])));

}

SocialGraph s = new SocialGraph(v,e);

System.out.println(" Graph");

s.printEdges();

int ch;

do

{

System.out.println(" Menu!!");

System.out.println("(1) isConnectted");

System.out.println("(2) normalizedDegreeOfCentrality");

System.out.println("(3) numberOfTrianglesIncidentToVertex");

System.out.println("(4) listOfTrianglesIncidentToVertex");

System.out.println("(5) clusterIndividual");

System.out.println("(6) averageClustering");

System.out.println("(7) addVertexAndEdges");

System.out.println("(8) breadthFirstSearch");

System.out.println("(9) depthFirstSearch");

System.out.println("(0) exit the loop and the program");

ch = Integer.parseInt(console.nextLine());

switch(ch)

{

case 1:

System.out.println(" Graph Connectivity");

if(s.isConnected())

System.out.println("Graph is connected");

else

System.out.println("Graph is not connected");

break;

case 2:

System.out.println(" Normalized Centrality");

System.out.print("Enter the vertex : ");

String tmp = console.nextLine();

System.out.println(tmp+" "+s.normalizedDegreeOfCentrality(tmp));

break;

case 3:

System.out.println(" Number of Triangle incident on the vertex");

System.out.print("Enter the vertex : ");

tmp = console.nextLine();

System.out.println(tmp+" "+s.numberOfTrianglesIncidentToVertex(tmp));

break;

case 4:

System.out.println(" List of Triangle incident on the vertex");

System.out.print("Enter the vertex : ");

tmp = console.nextLine();

System.out.println(tmp+" "+s.listOfTrianglesIncidentToVertex(tmp));

break;

case 5:

System.out.println(" ClusterIndividual");

System.out.print("Enter the vertex : ");

tmp = console.nextLine();

System.out.println(tmp+" "+s.clusterIndividual(tmp));

break;

case 6:

System.out.println(" Average Clustering");

System.out.println(s.averageClustering());

break;

case 7:

System.out.println(" New Graph");

System.out.print("Enter the new vertex : ");

tmp = console.nextLine();

System.out.print("Enter new edges for this : ");

String ed = console.nextLine();

String[] tk = ed.split(" ");

List<Integer> l = new ArrayList<Integer>();

for(int k = 0;k<tk.length;k++)

{

l.add(Integer.parseInt(tk[k]));

}

s.addVertexAndEdges(tmp, l);

s.printEdges();

break;

case 8:

System.out.println(" breadthFirstSearch");

System.out.print("Enter the vertex : ");

tmp = console.nextLine();

System.out.println(tmp+" "+s.breadthFirstSearch(tmp));

break;

case 9:

System.out.println(" depthFirstSearch");

System.out.print("Enter the vertex : ");

tmp = console.nextLine();

System.out.println(tmp+" "+s.depthFirstSearch(tmp));

break;

}

}while(ch!=0);

}

}

Snapshot for Output

https://www.dropbox.com/sh/wvteti5q5ojmauy/rzytixY6bt

This link contains the snapshot of the output

Test1 contains the menu driven program asked in question

Test2 contains a call to test functions that calls all the features on all the vertices

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.