package graphTheory.algorithms.minimumBranching;

import graphTheory.graph.Arc;
import graphTheory.graph.Graph;
import graphTheory.instances.spanningTree.MinimumBranchingArborescenceInstance;
import graphTheory.utils.Couple;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * The Edmond algorithm, or the Chu Liu Algorithm, compute in a directed graph a
 * minimum branching tree, equivalent to the minimum spanning tree in a directed
 * graph. Given a root r and weight on the arcs, the algorithm compute the
 * minimum weighted directed tree rooted in r spanning every nodes of the graph.
 * 
 * This algorithm is similar to the Kruskal algorithm.
 * 
 * Every node choose an input arc with minimum cost. If the union of all those
 * arcs is a tree rooted in r, return the tree. Otherwise there is a cycle.
 * 
 * Replace that cycle by a node vc. Every input arc a = (u,v) in the cycle
 * becomes an input arc of vc with modified cost. The modified cost is equals to
 * the cost of a minus the cost of v chosen arc (belonging to the cycle). Every
 * output arc of the cycle becomes an output arc of vc with same cost. Every arc
 * where input and output belongs to the cycle does not appear in that new
 * graph.
 * 
 * Restart the algorithm on that new graph, until there is no cycle.
 * 
 * Once a tree T is returned, backtrack on every contracted cycle. Replace the
 * node vc by the corresponding cycle. Add every arc of the cycle. Every arc of
 * T incomming or outgoing from vc is replaced by the corresponding arc
 * incomming or outgoing from the cycle. If an incomming arc (u,v) is added to
 * T, then remove the v choosen arc from the cycle and T.
 * 
 * Contrary to the other verion of Edmond Chu Liu, this version is iterative.
 * But it modifies the graph during computation by adding the contracted nodes
 * and then deleting them at the end of the algorithm.
 * 
 * @author Watel Dimitri
 * 
 * @see #EdmongChuLiuAlgorithm
 */
public class EdmondChuLiuIterAlgorithm extends MinimumBranchingAlgorithm {
	
	/**
	 * Comparator to compare arc costs.
	 */
	private Comparator<Arc> comp = new Comparator<Arc>() {

		@Override
		public int compare(Arc o1, Arc o2) {
			Integer i1 = getCost(o1);
			Integer i2 = getCost(o2);
			if (i1 == null)
				return -1;
			else if (i1.equals(i2))
				return 0;
			else if (i2 == null)
				return 1;
			else
				return i1.compareTo(i2);
		}

	};

	/**
	 * Costs of the arcs added during the algorithm (linked to the contracted
	 * nodes)
	 */
	private HashMap<Arc, Integer> virtCost;

	/**
	 * @return the cost of the arc a, even if a was added during the algorithm.
	 */
	private Integer getCost(Arc a) {
		Integer i = virtCost.get(a);
		if (i == null)
			i = instance.getCost(a);
		return i;
	}

	/**
	 * Map containing for each node the input arc of minimum cost.
	 */
	private HashMap<Integer, Arc> arcOfNode;

	@Override
	protected void computeWithoutTime() {

		arcOfNode = new HashMap<Integer, Arc>();
		contractions = new LinkedList<Couple<Integer, HashSet<Integer>>>();
		arcContractionLink = new HashMap<Arc, Arc>();
		virtCost = new HashMap<Arc, Integer>();

		HashSet<Arc> h = new HashSet<Arc>();
		markEdges(h);
		HashSet<Integer> cycle;
		while (true) {

			cycle = findCycle(h);
			if (cycle == null)
				break;

			contractCycle(cycle);

			h.clear();
			markEdges(h);
		}

		returnCyclesBack(h);

		cost = 0;
		arborescence = h;
		for (Arc a : arborescence)
			cost += instance.getCost(a);

	}

	/**
	 * Id used to add new nodes to the graph.
	 */
	private int maxId = -1;

	/**
	 * Fill h with every input arc of minimum cost for each node. arcOfNode is
	 * modified.
	 * 
	 * @param h
	 */
	private void markEdges(HashSet<Arc> h) {
		for (Integer v : instance.getGraph().getVertices()) {
			maxId = Math.max(maxId, v + 1);
			if (v.equals(instance.getRoot()))
				continue;
			markEdge(h, v);
		}
	}

	/**
	 * Add to h the input arc of minimum cost of v. arcOfNode is modified.
	 */
	private void markEdge(HashSet<Arc> h, Integer v) {
		Arc b = Collections.min(instance.getGraph().getInputArcs(v), comp);
		h.add(b);
		arcOfNode.put(v, b);
	}

	/**
	 * @param h
	 * @return one cycle of the induced graph by h.
	 */
	private HashSet<Integer> findCycle(HashSet<Arc> h) {
		Graph g = instance.getGraph().getInducedGraphFromArc(h);
		ArrayList<Integer> ar = g.getOneDirectedCycle();
		if (ar == null)
			return null;
		HashSet<Integer> cycle = new HashSet<Integer>();
		for (Integer v : ar)
			cycle.add(v);
		return cycle;
	}

	/**
	 * Map linking every arc entering or outgoing from a contraction node to the
	 * corresponding arc entering or outgoing from the corresponding cycle.
	 */
	private HashMap<Arc, Arc> arcContractionLink;

	/**
	 * List of couples linking every contraction node to the corresponding
	 * cycle.
	 */
	private LinkedList<Couple<Integer, HashSet<Integer>>> contractions;

	/**
	 * Virtually remove every node and arc in the cycle, and add a new node
	 * replacing the cycle. Each ingoing or outgoing arc in or out the cycle are
	 * copied as an arc ingoing or outgoing this new node.
	 */
	private void contractCycle(HashSet<Integer> cycle) {
		instance.getGraph().addVertice(maxId);
		int contractNode = maxId;
		maxId++;

		setContractionInputs(contractNode, cycle);
		setContractionOutputs(contractNode, cycle);

		removeCycle(cycle);

		contractions.addFirst(new Couple<Integer, HashSet<Integer>>(
				contractNode, cycle));
	}

	/**
	 * Virtually remove every node of the cycle.
	 * 
	 * @param cycle
	 */
	private void removeCycle(HashSet<Integer> cycle) {
		for (Integer n : cycle)
			instance.getGraph().virtuallyRemoveVertice(n);

	}

	/**
	 * Add for each input arc (u,v) of the cycle an input arc of contractInteger
	 * with modified cost : cost(u,v) - cost(v input arc in the cycle). If
	 * multiple arcs (u,*) enter the cycle, chose the one with minimum modified
	 * cost.
	 * 
	 * @param contractNode
	 * @param cycle
	 */
	private void setContractionInputs(Integer contractNode,
			HashSet<Integer> cycle) {
		HashMap<Integer, Arc> inputs = new HashMap<Integer, Arc>();
		HashMap<Integer, Integer> inputsC = new HashMap<Integer, Integer>();

		Arc a;
		Iterator<Arc> it;
		for (Integer n : cycle) {
			Arc aon = arcOfNode.get(n);
			it = instance.getGraph().getInputArcsIterator(n);
			while (it.hasNext()) {
				a = it.next();
				Integer input = a.getInput();
				if (cycle.contains(input))
					continue;
				int relCostA = getCost(a) - getCost(aon);
				Arc b = inputs.get(input);
				if (b != null) {
					int relCostB = inputsC.get(input);
					if (relCostA < relCostB) {
						inputs.put(input, a);
						inputsC.put(input, relCostA);
					}
				} else {
					inputs.put(input, a);
					inputsC.put(input, relCostA);
				}
			}
		}
		for (Integer input : inputs.keySet()) {
			Arc b = instance.getGraph().addDirectedEdge(input, contractNode);
			arcContractionLink.put(b, inputs.get(input));
			virtCost.put(b, inputsC.get(input));
		}
	}

	/**
	 * Add for each output arc (v,u) of the cycle an output arc of contractNode
	 * with same cost. If multiple arcs (*,u) out from the cycle, chose the one
	 * with minimum cost.
	 * 
	 * @param contractNode
	 * @param cycle
	 */
	private void setContractionOutputs(Integer contractNode,
			HashSet<Integer> cycle) {
		HashMap<Integer, Arc> outputs = new HashMap<Integer, Arc>();
		HashMap<Integer, Integer> outputsC = new HashMap<Integer, Integer>();

		Arc a;
		Iterator<Arc> it;
		for (Integer n : cycle) {

			it = instance.getGraph().getOutputArcsIterator(n);
			while (it.hasNext()) {
				a = it.next();
				Integer output = a.getOutput();
				if (cycle.contains(output))
					continue;

				int costA = getCost(a);
				Arc b = outputs.get(output);
				if (b != null) {
					int costB = outputsC.get(output);
					if (costA < costB) {
						outputs.put(output, a);
						outputsC.put(output, costA);
					}
				} else {
					outputs.put(output, a);
					outputsC.put(output, costA);
				}

			}

		}
		for (Integer output : outputs.keySet()) {
			Arc b = instance.getGraph().addDirectedEdge(contractNode, output);
			arcContractionLink.put(b, outputs.get(output));
			virtCost.put(b, outputsC.get(output));
		}
	}

	/**
	 * Backtrack on every contracted cycle to : - remove the added contraction
	 * node vc - replace every arc entering or outgoing from vc by the
	 * corresponding arc entering or outgoing from the cycle
	 * 
	 * @param h
	 */
	private void returnCyclesBack(HashSet<Arc> h) {
		for (Couple<Integer, HashSet<Integer>> contraction : contractions) {
			Integer contractNode = contraction.first;
			HashSet<Integer> cycle = contraction.second;

			Iterator<Arc> it = instance.getGraph().getInputArcsIterator(
					contractNode);
			while (it.hasNext()) {
				Arc b = it.next();
				if (!h.contains(b))
					continue;
				Arc a = arcContractionLink.remove(b);
				arcOfNode.put(a.getOutput(), a);
				h.remove(b);
				break;
			}

			it = instance.getGraph().getOutputArcsIterator(contractNode);
			while (it.hasNext()) {
				Arc c = it.next();
				if (h.remove(c))
					h.add(arcContractionLink.get(c));
			}

			instance.getGraph().removeVertice(contractNode);

			for (Integer n : cycle) {
				instance.getGraph().cancelVirtuallyRemoveVertice(n);
				h.add(arcOfNode.get(n));
			}
		}
	}

}
