package weka.clusterers.forMetisMQI.graph;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;



public class Bisection {
	
	private Subgraph a = null;
	
	private Subgraph b = null;
	
	private Set<Node> marked = null;
	
	private UndirectedGraph g = null;

	private Bisection() {
	}
	
	/**
	 * Initialize the bisection with a given subgraph.
	 * @param s
	 */
	public Bisection(Subgraph s) {
		g  = s.getGraph();
		a = s;
		b = new Subgraph(g);
		Iterator<Node> graphIterator =  g.getVertices().iterator();
		while(graphIterator.hasNext()) {
			Node u = graphIterator.next();
			if(!s.contains(u))
				b.addVertex(u);
		}
		marked = new HashSet<Node>();
	}
	
	/**
	 * Creates a bisection choosing randomly the nodes for each subgraph.
	 * @param g
	 */
	public Bisection(UndirectedGraph g){
		this.g = g;
		a = new Subgraph(g);
		b = new Subgraph(g);
		Iterator<Node> graph = g.vtxsPermutation().iterator();
		int i = 0;
		while(graph.hasNext()) {
			Node u = graph.next();
			if((i%2)==0)
				a.addVertex(u);
			else
				b.addVertex(u);
			i++;
		}
		marked = new HashSet<Node>();
	}
	
	public UndirectedGraph getGraph() {
		return g;
	}
	
	/**
	 * Returns the node marked as candidate for swapping or <code>null</code> if there aren't node available
	 * for swapping.
	 * @return
	 */
	public Node getCandidate() {
		Node u;
		if(a.getVertexCount() > b.getVertexCount()) {
			u = a.getCandidate(marked);
			if(u == null)
				u = b.getCandidate(marked);
		} else {
			u = b.getCandidate(marked);
			if(u == null)
				u = a.getCandidate(marked);
		}
		if(u != null) {
			marked.add(u);
		}
		return u;
	}
	
	public void swap(Node u) {
		Subgraph from = fromSubgraph(u);
		Subgraph to = toSubgraph(u);
		from.removeVertex(u);
		to.addVertex(u);
	}
	
	private Subgraph fromSubgraph(Node u) {
		Subgraph ret = null;
		if(a.contains(u))
			ret = a;
		if(b.contains(u))
			ret = b;
		return ret;
	}
	
	private Subgraph toSubgraph(Node u) {
		Subgraph ret = null;
		if(!a.contains(u))
			ret = a;
		if(!b.contains(u))
			ret = b;
		return ret;
	}

	public int edgeCut() {
		int acc = a.getExternalDegree() + b.getExternalDegree();
		return acc;
	}
	
	public Subgraph getSubgraph() {
		return a;
	}
	
	public Subgraph getComplement() {
		return b;
	}
	
	public Bisection copy(){
		Bisection clone = new Bisection();
		clone.a = (Subgraph) a.clone();
		clone.b = (Subgraph) b.clone();
		clone.marked = new HashSet<Node>();
		return clone;
	}
	
	@Override
	public String toString(){
		String out = a.toString();
		out = out + "\n";
		out = out + b.toString();
		return out;
	}
	
	/**
	 * Returns the smaller not empty subgraph of this bisection, null otherwise.
	 * @return
	 */
	public Subgraph getSmallerNotEmptySubgraph() {
		if(a.getVertexCount() > 0 && b.getVertexCount() == 0)
			return a;
		if(b.getVertexCount() > 0 && a.getVertexCount() == 0)
			return b;
		if(a.getVertexCount() < b.getVertexCount())
			return a;
		else
			return b;
	}
}