/**
 *
 * This file is part of the COIN-OR CBC MIP Solver
 *
 * Class responsible for finding cliques with weights
 * greater than a certain threshold. It implements the
 * Bron-Kerbosch Algorithm.
 *
 * @file CoinBronKerbosch.hpp
 * @brief Bron-Kerbosch Algorithm
 * @author Samuel Souza Brito and Haroldo Gambini Santos
 * Contact: samuelbrito@ufop.edu.br and haroldo@ufop.edu.br
 * @date 03/27/2020
 *
 * \copyright{Copyright 2020 Brito, S.S. and Santos, H.G.}
 * \license{This This code is licensed under the terms of the Eclipse Public License (EPL).}
 *
 **/

#ifndef COINBRONKERBOSCH_HPP
#define COINBRONKERBOSCH_HPP

#include <cstddef>
#include "CoinUtilsConfig.h"

class CoinConflictGraph;
class CoinCliqueList;

/**
 * Struct used to represent a weighted-vertex.
 **/
struct BKVertex {
  /**
   * Index of the vertex
   **/
  size_t idx;

  /**
   * Weight of the vertex
   **/
  double weight;

  /**
   * Degree of the vertex
   **/
  size_t degree;

  /**
   * Fitness of the vertex. Used to select
   * the pivot vertex in BK.
   **/
  double fitness;
};

/**
 * Class responsible for finding cliques with weights
 * greater than a certain threshold. It implements the
 * Bron-Kerbosch Algorithm.
 **/
class COINUTILSLIB_EXPORT CoinBronKerbosch {
public:
  /**
   * Default constructor.
   *
   * @param cgraph conflict graph
   * @param weights array containing the weights for each vertex
   * @param pivotingStrategy pivoting strategy used in BK algorithm. Values:
   * 0 = off; 1 = random; 2 = degree; 3 = weight; 4 = modified degree;
   * 5 = modified weight; 6 = modified degree + modified weight. Default: 3
   **/
  CoinBronKerbosch(const CoinConflictGraph *cgraph, const double *weights, size_t pivotingStrategy = 3);

  /**
   * Destructor
   **/
  ~CoinBronKerbosch();

  /**
   * Perform BK algorithm for finding cliques with weights
   * greater than a certain threshold.
   **/
  void findCliques();

  /**
   * Return the number of cliques found by BK algorithm.
   **/
  size_t nCliques() const;
  
  /**
   * Return the i-th clique found by BK algorithm.
   **/
  const size_t* getClique(const size_t i) const;

  /**
   * Return the size of the i-th clique found by BK algorithm.
   **/
  size_t getCliqueSize(const size_t i) const;

  /**
   * Return the weight of the i-th clique found by BK algorithm.
   **/
  double getCliqueWeight(const size_t i) const;

  /**
   * Set the minimum weight that a clique must have
   * to be detected and stored by BK algorithm.
   **/
  void setMinWeight(double minWeight);
  
  /**
   * Set the maximum number of recursive calls of BK algorithm.
   **/
  void setMaxCalls(size_t maxCalls);
  
  /**
   * Return true if BK algorithm ran completely, without
   * stopping by the maximum number of recursive calls.
   **/
  bool completedSearch() const;

  /**
   * Return the number of calls made by BK algorithm
   **/
  size_t numCalls() const;

private:
    /**
     * Compute the fitness of all vertices.
     *
     * @param array containing the weights for each vertex
     **/
    void computeFitness(const double *weights);

    /**
     * Return the sum of the weights of the vertices in P.
     * Store in u the vertice in P with the highest fitness.
     **/
    double weightP(size_t depth, size_t &u);

    /**
     * Call the BK algorithm
     **/
    void bronKerbosch(size_t depth);

    /**
     * Conflict graph
     **/
    const CoinConflictGraph *cgraph_;

    /**
     * Array of vertices
     **/
    BKVertex *vertices_;

    /**
     * Number of vertices of the conflict graph
     **/
    size_t nVertices_;

    /**
     * Size of each bit vector
     **/
    size_t sizeBitVector_;

    /**
     * Bit mask
     **/
    size_t *mask_;

    /**
     * Conflict graph and its complement represented by bit vectors
     **/
    size_t **cgBitstring_, **ccgBitstring_;

    /**
     * Bitstring with all vertices
     **/
    size_t *allIn_;

    /**
     * Set C of vertices that are part of the current clique
     **/
    size_t *C_, nC_;

    /**
     * Sum of the weights of the vertices in C
     **/
    double weightC_;

    /**
     * Set of the candidate vertices to enter in C
     * Contain a pointer for each depth of BK algorithm.
     **/
    size_t **P_, *nP_;

    /**
     * Set of all vertices that have already been considered
     * in earlier steps by BK. Contain a pointer for each
     * depth of BK algorithm.
     **/
    size_t **S_, *nS_;

    /**
     * Set of vertices P excluding the neighbors of a vertex v.
     * Contain a pointer for each depth of BK algorithm.
     **/
    size_t **L_, *nL_;

    /**
     * Array that stores the weights of each clique found by BK
     **/
    double *clqWeight_;

    /**
     * Current capacity of array clqWeight_
     **/
    size_t clqWeightCap_;

    /**
     * Minimum weight that a clique must have to be
     * detected and stored by BK algorithm.
     **/
    double minWeight_;

    /**
     * Maximum number of recursive calls of BK algorithm.
     **/
    size_t maxCalls_;

    /** Pivoting strategy used in BK algorithm. Options:
     * 0 - off
     * 1 - random
     * 2 - degree
     * 3 - weight
     * 4 - modified degree
     * 5 - modified weight
     * 6 - modified degree + modified weight
     **/
    size_t pivotingStrategy_;

    /**
     * Number of calls made by BK algorithm
     **/
    size_t calls_;

    /**
     * If BK algorithm ran completely, without stopping
     * by the maximum number of recursive calls.
     **/
    bool completeSearch_;

    /**
     * Cliques found by BK algorithm
     **/
    CoinCliqueList *cliques_;
};


#endif //COINBRONKERBOSCH_HPP
