import java.util.List;
import java.util.ArrayList;
class Graph {
private final int V; // number of vertices
private final List[] adj; // adjacency lists... 0 to V-1
/** create an empty graph with V vertices */
public Graph(int V) {
this.V = V;
this.adj = new ArrayList[V]; // create empty graph with V vertices
for(int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
/** add an edge v-w */
public void addEdge(int v, int w) {
// add edge v-w (parallel edges and self-loops allowed)
adj[v].add(w);
adj[w].add(v);
}
/** vertices adjacent to v */
public Iterable adj(int v) {
return adj[v];
}
/** number of vertices */
public int V() {
return V;
}
/** number of edges */
public int E() {
int countEdges = 0;
for(int v = 0; v < V; v++) {
countEdges += adj[v].size();
}
return countEdges/2; // Each edge counted twice
}
/** string representation */
public String toString() {
return "TODO";
}
public static void main (String[] args) {
System.out.println("Test graph ");
int[][] edges = new int[][] {
{0, 5},
{4, 3},
{0, 1},
{9, 12},
{6, 4},
{5, 4},
{0, 2},
{11, 12},
{9, 10},
{0, 6},
{7, 8},
{9, 11},
{5, 3}
};
Graph G = new Graph(edges.length);
// add all edges
for(int i = 0; i < edges.length; i++) {
int v = edges[i][0];
int w = edges[i][1];
G.addEdge(v, w);
}
System.out.println("V: " + G.V());
System.out.println("E: " + G.E());
System.out.println("Max degree: " + Graph.GraphProcessing.maxDegree(G));
System.out.println("Avg degree: " + Graph.GraphProcessing.averageDegree(G));
System.out.println("No of self loops: " + Graph.GraphProcessing.numberOfSelfLoops(G));
}
public static class GraphProcessing {
/** compute degree of v */
public static int degree(Graph G, int v) {
int degree = 0;
for(int w : G.adj(v)) {
degree++;
}
return degree; // (or) return G.adj(v).size()
}
/** Compute max degree of graph */
public static int maxDegree(Graph G) {
int maxDegree = 0;
for(int v = 0; v < G.V(); v++) {
int degreeOfV = degree(G, v);
maxDegree = degreeOfV > maxDegree ? degreeOfV : maxDegree;
}
return maxDegree;
}
/** Compute average degree */
public static double averageDegree(Graph G) {
return 2.0 * G.E()/G.V();
}
/** Compute self loops */
public static int numberOfSelfLoops(Graph G) {
int numberOfLoops = 0;
for(int v = 0; v < G.V(); v++) {
for(int w : G.adj(v)) {
numberOfLoops = (v == w) ? ++numberOfLoops : numberOfLoops;
}
}
return numberOfLoops/2; // each edge counted twice
}
}
public static class Path {
/* is there a path from s to v? */
public boolean hasPathTo(Graph G, int s, int v) {
return G.adj(s).contains(v);
}
/* path from s to v; null if no such path */
public Iterable pathTo(Graph G, int s, int v) {
}
/* Print all vertices connected to s */
public void printAllConnected(Graph G, int s) {
//for()
}
}
}
Output
Test graph
V: 13
E: 13
Max degree: 4
Avg degree: 2.0
No of self loops: 0
Comments
Post a Comment