1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
|
/*
*
* 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/>.
*/
#include "gengraph_header.h"
#include "gengraph_graph_molloy_optimized.h"
#include "gengraph_graph_molloy_hash.h"
#include "gengraph_degree_sequence.h"
#include "gengraph_random.h"
#include "igraph_datatype.h"
#include "igraph_types.h"
#include "igraph_error.h"
namespace gengraph {
// return negative number if program should exit
int parse_options(int &argc, char** &argv);
// options
static const bool MONITOR_TIME = false;
static const int SHUFFLE_TYPE = FINAL_HEURISTICS;
static const bool RAW_DEGREES = false;
static const FILE *Fdeg = stdin;
//_________________________________________________________________________
// int main(int argc, char** argv) {
// // options
// SET_VERBOSE(VERBOSE_NONE);
// if(parse_options(argc, argv) < 0) return -1;
// //Read degree distribution
// degree_sequence dd(Fdeg, !RAW_DEGREES);
// //Allocate memory
// if(VERBOSE()) fprintf(stderr,"Allocate memory for graph...");
// graph_molloy_opt g(dd);
// dd.~degree_sequence();
// //Realize degree sequence
// if(VERBOSE()) fprintf(stderr,"done\nRealize degree sequence...");
// bool FAILED = !g.havelhakimi();
// if(VERBOSE()) fprintf(stderr," %s\n", FAILED ? "Failed" : "Success");
// if(FAILED) return 2;
// //Merge connected components together
// if(VERBOSE()) fprintf(stderr,"Connecting...");
// FAILED = !g.make_connected();
// if(VERBOSE()) fprintf(stderr," %s\n", FAILED ? "Failed" : "Success");
// if(FAILED) return 3;
// //Convert graph_molloy_opt to graph_molloy_hash
// if(VERBOSE()) fprintf(stderr,"Convert adjacency lists into hash tables...");
// int *hc = g.hard_copy();
// g.~graph_molloy_opt();
// graph_molloy_hash gh(hc);
// delete[] hc;
// if(VERBOSE()) fprintf(stderr,"Done\n");
// //Shuffle
// gh.shuffle(5*gh.nbarcs(), SHUFFLE_TYPE);
// //Output
// gh.print();
// if(MONITOR_TIME) {
// double t = double(clock()) / double(CLOCKS_PER_SEC);
// fprintf(stderr,"Time used: %f\n", t);
// }
// return 0;
// }
//_________________________________________________________________________
// int parse_options(int &argc, char** &argv) {
// bool HELP = false;
// int argc0 = argc;
// argc = 1;
// for(int a=1; a<argc0; a++) {
// if(strcmp(argv[a],"-v")==0) SET_VERBOSE(VERBOSE_SOME);
// else if(strcmp(argv[a],"-vv")==0) SET_VERBOSE(VERBOSE_LOTS);
// else if(strcmp(argv[a],"-s")==0) my_srandom(0);
// else if(strcmp(argv[a],"-?")==0 || strcmp(argv[1],"--help")==0 || strcmp(argv[1],"/?")==0) HELP = true;
// else if(strcmp(argv[a],"-t")==0) MONITOR_TIME = true;
// else if(strcmp(argv[a],"-g")==0) SHUFFLE_TYPE = GKAN_HEURISTICS;
// else if(strcmp(argv[a],"-b")==0) SHUFFLE_TYPE = BRUTE_FORCE_HEURISTICS;
// else if(strcmp(argv[a],"-f")==0) SHUFFLE_TYPE = FAB_HEURISTICS;
// else if(strcmp(argv[a],"-o")==0) SHUFFLE_TYPE = OPTIMAL_HEURISTICS;
// else if(strcmp(argv[a],"-raw")==0) RAW_DEGREES=true;
// else // No option present
// argv[argc++] = argv[a];
// }
// if(!HELP && argc==2) {
// Fdeg = fopen(argv[1],"r");
// if(Fdeg==NULL) {
// fprintf(stderr,"Error : couldn't open file \"%s\" for reading\n",argv[1]);
// return -1;
// }
// argv[1]=argv[0];
// argv++;
// argc--;
// }
// if(HELP || argc!=1) {
// fprintf(stderr,"Usage : %s [options] [file containing degree distribution]\n",argv[0]);
// fprintf(stderr," -> %s returns a graph in its standard output\n",argv[0]);
// fprintf(stderr," If no file is given, %s reads its standard input\n",argv[0]);
// fprintf(stderr," [-v] and [-vv] options causes extra verbose.\n");
// fprintf(stderr," [-g] option uses the Gkantsidis heuristics.\n");
// fprintf(stderr," [-b] option uses the Brute Force heuristics.\n");
// fprintf(stderr," [-f] option uses the Modified Gkantsidis heuristics.\n");
// fprintf(stderr," [-o] option uses the Optimal Gkantsidis heuristics.\n");
// fprintf(stderr," [-t] option monitors computation time\n");
// fprintf(stderr," [-s] does a srandom(0) to get a constant random graph\n");
// fprintf(stderr," [-raw] is to take raw degree sequences as input\n");
// return -1;
// }
// return 0;
// }
} // namespace gengraph
using namespace gengraph;
extern "C" {
int igraph_degree_sequence_game_vl(igraph_t *graph,
const igraph_vector_t *out_seq,
const igraph_vector_t *in_seq) {
long int sum=igraph_vector_sum(out_seq);
if (sum % 2 != 0) {
IGRAPH_ERROR("Sum of degrees should be even", IGRAPH_EINVAL);
}
RNG_BEGIN();
if (in_seq && igraph_vector_size(in_seq) != 0) {
RNG_END();
IGRAPH_ERROR("This generator works with undirected graphs only", IGRAPH_EINVAL);
}
degree_sequence *dd = new degree_sequence(out_seq);
graph_molloy_opt *g = new graph_molloy_opt(*dd);
delete dd;
if (!g->havelhakimi()) {
delete g;
RNG_END();
IGRAPH_ERROR("Cannot realize the given degree sequence as an undirected, simple graph",
IGRAPH_EINVAL);
}
if (!g->make_connected()) {
delete g;
RNG_END();
IGRAPH_ERROR("Cannot make a connected graph from the given degree sequence",
IGRAPH_EINVAL);
}
int *hc = g->hard_copy();
delete g;
graph_molloy_hash *gh = new graph_molloy_hash(hc);
delete [] hc;
gh->shuffle(5*gh->nbarcs(), 100*gh->nbarcs(), SHUFFLE_TYPE);
IGRAPH_CHECK(gh->print(graph));
delete gh;
RNG_END();
return 0;
}
}
|