forked from lemonbashar/java-algo-expert
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTopologicalSort.java
More file actions
144 lines (125 loc) · 4.38 KB
/
TopologicalSort.java
File metadata and controls
144 lines (125 loc) · 4.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
package algoexpert.hard;
import java.util.*;
/*
ROUGH
-----
Input -> list of jobs ; dependencies d1 -> d2
Output -> order of execution
EXAMPLE
========
Input : [1,2,3,4], [ [1,2], [1,3], [3,2], [4,2], [4,3]]
Output : [1,4,3,2] or [4,1,3,2]
LOGIC (DFS)
===========
create hash map for each job
create set for each traversed
go through the dependencies
at each job : add list of dependencies | O(d)
{
1 : []
2 : [1, 4]
3 : [1, 2, 4]
4 : []
}
for each key | if not traversed
if empty -> add
if not empty -> go to first node & remove first node O(n)
also need cycle detection
SOLUTION
========
1. DFS
time : O(j + d) | space : O(j + d)
space complexity of a graph outweighs the complexity you get from DFS
*/
public class TopologicalSort
{
public static void test1()
{
List<Integer> jobs = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8));
Integer[][] depsArray = new Integer[][] {{3, 1}, {8, 1}, {8, 7}, {5, 7}, {5, 2}, {1, 4}, {1, 6}, {1, 2}, {7, 6}};
List<Integer[]> deps = new ArrayList<>();
for (Integer[] d : depsArray) { deps.add(d); }
System.out.println(topologicalSort(jobs, deps));
}
public static void test2()
{
List<Integer> jobs = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8));
Integer[][] depsArray = new Integer[][] {{3, 1}, {8, 1}, {8, 7}, {5, 7}, {5, 2}, {1, 4}, {6, 7}, {1, 2}, {7, 6}};
List<Integer[]> deps = new ArrayList<>();
for (Integer[] d : depsArray) { deps.add(d); }
System.out.println(topologicalSort(jobs, deps));
}
public static void test3()
{
List<Integer> jobs = new ArrayList<Integer>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12));
Integer[][] depsArray =
new Integer[][] {
{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8},
{7, 8}, {2, 3}, {2, 4}, {5, 4}, {7, 6}, {6, 2}, {6, 3}, {6, 5}, {5, 9}, {9, 8}, {8, 0},
{4, 0}, {5, 0}, {9, 0}, {2, 0}, {3, 9}, {3, 10}, {10, 11}, {11, 12}, {2, 12},
};
List<Integer[]> deps = new ArrayList<>();
for (Integer[] d : depsArray) { deps.add(d); }
System.out.println(topologicalSort(jobs, deps));
}
public static void test()
{
test1();
test2();
test3();
}
public static void addDependencies(List<Integer[]> deps, Map<Integer, List<Integer> > dependencies )
{
for (Integer [] pair : deps)
{
int job = pair[1];
int dependsOn = pair[0];
if (!dependencies.containsKey(job))
{
ArrayList<Integer> d = new ArrayList<Integer> ();
d.add(dependsOn);
dependencies.put(job, d);
}
else
{
List<Integer> d = dependencies.get(job);
d.add(dependsOn);
dependencies.put(job, d);
}
}
}
public static boolean traverse(int job, Set<Integer> traversed, Map<Integer, List<Integer>> dependencies, ArrayList<Integer> solution, Set<Integer> currentCall )
{
if (currentCall.contains(job)) { return true; }
currentCall.add(job);
if (traversed.contains(job)) { return false; }
boolean cycle = false;
if (dependencies.containsKey(job))
{
List<Integer> dependsOn = dependencies.get(job); // dependsOn
for (int d : dependsOn)
{
if (traversed.contains(d)) { continue; }
cycle = cycle || traverse(d, traversed, dependencies, solution, currentCall);
}
}
solution.add(job);
traversed.add(job);
currentCall.remove(job);
return cycle;
}
public static List<Integer> topologicalSort(List<Integer> jobs, List<Integer[]> deps)
{
Set<Integer> traversed = new HashSet<Integer> ();
Map<Integer, List<Integer> > dependencies = new HashMap<>();
addDependencies(deps, dependencies);
ArrayList<Integer> solution = new ArrayList<>();
for (int job : jobs)
{
Set<Integer> currentCall = new HashSet<Integer> ();
boolean cycle = traverse(job, traversed, dependencies, solution, currentCall );
if (cycle) { return new ArrayList<Integer>(); }
}
return solution;
}
}