tg.c

This program is free software you can redistribute it and/or modify it under the terms of the GN

		/* 2.3. CHANGE TO THE NEW maxid */
		graph->maxid = id;
		}

	/* 3. CHANGE POINTER */
	tgp(graph,task)->tid = id;
	graph->idarray[id] = graph->idarray[task];
	graph->idarray[task] = NULL;

	/* 4. CHANGE THE SUCCESORS AND PREDECESSORS POINTERS */
	for (count = 0;
		count < tg_pred_num(graph, id);
		count ++ )
		{
		target = tgp(graph, id)->pred[count];
		for (count2 = 0;
			count2 < tg_succ_num(graph, target);
			count2 ++ )
			{
			if (tgp(graph, target)->succ[count2] == task)
				{
				tgp(graph, target)->succ[count2] = id; 
				}
			}
		}

	for (count = 0;
		count < tg_succ_num(graph, id);
		count ++ )
		{
		target = tgp(graph, id)->succ[count];
		for (count2 = 0;
			count2 < tg_pred_num(graph, target);
			count2 ++ )
			{
			if (tgp(graph, target)->pred[count2] == task)
				tgp(graph, target)->pred[count2] = id; 
			}
		}


	/* 5. END */
	return TRUE;
}



/* --------------------------------------------------------------------
 * MINIMUM FREE IDENTIFIER
 */
int tg_free_id(tg graph)
{
	int	count;
	Bool	found;

	/* 1. CHECK IF THERE ARE IDENTIFIERS */
	if (graph->maxid < 0)
		return 0;

	/* 2. CHECK IF THERE ARE NOT HOLES IN THE INDEX ARRAY */
	if (tg_nodes(graph) == tg_maxid(graph)+1)
		return graph->maxid + 1;
	

	/* 3. LOCATE A NULL POINTER ON THE ARRAY */
	for (count = 0, found = FALSE;
		count <= graph->maxid && !found;
		count ++ )
		{
		if (graph->idarray[count] == NULL)
			found = TRUE;	
		}

	/* 3. IF FOUND RETURN THE IDENTIFIER */
	if (found)
		return count - 1;

	/* 4. IF NOT, ERROR */
	else Asystem_error("tg_free_id","No NULL pointer in array","");

	/* 5. END */
	return 0;
}




/* --------------------------------------------------------------------
 * ARC EXISTS
 */
Bool tg_arc(tg graph, tg_task task_from, tg_task task_to)
{
	int	count;
	Bool	found;

	/* 1. TRY TO LOCATE TASK_TO AS SUCCESOR OF TASK_FROM */
	for ( found = FALSE, count = 0;
		count < tgp(graph,task_from)->succnum && !found ;
		count ++ ) 
		{
		if (tgp(graph,task_from)->succ[count] == task_to)
			found = TRUE;
		}
	
	/* 2. RETURN found */
	return found;
}






/*---------------------------------------------------------------------------
 * 2. HIGH LEVEL OPERATIONS AND INFORMATION ABOUT THE GRAPH STRUCTURE
 *---------------------------------------------------------------------------
 */

/* --------------------------------------------------------------------
 * DELETE ALL ARRIVING EDGES OF A NODE
 */
void tg_del_arcs_A(tg graph, tg_task node) {
	task_list	predlist=NULL;
	int		count;
	int		elements;

	/* 1. GET THE PREDECESSORS LIST OF THE NODE */
	elements = tg_pred_num(graph, node);
	predlist = (task_list) malloc( sizeof(tg_task)*elements);
	if ( predlist == NULL ) { 
		Asystem_error("tg_del_arcs_A", "Not enough memory", "predlist");
		}
	memcpy(predlist, tg_pred(graph,node), sizeof(tg_task)*elements );

	/* 2. FOR ALL THE ARCS ON THE LIST */
	for (count = 0;
		count < elements;
		count ++ )
		{
		/* 2.1. DELETE ARC ORIGIN - SUCCESOR */
		tg_del_arc(graph, predlist[count], node);
		} 

	/* 3. FREEING LIST SPACE */
	free(predlist); predlist = NULL;

	/* 4. END */
	}

/* --------------------------------------------------------------------
 * DELETE ALL LEAVING EDGES OF A NODE
 */
void tg_del_arcs_L(tg graph, tg_task node) {
	task_list	succlist=NULL;
	int		count;
	int		elements;

	/* 1. GET THE SUCCESORS LIST OF THE NODE */
	elements = tg_succ_num(graph, node);
	succlist = (task_list)malloc(sizeof(tg_task)*elements);
	if ( succlist == NULL ) { 
		Asystem_error("tg_del_arcs_L", "Not enough memory", "succlist");
		}
	memcpy(succlist, tg_succ(graph,node), sizeof(tg_task)*elements);

	/* 2. FOR ALL THE ARCS ON THE LIST */
	for (count = 0;
		count < elements;
		count ++ )
		{
		/* 2.1. DELETE ARC ORIGIN - SUCCESOR */
		tg_del_arc(graph, node, succlist[count]);
		} 

	/* 3. FREEING LIST SPACE */
	free(succlist); succlist = NULL;

	/* 4. END */
	}

/* --------------------------------------------------------------------
 * MOVE SUCCESORS FROM A NODE TO ANOTHER
 */
void tg_move_succ(tg graph, tg_task task_orig, tg_task task_dest)
{
	task_list	succlist=NULL;
	int		count;
	int		elements;

	/* 1. GET THE SUCCESORS LIST OF THE ORIGIN */
	elements = tg_succ_num(graph, task_orig);
	succlist = (task_list)malloc(sizeof(tg_task)*elements);
	if ( succlist == NULL ) { 
		Asystem_error("tg_move_succ", "Not enough memory", "succlist");
		}
	memcpy(succlist, tg_succ(graph,task_orig), sizeof(tg_task)*elements);

	/* 2. FOR ALL THE ARCS ON THE LIST */
	for (count = 0;
		count < elements;
		count ++ )
		{
		/* 2.1. DELETE ARC ORIGIN - SUCCESOR */
		tg_del_arc(graph, task_orig, succlist[count]);

		/* 2.2. CREATE ARC DEST - SUCCESOR */
		tg_add_arc(graph, task_dest, succlist[count]);

		} 

	/* 3. FREEING LIST SPACE */
	free(succlist); succlist = NULL;

	/* 4. END */
}


/* --------------------------------------------------------------------
 * MOVE PREDECESORS FROM A NODE TO ANOTHER
 */
void tg_move_pred(tg graph, tg_task task_orig, tg_task task_dest)
{
	task_list	predlist=NULL;
	int		count;
	int		elements;

	/* 1. GET THE PREDECESORS LIST OF THE ORIGIN */
	elements = tg_pred_num(graph, task_orig);
	predlist = (task_list) malloc( sizeof(tg_task)*elements);
	if ( predlist == NULL ) { 
		Asystem_error("tg_move_pred", "Not enough memory", "predlist");
		}
	memcpy(predlist, tg_pred(graph,task_orig), sizeof(tg_task)*elements );

	/* 2. FOR ALL THE ARCS ON THE LIST */
	for (count = 0;
		count < elements;
		count ++ )
		{
		/* 2.1. DELETE ARC ORIGIN - SUCCESOR */
		tg_del_arc(graph, predlist[count], task_orig);

		/* 2.2. CREATE ARC DEST - SUCCESOR */
		tg_add_arc(graph, predlist[count], task_dest);

		} 

	/* 3. FREEING NLIST SPACE */
	free(predlist); predlist = NULL;

	/* 4. END */
}



/* --------------------------------------------------------------------
 * LIST OF NODES OF PREDECESSORS GRADE n
 */
int tg_pred_grade(tg graph, int grade, task_list *resultlist)
{
	int 		count, already, nodes;
	task_list	list=NULL;

	/* 1. COUNT THE NUMBER OF NODES */
	for (count = 0, nodes = 0;
		count <= tg_maxid(graph);
		count ++ )
		{
		if (!tg_id(graph, count))
			continue;

		if (tg_pred_num(graph, count) == grade)
			nodes ++;
		}
	

	/* 2. GET SPACE FOR THE NULL LIST */
	list = (task_list) malloc( sizeof(tg_task) * (nodes + 1) );
	if ( list == NULL ) {
		Asystem_error("tg_pred_grade", "Not enough memory", "list");
		}

	/* 3. FILL THE LIST */
	 for (count = 0, already = 0;
		count <= tg_maxid(graph) && already < nodes;
		count ++ )
		{
		if (!tg_id(graph, count))
			continue;

		if (tg_pred_num(graph, count) == grade)
			{
			list[already] = count;
			already ++;
			}
		}

	/* 4. RETURN THE LIST */
	*resultlist = list;
	return nodes;
}


/* --------------------------------------------------------------------
 * LIST OF NODES OF SUCCESORS GRADE n
 */
int tg_succ_grade(tg graph, int grade, task_list *resultlist)
{
	int 		count, already, nodes;
	task_list	list=NULL;

	/* 1. COUNT THE NUMBER OF NODES */
	for (count = 0, nodes = 0;
		count <= tg_maxid(graph);
		count ++ )
		{
		if (!tg_id(graph, count))
			continue;

		if (tg_succ_num(graph, count) == grade)
			nodes ++;
		}
	

	/* 2. GET SPACE FOR THE NULL LIST */
	list = (task_list) malloc( sizeof(tg_task) * (nodes + 1) );
	if ( list == NULL ) {
		Asystem_error("tg_succ_grade", "Not enough memory", "list");
		}

	/* 3. FILL THE LIST */
	 for (count = 0, already = 0;
		count <= tg_maxid(graph) && already < nodes;
		count ++ )
		{
		if (!tg_id(graph, count))
			continue;

		if (tg_succ_num(graph, count) == grade)
			{
			list[already] = count;
			already ++;
			}
		}

	/* 4. RETURN THE LIST */
	*resultlist = list;
	return nodes;
}





/***************************************************************/
/*	
 * From v1.0	(Adapted to the new internal structure)
 */

/* --------------------------------------------------------------------
 * READ THE GRAPH STRUCTURE FROM A TEXT FILE 
 */
tg	tg_read(FILE *fp)
{
	tg	graph;
	tg_task	tid;
	int	tasknum, resnum, i;
	int	succnum, succ, t;
	double	rvalue;
	char	comments[256];
	task_list	list=NULL;
	int		elements;
	int	check;

	/* SKIP INITIAL COMMENTS BEGINING WITH # */
	check = fscanf(fp, "%[#]", comments);
	while(check==1) {
		fscanf(fp, "%[^\n]", comments);
		fscanf(fp, "\n");
		check = fscanf(fp, "%[#]", comments);
		}

	/* 1. READ NUMBER OF TASK AND RESOURCES */
	tasknum=-1;
	check = fscanf(fp, "T:%d\n", &tasknum);
	CheckError(check==1 && tasknum>0, "reading graph file: Number of tasks");
	check = fscanf(fp, "R:%d\n", &resnum);
	CheckError(check==1 && resnum>=0, "reading graph file: Number of resources");

	/* 2. INITIALIZE GRAPH WITH NUMBER OF RESOURCES */
	graph = tg_init(resnum);


	/* 3. READ TASKS */
	for (t = 0; t < tasknum; t++) 
		{
		/* 3.1. READ NUMBER OF TASK */
		check = fscanf(fp,"t%d:",&tid);
		CheckError(check==1 && tid>=0, "reading graph file: Reading a task number");

		/* 3.2. CREATE TASK IF IT DOES NOT EXIST */
		if (!tg_id(graph, tid))
			tg_add_node(graph, tid);

		/* 3.3. RESOURCES */
		for ( i = 0; i < resnum; i++) {
			check = fscanf(fp,"%lf",&rvalue);
			CheckError(check==1 && rvalue>=0.0, "reading graph file: Reading task resource values");
			tg_set_resource(graph, tid, i, rvalue);
			}

		/* 3.4. NUMBER OF SUCCESORS */
		check = fscanf(fp,"%[ ]s%d:",comments,&succnum);
		CheckError(check==2 && succnum>=0.0, "reading graph file: Reading the number of successors of a task");

		/* 3.5. SUCCESORS */
		for ( i = 0; i < succnum; i++) {
			check = fscanf(fp,"%d",&succ);
			CheckError(check==1 && succ>=0, "reading graph file: Reading the successors of a task");
			if (!tg_id(graph, succ))
				{
				tg_add_node(graph, succ);
				}
			tg_add_arc(graph, tid, succ);
			}

		/* 3.6. END ON LINE */
		fscanf(fp,"%[ \n]", comments);
		}

	/* 4. DETECT ROOT */
	elements = tg_pred_grade(graph, 0, &list);
	if (elements == 1) tg_set_root(graph, list[0]);
	free(list); list = NULL;

	/* 5. RETURN THE NEW GRAPH */
	return graph;
}


/* --------------------------------------------------------------------
 * WRITE THE GRAPH STRUCTURE ON A TEXT FILE
 */
void   	tg_write(FILE *fp,tg graph)
{
        int     tid,count;
	task_list	list=NULL;
	int		elements;

	Assert(graph != NULL);

	/* 1. HEADING */
	fprintf(fp,"T: %d\n",tg_nodes(graph));
	fprintf(fp,"R: %d\n",tg_resnum(graph));

	/* 2. TASKS */
	for (tid = 0;
		tid <= tg_maxid(graph);
		tid ++ )
		{
		if (tg_id(graph, tid))
			{
			fprintf(fp,"t%d: ",tid);
			for (count = 0;
				count < tg_resnum(graph);
				count++)
				{
				fprintf(fp," %.4f",tg_get_resource(graph, tid, count));
				}
			fprintf(fp," s%d:",tg_succ_num(graph, tid));

			list = tg_succ(graph, tid);
			elements = tg_succ_num(graph, tid);

			for (count = 0;
				count < elements;
				count ++ )
				{
				fprintf(fp," %d",list[count]);
				}
			fprintf(fp,"\n");
			}
		}
}