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
|
// Calculate rank-width and rank-decompositions of graphs.
// Philipp Klaus Krause, philipp@informatik.uni-frankfurt.de, pkk@spth.de, 2009 - 2011
// Copyright (c) 2009-2016 Philipp Klaus Krause
// Copyright (c) 2009-2015 Goethe-Universität Frankfurt
// 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, write to the Free Software Foundation, Inc.,
// 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
// This is a program that calculates rank-width and rank-decompositions. It is based on ideas from "Computing rank-width exactly" by Sang-il Oum, "Sopra una formola numerica" by Ernesto Pascal and "Generation of a Vector from the Lexicographical Index" by B.P. Buckles and M. Lybanon.
// On 2009's computers it works quite well up to graph sizes of about 28 nodes.
// It is an implementation of the trivial algorithm from "Computing rank-width exactly". For larger graphs (more than about 40 nodes) the more algorithm based on fast subset convolution from the same paper would probably be faster.
#include <stdint.h>
// Use data type uint_leastN_t. N is an upper limit on the size of the graphs that can be handled. N=32 seems to be a good compromise for now (the code works well with other values of N).
// uint_leastN_t is faster than uint_fastN_t here, since the bottleneck is cache misses.
typedef uint_least32_t subset_t;
#define MAX_VERTICES 32
// Input graph.
//extern subset_t adjacency_matrix[NUM_VERTICES];
extern subset_t *adjacency_matrix;
// Output rank-decomposition
extern subset_t *cslots;
// Initialization (for getting rank-width only). Returns 0 on success.
//int init_rw(uint_fast8_t n);
// Initialization (for getting both rank-width and rank-decomposition). Returns 0 on success.
int init_rw_dec(uint_fast8_t n);
// Free memory allocated during initialization.
void destroy_rw(void);
// Calculate everything. May take some time.
void calculate_all(void);
// Calculate a single level only
void calculate_level(uint_fast8_t subset_size);
// Get the rank-width.
uint_fast8_t get_rw(void);
|
