///////////////////////////////////////////////////////////////////////////////
// For information as to what this class does, see the Javadoc, below.       //
// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,       //
// 2007, 2008, 2009, 2010, 2014, 2015 by Peter Spirtes, Richard Scheines, Joseph   //
// Ramsey, and Clark Glymour.                                                //
//                                                                           //
// This program is free software; you can redistribute it and/or modify      //
// it under the terms of the GNU General Public License as published by      //
// the Free Software Foundation; either version 2 of the License, or         //
// (at your option) any later version.                                       //
//                                                                           //
// This program 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 General Public License for more details.                              //
//                                                                           //
// You should have received a copy of the GNU General Public License         //
// along with this program; if not, write to the Free Software               //
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA //
///////////////////////////////////////////////////////////////////////////////

package edu.cmu.tetrad.graph;

import edu.cmu.tetrad.util.RandomUtil;

import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;


/**
 * Modifies the UniformGraphGenerator to generate random DAGs (not assuming
 * connectivity) with number of edges in given range, min to max. Constraints on
 * connectivity are removed. Original docs follow.
 * <p/>
 * Generates random DAGs uniformly with certain classes of DAGs using variants
 * of Markov chain algorithm by Malancon, Dutour, and Philippe. Pieces of the
 * infrastructure of the algorithm are adapted from the the BNGenerator class by
 * Jaime Shinsuke Ide jaime.ide@poli.usp.br, released under the GNU General
 * Public License, for which the following statement is being included as part
 * of the license agreement:
 * <p/>
 * "The BNGenerator distribution is free software; you can redistribute it
 * and/or modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation (either version 2 of the License
 * or, at your option, any later version), provided that this notice and the
 * name of the author appear in all copies. </p> "If you're using the software,
 * please notify jaime.ide@poli.usp.br so that you can receive updates and
 * patches. BNGenerator is distributed "as is", 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 General
 * Public License for more details. You should have received a copy of the GNU
 * General Public License along with the BNGenerator distribution. If not, write
 * to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139,
 * USA."
 *
 * @author Joseph Ramsey
 */
public final class GraphGeneratorRandomNumEdges {
    private static final int ANY_DAG = 0;

    /**
     * Indicates the structural assumption. May be ANY_DAG, CONNECTED_DAG.
     */
    private int structure;

    /**
     * The number of nodes in a graph. The default is 4.
     */
    private int numNodes;

    /**
     * The maximum number of edges in the graph. The default is the number of
     * nodes minus 1.
     */
    private int maxEdges;

    /**
     * The minimum number of edges in the graph. The default is 0. If a
     */
    private int minEdges;

    /**
     * The number of iterations for the Markov chain process.
     */
    private int numIterations;

    /**
     * Matrix of parents for each node. parentMatrix[i][0] indicates the number
     * of parents; parentMatrix[i][k] represents the (k-1)'th parent, k =
     * 1...max.
     */
    private int[][] parentMatrix;

    /**
     * Matrix of parents for each node. childMatrix[i][0] indicates the number
     * of parents; childMatrix[i][k] represents the (k-1)'th child, k =
     * 1...max.
     */
    private int[][] childMatrix;

    /**
     * Parent of random edge. 0 is the default parent node.
     */
    private int randomParent = 0;

    /**
     * Child of random edge. 0 is the default child node.
     */
    private int randomChild = 1;

    //===============================CONSTRUCTORS==========================//

    /**
     * Constructs a random graph generator for the given structure.
     *
     * @param structure One of ANY_DAG, POLYTREE, or CONNECTED_DAG.
     */
    public GraphGeneratorRandomNumEdges(int structure) {
        switch (structure) {
            case ANY_DAG:
                break;
            default:
                throw new IllegalArgumentException("Unrecognized structure.");
        }

        this.structure = structure;
        this.numNodes = 4;
        this.minEdges = 0;
        this.maxEdges = numNodes - 1;

        // Determining the number of iterations for the chain to converge is a
        // difficult task. This value follows the DagAlea (see Melancon;Bousque,
        // 2000) suggestion, and we verified that this number is satisfatory. (Ide.)
        this.numIterations = 6 * numNodes * numNodes;
    }

    //===============================PUBLIC METHODS========================//

    private int getNumNodes() {
        return numNodes;
    }

    /**
     * Sets the number of nodes and resets all of the other parameters to
     * default values accordingly.
     *
     * @param numNodes Must be an integer >= 4.
     */
    public void setNumNodes(int numNodes) {
        if (numNodes < 4) {
            throw new IllegalArgumentException("Number of nodes must be >= 4.");
        }

        this.numNodes = numNodes;
        this.maxEdges = numNodes - 1;
        this.numIterations = 6 * numNodes * numNodes;
        this.parentMatrix = null;
        this.childMatrix = null;
    }

    private int getMaxEdges() {
        return maxEdges;
    }

    private int getNumIterations() {
        return numIterations;
    }

    private int getStructure() {
        return structure;
    }


    private int getMinEdges() {
        return minEdges;
    }

    public void setMinEdges(int minEdges) {
        if (minEdges < 0) {
            throw new IllegalArgumentException("Min edges must be >= 0.");
        }

        if (minEdges >= maxEdges - 2) {
            throw new IllegalArgumentException(
                    "Min edges must be < max edges - 1.");
        }

        this.minEdges = minEdges;
    }

    private int getMaxPossibleEdges() {
        return getNumNodes() * (getNumNodes() - 1) / 2;
    }

    public void setMaxEdges(int maxEdges) {
        if (maxEdges < 1) {
            throw new IllegalArgumentException("Max edges must be >= 1.");
        }

        if (maxEdges <= getMinEdges() + 2) {
            throw new IllegalArgumentException(
                    "Max edgs must be > max edges - 2.");
        }

        if (maxEdges > getMaxPossibleEdges()) {
            maxEdges = getMaxPossibleEdges();
//            System.out.println("\nThe value maxEdges = " +
//                    maxEdges + " is too high; it has been set to the maximum " +
//                    "number of possible edges, which is " +
//                    getMaxPossibleEdges() + ".");
        }

        this.maxEdges = maxEdges;
    }

    public void generate() {
        if (ANY_DAG == getStructure()) {
            generateArbitraryDag();
        } else {
            throw new IllegalStateException("Unknown structure type.");
        }
    }

    public Dag getDag() {
        Dag dag = new Dag();

        List<Node> nodes = new ArrayList<>();
        NumberFormat nf = NumberFormat.getInstance();
        nf.setMaximumFractionDigits(0);

        int numDigits = (int) Math.ceil(Math.log(numNodes) / Math.log(10.0));
        nf.setMinimumIntegerDigits(numDigits);

        for (int i = 1; i <= getNumNodes(); i++) {
            GraphNode node = new GraphNode("X" + nf.format(i));
            dag.addNode(node);
            nodes.add(node);
        }

        for (int i = 0; i < getNumNodes(); i++) {
            Node child = nodes.get(i);

            if (parentMatrix[i][0] != 1) {
                for (int j = 1; j < parentMatrix[i][0]; j++) {
                    Node parent = nodes.get(parentMatrix[i][j]);
                    dag.addDirectedEdge(parent, child);
                }
            }
        }

        GraphUtils.circleLayout(dag, 200, 200, 150);
        return dag;
    }

    public String toString() {
        String buf = "\nStructural information for generated graph:" +
                "\n\tNumber of nodes:" + getNumNodes() +
                "\n\tNumber of transitions between samples:" + getNumIterations();

        return buf;
    }

    //================================PRIVATE METHODS======================//

    private void generateArbitraryDag() {
        initializeGraphAsEmpty();

        int numEdges = 0;

        for (int i = 0; i < getNumIterations(); i++) {
            sampleEdge();

            if (edgeExists()) {
                if (numEdges > getMinEdges()) {
                    removeEdge();
                    numEdges--;
                }
            } else {
                if ((numEdges < getMaxEdges() && isAcyclic())) {
                    addEdge();
                    numEdges++;
                }
            }
        }
    }

    /**
     * @return true if the edge parent-->child exists in the graph.
     */
    private boolean edgeExists() {
        for (int i = 1; i < parentMatrix[randomChild][0]; i++) {
            if (parentMatrix[randomChild][i] == randomParent) {
                return true;
            }
        }
        return false;
    }

    /**
     * @return true if the graph is still acyclic after the last edge was added.
     * This method only works after adding an edge, not after removing an edge.
     */
    private boolean isAcyclic() {
        boolean visited[] = new boolean[getNumNodes()];
        boolean noCycle = true;
        int list[] = new int[getNumNodes() + 1];
        int index = 0;
        int lastIndex = 1;
        list[0] = randomParent;
        visited[randomParent] = true;
        while (index < lastIndex && noCycle) {
            int currentNode = list[index];
            int i = 1;

            // verify parents of getModel node
            while ((i < parentMatrix[currentNode][0]) && noCycle) {
                if (!visited[parentMatrix[currentNode][i]]) {
                    if (parentMatrix[currentNode][i] != randomChild) {
                        list[lastIndex] = parentMatrix[currentNode][i];
                        lastIndex++;
                    } else {
                        noCycle = false;
                    }
                    visited[parentMatrix[currentNode][i]] = true;
                } // end of if(visited)
                i++;
            }
            index++;
        }
        //System.out.println("\tnoCycle:"+noCycle);
        return noCycle;
    }

    /**
     * Initializes the graph to have no edges.
     */
    private void initializeGraphAsEmpty() {
        int max = getNumNodes();

        parentMatrix = new int[getNumNodes()][max];
        childMatrix = new int[getNumNodes()][max];

        for (int i = 0; i < getNumNodes(); i++) {
            parentMatrix[i][0] = 1; //set first node
            childMatrix[i][0] = 1;
        }

        for (int i = 0; i < getNumNodes(); i++) {
            for (int j = 1; j < max; j++) {
                parentMatrix[i][j] = -5; //set first node
                childMatrix[i][j] = -5;
            }
        }
    }

    /**
     * Sets randomParent-->randomChild to a random edge, chosen uniformly.
     */
    private void sampleEdge() {
        int rand = RandomUtil.getInstance().nextInt(
                getNumNodes() * (getNumNodes() - 1));
        randomParent = rand / (getNumNodes() - 1);
        int rest = rand - randomParent * (getNumNodes() - 1);
        if (rest >= randomParent) {
            randomChild = rest + 1;
        } else {
            randomChild = rest;
        }
    }

    /**
     * Adds the edge randomParent-->randomChild to the graph.
     */
    private void addEdge() {
        childMatrix[randomParent][childMatrix[randomParent][0]] = randomChild;
        childMatrix[randomParent][0]++;
        parentMatrix[randomChild][parentMatrix[randomChild][0]] = randomParent;
        parentMatrix[randomChild][0]++;
    }

    /**
     * Removes the edge randomParent-->randomChild from the graph.
     */
    private void removeEdge() {
        boolean go = true;
        int lastNode;
        int proxNode;
        int atualNode;
        if ((parentMatrix[randomChild][0] != 1) &&
                (childMatrix[randomParent][0] != 1)) {
            lastNode =
                    parentMatrix[randomChild][parentMatrix[randomChild][0] - 1];
            for (int i = (parentMatrix[randomChild][0] - 1); (i > 0 && go); i--) { // remove element from parentMatrix
                atualNode = parentMatrix[randomChild][i];
                if (atualNode != randomParent) {
                    proxNode = atualNode;
                    parentMatrix[randomChild][i] = lastNode;
                    lastNode = proxNode;
                } else {
                    parentMatrix[randomChild][i] = lastNode;
                    go = false;
                }
            }
            if ((childMatrix[randomParent][0] != 1) &&
                    (childMatrix[randomParent][0] != 1)) {
                lastNode = childMatrix[randomParent][
                        childMatrix[randomParent][0] - 1];
                go = true;
                for (int i = (childMatrix[randomParent][0] - 1); (i > 0 &&
                        go); i--) { // remove element from childMatrix
                    atualNode = childMatrix[randomParent][i];
                    if (atualNode != randomChild) {
                        proxNode = atualNode;
                        childMatrix[randomParent][i] = lastNode;
                        lastNode = proxNode;
                    } else {
                        childMatrix[randomParent][i] = lastNode;
                        go = false;
                    }
                } // end of for
            }
            childMatrix[randomParent][(childMatrix[randomParent][0] - 1)] = -4;
            childMatrix[randomParent][0]--;
            parentMatrix[randomChild][(parentMatrix[randomChild][0] - 1)] = -4;
            parentMatrix[randomChild][0]--;
        }
    }
}