summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorHaidong Ji2020-07-12 21:25:07 -0500
committerHaidong Ji2020-07-12 21:25:07 -0500
commitaa6262b550c2fcb417d1ff0a6f4b22ce0c2453e2 (patch)
treeba1c5cda04a80657b075cf6394e408d851541a4f /src
parent4008cc6f7eb547d7e93808b9ba9a87fba9acf0e6 (diff)
Finally Topological sort done! I started from scratch and used Array, not ArrayList, in dfs and explore methods, which helped! I also used IntStream and boxed method to do clever post order array sorting.
Diffstat (limited to 'src')
-rw-r--r--src/main/Toposort.java124
-rw-r--r--src/test/ToposortTest.java8
2 files changed, 31 insertions, 101 deletions
diff --git a/src/main/Toposort.java b/src/main/Toposort.java
index 17cebff..a59ad1a 100644
--- a/src/main/Toposort.java
+++ b/src/main/Toposort.java
@@ -1,134 +1,64 @@
import java.util.ArrayList;
-import java.util.Collections;
import java.util.Scanner;
-import java.util.Stack;
import java.util.Arrays;
+import java.util.stream.IntStream;
public class Toposort {
- private static ArrayList<Integer> toposort(ArrayList<ArrayList<Integer>> adj) {
- boolean[] visited = new boolean[adj.size()];
- Integer[] postv = new Integer[adj.size()];
+ private static ArrayList<Integer> toposort(ArrayList<Integer>[] adj) {
+ boolean[] visited = new boolean[adj.length];
+ ArrayList<Integer> order = new ArrayList<Integer>();
+ int[] postV = new int[adj.length];
int[] clock = new int[1];
- dfs(adj, visited, postv, clock);
+ dfs(adj, visited, postV, clock);
+ // https://stackoverflow.com/questions/951848/java-array-sort-quick-way-to-get-a-sorted-list-of-indices-of-an-array/35701049
+ int[] temp = IntStream.range(0, postV.length).boxed().sorted((i, j) -> postV[i] - postV[j]).mapToInt(ele -> ele).toArray();
+ Arrays.sort(postV);
- Integer[] reverse_postv = postv.clone();
- Arrays.sort(reverse_postv, Collections.reverseOrder());
-
- ArrayList<Integer> order = new ArrayList<>();
-
- for (int n : reverse_postv) {
- order.add(Arrays.asList(postv).indexOf(n));
+ for (int i = adj.length - 1; i > -1; i--) {
+ order.add(temp[i]);
}
-
return order;
-
}
- private static void dfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, Integer[] postv, int[] clock) {
- for (int v = 0; v < adj.size(); v++) {
- if (visited[v] == false)
- explore(adj, v, visited, postv, clock);
+ private static void dfs(ArrayList<Integer>[] adj, boolean[] visited, int[] postV, int[] clock) {
+ for (int v = 0; v < adj.length; v++) {
+ if (!visited[v])
+ explore(v, adj, visited, postV, clock);
}
}
- private static void explore(ArrayList<ArrayList<Integer>> adj, int v, boolean[] visited, Integer[] postv, int[] clock) {
+ private static void explore(int v, ArrayList<Integer>[] adj, boolean[] visited, int[] postV, int[] clock) {
visited[v] = true;
- clock[0] = clock[0] + 1;
-
- for (int n : adj.get(v)) {
- if (visited[n] == false)
- explore(adj, n, visited, postv, clock);
+ for (int w : adj[v]) {
+ if (!visited[w])
+ explore(w, adj, visited, postV, clock);
}
- postv[v] = clock[0];
- clock[0] = clock[0] + 1;
+ postVisit(v, clock, postV);
+ }
+ private static void postVisit(int v, int[] clock, int[] postV) {
+ postV[v] = clock[0];
+ clock[0] = clock[0] + 1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
- ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
+ ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n];
for (int i = 0; i < n; i++) {
- adj.add(new ArrayList<Integer>());
+ adj[i] = new ArrayList<Integer>();
}
for (int i = 0; i < m; i++) {
int x, y;
x = scanner.nextInt();
y = scanner.nextInt();
- adj.get(x - 1).add(y - 1);
+ adj[x - 1].add(y - 1);
}
ArrayList<Integer> order = toposort(adj);
for (int x : order) {
System.out.print((x + 1) + " ");
}
}
-
- static ArrayList<Integer> postOrder(ArrayList<ArrayList<Integer>> adj) {
- boolean[] visited = new boolean[adj.size()];
- ArrayList<Integer> postv = new ArrayList<>(Collections.nCopies(adj.size(), 0));
- int[] clock = new int[1];
- clock[0] = clock[0] + 1;
- for (int v = 0; v < adj.size(); v++) {
- exploreIterative(adj, v, visited, postv, clock);
- }
- return postv;
- }
-
- private static void exploreIterative(ArrayList<ArrayList<Integer>> adj, int v, boolean[] visited, ArrayList<Integer> postv, int[] clock) {
- if (visited[v] == false) {
- // prev[v] = clock[0]
- boolean[] inStack = new boolean[adj.size()];
- clock[0] = clock[0] + 1;
- visited[v] = true;
- inStack[v] = true;
- Stack<Integer> vertexStack = new Stack<>();
- vertexStack.push(v);
-
- while (vertexStack.isEmpty() == false) {
- int tempVertex = vertexStack.peek();
-// if (tempVertex != v) {
-// visited[tempVertex] = true;
-// // prev[v] = clock[0]
-// clock[0] = clock[0] + 1;
-// }
- if (tempVertex != v && visited[tempVertex]) {
- vertexStack.pop();
- continue;
- }
- if (adj.get(tempVertex).size() == 0) {
- if (tempVertex != v) {
- // prev[tempVertex] = clock[0];
- clock[0] = clock[0] + 1;
- visited[tempVertex] = true;
- }
- postv.set(tempVertex, clock[0]);
- clock[0] = clock[0] + 1;
- vertexStack.pop();
- } else {
- boolean allEdgesFollowed = true;
- for (int i : adj.get(tempVertex)) {
- if (visited[i] == false) {
-// visited[i] = true;
- // prev[i] = clock[0]
- if (inStack[i] == false) {
- inStack[i] = true;
- vertexStack.push(i);
- }
- allEdgesFollowed = false;
- }
- }
- if (allEdgesFollowed) {
- visited[tempVertex] = true;
- if (postv.get(tempVertex) == 0)
- postv.set(tempVertex, clock[0]);
- clock[0] = clock[0] + 1;
- vertexStack.pop();
- }
- }
- }
- }
- }
-
}
diff --git a/src/test/ToposortTest.java b/src/test/ToposortTest.java
index e38d3bc..3b8ee8a 100644
--- a/src/test/ToposortTest.java
+++ b/src/test/ToposortTest.java
@@ -20,7 +20,7 @@ class ToposortTest {
adj.get(3).add(0);
ArrayList<Integer> results = new ArrayList<Integer>(Arrays.asList(4, 3, 6, 8));
- assertEquals(results, Toposort.postOrder(adj));
+ //assertEquals(results, Toposort.postOrder(adj));
}
@Test
@@ -45,7 +45,7 @@ class ToposortTest {
adj.get(4).add(0);
ArrayList<Integer> results = new ArrayList<Integer>(Arrays.asList(2, 7, 6, 5, 4));
- assertEquals(results, Toposort.postOrder(adj));
+ //assertEquals(results, Toposort.postOrder(adj));
}
@Test
@@ -70,7 +70,7 @@ class ToposortTest {
adj.get(4).add(0);
ArrayList<Integer> results = new ArrayList<Integer>(Arrays.asList(2, 7, 6, 5, 4));
- assertEquals(results, Toposort.postOrder(adj));
+ //assertEquals(results, Toposort.postOrder(adj));
}
@Test
@@ -102,7 +102,7 @@ class ToposortTest {
adj.get(4).add(2);
ArrayList<Integer> results = new ArrayList<Integer>(Arrays.asList(13, 7, 9, 5, 10, 3, 11, 6, 12, 8));
- assertEquals(results, Toposort.postOrder(adj));
+ //assertEquals(results, Toposort.postOrder(adj));
}
} \ No newline at end of file