source: proiecte/GAIIA/TaskGraf.cpp @ 122

#include "Graf.h"
#include <vector>

#define DEBUG 0

using namespace std;

typedef struct
{
        Task * nod;
        int stare;
        int nr_parinti;
} Candidat;

/**
* method initializing a graph of tasks to the structure specified in the file
*
* @param filename the input filename containing the configuration
*/
void TaskGraf::init(char * filename)
{
        FILE *file = fopen(filename, "r");
        int s, d;
        double cost;

      

        if (file == NULL)
        { 
                perror("Error reading file");
                exit(1);
        }
        else
        {
                fscanf(file, "%i %i", &nr_noduri, &nr_muchii);
                noduri = (Task*)calloc(nr_noduri, sizeof(Task));
                muchii = (Muchie*) calloc(nr_muchii, sizeof(Muchie));
                for(int i = 0 ; i < nr_noduri ; i ++)
                {
                        fscanf(file, "%lf", &cost);
                        noduri[i] = Task(i, cost);      
                }
                for(int i = 0 ; i < nr_muchii ; i ++)
                {
                        fscanf(file, "%i %i %lf", &s, &d, &cost);
                        int gasit = 0, sursa = -1, destin = -1;
                        for(int j = 0 ; j < nr_noduri ; j ++)
                        {       
                                if(gasit == 2) break;
                                if(noduri[j].id == s) { sursa = j; gasit ++;} 
                                if(noduri[j].id == d) { destin = j; gasit ++;}
                        }
                        muchii[i] = Muchie(&noduri[sursa], &noduri[destin], cost);
                        noduri[destin].addPredecesor(&muchii[i]);       
                        noduri[sursa].addSuccesor(&muchii[i]);
                }
        }
        fclose (file);
        max_level = sortare_topologica();
        sortare_topologica_inversa();
        computeFreeFloatingNodes();
}

/**
* the constructor
*
* @param n the number of tasks
* @param m the number of communication links
*/
TaskGraf::TaskGraf(int n, int m)
{
        nr_noduri = n;
        nr_muchii = m;
        noduri = (Task *)calloc (n, sizeof(Task));
        muchii = (Muchie *)calloc (m, sizeof (Muchie));
}

/**
* method that computes the list of free floating nodes
*/
void TaskGraf::computeFreeFloatingNodes(){
        int i,j;
        int id_succ; 
        int free_node;
        
        for (i = 0 ; i < nr_noduri ; i++){
                if ( noduri[i].niv_topo_min < noduri[i].niv_topo_max){
                        free_node = 1;                  
                        for (j = 0 ; j < noduri[i].nr_succ ; j++){
                                id_succ = ((Muchie *)(noduri[i].succesori[j]))->succesor->id;
                                if (noduri[id_succ].niv_topo_min <= noduri[i].niv_topo_min + 1)
                                        free_node = 0;
                        } 
                        if (free_node == 1){
                                f_nodes.push_back(i);
                        }

                }
        }
        if (DEBUG == 1) {
                for (i = 0 ; i < (int)f_nodes.size() ; i++)
                        printf("%d ",f_nodes[i]);
                printf("\n");
        }

}

/**
* method that prints the information about the graph of tasks
*/
void TaskGraf::print()
{
        printf("### task graf\n");
        printf("nr_noduri = %i, nr_muchii = %i\n", nr_noduri, nr_muchii);
        for(int i = 0 ; i < nr_noduri ; i ++)
                noduri[i].print();
        for(int i = 0 ; i < nr_muchii ; i ++)   
                muchii[i].print();
        printf("###\n");
}

/**
* method that computes the topological sort 
*
* @return the maximum topological level
*/
int TaskGraf::sortare_topologica()
{
        int nivel = 1;
        Candidat * cand= (Candidat * )calloc(nr_noduri, sizeof(Candidat));
        for(int i = 0 ; i < nr_noduri ; i ++)
        {
                cand[i].nod = &noduri[i];
                cand[i].stare = -1;
                cand[i].nr_parinti = noduri[i].nr_pred;
        }       
        for(int gasit = 0 ; gasit < nr_noduri ;)
        {
                for(int i = 0 ; i < nr_noduri ; i ++)
                        if(cand[i].nr_parinti == 0 && cand[i].stare == -1 )
                        {
                                cand[i].nod->niv_topo_min = nivel;
                                cand[i].nod->niv_topo = nivel;
                                cand[i].stare = 0;
                                gasit++;
                        }       
                for(int i = 0 ; i < nr_noduri ; i ++)
                        if(cand[i].stare == 0 )
                        {
                                cand[i].stare = 1;
                                for(int j = 0 ; j < nr_noduri ; j ++)
                                        for(int k = 0 ; k < cand[j].nod->nr_pred ; k ++ )
                                                if(((Muchie *)cand[j].nod->predecesori[k])->predecesor->id == cand[i].nod->id)
                                                        cand[j].nr_parinti --;
                        }
                nivel++;
        }
        return nivel;
}

/**
* method that computes the reverse topological sort 
*/
void TaskGraf::sortare_topologica_inversa()
{
        int nivel = 1;
        Candidat * cand= (Candidat * )calloc(nr_noduri, sizeof(Candidat));
        for(int i = 0 ; i < nr_noduri ; i ++)
        {
                cand[i].nod = &noduri[i];
                cand[i].stare = -1;
                cand[i].nr_parinti = noduri[i].nr_succ;
        }       
        for(int gasit = 0 ; gasit < nr_noduri ;)
        {
                for(int i = 0 ; i < nr_noduri ; i ++)
                        if(cand[i].nr_parinti == 0 && cand[i].stare == -1 )
                        {
                                cand[i].nod->niv_topo_max = max_level - nivel;
                                cand[i].stare = 0;
                                gasit++;
                        }       
                for(int i = 0 ; i < nr_noduri ; i ++)
                        if(cand[i].stare == 0 )
                        {
                                cand[i].stare = 1;
                                for(int j = 0 ; j < nr_noduri ; j ++)
                                        for(int k = 0 ; k < cand[j].nod->nr_succ ; k ++ )
                                                if(((Muchie *)cand[j].nod->succesori[k])->succesor->id == cand[i].nod->id)
                                                        cand[j].nr_parinti --;
                        }
                nivel++;
        }
}

/**
* method that initializes the structure with the default configuration
*/
void TaskGraf::init(){
        int i;
        for (i = 0 ; i < nr_noduri ; i++)
                noduri[i].init();
}

/**
* the copy operator
*/
TaskGraf& TaskGraf::operator=(const TaskGraf& clone)
{
        //printf("!!!\n");
        nr_noduri = clone.nr_noduri;
        nr_muchii = clone.nr_muchii;
        max_level = clone.max_level;
        f_nodes = clone.f_nodes;
        noduri = (Task *)calloc(nr_noduri, sizeof(Task));
        muchii = (Muchie *)calloc(nr_muchii, sizeof(Muchie));
        for(int i = 0 ; i < nr_noduri ; i ++){
                noduri[i] = Task(clone.noduri[i].id, clone.noduri[i].cost);
                noduri[i].niv_topo_min = clone.noduri[i].niv_topo_min;
                noduri[i].niv_topo_max = clone.noduri[i].niv_topo_max;  
        }
        for(int i = 0 ; i < nr_muchii ; i ++)
        {
                int gasit = 0, sursa = -1, destin = -1;
                for(int j = 0 ; j < nr_noduri ; j ++)
                {       
                        if(gasit == 2) break;
                        if(noduri[j].id == clone.muchii[i].predecesor->id) { sursa = j; gasit ++;} 
                        if(noduri[j].id == clone.muchii[i].succesor->id) { destin = j; gasit ++;}
                }
                muchii[i] = Muchie(&noduri[sursa], &noduri[destin], clone.muchii[i].cost);
                noduri[destin].addPredecesor(&muchii[i]);       
                noduri[sursa].addSuccesor(&muchii[i]);
        }
        
        return *this;
}