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.

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

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

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

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

}

public int countTriangles() {

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

// 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());

}

}