Problem 1

You are given an undirected graph G which is represented as adjacency list. Its n nodes are labelled from 0 to n1. 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|² + |E|) time. Feel free to change the given graph as needed. However, do not change the IDs of the vertices.

Problem 2

You are given a weighted directed acyclic graph G and a vertex s. Implement an algorithm that determines in linear time the distance from s to all other vertices. Note that edge weights can be negative. The output should be an int-array containing the distances from s to all vertices ordered by their IDs, I.E., the output should be [d(s, v₀), d(s, v₁), ... ]. If there is no path from s to some vertex v_i, set d(s, v_i) := Integer.MAX_VALUE.

Two driver classes are provided: Graph and Lab6:

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Graph

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

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

}

}

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Lab6

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

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 < h.noOfVertices; 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 < h.edges[vId].length; 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 < answer.length; 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 <= noOfLines; 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 < size; i++)

{

graph.add(new HashSet());

}

for (int i = 1; i < size; 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 < edges; 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 < size; 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 < size; 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 < size; i++)

{

int par = rng.nextInt(i);

int wei = rng.nextInt(2 * logSize + 1) - logSize;

int fr = -1;

int to = -1;

if (topOrder[par] < topOrder[i])

{

fr = par;

to = i;

}

else

{

fr = i;

to = par;

}

edgeSet.get(fr).put(to, wei);

}

for (int i = 0; i < edges; 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 < size; 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 < deg; 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 < arr.length - 1; i++)

{

int rndInd = rng.nextInt(arr.length - i) + i;

int tmp = arr[i];

arr[i] = arr[rndInd];

arr[rndInd] = tmp;

}

}

}