File: bliss_C.h

package info (click to toggle)
bliss 0.73-4
  • links: PTS, VCS
  • area: main
  • in suites: sid
  • size: 712 kB
  • sloc: cpp: 6,538; makefile: 144; sh: 6
file content (206 lines) | stat: -rw-r--r-- 6,715 bytes parent folder | download | duplicates (3)
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#ifndef BLISS_C_H
#define BLISS_C_H

/*
  Copyright (c) 2003-2015 Tommi Junttila
  Released under the GNU Lesser General Public License version 3.
  
  This file is part of bliss.
  
  bliss is free software: you can redistribute it and/or modify
  it under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation, version 3 of the License.

  bliss 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 Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with bliss.  If not, see <http://www.gnu.org/licenses/>.
*/

/**
 * \file
 * \brief The bliss C API.
 *
 * This is the C language API to
 * <A href="http://www.tcs.hut.fi/Software/bliss/">bliss</A>.
 * Note that this C API is only a subset of the C++ API;
 * please consider using the C++ API whenever possible.
 */

#include <stdlib.h>
#include <stdio.h>


/**
 * \brief The true bliss graph is hiding behind this typedef.
 */
typedef struct bliss_graph_struct BlissGraph;


/**
 * \brief The C API version of the statistics returned by
 * the bliss search algorithm.
 */
typedef struct bliss_stats_struct
{
  /**
   * An approximation (due to possible rounding errors) of
   * the size of the automorphism group.
   */
  long double group_size_approx;
  /** The number of nodes in the search tree. */
  long unsigned int nof_nodes;
  /** The number of leaf nodes in the search tree. */
  long unsigned int nof_leaf_nodes;
  /** The number of bad nodes in the search tree. */
  long unsigned int nof_bad_nodes;
  /** The number of canonical representative updates. */
  long unsigned int nof_canupdates;
  /** The number of generator permutations. */
  long unsigned int nof_generators;
  /** The maximal depth of the search tree. */
  unsigned long int max_level;
} BlissStats;


/**
 * Create a new graph instance with \a N vertices and no edges.
 * \a N can be zero and bliss_add_vertex() called afterwards
 * to add new vertices on-the-fly.
 */
BlissGraph *bliss_new(const unsigned int N);


/**
 * Read an undirected graph from a file in the DIMACS format into a new bliss
 * instance.
 * Returns 0 if an error occurred.
 * Note that in the DIMACS file the vertices are numbered from 1 to N while
 * in the bliss C API they are from 0 to N-1.
 * Thus the vertex n in the file corresponds to the vertex n-1 in the API.
 */
BlissGraph *bliss_read_dimacs(FILE *fp);


/**
 * Output the graph in the file stream \a fp in the DIMACS format.
 * See the User's Guide for the file format details.
 * Note that in the DIMACS file the vertices are numbered from 1 to N while
 * in bliss they are from 0 to N-1.
 */
void bliss_write_dimacs(BlissGraph *graph, FILE *fp);


/**
 * Release the graph.
 * Note that the memory pointed by the arguments of hook functions for
 * bliss_find_automorphisms() and bliss_find_canonical_labeling()
 * is deallocated and thus should not be accessed after calling this function.
 */
void bliss_release(BlissGraph *graph);


/**
 * Print the graph in graphviz dot format.
 */
void bliss_write_dot(BlissGraph *graph, FILE *fp);


/**
 * Return the number of vertices in the graph.
 */
unsigned int bliss_get_nof_vertices(BlissGraph *graph);


/**
 * Add a new vertex with color \a c in the graph \a graph and return its index.
 * The vertex indices are always in the range
 * [0,bliss::bliss_get_nof_vertices(\a bliss)-1].
 */
unsigned int bliss_add_vertex(BlissGraph *graph, unsigned int c);


/**
 * Add a new undirected edge in the graph.
 * \a v1 and \a v2 are vertex indices returned by bliss_add_vertex().
 * If duplicate edges are added, they will be ignored (however, they are not
 * necessarily physically ignored immediately but may consume memory for
 * a while so please try to avoid adding duplicate edges whenever possible).
 */
void bliss_add_edge(BlissGraph *graph, unsigned int v1, unsigned int v2);


/**
 * Compare two graphs according to a total order.
 * Return -1, 0, or 1 if the first graph was smaller than, equal to,
 * or greater than, resp., the other graph.
 * If 0 is returned, then the graphs have the same number vertices,
 * the vertices in them are colored in the same way, and they contain
 * the same edges; that is, the graphs are equal.
 */
int bliss_cmp(BlissGraph *graph1, BlissGraph *graph2);


/**
 * Get a hash value for the graph.
 */
unsigned int bliss_hash(BlissGraph *graph);


/**
 * Permute the graph with the given permutation \a perm.
 * Returns the permuted graph, the original graph is not modified.
 * The argument \a perm should be an array of
 * N=bliss::bliss_get_nof_vertices(\a graph) elements describing
 * a bijection on {0,...,N-1}.
 */
BlissGraph *bliss_permute(BlissGraph *graph, const unsigned int *perm);


/**
 * Find a set of generators for the automorphism group of the graph.
 * The hook function \a hook (if non-null) is called each time a new generator
 * for the automorphism group is found.
 * The first argument \a user_param for the hook function is
 * the \a hook_user_param argument,
 * the second argument \a N is the length of the automorphism (equal to
 * bliss::bliss_get_nof_vertices(\a graph)) and
 * the third argument \a aut is the automorphism (a bijection on {0,...,N-1}).
 * The memory for the automorphism \a aut will be invalidated immediately
 * after the return from the hook;
 * if you want to use the automorphism later, you have to take a copy of it.
 * Do not call bliss_* functions in the hook.
 * If \a stats is non-null, then some search statistics are copied there.
 */
void
bliss_find_automorphisms(BlissGraph *graph,
			 void (*hook)(void *user_param,
				      unsigned int N,
				      const unsigned int *aut),
			 void *hook_user_param,
			 BlissStats *stats);


/**
 * Otherwise the same as bliss_find_automorphisms() except that
 * a canonical labeling for the graph (a bijection on {0,...,N-1}) is returned.
 * The returned canonical labeling will remain valid only until
 * the next call to a bliss_* function with the exception that
 * bliss_permute() can be called without invalidating the labeling.
 * To compute the canonical version of a graph, call this function and
 * then bliss_permute() with the returned canonical labeling.
 * Note that the computed canonical version may depend on the applied version
 * of bliss.
 */
const unsigned int *
bliss_find_canonical_labeling(BlissGraph *graph,
			      void (*hook)(void *user_param,
					   unsigned int N,
					   const unsigned int *aut),
			      void *hook_user_param,
			      BlissStats *stats);

#endif