Problem 1
You are given an undirected graph G which is represented as adjacency list. Its n nodes are labelled from 0 to n-1. For each node, its list of neighbors is out of order. Implement an algorithm that sorts all these lists in total
linear time. Note that linear-time for graphs means in O(|V| + |E|) time where V is the number of vertices and E is the number of edges. Using counting sort on each list of neighbors requires a total of O(|V|2
+ |E|) time. Feel free to change the given graph as needed. However, do not change the IDs of the vertices.
You are given a fileLab6.java and a file Graph.java. The file Lab6.java contains a class Lab6 with the problem1 function. Implement your solution in the problem1 function. Do not make any changes outside of that function (e. g. by adding helper functions). The class Graph in the file Graph.java contains the functions relax, bfs, and dfs. Feel free to use these functions.
Provided code:
Lab6.java:
import java.io.*;
import java.util.*;
public class Lab6
{
/**
* Problem 1: Sort the list of neighbors for each vertex.
*/
private static void problem1(Graph g)
{
// Implement me!
}
/**
* Problem 2: Find the distances in a directed acyclic graph.
*/
private static int[] problem2(Graph g, int startId)
{
// Implement me!
return null;
}
// ---------------------------------------------------------------------
// Do not change any of the code below!
private static final int LabNo = 6;
private static final String quarter = "Spring 2021";
private static final Random rng = new Random(123456);
private static boolean testProblem1(int[][] testCase)
{
Graph g = new Graph(testCase, false);
Graph h = new Graph(testCase, false);
problem1(g);
if (g.noOfVertices != h.noOfVertices) return false;
if (g.edges == null || g.edges.length != g.noOfVertices) return false;
for (int vId = 0; vId
{
if (g.edges[vId] == null) return false;
if (g.edges[vId].length != h.edges[vId].length) return false;
Arrays.sort(h.edges[vId]);
for (int i = 0; i
{
if (g.edges[vId][i] != h.edges[vId][i]) return false;
}
}
return true;
}
private static boolean testProblem2(int[][] testCase)
{
int[][] graphData = Arrays.copyOf(testCase, testCase.length - 1);
int startId = testCase[testCase.length - 1][0];
Graph g = new Graph(graphData, true);
int[] solution = g.bellmanFord(startId);
int[] answer = problem2(g, startId);
if (answer.length != solution.length) return false;
for (int i = 0; i
{
if (answer[i] != solution[i]) return false;
}
return true;
}
public static void main(String args[])
{
System.out.println("CS 302 -- " + quarter + " -- Lab " + LabNo);
testProblems(1);
testProblems(2);
}
private static void testProblems(int prob)
{
int noOfLines = 5000;
System.out.println("-- -- -- -- --");
System.out.println(noOfLines + " test cases for problem " + prob + ".");
boolean passedAll = true;
for (int i = 1; i
{
int[][] testCase = null;
boolean passed = false;
boolean exce = false;
try
{
switch (prob)
{
case 1:
testCase = createProblem1(i);
passed = testProblem1(testCase);
break;
case 2:
testCase = createProblem2(i);
passed = testProblem2(testCase);
break;
}
}
catch (Exception ex)
{
passed = false;
exce = true;
}
if (!passed)
{
System.out.println("Test " + i + " failed!" + (exce ? " (Exception)" : ""));
passedAll = false;
break;
}
}
if (passedAll)
{
System.out.println("All test passed.");
}
}
private static int[][] createProblem1(int testNo)
{
int size = rng.nextInt(Math.min(1000, testNo)) + 10;
// WTF Java, I want HashSet[size]!
ArrayList> graph = new ArrayList>(size);
for (int i = 0; i
{
graph.add(new HashSet());
}
for (int i = 1; i
{
int par = rng.nextInt(i);
graph.get(i).add(par);
graph.get(par).add(i);
}
int logSize = -1;
for (int s = size; s > 0; s /= 2) logSize++;
int avgDeg = rng.nextInt(logSize * logSize - 3) + 3;
int edges = (avgDeg * size) / 2 - size + 1;
for (int i = 0; i
{
int uId = rng.nextInt(size);
// Ensures vId != uId
int vId = rng.nextInt(size - 1);
if (vId >= uId) vId++;
graph.get(uId).add(vId);
graph.get(vId).add(uId);
}
int[][] testCase = new int[size][];
for (int vId = 0; vId
{
int deg = graph.get(vId).size();
int[] neighs = new int[deg];
int ctr = 0;
for (Integer uId : graph.get(vId))
{
neighs[ctr] = uId;
ctr++;
}
shuffle(neighs);
testCase[vId] = neighs;
}
return testCase;
}
private static int[][] createProblem2(int testNo)
{
int size = rng.nextInt(Math.min(1000, testNo)) + 10;
ArrayList> edgeSet = new ArrayList>();
int[] topOrder = new int[size];
for (int i = 0; i
{
edgeSet.add(new Hashtable());
topOrder[i] = i;
}
shuffle(topOrder);
int logSize = -1;
for (int s = size; s > 0; s /= 2) logSize++;
int avgDeg = rng.nextInt(logSize * logSize - 3) + 3;
int edges = (avgDeg * size) / 2 - size + 1;
for (int i = 1; i
{
int par = rng.nextInt(i);
int wei = rng.nextInt(2 * logSize + 1) - logSize;
int fr = -1;
int to = -1;
if (topOrder[par]
{
fr = par;
to = i;
}
else
{
fr = i;
to = par;
}
edgeSet.get(fr).put(to, wei);
}
for (int i = 0; i
{
int uvWei = rng.nextInt(2 * logSize + 1) - logSize;
int frId = rng.nextInt(size);
// Ensures vId != uId
int toId = rng.nextInt(size - 1);
if (toId >= frId) toId++;
if (topOrder[frId] > topOrder[toId])
{
int tmp = frId;
frId = toId;
toId = tmp;
}
edgeSet.get(frId).put(toId, uvWei);
}
int[][] testCase = new int[2 * size + 1][];
for (int vId = 0; vId
{
Hashtable vEdges = edgeSet.get(vId);
int deg = vEdges.size();
int[] neighs = new int[deg];
int[] weights = new int[deg];
Set neighSet = vEdges.keySet();
int nInd = 0;
for (Integer nId : neighSet)
{
neighs[nInd] = nId;
nInd++;
}
Arrays.sort(neighs);
for (int i = 0; i
{
weights[i] = vEdges.get(neighs[i]);
}
testCase[2 * vId] = neighs;
testCase[2 * vId + 1] = weights;
}
// Start vertex.
testCase[2 * size] = new int[] { rng.nextInt(size) };
return testCase;
}
private static void shuffle(int[] arr)
{
for (int i = 0; i
{
int rndInd = rng.nextInt(arr.length - i) + i;
int tmp = arr[i];
arr[i] = arr[rndInd];
arr[rndInd] = tmp;
}
}
}
Graph.java:
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
{
int dataInd = 2 * i;
int deg = data[dataInd].length;
edges[i] = new int[deg];
weights[i] = new int[deg];
for (int j = 0; 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
{
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 neighborhood 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
}
else
{
update = vDis + vuWeight
}
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
{
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
{
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
{
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
{
int vInd = q[qInd];
int nDis = distances[vInd] + 1;
for (int nInd = 0; nInd
{
int uInd = edges[vInd][nInd];
if (nDis
{
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
{
if (relax(vId, i, distances))
{
updateNext.add(edges[vId][i]);
}
}
}
updatedLast.clear();
HashSet tmp = updatedLast;
updatedLast = updateNext;
updateNext = tmp;
}
return distances;
}
}