# Test Data of Programming Assignment #4 A project of 13 tasks labeled 0,1,….,12 with the following data: Task Predecessors Time needed for the task 0 Null 2 1 0 4 2 0 5 3 0 9 4 1 3 5 1,2,3 2 6 4,5 1 7...

Test Data of Programming Assignment #4
A project of 13 tasks labeled 0,1,….,12 with the following data:
Predecessors
0
Null
2
1
0
4
2
0
5
3
0
9
4
1
3
5
1,2,3
2
6
4,5
1
7
5
10
8
3
11
9
6,7
6
10
8
9
11
8
8
12
9,10,11
7

CS3310 Design and Analysis of Algorithms XXXXXXXXXXProgramming Assignment #4
The Critical Path Procedure (CPM) can be described as follows:
Method1:We assume there are a precedence constraints described by acyclic graph and there is only one final task( if there is no final task you may create a dummy task with zero time to complete).
The parameters ES(earliest start time ) , EF(earliest finish time), LS(latest start time), and LF(latest start time) of every task is computed by two passes through the graph. The first two parameters are computing during a forward pass from the initial tasks (those without any predecessor) to the final task as follows:
For each initial task ES=0 and EF= the time needed to complete the task
If the task A has P1 , P2,…Pk as immediate predecessor tasks , then ES of A = max(EF of P1 ,EF of P2,……,EF of Pk), and
EF of A = ES + the time needed to complete the task A
The parameters LS and LF are computed during a backward pass from the final task to the initial tasks as follows:
LS and LF of the final task are exactly ES and EF of the final task, respectively.
If the task B has P1, P2 ,…., Pk as immediate successor tasks, then LF of B= min( LS of P1, LS of P2,…..LS of Pk), and
LS of B= LF -the time needed to complete the task B.
Define the class Node which includes the attributes: Task Name, Time to complete the task, ES, EF, LS, and LF. Let T be an a
ay of n objects of type Node. The initial values of the four parameters ES, EF,LS, and LF are set to zero. The precedence constrains are defined by a graph represented by the adjacency matrix G. You may use the topological sorting algorithm for ordering the tasks( Why do we need topological sorting?).
Use the Class Node, the a
ay T, and the matrix G to write the Critical Path Method for computing the minimum completion time of a given project consists of many tasks, and determining the critical tasks and also determining the possible delay for each task without changing the minimum completion time. Assume the time needed to complete each task is given.
The parameter slack is defined for reach task as LS-ES. A task is critical if and only if its slack = 0
Slack is the amount of time that an activity can be delayed past its earliest start or earliest finish without delaying the project.
Method2:
As follows the outline for implementing this programming assignment:
Write an algorithm for computing the ES, EF, LS, and LF for every task using the following data structures:
The tasks are labeled 1, 2,….n.
The a
ays ES[], EF[] ,LS[] , LF[], and T[]
Where ES[i] represents the earliest start time of the task i;
EF[i] represents the earliest finish time of i;
LS[i] represents latest start time of the task i;
LF[i] represents latest finish time of the task I;
T[i] represents the required time to complete the task i.
The graph of the project is represented by the incidence matrix (adjacency matrix) A[][],
Where A[i][j] = 1 iff the task j is an immediate successor of the task i.
The a
ay TS[] represents the sequence of the tasks listed according to the Topological soring.
Note that If the task A has P1 , P2,…Pk as immediate predecessor tasks , then ES of A = max(EF of P1 ,EF of P2,……,EF of Pk), and
EF of A = ES + the time needed to complete the task A
The parameters LS and LF are computed during a backward pass from the final task to the initial tasks as follows:
If the task B has P1, P2 ,…., Pk as immediate successor tasks, then LF of B= min( LS of P1, LS of P2,…..LS of Pk), and
LS of B= LF -the time needed to complete the task B.
Answered 7 days AfterAug 01, 2021

## Solution

Shashi Kant answered on Aug 09 2021
Assg/data.csv
0,,2
1,0,4
2,0,5
3,0,9
4,1,3
5,1 2 3,2
6,4 5,1
7,5,10
8,3,11
9,6 7,6
10,8,9
11,8,8
12,9 10 11,7
End,9 10 11,7
Assg/output.png
Assg/test.py
import networkx as nx
import numpy as np
import pandas as pd
import pyla
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not start in graph.keys():
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
for index, row in Df.ite
ows():
if str(row["Predecessors"])=='nan':
pass
else:
acts=str(row["Predecessors"]).split(" ")
for act in acts:
...
SOLUTION.PDF