Part 1: Implement the methods in the Undirected Graph class. The methods must make use of the data structure given in the class.

Part 2: Implement a main method in the Undirected Graph class. I have given you part of main. You must complete the part that builds the graph from the input. The input to the main method will come from a text file whose name is given in a command line argument. Triangle Counting Algorithm triangleCount = 0

for each vertex, v1, in the graph {

for each vertex, v2, in the orderedNeighbors of v1 { triangleCount = triangleCount + the number of

} }

elements in the intersection of the orderedNeighbors of v1 and the orderedNeighbors of v2

Create Ordered Neighbor Sets for each edge (v1,v2) in the graph {

if (degree(v1) < degree(v2)) or (degree(v1)==degree(v2) and v1 < v2)

add v2 to the orderedNeighbors of v1 else

add v1 to the orderedNeighbors of v2 }

import java.io.IOException;

public class UndirectedGraph {

private class Vertex {

private EdgeNode edges1;

private EdgeNode edges2;

private int numNeighbors; // This is the same as the degree of the

// vertex private int orderedNeighbors[];

// //Set of ordered neighbors

// We will learn others ways to store sets but for this assignment //you

// must store the set in an array

private Vertex() {

}

}

private class EdgeNode {

private int vertex1;

private int vertex2;

private EdgeNode next1;

private EdgeNode next2;

private EdgeNode(int v1, int v2, EdgeNode e1, EdgeNode e2) { // PRE: v1

// < v2

// Each edge node is stored only once but it will be part of two

// lists }

}

private Vertex[] g;

}

public UndirectedGraph(int size) {

// Create a graph with size vertices

// The vertices will be identified by ints between 0 and size-1 //The

// vertices are stored in a array

g = new Vertex[size];

for (int i = 0; i < size; i++) {

g[i] = new Vertex();

}

}

public void addEdge(int v1, int v2) { // add a new edge between v1 and v2

}

public void printNeighbors() {

// print the neighbors of each vertex to standard output

// this will be useful for checking if you built the graph correctly

// //there should be one line for each vertex

// the format of the line should be vertex name: comma delimited list of

// //neighbors

}

private void populateOrderedNeighbors() {

// find the ordered neighbors of each vertex

// each orderedNeighbor set should be sorted in ascending order

}

private int intersectionSize(int v1, int v2) {

return v2;

// find the number of elements in the intersection of the

// orderedNeighbors //of v1 and the orderedNeighbors of v2

// your code must make use of the fact that the orderNeighbor sets are

// //sorted in ascending order

}

public int countTriangles() {

return 0;

// return the number of triangles in the graph

}

public static void main(String args[]) throws IOException { //build the graph and find the number of triangles

UndirectedGraph g = null;

//build the graph

g.printNeighbors(); //put this line in a comment before sending

//me your homework

System.out.println("The number of triangles is" +g.countTriangles());

}

}