package graphTheory.algorithms.steinerProblems.steinerArborescenceApproximation;

import graphTheory.algorithms.shortestDistance.arcCost.RoyWarshallFloydAlgorithm;
import graphTheory.graph.Arc;
import graphTheory.graph.DirectedGraph;
import graphTheory.instances.shortestPath.ArcShortestPathsInstance;
import graphTheory.instances.steiner.classic.SteinerDirectedInstance;
import graphTheory.utils.Couple;

import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

/**
 * 
 * Implementation of the G_F_Triangle algorithm.
 * <p>
 * This algorithm returns a feasible solution for the Directed Steiner Tree
 * problem. It is a greedy algorihm which uses a sub-algorihthm named FLAC.
 * <p>
 * FLAC is designed to returns a feasible solution for the minimum Density
 * Directed Steiner Tree problem: it searches for a tree rooted in the root of
 * the instance which spans a part of the terminal. It try to minimize the total
 * cost of the tree divided by the number of terminals.
 * <p>
 * G_F_Triangle first builds the closure metric of the graph. It then works
 * exclusively in that new graph. It uses FLAC to span some terminals, delete those terminals, and repeat FLAC
 * to span other terminals. It continues until all the terminals are reached.
 * <p>
 * To span the terminals, FLAC grows a flow from the terminals: we call them
 * sources. That flow is send through the entering arcs, with a flow rate equals
 * to 1 L/s, considering the volume of an arc is its weight. Then, when an arc
 * is full (we say saturated), the source feeds its entering arcs. If two
 * sources reach the same arc with a path of saturated arcs, the flow rate is 2
 * L/s. And if more sources reaches the arc, the flow rate increases again: the
 * flow rate inside an arc is equals to the number of sources it can reach with
 * paths of saturated arcs
 * <p>
 * FLAC continue until the root is reached, and we return the set of saturated
 * arcs linked to the root. As we want to return a tree, each time an arc is
 * saturated, if a node is connected to the same source with two paths of
 * saturated arcs, we delete that last saturated arc.
 * <p>
 * 
 * @author Watel Dimitri
 * 
 */
public class GFLACTRAlgorithm extends SteinerArborescenceApproximationAlgorithm {

	// --------------------   Directed Steiner Tree Part --------------------//


	@Override
	protected void computeWithoutTime() {

		ArcShortestPathsInstance aspi = new ArcShortestPathsInstance(instance.getGraph());
		aspi.setCosts(instance.getCosts());

		// Compute shortest paths

		RoyWarshallFloydAlgorithm rwf = new RoyWarshallFloydAlgorithm();
		rwf.setInstance(aspi);
		rwf.setCheckFeasibility(false);
		rwf.setComputeOnlyCosts(false);
		rwf.compute();

		// Generate the metric closure instance

		DirectedGraph closureGraph = new DirectedGraph();
		Iterator<Integer> it = instance.getGraph().getVerticesIterator();
		while(it.hasNext())
			closureGraph.addVertice(it.next());

		SteinerDirectedInstance closureInstance = new SteinerDirectedInstance(closureGraph);
		closureInstance.setRoot(instance.getRoot());
		it = instance.getRequiredVerticesIterator();
		while(it.hasNext())
			closureInstance.setRequired(it.next());

		it = closureGraph.getVerticesIterator();
		Iterator<Integer> it2;
		Integer u,v;
		while(it.hasNext()){
			u = it.next();
			it2 = closureGraph.getVerticesIterator();
			while(it2.hasNext()){
				v = it2.next();
				Integer shortestCost = rwf.getCosts().get(new Couple<Integer,Integer>(u,v));
				if (shortestCost != null){ 
					Arc a = closureGraph.addDirectedEdge(u, v);
					closureInstance.setCost(a, shortestCost);
				}
			}
		}

		// Compute GFLAC on the closure instance

		GFLACAlgorithm gflac = new GFLACAlgorithm();
		gflac.setInstance(closureInstance);
		gflac.setCheckFeasibility(false);
		gflac.compute();

		HashSet<Arc> h = gflac.getArborescence();
		HashSet<Arc> h2 = new HashSet<Arc>();
		Integer cst = 0;

		// Build the solution from the closure instance solution

		for(Arc a : h){
			Couple<Integer,Integer> c = new Couple<Integer,Integer>(a.getInput(), a.getOutput());
			List<Arc> path = rwf.getShortestPaths().get(c);
			for(Arc b : path){
				if(h2.add(b))
					cst += instance.getCost(b);
			}
		}

		arborescence = h2;
		cost = cst;

	}


}