package graphTheory.instances.steiner.classic;

import graphTheory.graph.Arc;
import graphTheory.graph.DirectedGraph;
import graphTheory.graph.Graph;
import graphTheory.graph.UndirectedGraph;
import graphTheory.utils.Math2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

/**
 * 
 * Instance for the Directed Steiner Tree problem : given a graph,
 * one node {@link #root} of that graph, some nodes called terminals
 * or required vertices,  and weight over the arcs, return the
 * minimum cost directed tree rooted in {@link #root} spanning all the terminals.
 * 
 * @author Watel Dimitri
 *
 */
public class SteinerDirectedInstance extends SteinerInstance implements
		Cloneable {

	public SteinerDirectedInstance(DirectedGraph g) {
		super(g);
	}

	Integer root;

	public Integer getRoot() {
		return root;
	}

	public void setRoot(Integer root) {
		if (root != null) {
			Integer r = getRoot();
			if (r != null)
				graph.setCircleSymbol(r);
			this.root = root;
			graph.setSquareSymbol(root);
		}
	}

	public DirectedGraph getGraph() {
		return (DirectedGraph) graph;
	}

	/**
	 * 
	 * From a undirected steiner instance sui and an optimal solution optTree of that instance,
	 * build and return a Strongly Connected Directed Steiner instance sdi with same optimal cost
	 * as sui.
	 * <p>
	 * sdi contains all the nodes in sui.
	 * The root of sdi is chosen among the nodes in optTree. Then the arcs of opttree are
	 * directed from the root to the leaves of optTree.
	 * Each other edge is then uniformly randomly directed. The cost of the build arc is the same
	 * as the cost of the edge is was built from.
	 * <p>
	 * This does not ensure the graph is strongly connected. So we add arcs between couples of
	 * nodes chosen uniformly randomly until the graph is strongly connected. The cost of this
	 * arc is the shortest path cost between that couple of nodes in the undirected instance sui.
	 * <p>
	 * As a consequence, the cost of the optimale solution is the same in sui and sdi.
	 * 
	 * @param sui
	 * @param optTree
	 * @return a Strongly Connected Directed Steiner instance sdi with same optimal cost
	 * as sui 
	 */
	public static SteinerDirectedInstance getRandomGraphStronglyConnectedFromUndirectedInstance(
			SteinerUndirectedInstance sui, HashSet<Arc> optTree) {
		DirectedGraph dg = new DirectedGraph();
		SteinerDirectedInstance sdi = new SteinerDirectedInstance(dg);

		UndirectedGraph ug = sui.getGraph();

		int s = ug.getNumberOfVertices();
		
		// Those maps associate an id from 1 to s to each node (the nodes are not
		// necessarily numbered from 1 to s at the beginning of the methods)
		HashMap<Integer, Integer> nodes2ids = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> ids2nodes = new HashMap<Integer, Integer>();
		
		// shpInSui contains for each couple of nodes the shortest path costs in sui
		// between those nodes
		Integer[][] shpInSui = new Integer[s][s];
		
		// connectionsInSdi[i][j] is true if sdi contains a path from the node
		// if id i to the node of id j. At the beginning, sdi is empty and do not
		// contains any arc
		boolean[][] connectionsInSdi = new boolean[s][s];
		
		
		// We firstly build every node of sdi and place every terminals
		// but we do not place the root.
		
		Iterator<Integer> it = ug.getVerticesIterator();
		Integer n;

		int id = 0;
		while (it.hasNext()) {
			n = it.next();
			dg.addVertice(n);
			sdi.setRequired(n, sui.isRequired(n));

			shpInSui[id][id] = 0; // The shortest path from a node to itself is 0
			connectionsInSdi[id][id] = true; // sdi contains a path from any node to itself 

			nodes2ids.put(n, id);
			ids2nodes.put(id++, n);
		}

		// We get the induced graph of sui by the arcs in optTree
		Graph inducedGraph = ug.getInducedGraphFromArc(optTree);

		// A root is choosen at random inside optTree
		Integer root;
		root = inducedGraph.getRandomVertice();
		sdi.setRoot(root);
		if (sui.getNumberOfRequiredVertices() != 1)
			sdi.setRequired(root, false);
		
		// We directed the edges in optTree from the chosen root
		// to each terminal
		HashSet<Arc> alreadyDirected = new HashSet<Arc>();
		it = inducedGraph.getVerticesIterator();
		Arc aInducedGraph;
		Integer m, p;
		while (it.hasNext()) {
			n = it.next();
			if (!sui.isRequired(n))
				continue;
			ArrayList<Arc> arcs = inducedGraph.getMinimumNumberOfEdgePath(root,
					n);
			m = root;
			for (int i = 0; i < arcs.size(); i++) {
				aInducedGraph = arcs.get(i);
				p = inducedGraph.getNeighbourNode(m, aInducedGraph);
				if (!alreadyDirected.contains(aInducedGraph)) {
					alreadyDirected.add(aInducedGraph);
					Arc a = dg.addDirectedEdge(m, p);
					sdi.setCost(a, sui.getCost(aInducedGraph));
					
					// For each new arc in sdi, we update the connection between the nodes
					connectionsInSdi[nodes2ids.get(a.getInput())][nodes2ids
							.get(a.getOutput())] = true; 
				}
				m = p;
			}

		}

		// We randomly directed the other edges of sui
		
		Iterator<Arc> it2 = ug.getEdgesIterator();
		Arc a;
		while (it2.hasNext()) {
			a = it2.next();

			boolean b = Math2.randomBoolean();
			if (b) {
				n = a.getInput();
				m = a.getOutput();
			} else {
				n = a.getOutput();
				m = a.getInput();
			}

			Integer cost = sui.getCost(a);

			// If the edge was not already directed
			if (!optTree.contains(a)) {
				Arc c = dg.addDirectedEdge(n, m);
				sdi.setCost(c, cost);
				// We udpate the connection betwwen the nodes of the added arc
				connectionsInSdi[nodes2ids.get(n)][nodes2ids.get(m)] = true; 
			}

			// We set the currently known shortest path between the nodes of that arc
			// This shortest path will be updated later
			shpInSui[nodes2ids.get(n)][nodes2ids.get(m)] = cost;
			shpInSui[nodes2ids.get(m)][nodes2ids.get(n)] = cost;
		}

		// We now compute all the shortest path between all couple of nodes
		// using the raw warshall floyd algorithm
		
		Iterator<Integer> itu, itv, itw;
		Integer idu, idv, idw, uv, vw, uw;
		itv = ug.getVerticesIterator();
		while (itv.hasNext()) {
			idv = nodes2ids.get(itv.next());
			itu = ug.getVerticesIterator();
			while (itu.hasNext()) {
				idu = nodes2ids.get(itu.next());
				itw = ug.getVerticesIterator();
				while (itw.hasNext()) {
					idw = nodes2ids.get(itw.next());
					uw = shpInSui[idu][idw];
					uv = shpInSui[idu][idv];
					vw = shpInSui[idv][idw];
					if (uv != null && vw != null) {
						if (uw != null)
							shpInSui[idu][idw] = shpInSui[idw][idu] = Math.min(
									uw, uv + vw);
						else
							shpInSui[idu][idw] = shpInSui[idw][idu] = uv + vw;
					}
					
					// If u is connected to v and v is connected to w, then u is connected to w
					connectionsInSdi[idu][idw] = connectionsInSdi[idu][idw]
							|| (connectionsInSdi[idu][idv] && connectionsInSdi[idv][idw]);
				}
			}
		}
		
		// We now randomly add new arcs to the graph until it is strongly connected:
		// this is true if connectionsInSdi contains only true.
		
		
		// Permute randomly couples of nodes
		int[] shuffledCouples = Math2.getRandomPermutation(s * s);

		for (int i = 0; i < s * s; i++) {
			int shc = shuffledCouples[i];
			int raw = shc / s;
			int column = shc % s;

			// If the nodes are already connected we do nothing
			if (connectionsInSdi[raw][column])
				continue;

			// If not we add a new arc and update connections in sdi
			
			Arc b = dg.addDirectedEdge(ids2nodes.get(raw),
					ids2nodes.get(column));
			
			// The cost of that arc is the shortet path in sui
			sdi.setCost(b, shpInSui[raw][column]); 
			for (int k = 0; k < s; k++) {
				for (int l = 0; l < s; l++) {
					
					// Update connections
					connectionsInSdi[k][l] = connectionsInSdi[k][l]
							|| (connectionsInSdi[k][raw] && connectionsInSdi[column][l]);
				}
			}

		}

		return sdi;
	}

	/**
	 * 
	 * From a undirected steiner instance sui and an optimal solution optTree of that instance,
	 * build and return a Acyclic Directed Steiner instance sdi with same optimal cost
	 * as sui.
	 * <p>
	 * sdi contains all the nodes in sui.
	 * The root of sdi is chosen among the nodes in optTree. Then the arcs of opttree are
	 * directed from the root to the leaves of optTree.
	 * Each other edge is then directed in an acyclic way using breadth-first-search from the root. The cost of the build arc is the same
	 * as the cost of the edge is was built from.
	 * <p>
	 * As a consequence, the cost of the optimale solution is the same in sui and sdi.
	 * 
	 * @param sui
	 * @param optTree
	 * @return a Strongly Connected Directed Steiner instance sdi with same optimal cost
	 * as sui 
	 */
	public static SteinerDirectedInstance getAcyclicGraphFromUndirectedInstance(
			SteinerUndirectedInstance sui, HashSet<Arc> optTree) {

		DirectedGraph dg = new DirectedGraph();
		SteinerDirectedInstance sdi = new SteinerDirectedInstance(dg);
		UndirectedGraph ug = sui.getGraph();

		// We firstly build every node of sdi and place every terminals
				// but we do not place the root.
		
		Iterator<Integer> it = sui.getGraph().getVerticesIterator();
		Integer v;
		while (it.hasNext()) {
			v = it.next();
			dg.addVertice(v);
			sdi.setRequired(v, sui.isRequired(v));
		}

		// We get the induced graph of sui by the arcs in optTree
		Graph inducedGraph = ug.getInducedGraphFromArc(optTree);

		// A root is choosen at random inside optTree
		Integer r = inducedGraph.getRandomVertice();
		sdi.setRoot(r);
		if (sui.getNumberOfRequiredVertices() != 1)
			sdi.setRequired(r, false);

		// We directed the edges in optTree from the chosen root
				// to each terminal
		HashSet<Arc> alreadyUsed = new HashSet<Arc>();
		it = inducedGraph.getVerticesIterator();
		Arc aInducedGraph;
		Integer n, m, p;
		while (it.hasNext()) {
			n = it.next();
			if (!sui.isRequired(n))
				continue;
			ArrayList<Arc> arcs = inducedGraph.getMinimumNumberOfEdgePath(r, n);
			m = r;
			for (int i = 0; i < arcs.size(); i++) {
				aInducedGraph = arcs.get(i);
				p = inducedGraph.getNeighbourNode(m, aInducedGraph);
				if (!alreadyUsed.contains(aInducedGraph)) {
					alreadyUsed.add(aInducedGraph);
					Arc a = dg.addDirectedEdge(m, p);
					sdi.setCost(a, sui.getCost(aInducedGraph));
				}
				m = p;
			}
		}
		
		// Each other edge is directed in an acyclic way using breadth-first-search
		// from the root.

		HashSet<Integer> seen = new HashSet<Integer>();
		LinkedList<Integer> toSee = new LinkedList<Integer>();

		toSee.add(r);
		Integer u;
		while (!toSee.isEmpty()) {
			u = toSee.pollFirst();
			if (seen.contains(u))
				continue;

			Iterator<Arc> it2 = ug.getUndirectedNeighbourEdgesIterator(u);
			while (it2.hasNext()) {
				Arc a = it2.next();
				v = ug.getNeighbourNode(u, a);
				if (alreadyUsed.contains(a)) {
					toSee.add(v);
					continue;
				}
				if (seen.contains(v))
					continue;
				Arc b = dg.addDirectedEdge(u, v);
				sdi.setCost(b, sui.getCost(a));
				toSee.add(v);

			}

			seen.add(u);
		}

		return sdi;

	}

	/** 
	 * From a undirected steiner instance sui build and return a BiDirected Steiner instance sdi with same optimal cost
	 * as sui.
	 * <p>
	 * sdi contains all the nodes in sui and for each edge in sui, sdi contains 2 opposite arcs with same cost.
	 * <p>
	 * As a consequence, the cost of the optimale solution is the same in sui and sdi.
	 */
	public static SteinerDirectedInstance getSymetrizedGraphFromUndirectedInstance(
			SteinerUndirectedInstance sug) {
		DirectedGraph dg = new DirectedGraph();
		SteinerDirectedInstance sdg = new SteinerDirectedInstance(dg);

		Iterator<Integer> it = sug.getGraph().getVerticesIterator();
		Integer v, r = sug.getRandomRequiredVertice();
		while (it.hasNext()) {
			v = it.next();
			dg.addVertice(v);
			sdg.setRequired(v, sug.isRequired(v));
			if (v.equals(r)) {
				sdg.setRoot(v);
				if (sug.getNumberOfRequiredVertices() != 1)
					sdg.setRequired(v, false);
			}
		}

		Iterator<Arc> it2 = sug.getGraph().getEdgesIterator();
		Arc a;
		Integer u;
		while (it2.hasNext()) {
			a = it2.next();
			u = a.getInput();
			v = a.getOutput();

			Arc b1 = dg.addDirectedEdge(u, v);
			Arc b2 = dg.addDirectedEdge(v, u);

			sdg.setCost(b1, sug.getCost(a));
			sdg.setCost(b2, sug.getCost(a));
		}
		return sdg;
	}

	public String toString() {
		StringBuilder s = new StringBuilder();
		s.append("Noeuds\n\n");
		for (Integer n : getGraph().getVertices()) {
			s.append(n);
			if (isRequired(n))
				s.append(" ").append("x");
			if (getRoot().equals(n))
				s.append(" ").append("o");
			s.append("\n");
		}

		s.append("\nArcs\n\n");
		for (Arc a : getGraph().getEdges()) {
			s.append(a).append(" ").append(getCost(a)).append("\n");
		}

		return s.toString();
	}

	@Override
	public boolean hasSolution() {
		ListIterator<Integer> it = this.getRequiredVerticesIterator();
		while (it.hasNext()) {
			if (!graph.areConnectedByDirectedPath(root, it.next()))
				return false;
		}
		return true;
	}
	
	public boolean isFeasibleSolution(HashSet<Arc> tree){
		
		HashMap<Integer, HashSet<Integer>> adj = new HashMap<Integer, HashSet<Integer>>();
		for(Arc a : tree){
			Integer u = a.getInput();
			Integer v = a.getOutput();
			HashSet<Integer> neigh = adj.get(u);
			if(neigh == null)
			{
				neigh = new HashSet<Integer>();
				adj.put(u,neigh);
			}
			neigh.add(v);
		}
		
		LinkedList<Integer> toCheck = new LinkedList<Integer>();
		HashSet<Integer> visited = new HashSet<Integer>();
		toCheck.add(this.getRoot());
		
		while(!toCheck.isEmpty()){
			Integer u = toCheck.pollFirst();
			if(visited.contains(u))
				continue;
			visited.add(u);
			
			HashSet<Integer> neigh = adj.get(u);
			if(neigh == null)
			{
				neigh = new HashSet<Integer>();
			}
			toCheck.addAll(neigh);
		}
		return visited.containsAll(this.getRequiredVertices());
		
	}

}
