pathComp_tools.c

/*
 * Copyright 2022-2023 ETSI TeraFlowSDN - TFS OSG (https://tfs.etsi.org/)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */


#include <stdio.h>
#include <stdlib.h> 
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <string.h>
#include <unistd.h>
#include <netdb.h>
#include <glib.h>
#include <sys/time.h>
#include <ctype.h>
#include <strings.h>
#include <time.h>
#include <math.h>
#include <fcntl.h>
#include <uuid/uuid.h>
#include <errno.h>

#include "pathComp_log.h"
#include "pathComp.h"
#include "pathComp_tools.h"

gint numPathCompIntents = 0;  // number of events triggering the path computation
//gint numSuccesPathComp = 0; // number of events resulting in succesfully path computations fulfilling the constraints
struct timeval total_path_comp_time;
gdouble totalReqBw = 0.0;
gdouble totalServedBw = 0.0;

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Function for time processing
 *
 * 	@param a
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 ////////////////////////////////////////////////////////////////////////////////////////
struct timeval tv_adjust (struct timeval a) {
	while (a.tv_usec >= 1000000) {
		a.tv_usec -= 1000000;
		a.tv_sec++;
	}
	while (a.tv_usec < 0) {
		a.tv_usec += 1000000;
		a.tv_sec--;
	}
	return a;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief friendly function to copy safely strings
 *
 * 	@param dst
 *  @param src
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 ////////////////////////////////////////////////////////////////////////////////////////
void duplicate_string(gchar* dst, gchar* src) {
	g_assert(dst); g_assert(src);
	strcpy(dst, src);
	dst[strlen(dst)] = '\0';
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Function used to print the computed the path
 *
 *	@param path
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void print_path (struct compRouteOutputItem_t *p) {
	g_assert(p);	
	DEBUG_PC ("=========== COMPUTED PATH =======================");
	DEBUG_PC ("E2E Avail. Bw: %f, Latency: %f, Cost: %f, Consumed Power (in W): %f", p->availCap, p->delay, p->cost, p->power);
	for (gint k = 0; k < p->numRouteElements; k++) {
		DEBUG_PC ("%s[%s] --> %s[%s]", p->routeElement[k].aNodeId.nodeId, p->routeElement[k].aEndPointId,
																p->routeElement[k].zNodeId.nodeId, p->routeElement[k].zEndPointId);
		DEBUG_PC("\t linkId: %s", p->routeElement[k].linkId);
		DEBUG_PC("\t aTopologyId: %s", p->routeElement[k].aTopologyId);
		DEBUG_PC("\t zTopologyId: %s", p->routeElement[k].zTopologyId);
	}
	DEBUG_PC ("==================================================================");		
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Function used to print the output path formed by link Ids
 *
 *	@param p
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void print_path_t(struct path_t* p) {
	g_assert(p);
	DEBUG_PC(" ============ COMPUTED OUTPUT PATH =================");
	DEBUG_PC("Path AvailBw: %f, Cost: %f, Latency: %f, Power: %f", p->path_capacity.value,
			p->path_cost.cost_value, p->path_latency.fixed_latency, p->path_power.power);
	DEBUG_PC("number of links of path %d", p->numPathLinks);
	for (gint k = 0; k < p->numPathLinks; k++) {
		DEBUG_PC("Link: %s", p->pathLinks[k].linkId);
		for (gint l = 0; l < p->pathLinks[k].numLinkTopologies; l++) {
			DEBUG_PC("end Link [%d] TopologyId: %s", l, p->pathLinks[k].linkTopologies[l].topologyId);
		}
		DEBUG_PC(" ContextId: %s", p->pathLinks[k].topologyId.contextId);
		DEBUG_PC(" TopologyUUid: %s", p->pathLinks[k].topologyId.topology_uuid);
		DEBUG_PC(" aDeviceId: %s", p->pathLinks[k].aDeviceId);
		DEBUG_PC(" aEndpointId: %s", p->pathLinks[k].aEndPointId);
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Function used allocate memory for struct path_t
 *
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 ////////////////////////////////////////////////////////////////////////////////////////
struct path_t* create_path() {
	struct path_t* p = g_malloc0(sizeof(struct path_t));
	if (p == NULL) {
		DEBUG_PC("Memory allocation failure");
		exit(-1);
	}
	return(p);
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Returns the char (36 bytes) format of a uuid
 *
 *	@param uuid
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
gchar* get_uuid_char(uuid_t uuid) {
	gchar* uuidChar = g_malloc0(16); // uuid has 36 chars
	if (uuidChar == NULL) {
		DEBUG_PC("Memory Allocation failure");
		exit(-1);
	}
	uuid_unparse(uuid, (char *)uuidChar);
	return uuidChar;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Makes a copy of the service identifier (including the context)
 *
 *	@param o
 *  @param i
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void copy_service_id(struct serviceId_t* o, struct serviceId_t* i) {
	g_assert(o); g_assert(i);
	memcpy(o->contextId, i->contextId, sizeof(i->contextId));
	memcpy(o->service_uuid, i->service_uuid, sizeof(i->service_uuid));
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Makes a copy of the service endpoint identifier (including the topology (contect and topology id), device and endpoint (port))
 *
 *	@param oEp
 *  @param iEp
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void copy_service_endpoint_id(struct service_endpoints_id_t* oEp, struct service_endpoints_id_t* iEp) {
	g_assert(oEp); g_assert(iEp);

	// copy topology information
	memcpy(oEp->topology_id.contextId, iEp->topology_id.contextId, sizeof(iEp->topology_id.contextId));
	memcpy(oEp->topology_id.topology_uuid, iEp->topology_id.topology_uuid, sizeof(iEp->topology_id.topology_uuid));

	// copy the endpoint
	memcpy(oEp->device_uuid, iEp->device_uuid, sizeof(iEp->device_uuid));
	memcpy(oEp->endpoint_uuid, iEp->endpoint_uuid, sizeof(iEp->endpoint_uuid));
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief From the set of contexts, it is returned the graph associated to that context matching
 *	with the passed contextId.
 *
 *	@param Set
 *  @param contextId
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
struct graph_t* get_graph_by_contextId(GList* set, gchar* contextId) {
	g_assert(contextId);

	// iterate over the set of context. Pick the one matching with contextId, and return the graph.
	// If not found, return NULL
	struct graph_t* g = NULL;
	for (GList *ln = g_list_first(set);
		ln;
		ln = g_list_next(ln)){
		struct context_t* context = (struct context_t*)(ln->data);
		if (strcmp(context->contextId, contextId) == 0) {
			g = &(context->g);
			return g;
		}
	}
	return NULL;
}

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Process the service constraint and maps them into the path constraints
 * to be fulfilled
 *
 *  @param path_constraints
 *  @param s
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
struct path_constraints_t * get_path_constraints(struct service_t* s) {
	g_assert(s);
	
	struct path_constraints_t* path_constraints = g_malloc0(sizeof(struct path_constraints_t));
	if (path_constraints == NULL) {
		DEBUG_PC("Memory Allocation Failure");
		exit(-1);
	}

	char* eptr;
	for (gint i = 0; i < s->num_service_constraints; i++) {
		struct constraint_t* constraint = &(s->constraints[i]);;
		if (strncmp((const char*)constraint->constraint_type, "bandwidth", 9) == 0) {
			path_constraints->bwConstraint = (gdouble)(strtod((char*)constraint->constraint_value, &eptr));
			path_constraints->bw = TRUE;
			//DEBUG_PC("Path Constraint Bw: %f", path_constraints->bwConstraint);
		}
		if (strncmp((const char*)constraint->constraint_type, "cost", 4) == 0) {
			path_constraints->costConstraint = (gdouble)(strtod((char*)constraint->constraint_value, &eptr));
			path_constraints->cost = TRUE;
			//DEBUG_PC("Path Constraint Cost: %f", path_constraints->costConstraint);
		}
		if (strncmp((const char*)constraint->constraint_type, "latency", 7) == 0) {
			path_constraints->latencyConstraint = (gdouble)(strtod((char*)constraint->constraint_value, &eptr));
			path_constraints->latency = TRUE;
			//DEBUG_PC("Path Constraint Latency: %f", path_constraints->latencyConstraint);
		}
		if (strncmp((const char*)constraint->constraint_type, "energy", 6) == 0) {
			path_constraints->energyConstraint = (gdouble)(strtod((char*)constraint->constraint_value, &eptr));
			path_constraints->energy = TRUE;
			//DEBUG_PC("Path Constraint Energy: %f", path_constraints->energyConstraint);
		}
	}
	return path_constraints;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Creates the predecessors to keep the computed path
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
struct pred_t * create_predecessors () {
	struct pred_t *predecessors = g_malloc0 (sizeof (struct pred_t));
	if (predecessors == NULL) {
		DEBUG_PC ("memory allocation failed\n");
		exit (-1);
	}   
	return predecessors;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief create edge
 *
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
struct edges_t* create_edge() {
	struct edges_t* e = g_malloc0(sizeof(struct edges_t));
	if (e == NULL) {
		DEBUG_PC("Memory allocation failed\n");
		exit(-1);
	}
	return e;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Prints the list of the predecessors for a given computed Shortest Path
 *
 *	@param p 
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void print_predecessors (struct pred_t *p)
{
	g_assert (p);
	DEBUG_PC ("Number of Predecessors: %d", p->numPredComp);
	for (gint i = 0; i < p->numPredComp; i++) {
		struct pred_comp_t *pComp = &(p->predComp[i]);
		DEBUG_PC ("deviceId: %s", pComp->v.nodeId);		
		struct edges_t *e = &(pComp->e);
		DEBUG_PC("Edge[#%d] (linkId): %s", i, e->linkId);
		DEBUG_PC ("\t %s[%s] ===>", e->aNodeId.nodeId, e->aEndPointId);
		DEBUG_PC("\t %s[%s]", e->zNodeId.nodeId, e->zEndPointId);
		DEBUG_PC("\t aTopologyId: %s", e->aTopologyId);
		DEBUG_PC("\t zTopologyId: %s", e->zTopologyId);
	}	
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Builds the list of predecessors for the request destination using the computed Shortest Path
 *	being stored in map
 *
 *	@param p 
 *	@param s
 *	@param map
 *	
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void build_predecessors (struct pred_t *p, struct service_t *s, struct map_nodes_t *map) {
	g_assert (p); g_assert (s); g_assert (map);
	
	struct nodes_t *v = create_node();
	duplicate_string(v->nodeId, s->service_endpoints_id[1].device_uuid);
	
	struct edges_t *e = create_edge();	
	get_edge_from_map_by_node (e, v, map);
			
	// Get u (being source of edge e)
	struct nodes_t u;	
	duplicate_node_id (&e->aNodeId, &u);
		
	// Add to the predecessors list
	struct pred_comp_t *pred = &(p->predComp[p->numPredComp]);
	duplicate_node_id (&u, &pred->v);	
	struct edges_t *e1 = &(pred->e);	
	duplicate_edge (e1, e);
	p->numPredComp++;	
	// Back-trace edges till reaching the srcPEId
	struct nodes_t* srcNode = create_node();
	duplicate_string(srcNode->nodeId, s->service_endpoints_id[0].device_uuid);

	while (compare_node_id (&u, srcNode) != 0) 	{		
		duplicate_node_id (&u, v);
		get_edge_from_map_by_node (e, v, map);		
		// Get the u (being source of edge e)		
		duplicate_node_id (&e->aNodeId, &u);		
		// Get the new predecessor
		struct pred_comp_t *pred = &p->predComp[p->numPredComp];			
		// Add to the predecessors list					
		duplicate_node_id (&u, &pred->v);		
		struct edges_t *e1 = &(pred->e);
		duplicate_edge (e1, e);
		p->numPredComp++;		
	}
	print_predecessors (p);
    g_free (e); g_free(v); g_free(srcNode);
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief It creates a struct nodes_t
 *
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
struct nodes_t * create_node ()
{
	struct nodes_t *n = g_malloc0 (sizeof (struct nodes_t));
	if (n == NULL) {
		DEBUG_PC ("memory allocation problem");
		exit (-1);
	}
	return n;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief It creates a routeElement_t
 *
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
struct routeElement_t * create_routeElement () {
	struct routeElement_t *rE = g_malloc0 (sizeof (struct routeElement_t));
	if (rE == NULL)	{
		DEBUG_PC ("memory allocation problem");
		exit (-1);		
	}
	return rE;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief copy node ids
 *
 *	@param src
 *  @param dst
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void duplicate_node_id (struct nodes_t *src, struct nodes_t *dst) {	
	g_assert (src);
	g_assert (dst);	
	//DEBUG_PC ("Duplicate nodeId for %s", src->nodeId);	
	strcpy (dst->nodeId, src->nodeId);	
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief compares a pair of node Ids
 *
 *	@param a
 *  @param b
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gint compare_node_id (struct nodes_t *a, struct nodes_t *b) {
	g_assert (a);
	g_assert (b);	
	return (memcmp (&a->nodeId, b->nodeId, strlen (b->nodeId)));	
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief duplicate two routeElement_t
 *
 *	@param src
 *  @param dst
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void duplicate_routeElement (struct routeElement_t *src, struct routeElement_t *dst)
{
	g_assert (src);
	g_assert (dst);
	
	duplicate_node_id (&(src->aNodeId), &(dst->aNodeId));
	duplicate_node_id (&(src->zNodeId), &(dst->zNodeId));
	duplicate_string(dst->aEndPointId, src->aEndPointId);
	duplicate_string(dst->zEndPointId, src->zEndPointId);
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief duplicate two edges
 *
 *	@param e1 (destination)
 *  @param e2 (source)
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void duplicate_edge (struct edges_t *e1, struct edges_t *e2) {
	g_assert (e1); g_assert (e2);
		
	duplicate_node_id (&e2->aNodeId, &e1->aNodeId);
	duplicate_node_id (&e2->zNodeId, &e1->zNodeId);
	//DEBUG_PC ("e->aNodeId: %s --->  e->zNodeId: %s", e1->aNodeId.nodeId, e1->zNodeId.nodeId);
	duplicate_string(e1->aEndPointId, e2->aEndPointId);
	duplicate_string(e1->zEndPointId, e2->zEndPointId);
	duplicate_string(e1->linkId, e2->linkId);
	duplicate_string(e1->interDomain_localId, e2->interDomain_localId);
	duplicate_string(e1->interDomain_remoteId, e2->interDomain_remoteId);
	duplicate_string(e1->aTopologyId, e2->aTopologyId);
	duplicate_string(e1->zTopologyId, e2->zTopologyId);
	
	e1->unit = e2->unit;
	memcpy(&e1->totalCap, &e2->totalCap, sizeof(gdouble));
	memcpy(&e1->availCap, &e2->availCap, sizeof(gdouble));

	memcpy (&e1->cost, &e2->cost, sizeof (gdouble));
    memcpy (&e1->delay, &e2->delay, sizeof (gdouble));
	memcpy(&e1->energy, &e2->energy, sizeof(gdouble));
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Duplicate path 
 *
 *	@param a - original
 *  @param b - copy
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void duplicate_path (struct compRouteOutputItem_t *a, struct compRouteOutputItem_t *b) {		
	g_assert (a); 	g_assert (b);
	memcpy(&b->availCap, &a->availCap, sizeof (gdouble));		
	memcpy(&b->cost, &a->cost, sizeof(gdouble));	
	memcpy(&b->delay, &a->delay, sizeof (gdouble));
	memcpy(&b->power, &a->power, sizeof(gdouble));
	b->numRouteElements = a->numRouteElements;
	for (gint k = 0; k < a->numRouteElements; k++) {			
		//DEBUG_PC ("aNodeId: %s // zNodeId: %s", a->routeElement[k].aNodeId.nodeId, a->routeElement[k].zNodeId.nodeId);
		// aNodeId duplication
		struct nodes_t *n1 = &(a->routeElement[k].aNodeId);
		struct nodes_t *n2 = &(b->routeElement[k].aNodeId);			
		duplicate_node_id (n1, n2);					
		//zNodeId duplication
		n1 = &(a->routeElement[k].zNodeId);
		n2 = &(b->routeElement[k].zNodeId);			
		duplicate_node_id (n1, n2);
		duplicate_string(b->routeElement[k].aEndPointId, a->routeElement[k].aEndPointId);
		duplicate_string(b->routeElement[k].zEndPointId, a->routeElement[k].zEndPointId);
		duplicate_string(b->routeElement[k].linkId, a->routeElement[k].linkId);
		duplicate_string(b->routeElement[k].aTopologyId, a->routeElement[k].aTopologyId);
		duplicate_string(b->routeElement[k].zTopologyId, a->routeElement[k].zTopologyId);
	}	
	return;	
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Duplicate path from compRouteOutputItem_t to path_t
 *
 *	@param a - original
 *  @param b - copy
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void duplicate_path_t(struct compRouteOutputItem_t* a, struct path_t* b) {
	g_assert(a); g_assert(b);

	// transfer path characteristics ...
	memcpy(&b->path_capacity.value, &a->availCap, sizeof(gdouble));
	memcpy(&b->path_cost.cost_value, &a->cost, sizeof(gdouble));
	memcpy(&b->path_latency.fixed_latency, &a->delay, sizeof(gdouble));
	memcpy(&b->path_power.power, &a->power, sizeof(gdouble));

	b->numPathLinks = a->numRouteElements;

	for (gint k = 0; k < a->numRouteElements; k++) {
		struct routeElement_t* rE = &(a->routeElement[k]);
		struct pathLink_t* pL = &(b->pathLinks[k]);

		// copy the aDeviceId and aEndpointId, zDeviceId and zEndPointId
		duplicate_string(pL->aDeviceId, rE->aNodeId.nodeId);
		duplicate_string(pL->zDeviceId, rE->zNodeId.nodeId);
		duplicate_string(pL->aEndPointId, rE->aEndPointId);
		duplicate_string(pL->zEndPointId, rE->zEndPointId);

		duplicate_string(pL->topologyId.topology_uuid, rE->aTopologyId);
		duplicate_string(pL->topologyId.contextId, rE->contextId);

		//copy the linkId
		duplicate_string(pL->linkId, rE->linkId);
		pL->numLinkTopologies++;
		duplicate_string(pL->linkTopologies[pL->numLinkTopologies - 1].topologyId, rE->aTopologyId);
		pL->numLinkTopologies++;
		duplicate_string(pL->linkTopologies[pL->numLinkTopologies - 1].topologyId, rE->zTopologyId);
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Return the index into mapN related nodeId
 * 
 *  @param nodeId
 *  @para mapN
 *
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gint get_map_index_by_nodeId (gchar *nodeId, struct map_nodes_t * mapN) {
    gint i = 0;    
    for (i = 0; i < mapN->numMapNodes; i++) {
		//DEBUG_PC ("i: %d; current: %s // targeted: %s", i, mapN->map[i].verticeId.nodeId, nodeId);
        if (memcmp (mapN->map[i].verticeId.nodeId, nodeId, strlen (nodeId)) == 0) {
			//DEBUG_PC ("Index: %d", i);
			return i;            
        }
    }
	//DEBUG_PC ("Index: %d", index);
    return -1;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Get the edge e enabling reaching the computed v in mapNodes
 * 
 *  @param e
 *  @param v
 *  @param mapN
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void get_edge_from_map_by_node (struct edges_t *e, struct nodes_t* v, struct map_nodes_t *mapN) {	
	//DEBUG_PC ("Get the Edge into map from node v: %s", v.nodeId);	
	// Get the edge reaching the node v from mapNodes
	gint map_vIndex = get_map_index_by_nodeId (v->nodeId, mapN);	
	//DEBUG_PC ("aNodeId: %s --> zNodeId: %s", mapN->map[map_vIndex].predecessor.aNodeId.nodeId, mapN->map[map_vIndex].predecessor.zNodeId.nodeId);	
	struct edges_t *te = &(mapN->map[map_vIndex].predecessor);	
	duplicate_edge (e, te);
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Get the edge from the predecessors array for a given node n
 * 
 *  @param e
 *  @param n
 *  @param predecessors
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void get_edge_from_predecessors (struct edges_t *e, struct nodes_t* n, struct pred_t *predecessors) {
	g_assert(predecessors);
	DEBUG_PC ("Get edge outgoing node %s from predecessors list", n->nodeId);
	//print_predecessors (predecessors);
	for (gint i = 0; i < predecessors->numPredComp; i++) {
		struct pred_comp_t *pred = &(predecessors->predComp[i]);
		if (compare_node_id (n, &pred->v) == 0) {
			// Add to the predecessors list
			struct edges_t *te = &(pred->e);
			DEBUG_PC("add e (linkId): %s", te->linkId);
			duplicate_edge (e, te);
			return;
		}	
	}	
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Construct the path using the predecessors list
 * 
 *  @param path
 *  @param predecessors
 *	@param s
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void build_path (struct compRouteOutputItem_t *p, struct pred_t *predecessors, struct service_t *s) {
	// Get the source device Id	of the network connectivity service
	struct nodes_t *v = create_node();
	// Src Node of the Service set to v
	duplicate_string(v->nodeId, s->service_endpoints_id[0].device_uuid);
								  	
	// Get the edge for v in predecessors
	struct edges_t* e = create_edge();
	get_edge_from_predecessors (e, v, predecessors);	
	// Get the target for e
	struct nodes_t u;	
	duplicate_node_id (&e->zNodeId, &u);
	//DEBUG_PC ("u: %s", u.nodeId);
	struct path_constraints_t* pathCons = get_path_constraints(s);		

	// Add route element to the path being constructed
	gint k = 0;
	duplicate_node_id (&e->aNodeId, &p->routeElement[k].aNodeId);
	duplicate_node_id (&e->zNodeId, &p->routeElement[k].zNodeId);
	duplicate_string(p->routeElement[k].aEndPointId, e->aEndPointId);
	duplicate_string(p->routeElement[k].zEndPointId, e->zEndPointId);
	duplicate_string(p->routeElement[k].linkId, e->linkId);
	duplicate_string(p->routeElement[k].aTopologyId, e->aTopologyId);
	duplicate_string(p->routeElement[k].zTopologyId, e->zTopologyId);
	duplicate_string(p->routeElement[k].contextId, s->serviceId.contextId);
	p->numRouteElements++;

	// Get Dst Node of connectivity service
	struct nodes_t* dst = create_node();
	duplicate_string(dst->nodeId, s->service_endpoints_id[1].device_uuid);
	while (compare_node_id (&u, dst) != 0) {
		k++; 
		p->numRouteElements++;			
		duplicate_node_id (&u, v);
		get_edge_from_predecessors (e, v, predecessors);
		// Get the target u		
		duplicate_node_id (&e->zNodeId, &u);
		// Add route element to the path being constructed		
		duplicate_node_id (&e->aNodeId, &p->routeElement[k].aNodeId);
		duplicate_node_id (&e->zNodeId, &p->routeElement[k].zNodeId);
		duplicate_string(p->routeElement[k].aEndPointId, e->aEndPointId);
		duplicate_string(p->routeElement[k].zEndPointId, e->zEndPointId);
		duplicate_string(p->routeElement[k].linkId, e->linkId);
		duplicate_string(p->routeElement[k].aTopologyId, e->aTopologyId);
		duplicate_string(p->routeElement[k].zTopologyId, e->zTopologyId);
		duplicate_string(p->routeElement[k].contextId, s->serviceId.contextId);		
	}		
	g_free(e); g_free(v); g_free(pathCons);
	//DEBUG_PC ("Path is constructed");	
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Print the graph for DEBUG_PCging purposes
 * 
 *  @param g
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
void print_graph (struct graph_t *g) {
	g_assert(g);
    DEBUG_PC ("================================================================");
    DEBUG_PC ("===========================   GRAPH   ==========================");
    DEBUG_PC ("================================================================");
	DEBUG_PC("Graph Num Vertices: %d", g->numVertices);    
    
    for (gint i = 0; i < g->numVertices; i++) {
        DEBUG_PC ("Head Vertice [%s]", g->vertices[i].verticeId.nodeId);
        for (gint j = 0; j < g->vertices[i].numTargetedVertices; j++)
        {
            DEBUG_PC ("  Tail Vertice: %s", g->vertices[i].targetedVertices[j].tVertice.nodeId);
            for (gint k = 0; k < g->vertices[i].targetedVertices[j].numEdges; k++)
            {
                struct edges_t *e = &(g->vertices[i].targetedVertices[j].edges[k]);
				DEBUG_PC ("%s(%s) --> %s(%s) [C: %f, Bw: %f b/s, Delay: %f ms]", e->aNodeId.nodeId, e->aEndPointId, e->zNodeId.nodeId, 
								e->zEndPointId, e->cost, e->availCap, e->delay);				
           }
        }       
    }     
    return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Look for a given edge into the graph
 *
 *  @param verticeIndex
 *	@param targetedVerticeIndex
 *  @param e
 *  @param g
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gint graph_edge_lookup (gint verticeIndex, gint targetedVerticeIndex, struct edges_t *e, struct graph_t *g)	{
	gint indexEdge = -1;
	
	for (gint j = 0; j < g->vertices[verticeIndex].targetedVertices[targetedVerticeIndex].numEdges; j++) {
		struct edges_t *e2 = &(g->vertices[verticeIndex].targetedVertices[targetedVerticeIndex].edges[j]);
		if ((compare_node_id (&e->aNodeId, &e2->aNodeId) == 0) &&
			(compare_node_id (&e->zNodeId, &e2->zNodeId) == 0) &&
			(strcmp (e->aEndPointId, e2->aEndPointId) == 0) &&
			(strcmp (e->zEndPointId, e2->zEndPointId) == 0) &&
			(strcmp(e->linkId, e2->linkId) == 0)) {
			DEBUG_PC ("%s (%s) --> %s (%s) [linkId: %s] FOUND in the Graph at index: %d", e->aNodeId.nodeId, e->aEndPointId, e->zNodeId.nodeId, 
							e->zEndPointId, e->linkId, j);
			indexEdge = j;
			return indexEdge;
		}		
	}	
	return indexEdge;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Look for a given vertice within the graph using the nodeId
 *
 *  @param nodeId
 *	@param g
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gint graph_vertice_lookup (gchar *nodeId, struct graph_t *g)
{
    gint index = -1; 
	//DEBUG_PC("Searching Node: %s", nodeId);
    for (gint i = 0; i < g->numVertices; i++) {
		//DEBUG_PC("Checked Graph Node: %s", g->vertices[i].verticeId.nodeId);
		if (memcmp (g->vertices[i].verticeId.nodeId, nodeId, strlen (nodeId)) == 0)
        {
            index = i;
            //DEBUG_PC ("%s is found in the graph vertice [%d]", nodeId, index);
            break;
        }     
    }  
    return (index);
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Check if a nodeId is already considered into the set of targeted vertices from a given vertice
 *
 *  @param nodeId
 *  @param vIndex
 *  @param g
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gint graph_targeted_vertice_lookup (gint vIndex, gchar *nodeId, struct graph_t *g)
{
    gint addedTargetedVerticeIndex = -1;
    gint i = 0;
    
    if (g->vertices[vIndex].numTargetedVertices == 0)
    {
        return (addedTargetedVerticeIndex);
    }
    
    for (i = 0; i < g->vertices[vIndex].numTargetedVertices; i++)
    {
        if (memcmp (g->vertices[vIndex].targetedVertices[i].tVertice.nodeId, nodeId, strlen (nodeId)) == 0)
        {
            DEBUG_PC ("Targeted %s reachable from %s", nodeId, g->vertices[vIndex].verticeId.nodeId);
            addedTargetedVerticeIndex = i;
            return (addedTargetedVerticeIndex);
        }        
    }    
    // not found ...    
    return (addedTargetedVerticeIndex);
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Check if a nodeId is already considered into the set of targeted vertices from a given vertice, if not to be added
 *
 *  @param nodeId
 *  @param vIndex
 *  @param g
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gint graph_targeted_vertice_add (gint vIndex, gchar *nodeId, struct graph_t *g)
{
    gint addedTargetedVerticeIndex = -1;
    gint i = 0;
    
    if (g->vertices[vIndex].numTargetedVertices == 0)
    {
        //DEBUG_PC ("targeted vertice %s being reachable from vertice %s", nodeId, g->vertices[vIndex].verticeId.nodeId);        
        addedTargetedVerticeIndex = 0;
        return (addedTargetedVerticeIndex);
    }
    
    for (i = 0; i < g->vertices[vIndex].numTargetedVertices; i++)
    {        
		if (memcmp (g->vertices[vIndex].targetedVertices[i].tVertice.nodeId, nodeId, strlen (nodeId)) == 0)
        {
            //DEBUG_PC ("Targeted vertice %s is already considered in the reachable from vertice %s", nodeId, g->vertices[vIndex].verticeId.nodeId);
            addedTargetedVerticeIndex = -1;
            return (addedTargetedVerticeIndex);
        }        
    }    
    // It is not found, next to be added at i position
    addedTargetedVerticeIndex = i;
    return (addedTargetedVerticeIndex);
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_tools.c
 * 	@brief Remove edge from the graph
 *
 *  @param g
 *  @param e
 * 
 * 	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
void remove_edge_from_graph (struct graph_t *g, struct edges_t *e) {
	// Find the ingress vertice into the graph
	DEBUG_PC ("Removing from Graph %s[%s]) ---> %s[%s] (linkId: %s)", e->aNodeId.nodeId, e->aEndPointId, e->zNodeId.nodeId, e->aEndPointId, e->linkId);
	gint verticeIndex = -1;		
	verticeIndex = graph_vertice_lookup (e->aNodeId.nodeId, g);
	if (verticeIndex == -1)	{
		DEBUG_PC ("Edge w/ %s is NOT in the Graph!!", e->aNodeId.nodeId);
		return;
	}
	
	// Find the targeted vertice from vertice Id
	gint targetedVerticeIndex = -1;
	targetedVerticeIndex = graph_targeted_vertice_lookup (verticeIndex, e->zNodeId.nodeId, g);
	if (targetedVerticeIndex == -1)	{
		DEBUG_PC ("%s --> %s NOT in the Graph!!", e->aNodeId.nodeId, e->zNodeId.nodeId);
		return;
	}	
	//DEBUG_PC ("%s --> %s found in the Graph", e->aNodeId.nodeId, e->zNodeId.nodeId);
	
	// Get the edge position
	gint edgeIndex = -1;
	edgeIndex = graph_edge_lookup (verticeIndex, targetedVerticeIndex, e, g);
	if (edgeIndex == -1) {
		DEBUG_PC ("%s --> %s NOT in the Graph!!", e->aNodeId.nodeId, e->zNodeId.nodeId);
		return;
	}