jeudi 12 mars 2015

Toplogical Sort uses a queue not a DFS?


I need help with this program for class. I am giving an adjacency list of only a DAG's outdegrees . SO a vertex and all that depends on that vertex. I need to do a toplogical sort and I don't know where I am going wrong i get close but still not quite right.


My teacher said that toplogical sort uses a queue not a DFS but I thought you could use a DFS? I've tried different ways and it doesn't work. And I can't find any other way without doing a DFS. Also I cannot use the STL. Here is how I am calculating the indegrees and calling the DFS to do the sort in the constructor:



ClassName::ClassName(int numJobs, int numWorkers, Job *jobs, int numPeople)
{

Node queue [numJobs]; //holds all the vertices
int tail = numJobs;
//int head = 0;
Node* topSort = new Node [numJobs];
Node noJob;
noJob.ID = -1;
int start;
//already have a jobs array
//need to create queue then
//loop through jobs and increment the dependencies

Node* vertices = new Node [numJobs];
for(int i = 0; i < numJobs; i++){
topSort[i] = noJob;
vertices[i].indegree = 0;
vertices[i].ID = i;
vertices[i].job = jobs[i];
vertices[i].visited = false;
cout << "vertex made: " << vertices[i].ID << endl;
queue[--tail] = vertices[i];
}

for(int j = 0; j < numJobs; j++){
// cout << "vertex ID " << vertices[j].ID << endl;
// cout << "vertex numDependencies " << vertices[j].job.numDependencies << endl;
if(vertices[j].job.numDependencies != 0){
for(int k = 0; k < vertices[j].job.numDependencies; k++){
// cout << "index: " << j << endl;
int depID = vertices[j].job.dependencies[k];
// cout << "vertex dependency " << vertices[j].job.dependencies[k] << endl;
vertices[depID].indegree++;
// cout << "vertex depID " << vertices[depID].ID << endl;
// cout << "v depID numDependencies " << vertices[depID].job.numDependencies << endl;
// cout << vertices[depID].ID << endl;
// cout << vertices[depID].indegree << endl;
}
}
}

for(int m = 0; m< numJobs; m++){

if(vertices[m].indegree == 0){
start = vertices[m].ID;
break;
}

}

DFS(start, vertices, topSort, numJobs, 0);
//queue to sort them in toplogical orders

for(int q = 0; q < numJobs; q++){
cout << "topSort vertex: " << topSort[q].ID << endl;

}




// int finishTime = int(ceil(job[ID].length/double(jobs[ID].numPeopleUsed)));
}


Here is my DFS search method anyway:



void ClassName::DFS(int start, Node* vertices, Node* topSort, int last, int counter){
//need to enqueue all the zero indegrees and then do decrement all of them
// watch the toplogical video!
// cout << "start:" << start << endl;
topSort[counter++] = vertices[start];
vertices[start].visited = true;

//topSort[0] = vertices[start];
for(int p = 0; p < vertices[start].job.numDependencies; p++){
int depID = vertices[start].job.dependencies[p];
vertices[depID].indegree--;
}

for(int m = 0; m< last; m++){

if((vertices[m].indegree == 0) && (vertices[m].visited == false)){
start = vertices[m].ID;
break;
}
}
// cout << "new start: " << start << endl;
// cout << "new indegree: " << vertices[start].indegree << endl;

if(!vertices[start].visited && start != last)
DFS(start, vertices, topSort, last, counter);



}



Aucun commentaire:

Enregistrer un commentaire