Homework SourseThe maximum that Chegg will allow me to assign for a single
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:]
Solution
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)+\"\\t\"+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)+\"\\t\"+s.numberOfTrianglesIncidentToVertex(v.get(i))+\"\\t\"+s.listOfTrianglesIncidentToVertex(v.get(i)));
}
System.out.println(\"\ Individual Clustering\");
for(int i = 0;i<v.size();i++)
{
System.out.println(v.get(i)+\"\\t\"+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)+\"\\t\"+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)+\"\\t\"+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+\"\\t\"+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+\"\\t\"+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+\"\\t\"+s.listOfTrianglesIncidentToVertex(tmp));
break;
case 5:
System.out.println(\"\ ClusterIndividual\");
System.out.print(\"Enter the vertex : \");
tmp = console.nextLine();
System.out.println(tmp+\"\\t\"+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+\"\\t\"+s.breadthFirstSearch(tmp));
break;
case 9:
System.out.println(\"\ depthFirstSearch\");
System.out.print(\"Enter the vertex : \");
tmp = console.nextLine();
System.out.println(tmp+\"\\t\"+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
