package graphTheory.algorithms.steinerProblems.steinerArborescenceApproximation;

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

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 paths from the root using the dijkstra
 * algorithm and compute the union of all the shortest path from the root to the
 * terminals.
 * 
 * @author Watel Dimitri
 * 
 */
public class ShPAlgorithm 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.setInstance(aspi);
		alg.setComputeOnlyCosts(false);
		alg.compute();

		HashMap<Integer, List<Arc>> shp = alg.getShortestPaths();

		// Merge the shortest paths from root to terminals
		Iterator<Integer> it = instance.getRequiredVerticesIterator();
		while (it.hasNext()) {
			v = it.next();
			h.addAll(shp.get(v));
		}

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

		arborescence = h;
		cost = c;
	}

}
