haskell-igraph-0.8.5: igraph/include/gengraph_graph_molloy_optimized.h
/*
*
* 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 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, 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