package graphTheory.algorithms.steinerProblems.steinerArborescenceApproximation;

import graphTheory.algorithms.shortestDistance.arcCost.ArcDijkstraOneSourceAlgorithm;
import graphTheory.graph.Arc;
import graphTheory.graph.DirectedGraph;
import graphTheory.instances.shortestPath.ArcShortestPathOneSourceInstance;
import graphTheory.instances.steiner.classic.SteinerDirectedInstance;

import java.awt.image.DirectColorModel;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

/**
 * 
 * This algorithm is a k-approximation for the Directed Steiner Tree problem. It
 * returns the union of all the shortest path from the root to all the
 * terminals.
 * 
 * To do so, it computes all the shortest path from the root using the dijkstra
 * algorithm and and keep the shortest one reaching a terminal, then set the weight 
 * of the arcs of this path to 0 and restart until all the terminals are covered.
 * 
 * @author Watel Dimitri
 * 
 */
public class ShP2Algorithm extends SteinerArborescenceApproximationAlgorithm {


	
	@Override
	protected void computeWithoutTime() {
		HashMap<Arc, Integer> costs = instance.getCosts();
		HashSet<Arc> h = new HashSet<Arc>();
		Integer v;

		// Create a shortest path instance
		ArcShortestPathOneSourceInstance aspi = new ArcShortestPathOneSourceInstance(
				instance.getGraph());
		aspi.setCosts(costs);
		aspi.setSource(instance.getRoot());

		// Create a dijkstra algorithm
		ArcDijkstraOneSourceAlgorithm alg = new ArcDijkstraOneSourceAlgorithm();
		alg.setCheckFeasibility(false); // No need to check if there is a shortest path from the root to all nodes
		alg.setComputeOnlyCosts(false);
		alg.setInstance(aspi);
		
		HashSet<Integer> toCover = new HashSet<Integer>(instance.getRequiredVertices());
		do{

			alg.compute();
			HashMap<Integer, Integer> shc = alg.getCosts();
			
			// Get the shortest path from the root to any terminal
			Integer term = getNearestRequiredVertice(shc, toCover);

			List<Arc> path = alg.getShortestPaths().get(term);
			for(Arc a : path){
				costs.put(a, 0);
				h.add(a);
			}
			toCover.remove(term);

		}while(!(toCover.isEmpty()));
		
		// Compute the cost of optimal solution
		int c = 0;
		for (Arc a : h)
			c += instance.getCost(a);

		arborescence = h;
		cost = c;
	}

	private Integer getNearestRequiredVertice(HashMap<Integer, Integer> shc, HashSet<Integer> toCover){
		int bestCost = Integer.MAX_VALUE;
		Integer nearestTerm = null;
		for(Integer term : toCover){
			int cost = shc.get(term);
			if(cost < bestCost){
				bestCost = cost; 
				nearestTerm = term;
			}
		}
		return nearestTerm;
	}

}
