-
Notifications
You must be signed in to change notification settings - Fork 1
Enumeration of all Permutations (Recursion, Single Swap, and in Lexicographic Order), and Combinations. Enumeration of all Topological Orderings on a Directed Graph. Enumeration of all Paths in a connected Graph. Evaluates Critical Path using PERT Algorithm.
License
rahul1947/LP4-PERT-Enumeration-of-Topological-Orders
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
# Long Project LP4: PERT, Enumeration of Topological Orders # Team: LP101 * Rahul Nalawade (https://github.com/rahul1947) [email protected] * Prateek Sarna (https://github.com/prateek5795) [email protected] * Bhavish Khanna Narayanan (https://github.com/bhavish14) [email protected] # End Date: * Sunday, November 25, 2018 _______________________________________________________________________________ # PROBLEM STATEMENT: 1. Implement Enumeration of Permutations and Combinations in Enumerate.java. It also contains methods for other Enumeration problem which is optional for implementation. 2. Implement Enumeration of all Topological Orders of a given directed graph in EnumerateTopological.java. 3. Implement PERT algorithm with all the methods in PERT.java. Input: 1. G = (V,E), G must be a DAG 2. duration(u) = {0, 1, 2, ...}, where u is a node (task) in V. Output: 1. Critical Path Length (Minimum time to complete Project) 2. slack(u): Slack available for each node (task) 3. EC(u): Earliest Completion Time for each node 4. LC(u): Latest Completion Time for each node /** * Implement PERT algorithm by computing all the necessary output values. * Run PERT algorithm on graph g. Assume that vertex 1 is s and vertex n is t. * You need to add edges from s to all vertices and from all vertices to t. */ public static PERT pert(Graph g, int[] duration) {...} // non-static method called after calling the constructor public boolean pert(); The following methods can be called to query the results, after running one of the above methods: public int ec(Vertex u); // Earliest completion time of u public int lc(Vertex u); // Latest completion time of u public int slack(Vertex u); // Slack of u public int criticalPath(); // Length of critical path public boolean critical(Vertex u); // Is vertex u on a critical path? public int numCritical(); // Number of critical nodes in graph _______________________________________________________________________________ # DESCRIPTION: #1. Enumerate.java: ATTRIBUTES: ----------- - T[] arr: Array of elements on which enumeration is to be done. n = arr.length - k: number of elements to be selected (default = n). E.g nPk or nCk. - count: counts the number of times visit has been called based on the Approver. APPROVER<T>: ------------ - Responsible for selection and de-selection (backtracking) of an element based on certain precedence constraints coded in select() and unselect() methods respectively. - visit() is called by non-static visit() to print the k elements in the arr[0...k-1] METHODS: -------- A. permute(c): recursive method to visit all valid permutations, where c is number of elements yet to visit. B. combine(i, c): recursive method to visit all valid combinations, where c is the number of element we need to choose from arr[i...n-1]. C. heap(g): recursive method to visit all permutations by a single swap from previous permutation, where first g elements are not frozen, i.e. arr[g...n-1] are frozen, and arr[0..g-1] can only be changed. D. algorithmL(Comparator c): Knuth's L Algorithm based on Comparator c. ------------------------------------------------------------------------------- #2. EnumerateTopological.java: ATTRIBUTES: ----------- - print: boolean if true prints all enumerations, else no printing. - selector: Approver of EnumerateTopological itself. - Vertex[] A: array of vertices in the Graph. SELECTOR extended from APPROVER<T> ---------------------------------- - select(u): selects u, if it has inDegrees = 0. - unselect(u): do v.inDegrees++, where edge e = (u,v) exists. METHODS: -------- A. initialize(): initializes get(u).inDegrees = u.inDegree for all u. B. enumerateTopological(): based on selector, enumerates all permutations using permute() from Enumerate. Returns count of enumerations from Enumerate itself. NOTE: Counting and Enumerating Topological Orders uses the same algorithm. ------------------------------------------------------------------------------- #3. PERT.java: PERTVertex: ----------- - duration: duration of this vertex - slack: slack available for this vertex - earliestCT: earliest completion time (EC) for this vertex - latestCT: latest completion time (LC) for this vertex METHODS: -------- A. initialize(): add edges from source (first vertex) to all vertices, and all vertices to the sink (last vertex). B. pert(): Implements PERT by computing slack, EC, LC for all vertices. Returns true if Graph is not a DAG, false otherwise. NOTE: it uses a topological order from DFS.java _______________________________________________________________________________ # RESULTS: # Enumerate: $java rsn170330.Enumerate Permutations: 4 3 1 2 3 1 2 4 1 3 2 ... 4 1 3 4 1 2 Count: 24 _________________________ Combinations: 4 3 1 2 3 1 2 4 1 3 4 2 3 4 Count: 4 _________________________ Heap Permutations: 4 1 2 3 4 2 1 3 4 3 1 2 4 ... 3 2 4 1 2 3 4 1 Count: 24 _________________________ Algorithm L Permutations: 1 2 2 3 3 4 1 2 2 3 4 3 1 2 2 4 3 3 ... 4 3 3 2 1 2 4 3 3 2 2 1 Count: 180 _________________________ # Enumerate Topological: $ java rsn170330.EnumerateTopological 0 rsn170330/lp4-test/enumtop-t08.txt +-------------------------------------------------------------------------+ | File | |V| |E| | Output | Time (mSec) | Memory (used/avail) | |-------------------------------------------------------------------------| | enumtop-t01 | 7 6 | 105 | 2 | 1 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t02 | 8 9 | 280 | 4 | 1 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t03 | 8 11 | 118 | 3 | 1 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t04 | 10 30 | 20 | 2 | 1 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t05 | 20 100 | 3864 | 14 | 3 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t06 | 30 300 | 107136 | 60 | 7 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t07 | 40 500 | 38052 | 31 | 5 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t08 | 50 800 | 6193152 | 1390 | 7 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t09 | 50 900 | 552960 | 653 | 4 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t10 | 100 4000 | 29160 | 612 | 12 MB / 117 MB | |-------------------------------------------------------------------------| | enumtop-t11 | 200 18000 | 768000 | 2512 | 22 MB / 147 MB | +-------------------------------------------------------------------------+ NOTE: |V|: Number of Vertices in the Graph |E|: Number of Edges in the Graph Output: Total number of all valid permutations of Topological Orderings Refer Results/lp4-enumtop.txt as obtained from $ ./lp4-enumtop.sh > lp4-enumtop.txt _______________________________________________________________________________ # PERT: $ java rsn170330.PERT false rsn170330/lp4-test/pert-t04.txt +-------------------------------------------------------------------------+ | File | |V| |E| | Output | Time (mSec) | Memory (used/avail) | |-------------------------------------------------------------------------| | pert-t01 | 102 300 | 183 20 | 5 | 2 MB / 117 MB | |-------------------------------------------------------------------------| | pert-t02 | 52 1200 | 98 52 | 6 | 4 MB / 117 MB | |-------------------------------------------------------------------------| | pert-t03 | 102 1000 | 97 34 | 5 | 4 MB / 117 MB | |-------------------------------------------------------------------------| | pert-t04 | 502 675 | 89 64 | 9 | 3 MB / 117 MB | |-------------------------------------------------------------------------| | pert-t05 | 1002 1166 | 61 46 | 12 | 5 MB / 117 MB | |-------------------------------------------------------------------------| | pert-t06 | 502 6000 | 596 57 | 12 | 16 MB / 117 MB | |-------------------------------------------------------------------------| | pert-t07 | 502 6000 | 84 65 | 11 | 16 MB / 117 MB | |-------------------------------------------------------------------------| | pert-t08 | 1002 6000 | 99 26 | 12 | 17 MB / 117 MB | |-------------------------------------------------------------------------| | pert-t09 | 1002 6000 | 323 42 | 14 | 17 MB / 117 MB | +-------------------------------------------------------------------------+ NOTE: Output: x y x: Minimum Time needed to complete the Project/ Critical Path Length y: Number of Critical Nodes in the Graph Refer Results/lp4-pert.txt as obtained from $ ./lp4-pert.sh > lp4-pert.txt NOTE: - Time and Memory might change, as you run the test the program on a different system, but they could be comparable to the above values. Existing Processor: Intel® Core™ i5-8250U CPU @ 1.60GHz × 8 Memory: 7.5 GiB - EnumeratePath.java consist of extended version of this project where all paths from source (first vertex) to sink (last vertex) could be enumerated using two algorithms - with and without Selector/ Approver. NOTE: It uses VertexStack<T> of itself instead of java Stack. _______________________________________________________________________________ # HOW TO RUN: 1. Extract the rsn170330.zip 2. Compile: $ javac rsn170330/*.java 3. Run: [a] Enumerate.java: $ java rsn170330.Enumerate n k where combinations = nCk, permutations = nPk, i.e. n :- number of distinct elements k :- number of elements to choose from n NOTE: by default n = 4, k = 3 ----------------------------------------------------------------------------- [b] EnumerateTopological: $ java rsn170330.EnumerateTopological [arg0] [arg1] $ java rsn170330.EnumerateTopological 0 rsn170330/lp4-test/enumtop-t08.txt [arg0] :- true for verbose i.e. to print all topological orders, otherwise no enumeration of topological orders [arg1] :- file containing the graph NOTE: by default, verbose = false and it has a simple graph in it's main() ----------------------------------------------------------------------------- [c] EnumeratePath: $ java rsn170330.EnumeratePath [arg0] [arg1] $ java rsn170330.EnumeratePath 1 [arg0] :- true for verbose i.e. to print all paths, otherwise no enumeration of paths [arg1] :- file containing the graph. NOTE: by default, verbose = false and it has a simple graph in it's main() ----------------------------------------------------------------------------- [d] PERT: $ java rsn170330.PERT [arg0] [arg1] $ java rsn170330.PERT false rsn170330/lp4-test/pert-t04.txt [arg0] :- true for details i.e. to print the PERT chart, otherwise no chart [arg1] :- file containing the graph. NOTE: by default, details = false and it has a simple graph in it's main() ----------------------------------------------------------------------------- NOTE: the current directory must contain rbk directory with rbk/Graph.java _______________________________________________________________________________
About
Enumeration of all Permutations (Recursion, Single Swap, and in Lexicographic Order), and Combinations. Enumeration of all Topological Orderings on a Directed Graph. Enumeration of all Paths in a connected Graph. Evaluates Critical Path using PERT Algorithm.
Topics
Resources
License
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published