-
Notifications
You must be signed in to change notification settings - Fork 1
/
EnumerateTopological.java
169 lines (132 loc) · 4.92 KB
/
EnumerateTopological.java
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
package rsn170330.lp4;
import java.io.File;
import java.util.Scanner;
import rbk.Graph;
import rbk.Graph.GraphAlgorithm;
import rbk.Graph.Vertex;
import rbk.Graph.Edge;
import rbk.Graph.Factory;
/**
* CS 5V81.001: Implementation of Data Structures and Algorithms
* Long Project LP4: PERT, Enumeration of topological orders
*
* Team: LP101
* @author Rahul Nalawade (rsn170330)
* @author Prateek Sarna (pxs180012)
* @author Bhavish Khanna Narayanan (bxn170002)
*/
// Code for enumerating topological orders of a DAG
public class EnumerateTopological extends
GraphAlgorithm<EnumerateTopological.EnumVertex> {
private boolean print; // set true to print array in visit
private Selector selector; // Approver of EnumerateTopological itself
private Vertex[] A; // array of all vertices
// ------------------------- Constructor ---------------------------------
public EnumerateTopological(Graph g) {
super(g, new EnumVertex());
//tOrders = 0; // # topological orders visited
print = false; // no printing
selector = new Selector(); // will approve selection of an element
// passed as an array to Enumerate object
A = g.getVertexArray();
initialize(); // initializes inDegrees of each vertex in Graph g
}
// ------------------------- EnumVertex ----------------------------------
static class EnumVertex implements Factory {
int inDegrees; // number of incoming edges on a vertex
EnumVertex() { inDegrees = 0; }
public EnumVertex make(Vertex u) {
return new EnumVertex();
}
}
// -------------------------- Selector -----------------------------------
class Selector extends Enumerate.Approver<Vertex> {
/* Selects vertex u only if it has no incoming edge onto it. */
@Override
public boolean select(Vertex u) {
// When u has no incoming edge
if (get(u).inDegrees == 0) {
// As u is selected, decrement inDegrees of it's children
for (Edge e : g.incident(u)) {
Vertex v = e.otherEnd(u);
get(v).inDegrees--;
}
return true;
}
// NOTE: selector won't approve any cycle in the graph :)
return false;
}
/* Un-selects selected vertex by incrementing count of inDegrees. */
@Override
public void unselect(Vertex u) {
// Increment count v as u is un-selected for each edge(u,v)
for (Edge e : g.incident(u)) {
Vertex v = e.otherEnd(u);
get(v).inDegrees++;
}
}
/* Visits array with first k elements. Prints them if needed. */
@Override
public void visit(Vertex[] arr, int k) {
if (print) {
for (Vertex u : arr) {
System.out.print(u + " ");
}
System.out.println();
}
}
}
/* Initializes the inDegrees of each vertex in the Graph. */
private void initialize() {
for (Vertex u : g) {
get(u).inDegrees = u.inDegree();
}
}
/**
* Gives count of all Enumerations of Topological ordering of Graph g.
*
* Precondition: updated inDegrees of all vertices in the Graph.
*
* @param flag do we need to print all enumerations?
* @return number of all topological enumerations
*/
public long enumerateTopological(boolean flag) {
print = flag;
Enumerate<Vertex> en = new Enumerate<>(A, selector);
en.permute(A.length); // k = no of vertices
return en.count;
}
// -------------------------- STATIC METHODS -----------------------------
public static long countTopologicalOrders(Graph g) {
EnumerateTopological et = new EnumerateTopological(g);
return et.enumerateTopological(false);
}
public static long enumerateTopologicalOrders(Graph g) {
EnumerateTopological et = new EnumerateTopological(g);
return et.enumerateTopological(true);
}
// --------------------------- MAIN METHOD -------------------------------
public static void main(String[] args) throws Exception {
boolean VERBOSE = false;
if (args.length > 0) { VERBOSE = Boolean.parseBoolean(args[0]); }
Scanner in;
String graph = "10 12 1 3 1 1 8 1 6 8 1 6 10 1 3 2 1 8 2 1 8 5 1 5 10 1 2 4 1 5 4 1 4 7 1 10 9 1 0"; // class notes - 110
// graph = "7 6 1 2 1 1 3 1 2 4 1 3 4 1 3 5 1 6 7 1 0"; // enumtop-t01.txt - 105
// graph = "8 9 1 2 1 2 3 1 3 4 1 1 3 1 1 4 1 2 4 1 5 6 1 6 7 1 5 7 1 0"; // enumtop-t02.txt - 280
// graph = "8 11 1 2 1 2 3 1 3 4 1 1 3 1 1 4 1 2 4 1 5 6 1 6 7 1 5 7 1 2 8 1 6 8 1 0"; // enumtop-t03.txt - 118
// graph = "3 3 1 2 1 2 3 1 3 1 1 0"; // a cycle - 0
// If there is a command line argument, use it as file from which
// input is read, otherwise use input from string.
in = (args.length > 1) ? new Scanner(new File(args[1])) : new Scanner(graph);
Graph g = Graph.readDirectedGraph(in);
//g.printGraph(false); // UNCOMMENT TO PRINT THE GRAPH
long result;
Graph.Timer t = new Graph.Timer();
if (VERBOSE) {
result = enumerateTopologicalOrders(g);
} else {
result = countTopologicalOrders(g);
}
System.out.println("\n" + result + "\n" + t.end());
}
}