Program To Implement Undirected Graph in Java Assignment Solution

Instructions

Objective

To complete a Java assignment, you need to write a program that implements an undirected graph in the Java language. An undirected graph consists of a set of vertices connected by edges, where the edges have no direction. In the program, you should define classes to represent vertices and edges, along with methods to add vertices, create edges between them, and perform other graph-related operations like traversals or finding paths. Utilize data structures like arrays or linked lists to manage the graph's connectivity efficiently. Make sure to implement the necessary algorithms and error handling to ensure the program runs smoothly and produces correct results.

Requirements and Specifications

Source Code

import java.util.*; public class Graph { public int noOfVertices = - 1; public int[][] edges = null; public int[][] weights = null; // Creates a new empty graph. public Graph() { } public Graph(int[][] data, boolean weighted) { if (weighted) initWeighted(data); else initUnweighted(data); } private void initWeighted(int[][] data) { // Structure of data // ------------------ // length: 2 times number of vertices // 2i: neighbours of vertex i. // 2i + 1: weight of edges from vertex i to corresponding neighbour. noOfVertices = data.length / 2; edges = new int[noOfVertices][]; weights = new int[noOfVertices][]; for (int i = 0; i < noOfVertices; i++) { int dataInd = 2 * i; int deg = data[dataInd].length; edges[i] = new int[deg]; weights[i] = new int[deg]; for (int j = 0; j < deg; j++) { edges[i][j] = data[dataInd][j]; weights[i][j] = data[dataInd + 1][j]; } } } private void initUnweighted(int[][] data) { noOfVertices = data.length; edges = new int[noOfVertices][]; for (int i = 0; i < noOfVertices; i++) { edges[i] = data[i].clone(); } } /** * Relexas an edge of the graph based on the given distances. * @param vInd The vertex from which the edge starts. * @param neighInd The index of the vertex in the neighbourhood of v to * which the edge points. That is, the edge goes from vId * to edges[vId][neighInd]. */ public boolean relax(int vInd, int neighInd, int[] distances) { int uInd = edges[vInd][neighInd]; int uDis = distances[uInd]; int vDis = distances[vInd]; int vuWeight = weights[vInd][neighInd]; boolean update = false; // Avoid problems with overflow. if (vuWeight > 0) { update = vDis < uDis - vuWeight; } else { update = vDis + vuWeight < uDis; } if (update) { distances[uInd] = vDis + vuWeight; return true; } return false; } public int[][] dfs(int startId) { // Output data int[] parIds = new int[noOfVertices]; int[] preOrder = new int[noOfVertices]; int[] postOrder = new int[noOfVertices]; int preCount = 0; int postCount = 0; // Helpers to compute DFS int[] neighIndex = new int[noOfVertices]; int[] stack = new int[noOfVertices]; int stackSize = 0; boolean[] visited = new boolean[noOfVertices]; for (int vId = 0; vId < noOfVertices; vId++) { parIds[vId] = -1; preOrder[vId] = -1; postOrder[vId] = -1; visited[vId] = false; neighIndex[vId] = 0; } // Push stack[stackSize] = startId; stackSize++; while (stackSize > 0) { int vId = stack[stackSize - 1]; int nInd = neighIndex[vId]; if (nInd == 0) { visited[vId] = true; // *** Pre-order for vId *** preOrder[preCount] = vId; preCount++; } if (nInd < edges[vId].length) { int neighId = edges[vId][nInd]; if (!visited[neighId]) { // Push stack[stackSize] = neighId; stackSize++; parIds[neighId] = vId; } neighIndex[vId]++; } else { // All neighbours checked, backtrack. stackSize--; // Pop; // *** Post-order for vId *** postOrder[postCount] = vId; postCount++; } } return new int[][] { parIds, preOrder, postOrder }; } public int[][] bfs(int startId) { // Output data // 0: distances from start vertex // 1: BFS-order // 2: parent-IDs int[][] bfsResult = new int[3][noOfVertices]; int[] distances = bfsResult[0]; int[] q = bfsResult[1]; int[] parents = bfsResult[2]; for (int i = 0; i < noOfVertices; i++) { distances[i] = Integer.MAX_VALUE; q[i] = -1; parents[i] = -1; } // Set start vertex distances[startId] = 0; q[0] = startId; int qSize = 1; for (int qInd = 0; qInd < qSize; qInd++) { int vInd = q[qInd]; int nDis = distances[vInd] + 1; for (int nInd = 0; nInd < edges[vInd].length; nInd++) { int uInd = edges[vInd][nInd]; if (nDis < distances[uInd]) { distances[uInd] = nDis; parents[uInd] = vInd; q[qSize] = uInd; qSize++; } } } return bfsResult; } public int[] bellmanFord(int startId) { int[] distances = new int[noOfVertices]; Arrays.fill(distances, Integer.MAX_VALUE); distances[startId] = 0; HashSet updatedLast = new HashSet(); HashSet updateNext = new HashSet(); updatedLast.add(startId); while (updatedLast.size() > 0) { for (int vId : updatedLast) { for (int i = 0; i < edges[vId].length; i++) { if (relax(vId, i, distances)) { updateNext.add(edges[vId][i]); } } } updatedLast.clear(); HashSet tmp = updatedLast; updatedLast = updateNext; updateNext = tmp; } return distances; } }