package examen;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import com.net2plan.interfaces.networkDesign.IAlgorithm;
import com.net2plan.interfaces.networkDesign.Net2PlanException;
import com.net2plan.interfaces.networkDesign.NetPlan;
import com.net2plan.libraries.GraphUtils;
import com.net2plan.libraries.IPUtils;
import com.net2plan.utils.BooleanUtils;
import com.net2plan.utils.DoubleUtils;
import com.net2plan.utils.Pair;
import com.net2plan.utils.Triple;
public class examFeb2016_APELLIDOS_NOMBRE implements IAlgorithm
{
private Set<Long> linkIds;
private Set<Long> nodeIds;
private long[] demandIdsVector;
private long[] linkIdsVector;
private Map<Long, Double> u_e, h_d;
private Map<Long,Pair<Long,Long>> linkMap;
private Map<Long,Pair<Long,Long>> demandMap;
@Override
public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
{
final int N = netPlan.getNumberOfNodes();
final int D = netPlan.getNumberOfDemands();
final int E = netPlan.getNumberOfLinks();
/* Initialize some variables */
nodeIds = netPlan.getNodeIds();
linkIds = netPlan.getLinkIds();
linkMap = netPlan.getLinkMap();
demandMap = netPlan.getDemandMap();
demandIdsVector = netPlan.getDemandIdsVector();
linkIdsVector = netPlan.getLinkIdsVector();
u_e = netPlan.getLinkCapacityMap();
h_d = netPlan.getDemandOfferedTrafficMap();
/* A COMPLETAR (5%): Guardar los parametros de entrada en variables locales, con el mismo nombre que el parametro */
/* A COMPLETAR (5%): Establecer la solución inicial (peso para cada enlace), que se almacena en un mapa (de nombre current_weights_e) que almacene clave-valor = ID_enlace - peso asociado */
System.out.println("initial solution " + current_weights_e);
/* A COMPLETAR (5%): Calcular la congestión inicial y guardarla en current_congestion */
/* A COMPLETAR (10%): Actualizar la mejor solucion encontrada hasta la fecha, que en este punto es una COPIA de la solucion inicial. */
/* La mejor solución se guarda como best_weights_e (Map<Long,Double>) y double best_congestion */
/* A COMPLETAR (75%): implementación del algoritmo realizando la búsqueda best-fit */
/* Bucle principal */
/* Chequear la solucion final encontrada*/
if (best_weights_e.size() != E)
throw new Net2PlanException ("Error: El vector solucion no esta bien codificado");
for (int e = 0 ; e < E ; e ++)
if ((best_weights_e.get(linkIdsVector[e]) <= 0) || (best_weights_e.get(linkIdsVector[e]) > maxLinkWeight))
throw new Net2PlanException ("Error: el peso asociado al enlace " + e + " no es correcto: " +best_weights_e.get(linkIdsVector[e]));
if (Math.abs(best_congestion- computeNetCongestion(nodeIds, linkMap, best_weights_e, demandMap, u_e, h_d)) > 1e-3) throw new Net2PlanException ("La solución devuelta y la congestión devuelta no encajan");
/* Devolver la mejor solucion encontrada */
netPlan.removeAllRoutes();
netPlan.removeAllProtectionSegments();
IPUtils.setECMPForwardingRulesFromLinkWeights(netPlan, best_weights_e);
System.out.println(best_weights_e);
return "Ok! Congestion : " + best_congestion;
}
@Override
public String getDescription()
{
return "";
}
@Override
public List<Triple<String, String, String>> getParameters()
{
List<Triple<String, String, String>> algorithmParameters = new ArrayList<Triple<String, String, String>>();
algorithmParameters.add(Triple.of("maxLinkWeight", "5", "Maximum OSPF weight associated to a link"));
return algorithmParameters;
}
/* computes the congestion in the network (the objective function of the problem) */
private double computeNetCongestion (Set<Long> nodeIds, Map<Long,Pair<Long,Long>> linkMap, Map<Long,Double> linkWeightMap, Map<Long,Pair<Long,Long>> demandMap, Map<Long, Double> u_e , Map<Long,Double> h_d)
{
final int E = u_e.size();
double[][] f_te = IPUtils.computeECMPRoutingTableMatrix(nodeIds, linkMap, linkWeightMap);
List<Long> d_p = new ArrayList<Long>();
List<Double> x_p = new ArrayList<Double>();
List<List<Long>> pathList = new ArrayList<List<Long>>();
GraphUtils.convert_fte2xp(nodeIds,linkMap, demandMap, h_d, f_te, d_p, x_p, pathList);
double[] y_e = GraphUtils.convert_xp2ye(linkMap, x_p, pathList);
double [] _u_e = new double [u_e.size()];
for(int e=0;e<E; e++)
_u_e[e] = u_e.get(linkIdsVector[e]);
return DoubleUtils.maxValue(DoubleUtils.divide(y_e, _u_e));
}
}
