/*
  This file is part of the BJP package.

  BJP package is free software: you can redistribute it and/or modify it
  under the terms of the GNU Lesser General Public License as published by the
  Free Software Foundation, either version 3 of the License, or (at your
  option) any later version.

  BJP package is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with BJP package.  If not, see <http://www.gnu.org/licenses/>.
 */
package rep;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.Random;

import util.math.BitSetUtil;

/**
 * Simple data structure to represent an undirected graph with n nodes (one per
 * each random variable of the domain).
 * 
 * @author fschluter
 * 
 */
public class UndirectedGraph {

	/* Number of nodes of the graph */
	private int n;

	/* Maps the edges (i,j) in the graph */
	public boolean adjMatrix[][];

	/**
	 * Creates an undirected graph with n nodes and no edges
	 * 
	 * @param n
	 */
	public UndirectedGraph(int n) {
		this.n = n;
		adjMatrix = new boolean[n][n];
	}

	/**
	 * Creates an undirected graph with n nodes and no edges
	 * 
	 * @param n
	 * @param fully
	 */
	public UndirectedGraph(int n, boolean fully) {
		this.n = n;
		adjMatrix = new boolean[n][n];
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (fully) {
					adjMatrix[i][j] = true;
					adjMatrix[j][i] = true;
				} else {
					adjMatrix[i][j] = false;
					adjMatrix[j][i] = false;
				}
			}
		}

	}

	/**
	 * @param g
	 *            UndirectedGraph object to copy
	 */
	public UndirectedGraph(UndirectedGraph g) {
		n = g.n;
		adjMatrix = new boolean[n][n];
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				adjMatrix[i][j] = g.adjMatrix[i][j] ? true : false;
				adjMatrix[j][i] = g.adjMatrix[j][i] ? true : false;
			}
		}

	}

	public UndirectedGraph(int n, BitSet bitset) {
		this.n = n;
		adjMatrix = new boolean[n][n];
		int x = 0;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				adjMatrix[i][j] = bitset.get(x);
				adjMatrix[j][i] = adjMatrix[i][j];
				++x;
			}
		}
	}

	/**
	 * Flips an edge between nodes i and j.
	 * 
	 * @param i
	 * @param j
	 */
	public void flipEdge(int i, int j) {
		adjMatrix[i][j] = !adjMatrix[i][j];
		adjMatrix[j][i] = !adjMatrix[j][i];
	}

	/**
	 * Flips an edge between nodes i and j.
	 * 
	 * @param i
	 * @param j
	 */
	public void addEdge(int i, int j) {
		adjMatrix[i][j] = true;
		adjMatrix[j][i] = true;
	}

	/**
	 * Returns the Markov blanket of a variable (this is the set of adjacent
	 * variables in the graph)
	 * 
	 * @param x
	 *            Variable which we want to know its adjacencies set
	 * @return The Markov blanket of a variable (this is the set of adjacent
	 *         variables in the graph).
	 */
	public List<Integer> getBlanketOf(int x) {
		List<Integer> blanketOfX = new ArrayList<Integer>();
		for (int i = 0; i < n - 1; i++)
			for (int j = i + 1; j < n; j++) {
				if (i == x && adjMatrix[i][j])
					blanketOfX.add(j);
				if (j == x && adjMatrix[i][j])
					blanketOfX.add(i);
			}
		return blanketOfX;
	}

	/**
	 * Returns true or false whenever there exist an edge between variables x
	 * and y
	 * 
	 * @param x
	 *            First variable
	 * @param y
	 *            Second variable
	 * @return Returns true or false whenever there exist an edge between
	 *         variables x and y
	 */
	public boolean existEdge(int x, int y) {
		if (x < y)
			return adjMatrix[x][y];
		else
			return adjMatrix[y][x];
	}

	/**
	 * @return
	 */
	public int getNumberOfNodes() {
		return n;
	}

	/**
	 * Returns a boolean array which indicates the variables whose Markov
	 * blanket differ with respect to another input structure
	 * 
	 * @return
	 */
	public boolean[] getVariablesWithDifferentBlanket(UndirectedGraph g) {
		boolean[] vars = new boolean[g.getNumberOfNodes()];
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (adjMatrix[i][j] != g.adjMatrix[i][j]) {
					vars[i] = true;
					vars[j] = true;
				}
			}
		}
		return vars;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		String toString = "";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				toString += (adjMatrix[i][j] ? "1" : "0") + " ";
			}
			toString += "\n";
		}
		return toString;
	}

	/**
	 * @return
	 */
	public String getBitsetString() {
		String toString = "";
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				toString += (adjMatrix[i][j] ? "1" : "0");
			}
		}
		return toString;
	}

	public BitSet getBitset() {
		BitSet bitset = new BitSet(n * (n - 1) / 2);
		int k = 0;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (adjMatrix[i][j])
					bitset.set(k);
				k++;
			}
		}
		return bitset;
	}

	public void setBitset(BitSet bitset) {
		adjMatrix = new boolean[n][n];
		int k = 0;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				adjMatrix[i][j] = bitset.get(k) ? true : false;
				k++;
			}
		}
	}

	/**
	 * @param n
	 * @return
	 */
	public static List<UndirectedGraph> getAllPossibleGraphs(int n) {
		List<UndirectedGraph> allPossibleGraphs = new ArrayList<UndirectedGraph>();
		List<BitSet> possibleBitSets = BitSetUtil.getAllPossibleBitsets(n
				* (n - 1) / 2);
		for (BitSet bitset : possibleBitSets) {
			allPossibleGraphs.add(new UndirectedGraph(n, bitset));
		}
		return allPossibleGraphs;
	}

	public static UndirectedGraph getRandomGraph(int n, Random r) {
		UndirectedGraph g = new UndirectedGraph(n);
		for (int j = 0; j < n; ++j) {
			for (int k = j + 1; k < n; ++k) {
				if (r.nextBoolean())
					g.addEdge(j, k);
			}
		}
		return g;
	}

	public UndirectedGraph getComplementaryGraph() {
		UndirectedGraph complementaryGraph = new UndirectedGraph(n);
		complementaryGraph.adjMatrix = new boolean[n][n];
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n; j++) {
				if (i != j) {
					complementaryGraph.adjMatrix[i][j] = adjMatrix[i][j] ? false
							: true;
					complementaryGraph.adjMatrix[j][i] = adjMatrix[j][i] ? false
							: true;
				}
			}
		}
		return complementaryGraph;
	}

	/**
	 * Computes the following measure of irregularity: irr(G) = \sum_{u,v \in
	 * E(G)} |d_G(u) - d_G(v)| ``Albertson, Michael O.
	 * "The irregularity of a graph." Ars Combinatoria 46 (1997): 219-225.''
	 * 
	 * @return
	 */
	public int computeIrregularity() {
		int irregularity = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				irregularity += Math.abs(degree(i)-degree(j));
			}
		}
		return irregularity;
	}

	/**
	 * Return the amount of edges of a variable (its degree) 
	 * @param j
	 * @return
	 */
	private int degree(int i) {
		int degree = 0;
		for (int j = 0; j < n; j++) {
			if (adjMatrix[i][j]) {
				++degree;
			}
		}
		return degree;
	}

	public int getNumberOfEdges() {
		int numberOfEdges=0;
		for (int j = 0; j < n; ++j) {
			for (int k = j + 1; k < n; ++k) {
				if (existEdge(j,k)||existEdge(k,j)){
					++numberOfEdges;
				}
			}
		}
		return numberOfEdges;
	}

}
