/*
*
* 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 .
*/
#ifndef GRAPH_MOLLOY_HASH_H
#define GRAPH_MOLLOY_HASH_H
#include "gengraph_definitions.h"
#include "gengraph_hash.h"
#include "gengraph_degree_sequence.h"
#include
#include
// This class handles graphs with a constant degree sequence.
#define FINAL_HEURISTICS 0
#define GKAN_HEURISTICS 1
#define FAB_HEURISTICS 2
#define OPTIMAL_HEURISTICS 3
#define BRUTE_FORCE_HEURISTICS 4
namespace gengraph {
//****************************
// class graph_molloy_hash
//****************************
class graph_molloy_hash {
private:
// Number of vertices
int n;
//Number of arcs ( = #edges * 2 )
int a;
//Total size of links[]
int size;
// 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;
// Counts total size
void compute_size();
// Build neigh with deg and links
void compute_neigh();
// Allocate memory according to degree_sequence (for constructor use only!!)
int alloc(degree_sequence &);
// Add edge (a,b). Return FALSE if vertex a is already full.
// WARNING : only to be used by havelhakimi(), restore() or constructors
inline bool add_edge(int a, int b, int *realdeg) {
int deg_a = realdeg[a];
if (deg_a == deg[a]) {
return false;
}
// Check that edge was not already inserted
assert(fast_search(neigh[a], int((a == n - 1 ? links + size : neigh[a + 1]) - neigh[a]), b) == NULL);
assert(fast_search(neigh[b], int((b == n - 1 ? links + size : neigh[b + 1]) - neigh[b]), a) == NULL);
assert(deg[a] < deg_a);
int deg_b = realdeg[b];
if (IS_HASH(deg_a)) {
*H_add(neigh[a], HASH_EXPAND(deg_a), b) = b;
} else {
neigh[a][deg[a]] = b;
}
if (IS_HASH(deg_b)) {
*H_add(neigh[b], HASH_EXPAND(deg_b), a) = a;
} else {
neigh[b][deg[b]] = a;
}
deg[a]++;
deg[b]++;
// Check that edge was actually inserted
assert(fast_search(neigh[a], int((a == n - 1 ? links + size : neigh[a + 1]) - neigh[a]), b) != NULL);
assert(fast_search(neigh[b], int((b == n - 1 ? links + size : neigh[b + 1]) - neigh[b]), a) != NULL);
return true;
}
// Swap edges
inline void swap_edges(int from1, int to1, int from2, int to2) {
H_rpl(neigh[from1], deg[from1], to1, to2);
H_rpl(neigh[from2], deg[from2], to2, to1);
H_rpl(neigh[to1], deg[to1], from1, from2);
H_rpl(neigh[to2], deg[to2], from2, from1);
}
// Backup graph [sizeof(int) bytes per edge]
int* backup();
// Test if vertex is in an isolated component of size dmax.
void depth_isolated(int v, long &calls, int &left_to_explore, int dmax, int * &Kbuff, bool *visited);
public:
//degree of v
inline int degree(const int v) {
return deg[v];
};
// For debug purposes : verify validity of the graph (symetry, simplicity)
bool verify();
// Destroy deg[], neigh[] and links[]
~graph_molloy_hash();
// Allocate memory for the graph. Create deg and links. No edge is created.
graph_molloy_hash(degree_sequence &);
// Create graph from hard copy
graph_molloy_hash(int *);
// Create hard copy of graph
int *hard_copy();
// Restore from backup
void restore(int* back);
//Clear hash tables
void init();
// nb arcs
inline int nbarcs() {
return a;
};
// nb vertices
inline int nbvertices() {
return n;
};
// print graph in SUCC_LIST mode, in stdout
void print(FILE *f = stdout);
int print(igraph_t *graph);
// Test if graph is connected
bool is_connected();
// is edge ?
inline bool is_edge(int a, int b) {
assert(H_is(neigh[a], deg[a], b) == (fast_search(neigh[a], HASH_SIZE(deg[a]), b) != NULL));
assert(H_is(neigh[b], deg[b], a) == (fast_search(neigh[b], HASH_SIZE(deg[b]), a) != NULL));
assert(H_is(neigh[a], deg[a], b) == H_is(neigh[b], deg[b], a));
if (deg[a] < deg[b]) {
return H_is(neigh[a], deg[a], b);
} else {
return H_is(neigh[b], deg[b], a);
}
}
// Random edge swap ATTEMPT. Return 1 if attempt was a succes, 0 otherwise
int random_edge_swap(int K = 0, int *Kbuff = NULL, bool *visited = NULL);
// Connected Shuffle
unsigned long shuffle(unsigned long, unsigned long, int type);
// Optimal window for the gkantsidis heuristics
int optimal_window();
// Average unitary cost per post-validated edge swap, for some window
double average_cost(int T, int *back, double min_cost);
// Get caracteristic K
double eval_K(int quality = 100);
// Get effective K
double effective_K(int K, int quality = 10000);
// Try to shuffle T times. Return true if at the end, the graph was still connected.
bool try_shuffle(int T, int K, int *back = NULL);
/*_____________________________________________________________________________
Not to use anymore : use graph_molloy_opt class instead
private:
// 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);
public:
// Create graph
graph_molloy_hash(FILE *f);
// 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();
// "Fab" Shuffle (Optimized heuristic of Gkantsidis algo.)
long long fab_connected_shuffle(long long);
// Naive Shuffle
long long slow_connected_shuffle(long long);
// Maximum degree
int max_degree();
// compute vertex betweenness : for each vertex, a unique random shortest path is chosen.
// this choice is consistent (if shortest path from a to c goes through b and then d,
// then shortest path from a to d goes through b). If(trivial path), also count all the
// shortest paths where vertex is an extremity
int *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_HASH_H