DAG implementation I\'m having a lot of trouble of even starting this program, n
ID: 3691829 • Letter: D
Question
DAG implementation
I'm having a lot of trouble of even starting this program, not being able to use the STL is a real hinderance.
You are to implement a scheduling algorithm that will schedule tasks in a directed acyclic network graph (DAG). I strongly suggest that you use algorithms discussed in class and summarized in power point presentation(s) to complete this task.
• A “create” command, with syntax c # to create a new node for the DAG • An “arc” command, with syntax p, s, # where p (predecessor) is the number of the tail of the arc (using the text’s terminology) and s (successor) being the head of the directed arc. So, below is a sample input file that I will use in this discussion.
Output: The output of your program should be sent to standard output (cout or printf) and should include the following information: • The length of the critical path of the DAG (6 for our example) • A list of all nodes on one or more critical paths (1, 4, 5 four our example) • A listing of a schedule to complete the task which might look something like the following for our example
Requirements:
C++
Use separate classes for DAG, DAGNode DataReadySet
Not include any templates from the Standard Template Library
So, below is a sample input file that I will use in this discussion. - Input file c 1 C 2 a 1 2 1 a 13 1 a 1 4 1 a 2 53 a 354 a 4 55 - end of input fileExplanation / Answer
main.cpp
#include <iostream>
#include <string>
#include "dag.hpp"
using namespace std;
int main() {
DAG mainDAG;
mainDAG.findSink();
mainDAG.findNodeHeights(mainDAG.getSink());
mainDAG.printCriticalData();
mainDAG.makeSchedule();
return 0;
}
dag.cpp
/*
* This file contains the method definitions for the DAGNode, DAG, and
* DataReadySet classes, as well as the constructor definitions.
*
* */
#include <iostream>
#include <iomanip>
#include <string>
#include "dag.hpp"
using namespace std;
// Constructor for DAGNode. It's more convenient to initialize height,
// successorNode and completionTime here than it is in a separate method
DAGNode::DAGNode() {
height = 0;
successorNode = -1;
completionTime = 0;
classification = NORMAL;
}
DAG::DAG() {
// Variables for keeping track of current amount of nodes, and when
// to start reading in edge lengths
int nodeReadingFinished = 0, numberNodes, pred, succ, weight;
string inputTypeSpecifier, extra;
// First number from input is the number of crews
cin >> numCrews;
// Read in data until EOF
while (cin >> inputTypeSpecifier) {
if (inputTypeSpecifier == "c")
cin >> numberNodes;
else if (inputTypeSpecifier == "a") {
if (nodeReadingFinished == 0) {
// This code executes once node reading is finished,
// so allocation can begin for the adjacency matrix
// and the node array
adjMatrix = new int*[numberNodes];
for (int i = 0; i < numberNodes; ++i) {
adjMatrix[i] = new int[numberNodes];
// Set initial edge lengths to 0
for (int j = 0; j < numberNodes; ++j)
adjMatrix[i][j] = 0;
}
nodeArray = new DAGNode[numberNodes];
numNodes = numberNodes;
// Read in first edge data
cin >> pred >> succ >> weight;
adjMatrix[pred - 1][succ - 1] = weight;
nodeReadingFinished = 1;
}
else {
cin >> pred >> succ >> weight;
adjMatrix[pred - 1][succ - 1] = weight;
}
}
}
}
// Method definition for finding the sink. This is important, since
// the sink is the node where the backflow algorithm begins.
void DAG::findSink() {
// Iterate through loop. If loop completes without finding any
// successors for the current node represented by i, then that
// node is the sink. There is only one sink, according to the
// instructions, so once it is found, there is no reason to continue
// searching for it.
int j;
for (int i = 0; i < numNodes; ++i) {
for (j = 0; j < numNodes; ++j)
if (adjMatrix[i][j] > 0)
break;
// j only equals numNodes if no successor's were found
if (j == numNodes) {
sink = i;
return;
}
}
}
// Recursive algorithm for finding the height, successor node, and
// completion time of each node / task
void DAG::findNodeHeights(int currentNode) {
// Height adjustment. This checks for successors, and if one is
// found, it'll adjust height to the larger of current height
// or the successor's height plus the edge length, as well as set
// the successorNode and completionTime of the current node, which
// is useful for later finding the critical path as well as scheduling
for (int j = 0; j < numNodes; ++j)
if (adjMatrix[currentNode][j] > 0)
if (nodeArray[currentNode].getHeight() < nodeArray[j].getHeight() + adjMatrix[currentNode][j]) {
nodeArray[currentNode].setHeight(nodeArray[j].getHeight() + adjMatrix[currentNode][j]);
nodeArray[currentNode].setSuccessorNode(j);
nodeArray[currentNode].setCompletionTime(adjMatrix[currentNode][j]);
}
// Recursive part of algorithm. Is called on all predecessor's of
// whatever the current node is. Due to the nature of the adjacency matrix
// and DAGs, eventually nodes without predecessor's will be reached.
for (int i = 0; i < numNodes; ++i)
if (adjMatrix[i][currentNode] > 0)
findNodeHeights(i);
}
// Constructor for DataReadySet
DataReadySet::DataReadySet(int numNodes) {
readyArray = new status[numNodes];
for (int i = 0; i < numNodes; ++i)
readyArray[i] = UNREADY;
}
// This prints the critical data
void DAG::printCriticalData() {
// Find node with highest height
int highestNode = 0, nextNode;
for (int i = 0; i < numNodes; ++i)
if (nodeArray[i].getHeight() > nodeArray[highestNode].getHeight())
highestNode = i;
// Print highest height, which is the critical path length, along
// with first node in critical path
cout << "Critical Path Length: " << nodeArray[highestNode].getHeight() << endl;
cout << "Critical Path Nodes: " << highestNode + 1;
// Go through node successor chain, until all nodes in critical path
// have been printed
nextNode = nodeArray[highestNode].getSuccessorNode();
while (nextNode > 0) {
cout << ", " << nextNode + 1;
nextNode = nodeArray[nextNode].getSuccessorNode();
}
}
// Verify that all predecessors were scheduled
bool DAG::isPredecessor(int currentNode, int predecessorToCheck, int n) {
bool yes = false;
for (int i = 0; i < numNodes; ++i) {
if (adjMatrix[i][currentNode] > 0) {
if (i == predecessorToCheck) {
yes = true;
break;
}
else
yes = isPredecessor(i, predecessorToCheck, n + 1);
}
}
return yes;
}
// The scheduling algorithm. This is a mess, but it (hopefully) works.
void DAG::makeSchedule() {
// Variables
int **schedule, currCrew, *crewPos, currNode = -1, nodesScheduled = 0, k;
bool valid = false;
DataReadySet readySet(numNodes);
crewPos = new int[numCrews];
// Initialize crew position values
for (int i = 0; i < numCrews; ++i)
crewPos[i] = 0;
// Initialize 2D schedule matrix
schedule = new int*[numCrews];
for (int i = 0; i < numCrews; ++i) {
schedule[i] = new int[numNodes * numNodes];
for (int j = 0; j < numNodes * numNodes; ++j)
schedule[i][j] = -1;
}
// Sink needs completion time of one
nodeArray[sink].setCompletionTime(1);
// Begin the scheduling. Keep going until the number of nodes scheduled
// is equal to the amount of nodes, and then print out the schedule
while (nodesScheduled < numNodes) {
// Update ready status of nodes. Set each node to READY as it goes
// along, unless an UNREADY predecessor is found
for (int i = 0; i < numNodes; ++i)
if (readySet.getStatus(i) == UNREADY) {
readySet.ready(i);
for (int j = 0; j < numNodes; ++j)
if (adjMatrix[j][i] > 0)
if (readySet.getStatus(j) != SCHEDULED)
readySet.unready(i);
}
// Choose ready node with the highest height. Chances are,
// this is the node that must be scheduled next
currNode = -1;
for (int i = 0; i < numNodes; ++i)
if (readySet.getStatus(i) == READY) {
if (currNode == -1)
currNode = i;
else if (nodeArray[i].getHeight() > nodeArray[currNode].getHeight())
currNode = i;
}
// Choose crew with lowest available index, defaulting to crew 0
currCrew = 0;
for (int i = 0; i < numCrews; ++i)
if (crewPos[i] < crewPos[currCrew])
currCrew = i;
// Now, make sure that there would be no scheduling conflicts in
// ANY part of the currPos in all crews.
valid = false;
while (valid == false) {
// True until otherwise as such
valid = true;
//for (int i = 0; i < numNodes && valid == true; ++i)
//if (adjMatrix[i][currNode] > 0)
for (int j = 0; j < numCrews; ++j)
//if (schedule[j][crewPos[currCrew]] == i) {
if (schedule[j][crewPos[currCrew]] != -1 && isPredecessor(currNode, schedule[j][crewPos[currCrew]], 0)) {
valid = false;
crewPos[currCrew] += 1;
}
}
// Finally, do the scheduling
for (k = crewPos[currCrew]; k < (crewPos[currCrew] + nodeArray[currNode].getCompletionTime()); ++k)
schedule[currCrew][k] = currNode;
// Adjust crewPos for the currCrew to the value of k
crewPos[currCrew] = k;
// Adjust scheduled data
cout << endl << currNode + 1;
readySet.scheduled(currNode);
nodesScheduled++;
}
// Schedule Printing
// Top Border area with column labels
cout << " *** SCHEDULE ***" << endl;
cout << "--------------";
for (int i = 0; i < numCrews; ++i)
cout << "---------";
cout << endl;
cout << "| Time Units |";
for (int i = 0; i < numCrews; ++i)
cout << " Crew " << i + 1 << " |";
cout << " --------------";
for (int i = 0; i < numCrews; ++i)
cout << "---------";
cout << endl;
for (int i = 0; i < numNodes * numNodes; ++i) {
// Before printing row, check to see if there's still values
// to print
valid = false;
for (int j = 0; j < numCrews; ++j)
if (schedule[j][i] > -1)
valid = true;
// If valid is false, end row printing
if (valid == false)
break;
// Print time unit
cout << "| ";
cout << setw(6) << right << i + 1 << " |";
// Print each crew's data
for (int j = 0; j < numCrews; ++j)
if (schedule[j][i] > -1) {
if (readySet.getStatus(schedule[j][i]) != PRINTED) {
readySet.printed(schedule[j][i]);
cout << setw(5) << right << schedule[j][i] + 1 << " |";
}
else
cout << " |";
}
else
cout << " |";
cout << endl;
}
// Print bottom row
cout << "--------------";
for (int i = 0; i < numCrews; ++i)
cout << "---------";
cout << endl;
}
dag.hpp
/*
* This file contains the class definition code for the DAG, DAGNode,
* and DataReadySet classes, as well as two enums for the type of node
* and scheduled status.
*
* */
enum type {NORMAL, SINK};
enum status {UNREADY, READY, SCHEDULED, PRINTED};
class DAGNode {
private:
int height;
int successorNode;
int completionTime;
type classification;
public:
DAGNode();
void setHeight(int newHeight) {height = newHeight;};
void setSuccessorNode(int newSuccessor) {successorNode = newSuccessor;};
void setCompletionTime(int newCompletionTime) {completionTime = newCompletionTime;};
int getHeight() {return height;};
int getSuccessorNode() {return successorNode;};
int getCompletionTime() {return completionTime;};
};
class DataReadySet {
private:
status *readyArray;
public:
DataReadySet(int numNodes);
status getStatus(int node) {return readyArray[node];};
void ready(int node) {readyArray[node] = READY;};
void unready(int node) {readyArray[node] = UNREADY;};
void scheduled(int node) {readyArray[node] = SCHEDULED;};
void printed(int node) {readyArray[node] = PRINTED;};
};
class DAG {
private:
int **adjMatrix;
DAGNode *nodeArray;
int numNodes;
int numCrews;
int sink;
public:
DAG();
void findSink();
void TESTING();
void findNodeHeights(int currentNode);
void printCriticalData();
void makeSchedule();
bool isPredecessor(int currentNode, int predecessorToCheck, int n);
int getEdgeWeight(int row, int col) {return adjMatrix[row][col];};
DAGNode *getNode(int num) {return &nodeArray[num];};
int getNumNodes() {return numNodes;};
int getNumCrews() {return numCrews;};
int getSink() {return sink;};
};
scheduling_test.txt
0 T0 T1
1
2 T3
3
4
5 T6
6 T4
7
8
9
10
11
12 T7
13
14
15 T2
16 T5
17
18
19
20
21
22
23
24 T8
25
26
27
28
29
30
31 T9
32
33
34
35
36
37 DONE DONE
0 T0 T1
1
2 T3
3
4
5 T6
6 T4
7
8
9 T2
10 T5
11
12 T7
13
14
15
16
17
18
19
20
21 T8
22
23
24
25
26
27
28
29
30
31 T9
32
33
34
35
36
37 DONE DONE
0 T1 T0
1
2 T3
3
4
5 T6
6
7
8 T4
9
10
11
12 T7
13
14
15
16
17 T2
18
19
20
21
22 T5
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 T8
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 T9
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69 T10
70
0 T0 T1
1
2 T3
3
4
5 T6
6
7
8 T4
9
10
11
12
13
14 T2
15
16
17
18 T5
19
20
21
22
23
24
25
26 T7
27
28
29
30
31
32
33
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.