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

Implement a main method in the Undirected Graph class. 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.

The first line of the input file will contain the number of vertices in the graph (an int).

The remaining lines in the file will contains pairs of ints that represent edges.

Here is an example input file:

8 0 1 4 5 0 4 5 0 0 2 1 2 2 6 3 2 7 6 6 3 3 7 1 5 3 1

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 } }

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) {

//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

return 0;

}

public int countTriangles() {

//return the number of triangles in the graph

return 0;

}

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(); //comment this line before sending me your homework

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

} }