2
Copyright (C) 2003-2006 Tommi Junttila
4
This program is free software; you can redistribute it and/or modify
5
it under the terms of the GNU General Public License version 2
6
as published by the Free Software Foundation.
8
This program is distributed in the hope that it will be useful,
9
but WITHOUT ANY WARRANTY; without even the implied warranty of
10
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
GNU General Public License for more details.
13
You should have received a copy of the GNU General Public License
14
along with this program; if not, write to the Free Software
15
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
18
/* FSF address fixed in the above notice on 1 Oct 2009 by Tamas Nepusz */
20
#include "bliss_timer.hh"
21
#include "bliss_graph.hh"
22
#include "bliss_kqueue.hh"
23
#include "bliss_utils.hh"
29
using namespace igraph;
32
* \function igraph_canonical_permutation
33
* Canonical permutation using BLISS
35
* This function computes the canonical permutation which transforms
36
* the graph into a canonical form by using the BLISS algorithm.
38
* \param graph The input graph, it is treated as undirected and the
39
* multiple edges are ignored.
40
* \param labeling Pointer to a vector, the result is stored here. The
41
* permutation takes vertex 0 to the first element of the vector,
42
* vertex 1 to the second, etc. The vector will be resized as
44
* \param sh The split heuristics to be used in BLISS. See \ref
46
* \param info If not \c NULL then information on BLISS internals is
47
* stored here. See \ref igraph_bliss_info_t.
50
* Time complexity: exponential, in practice it is fast for many graphs.
52
int igraph_canonical_permutation(const igraph_t *graph, igraph_vector_t *labeling,
53
igraph_bliss_sh_t sh, igraph_bliss_info_t *info) {
54
Graph *g = Graph::from_igraph(graph);
56
const unsigned int N=g->get_nof_vertices();
57
unsigned int gsh=Graph::sh_flm;
60
case IGRAPH_BLISS_F: gsh= Graph::sh_f; break;
61
case IGRAPH_BLISS_FL: gsh= Graph::sh_fl; break;
62
case IGRAPH_BLISS_FS: gsh= Graph::sh_fs; break;
63
case IGRAPH_BLISS_FM: gsh= Graph::sh_fm; break;
64
case IGRAPH_BLISS_FLM: gsh= Graph::sh_flm; break;
65
case IGRAPH_BLISS_FSM: gsh= Graph::sh_fsm; break;
68
g->set_splitting_heuristics(gsh);
69
const unsigned int *cl = g->canonical_form(stats);
70
IGRAPH_CHECK(igraph_vector_resize(labeling, N));
71
for (unsigned int i=0; i<N; i++) {
72
VECTOR(*labeling)[i] = cl[i];
77
info->nof_nodes = stats.nof_nodes;
78
info->nof_leaf_nodes = stats.nof_leaf_nodes;
79
info->nof_bad_nodes = stats.nof_bad_nodes;
80
info->nof_canupdates = stats.nof_canupdates;
81
info->max_level = stats.max_level;
82
stats.group_size.tostring(&info->group_size);
89
* \function igraph_automorphisms
90
* Number of automorphisms using BLISS
92
* The number of automorphisms of a graph is computed using BLISS. The
93
* result is returned as part of the \p info structure, in tag \c
94
* group_size. It is returned as a string, as it can be very high even
95
* for relatively small graphs. If the GNU MP library is used then
96
* this number is exact, otherwise a <type>long double</type> is used
97
* and it is only approximate. See also \ref igraph_bliss_info_t.
99
* \param graph The input graph, it is treated as undirected and the
100
* multiple edges are ignored.
101
* \param sh The split heuristics to be used in BLISS. See \ref
103
* \param info The result is stored here, in particular in the \c
104
* group_size tag of \p info.
105
* \return Error code.
107
* Time complexity: exponential, in practice it is fast for many graphs.
109
int igraph_automorphisms(const igraph_t *graph,
110
igraph_bliss_sh_t sh, igraph_bliss_info_t *info) {
112
Graph *g = Graph::from_igraph(graph);
114
unsigned int gsh=Graph::sh_flm;
117
case IGRAPH_BLISS_F: gsh= Graph::sh_f; break;
118
case IGRAPH_BLISS_FL: gsh= Graph::sh_fl; break;
119
case IGRAPH_BLISS_FS: gsh= Graph::sh_fs; break;
120
case IGRAPH_BLISS_FM: gsh= Graph::sh_fm; break;
121
case IGRAPH_BLISS_FLM: gsh= Graph::sh_flm; break;
122
case IGRAPH_BLISS_FSM: gsh= Graph::sh_fsm; break;
125
g->set_splitting_heuristics(gsh);
126
g->find_automorphisms(stats);
129
info->nof_nodes = stats.nof_nodes;
130
info->nof_leaf_nodes = stats.nof_leaf_nodes;
131
info->nof_bad_nodes = stats.nof_bad_nodes;
132
info->nof_canupdates = stats.nof_canupdates;
133
info->max_level = stats.max_level;
134
stats.group_size.tostring(&info->group_size);
141
bool bliss_verbose = false;
142
FILE *bliss_verbstr = stdout;
146
typedef enum {FORMAT_BIN = 0, FORMAT_ADJ} Format;
147
// static Format input_format;
149
// static char *infilename = 0;
151
// static bool opt_canonize = false;
152
// static char *opt_output_can_file = 0;
153
// static unsigned int sh = Graph::sh_fm;
155
// static void usage(FILE *fp, char *argv0)
157
// char *program_name;
159
// program_name = strrchr(argv0, '/');
161
// if(program_name) program_name++;
162
// else program_name = argv0;
164
// if(!*program_name) program_name = "bliss";
165
// fprintf(fp, "bliss, version 0.35, compiled " __DATE__ "\n");
166
// fprintf(fp, "Copyright 2003-2006 Tommi Junttila\n");
168
// "%s [<graph file>]\n"
170
// " -can compute canonical form\n"
171
// " -ocan=f compute canonical form and output it in file f\n"
172
// //" -v switch verbose mode on\n"
173
// " -sh=x select splitting heuristics, where x is\n"
174
// " f first non-singleton cell\n"
175
// " fl first largest non-singleton cell\n"
176
// " fs first smallest non-singleton cell\n"
177
// " fm first maximally non-trivially connected non-singleton cell [default]\n"
178
// " flm first largest maximally non-trivially connected non-singleton cell\n"
179
// " fsm first smallest maximally non-trivially connected non-singleton cell\n"
184
// static void parse_options(int argc, char ** argv)
186
// for(int i = 1; i < argc; i++)
188
// //if(strcmp(argv[i], "-v") == 0 || strcmp(argv[i], "-verbose") == 0)
189
// //bliss_verbose = true;
191
// if(strcmp(argv[i], "-bin") == 0)
192
// input_format = FORMAT_BIN;
193
// else if(strcmp(argv[i], "-adj") == 0)
194
// input_format = FORMAT_ADJ;
196
// if(strcmp(argv[i], "-can") == 0)
197
// opt_canonize = true;
198
// else if((strncmp(argv[i], "-ocan=", 6) == 0) && (strlen(argv[i]) > 6))
200
// opt_canonize = true;
201
// opt_output_can_file = argv[i]+6;
203
// else if(strcmp(argv[i], "-sh=f") == 0)
205
// else if(strcmp(argv[i], "-sh=fs") == 0)
206
// sh = Graph::sh_fs;
207
// else if(strcmp(argv[i], "-sh=fl") == 0)
208
// sh = Graph::sh_fl;
209
// else if(strcmp(argv[i], "-sh=fm") == 0)
210
// sh = Graph::sh_fm;
211
// else if(strcmp(argv[i], "-sh=fsm") == 0)
212
// sh = Graph::sh_fsm;
213
// else if(strcmp(argv[i], "-sh=flm") == 0)
214
// sh = Graph::sh_flm;
215
// else if(argv[i][0] == '-') {
216
// fprintf(stderr, "unknown command line argument `%s'\n", argv[i]);
217
// usage(stderr, argv[0]);
222
// fprintf(stderr, "too many file arguments\n");
223
// usage(stderr, argv[0]);
227
// infilename = argv[i];
235
// using namespace igraph;
237
// int main(int argc, char **argv)
242
// parse_options(argc, argv);
246
// FILE *infile = stdin;
248
// if(input_format == FORMAT_BIN)
249
// infile = fopen(infilename, "rb");
251
// infile = fopen(infilename, "r");
253
// fprintf(stderr, "cannot not open `%s' for input\n", infilename);
257
// g = Graph::read_dimacs(infile);
259
// if(infile != stdin)
265
// fprintf(stdout, "Graph read in %.2fs\n", t.get_intermediate());
267
// #ifdef DEBUG_PRINT_DOT
268
// g->to_dot("debug_graph.dot");
273
// g->set_splitting_heuristics(sh);
277
// const unsigned int *cl = g->canonical_form(stats);
278
// //fprintf(stdout, "Canonical labeling: ");
279
// //print_permutation(stdout, g->get_nof_vertices(), cl);
280
// //fprintf(stdout, "\n");
281
// if(opt_output_can_file)
283
// Graph *cf = g->permute(cl);
284
// FILE *fp = fopen(opt_output_can_file, "w");
287
// fprintf(stderr, "Can not open '%s' for outputting the canonical form", opt_output_can_file);
290
// cf->print_dimacs(fp);
297
// g->find_automorphisms(stats);
300
// printf("Nodes:\t\t%lu\n", stats.nof_nodes);
301
// printf("Leaf nodes:\t%lu\n", stats.nof_leaf_nodes);
302
// printf("Bad nodes:\t%lu\n", stats.nof_bad_nodes);
303
// printf("Canrep updates:\t%lu\n", stats.nof_canupdates);
304
// printf("Generators:\t%lu\n", stats.nof_generators);
305
// printf("Max level:\t%lu\n", stats.max_level);
306
// printf("|Aut|:\t\t"); stats.group_size.print(stdout); printf("\n");
309
// printf("Total time:\t%.2fs\n", t.get_duration());
added
removed
src/bliss.cc
