/*
 *
 * gengraph - generation of random simple connected graphs with prescribed
 *            degree sequence
 *
 * Copyright (C) 2006  Fabien Viger
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 */
#ifndef GRAPH_MOLLOY_OPT_H
#define GRAPH_MOLLOY_OPT_H

#include "gengraph_definitions.h"
#include "gengraph_degree_sequence.h"
#include "gengraph_qsort.h"

#include <assert.h>
#include "gengraph_random.h"

namespace gengraph {

// This class handles graphs with a constant degree sequence.

class graph_molloy_opt {

private:
  // Random generator
  KW_RNG::RNG rng;
  // Number of vertices
  int n;
  //Number of arcs ( = #edges * 2 )
  int a;
  // The degree sequence of the graph
  int *deg;
  // The array containing all links
  int *links;
  // The array containing pointers to adjacency list of every vertices
  int **neigh;
  // Allocate memory according to degree_sequence (for constructor use only!!)
  void alloc(degree_sequence &);
  // Compute #edges
  inline void refresh_nbarcs() {
    a=0;
    for(int* d=deg+n; d!=deg; ) a += *(--d);
  }
  // Build neigh with deg and links
  void compute_neigh();
  // Swap edges. The swap MUST be valid !!!
  inline void swap_edges(int from1, int to1, int from2, int to2) {
    fast_rpl(neigh[from1],to1,to2);
    fast_rpl(neigh[from2],to2,to1);
    fast_rpl(neigh[to1],from1,from2);
    fast_rpl(neigh[to2],from2,from1);
  }

  // Swap edges only if they are simple. return false if unsuccessful.
  bool swap_edges_simple(int ,int ,int, int);
  // Test if vertex is in an isolated component of size<K
  bool isolated(int v, int K, int *Kbuff, bool *visited);
  // Pick random edge, and gives a corresponding vertex
  inline int pick_random_vertex() { return links[my_random()%a]; };
  // Pick random neighbour
  inline int* random_neighbour(const int v) { return neigh[v]+(my_random()%deg[v]); };
  // Returns complexity of isolation test
  long effective_isolated(int v, int K, int *Kbuff, bool *visited);
  // Depth-Exploration. Returns number of steps done. Stops when encounter vertex of degree > dmax.
  void depth_isolated(int v, long &calls, int &left_to_explore, int dmax, int * &Kbuff, bool *visited);
  // breadth-first search. Store the distance (modulo 3)  in dist[]. Returns eplorated component size.
  int width_search(unsigned char *dist, int *buff, int v0=0, int toclear=-1);
  // depth-first search.
  int depth_search(bool *visited, int *buff, int v0=0);
  // breadth-first search that count the number of shortest paths going from src to each vertex
  int breadth_path_search(int src, int *buff, double *paths, unsigned char *dist);
  // Used by traceroute_sample() ONLY
  void add_traceroute_edge(int, int, int*, double** red=NULL, double t=1.0);
  // Used by traceroute() and betweenness(). if newdeg[]=NULL, do not discover edges.
  // breadth_path_search() must have been called to give the corresponding buff[],dist[],paths[] and nb_vertices
  void explore_usp(double *target, int nb_vertices, int *buff, double *paths, unsigned char *dist, int *newdeg=NULL, double **edge_redudancy=NULL);
  void explore_asp(double *target, int nb_vertices, int *buff, double *paths, unsigned char *dist, int *newdeg=NULL, double **edge_redudancy=NULL);
  void explore_rsp(double *target, int nb_vertices, int *buff, double *paths, unsigned char *dist, int *newdeg=NULL, double **edge_redudancy=NULL);
  // Return component indexes where vertices belong to, starting from 0,
  // sorted by size (biggest component has index 0)
  int *components(int *comp=NULL);
  // pick k random vertices of degree > 0.
  int *pick_random_vertices(int &k, int *output=NULL, int nb_v=-1, int *among=NULL);
  
public:
  // neigh[]
  inline int** neighbors() { return neigh; };
  // deg[]
  inline int* degrees() { return deg; };
  //adjacency list of v
  inline int* operator[](const int v) { return neigh[v]; };
  //degree of v
  inline int degree(const int v) { return deg[v]; };
  //compare adjacency lists
  inline int compare(const int v, const int w) {
    return deg[v]==deg[w] ? lex_comp(neigh[v],neigh[w],deg[v]) : (deg[v]>deg[w] ? -1 : 1);
  };
  // Detach deg[] and neigh[]
  void detach();
  // Destroy deg and links
  ~graph_molloy_opt();
  // Create graph from file (stdin not supported unless rewind() possible)
  graph_molloy_opt(FILE *f);
  // Allocate memory for the graph. Create deg and links. No edge is created.
  graph_molloy_opt(degree_sequence &);
  // Create graph from hard copy
  graph_molloy_opt(int *);
  // Create hard copy of graph
  int *hard_copy();
  // Remove unused edges, updates neigh[], recreate links[]
  void clean();
  // nb arcs
  inline int nbarcs() { return a; };
  // last degree
  inline int last_degree() { return deg[n-1]; };
  // nb vertices
  inline int nbvertices() { return n; };
  // nb vertices having degree > 0
  inline int nbvertices_real() { 
    int s=0;
    for(int *d=deg+n; d--!=deg; ) if(*d) s++;
    return s;
  };
  // return list of vertices with degree > 0. Compute #vertices, if not given.
  int *vertices_real(int &nb_v);
  // Keep only giant component
  void giant_comp();
  // nb vertices in giant component
  int nbvertices_comp();
  // nb arcs in giant component
  int nbarcs_comp();
  // print graph in SUCC_LIST mode, in stdout
  void print(FILE *f=stdout, bool NOZERO=true);
  // Bind the graph avoiding multiple edges or self-edges (return false if fail)
  bool havelhakimi();
  // Get the graph connected  (return false if fail)
  bool make_connected();
  // Test if graph is connected
  bool is_connected();
  // Maximum degree
  int max_degree();
  // breadth-first search. Store the distance (modulo 3)  in dist[].
  void breadth_search(int *dist, int v0=0, int* buff=NULL);
  // is edge ?
  inline bool is_edge(const int a, const int b) {
    if(deg[b]<deg[a]) return(fast_search(neigh[b],deg[b],a)!=NULL);
    else return(fast_search(neigh[a],deg[a],b)!=NULL);
  }
  // Backup graph [sizeof(int) bytes per edge]
  int* backup(int *here = NULL);
  // Restore from backup. Assume that degrees haven't changed
  void restore(int* back);
  // Resplace with hard backup.
  void replace(int* _hardbackup);
  // Backup degs of graph
  int* backup_degs(int *here = NULL);
  // Restore degs from neigh[]. Need last degree, though
  void restore_degs(int last_degree);
  // Restore degs[] from backup. Assume that links[] has only been permuted
  void restore_degs_only(int* backup_degs);
  // Restore degs[] and neigh[]. Assume that links[] has only been permuted
  void restore_degs_and_neigh(int* backup_degs);
// WARNING : the following shuffle() algorithms are slow.
// Use graph_molloy_hash::connected_shuffle() instead.
  // "Fab" Shuffle (Optimized heuristic of Gkantsidis algo.)
  long fab_connected_shuffle(long);
  // "Optimized-Fab" Shuffle (Optimized heuristic of Gkantsidis algo, with isolated pairs)
  long opt_fab_connected_shuffle(long);
  // Gkantsidis Shuffle
  long gkantsidis_connected_shuffle(long);
  // Connected Shuffle
  long slow_connected_shuffle(long);
  // shortest paths where vertex is an extremity
  double *vertex_betweenness(int mode, bool trivial_path=false);
  // Sample the graph with traceroute-like exploration from src[] to dst[].
  // if dst[]=NULL, pick nb_dst new random destinations for each src
  double traceroute_sample(int mode, int nb_src, int *src, int nb_dst, int* dst, double *redudancy = NULL, double **edge_redudancy=NULL);
  // does one breadth-first search and returns the average_distance.
  double avg_dist(unsigned char *dist, int *buff, int v0, int &nb_vertices, int toclear=-1);
  // Number of edges needed to disconnect graph (one random instance)
  int disconnecting_edges();
  // Compute vertex covering of the graph. Warning : this modifies degs[]
  void vertex_covering();
  // Path sampling. Input is nb_dst[] and dst[]. nb_dst[v],dst[v] describe all paths (v,x)
  double path_sampling(int *nb_dst, int *dst=NULL, double *redudancies=NULL, double **edge_redudancy=NULL); 
  // keep only core (tree parts are deleted). Returns number of removed vertices.
  int core();
  // try to disconnect the graph by swapping edges (with isolation tests)
  int try_disconnect(int K, int max_tries=10000000);
  // Eric & Cun-Hui estimator
  double rho(int mode, int nb_src, int *src, int nb_dst, int *dst=NULL);
  // sort adjacency lists
  void sort();
  // sort the vertices according to their degrees (highest first) and to their adjacency lists (lexicographic)
  int* sort_vertices(int *buff = NULL);
  // count cycles passing through vertex v
  int cycles(int v);
  // remove vertex (i.e. remove all edges adjacent to vertex)
  void remove_vertex(int v);
  // pick k random vertices of degree > 0. If k \in [0,1[, k is understood as a density.
  int *pick_random_src(double k, int *nb=NULL, int* buff=NULL, int nb_v=-1, int* among=NULL);
  // pick k random vertices of degree > 0. If k \in [0,1], k is understood as a density.
  int *pick_random_dst(double k, int *nb=NULL, int* buff=NULL, int nb_v=-1, int* among=NULL);

  // For debug purposes : verify validity of the graph (symetry, simplicity)
#define VERIFY_NORMAL  0
#define VERIFY_NONEIGH 1
#define VERIFY_NOARCS  2
  bool verify(int mode=VERIFY_NORMAL);

/*___________________________________________________________________________________
  Not to use anymore : use graph_molloy_hash class instead


public:
  // Shuffle. returns number of swaps done.
  void shuffle(long);
  // Connected Shuffle
  long connected_shuffle(long);
  // Get caracteristic K
  double eval_K(int quality = 100);
  // Get effective K
  double effective_K(int K, int quality = 10000);
  // Test window
  double window(int K, double ratio);
  // Try to shuffle n times. Return true if at the end, the graph was still connected.
  bool try_shuffle(int T, int K);

//___________________________________________________________________________________
//*/

/*___________________________________________________________________________________
  Not to use anymore : replaced by vertex_betweenness()     22/04/2005

  // shortest paths where vertex is an extremity
  long long *vertex_betweenness_usp(bool trivial_path);
  // shortest paths where vertex is an extremity
  long long *vertex_betweenness_rsp(bool trivial_path);
  // same, but when multiple shortest path are possible, average the weights.
  double *vertex_betweenness_asp(bool trivial_path);
//___________________________________________________________________________________
//*/

};

} // namespace gengraph

#endif //GRAPH_MOLLOY_OPT_H