File: gengraph_mr-connected.cpp

package info (click to toggle)
r-cran-igraph 0.7.1-1~bpo8%2B1
  • links: PTS, VCS
  • area: main
  • in suites: jessie-backports
  • size: 14,280 kB
  • sloc: ansic: 150,105; cpp: 19,404; fortran: 3,777; yacc: 1,164; tcl: 931; lex: 484; makefile: 13; sh: 9
file content (186 lines) | stat: -rw-r--r-- 6,279 bytes parent folder | download | duplicates (8)
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;
}

}