-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathTopologicalSort.java
More file actions
95 lines (82 loc) · 2.81 KB
/
TopologicalSort.java
File metadata and controls
95 lines (82 loc) · 2.81 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
/**
* Author: Kevin Richardson <[email protected]>
* Date: 11/21/11
* Time: 1:52 PM
*
* Use a topological sort algorithm to return the topological order of the user-chosen
* graph file.
*/
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class TopologicalSort
{
static ListGraph graph;
static Scanner scanner = new Scanner(System.in);
static Queue<Integer> zeroQueue = new LinkedList<Integer>();
static int[] inDegree;
// Get user's desired graph file and run topological sort on it.
public static void main(String[] args)
{
System.out.print("Desired graph file: ");
graph = new ListGraph(scanner.nextLine());
topologicalSort(graph);
}
public static void topologicalSort(ListGraph graph)
{
// Preprocess the graph file.
preprocess(graph);
// while there is an unlisted vertex
int counter = 0;
while(counter < graph.connections.size())
{
// If there is a vertex with inDegree 0...
if(!zeroQueue.isEmpty())
{
// List the node and remove all edges stemming from it.
int node = zeroQueue.remove();
System.out.print(node + " ");
LinkedList<Integer> origin = graph.connections.get(node);
for(Integer destination : origin)
{
inDegree[destination]--;
if(inDegree[destination] == 0)
{
zeroQueue.add(destination);
}
}
}
// Otherwise, a cycle exists and the sort should halt.
else
{
System.out.println("==> A cycle has been detected. Execution has halted.");
break;
}
counter++;
}
}
public static void preprocess(ListGraph graph)
{
// Create an array to track the number of times each node has an incoming connection.
inDegree = new int[graph.connections.size()];
// Create a zero queue (indegree = 0) containing all elements by default.
for(int i = 0; i < graph.connections.size(); i++)
{
zeroQueue.add(i);
}
// Run through the linked lists to count inDegrees.
// If a node ever exists as a destination, remove it from the zeroQueue.
for(LinkedList<Integer> origin : graph.connections)
{
for(Integer destination : origin)
{
inDegree[destination]++;
// If the destination node exists on the zeroQueue, remove it.
if(zeroQueue.contains(destination))
{
zeroQueue.remove(destination);
}
}
}
}
}