1 #ifndef bliss_digraphs_C_H 2 #define bliss_digraphs_C_H 3 4 /* 5 Copyright (c) 2003-2015 Tommi Junttila 6 Released under the GNU Lesser General Public License version 3. 7 8 This file is part of bliss. 9 10 bliss is free software: you can redistribute it and/or modify 11 it under the terms of the GNU Lesser General Public License as published by 12 the Free Software Foundation, version 3 of the License. 13 14 bliss is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU Lesser General Public License for more details. 18 19 You should have received a copy of the GNU Lesser General Public License 20 along with bliss. If not, see <http://www.gnu.org/licenses/>. 21 */ 22 23 /** 24 * \file 25 * \brief The bliss C API. 26 * 27 * This is the C language API to 28 * <A href="http://www.tcs.hut.fi/Software/bliss/">bliss</A>. 29 * Note that this C API is only a subset of the C++ API; 30 * please consider using the C++ API whenever possible. 31 */ 32 33 #include <stdlib.h> 34 #include <stdio.h> 35 36 37 /** 38 * \brief The true bliss graph is hiding behind this typedef. 39 */ 40 typedef struct bliss_digraphs_graph_struct BlissGraph; 41 42 43 /** 44 * \brief The C API version of the statistics returned by 45 * the bliss search algorithm. 46 */ 47 typedef struct bliss_digraphs_stats_struct 48 { 49 50 /* The true size of the group */ 51 /* This is a list of integers of length group_size_len */ 52 /* This is only used when BLISS_IN_GAP is defined */ 53 int* group_size; 54 int group_size_len; 55 56 /** 57 * An approximation (due to possible rounding errors) of 58 * the size of the automorphism group. 59 */ 60 long double group_size_approx; 61 /** The number of nodes in the search tree. */ 62 long unsigned int nof_nodes; 63 /** The number of leaf nodes in the search tree. */ 64 long unsigned int nof_leaf_nodes; 65 /** The number of bad nodes in the search tree. */ 66 long unsigned int nof_bad_nodes; 67 /** The number of canonical representative updates. */ 68 long unsigned int nof_canupdates; 69 /** The number of generator permutations. */ 70 long unsigned int nof_generators; 71 /** The maximal depth of the search tree. */ 72 unsigned long int max_level; 73 } BlissStats; 74 75 76 /** 77 * Create a new graph instance with \a N vertices and no edges. 78 * \a N can be zero and bliss_digraphs_add_vertex() called afterwards 79 * to add new vertices on-the-fly. 80 */ 81 BlissGraph *bliss_digraphs_new(const unsigned int N); 82 83 84 /** 85 * Read an undirected graph from a file in the DIMACS format into a new bliss 86 * instance. 87 * Returns 0 if an error occurred. 88 * Note that in the DIMACS file the vertices are numbered from 1 to N while 89 * in the bliss C API they are from 0 to N-1. 90 * Thus the vertex n in the file corresponds to the vertex n-1 in the API. 91 */ 92 BlissGraph *bliss_digraphs_read_dimacs(FILE *fp); 93 94 95 /** 96 * Output the graph in the file stream \a fp in the DIMACS format. 97 * See the User's Guide for the file format details. 98 * Note that in the DIMACS file the vertices are numbered from 1 to N while 99 * in bliss they are from 0 to N-1. 100 */ 101 void bliss_digraphs_write_dimacs(BlissGraph *graph, FILE *fp); 102 103 104 /** 105 * Release the graph. 106 * Note that the memory pointed by the arguments of hook functions for 107 * bliss_digraphs_find_automorphisms() and bliss_digraphs_find_canonical_labeling() 108 * is deallocated and thus should not be accessed after calling this function. 109 */ 110 void bliss_digraphs_release(BlissGraph *graph); 111 112 void bliss_digraphs_clear(BlissGraph *graph); 113 void bliss_digraphs_change_color(BlissGraph* graph, const unsigned int vertex, const unsigned int color); 114 115 /** 116 * Print the graph in graphviz dot format. 117 */ 118 void bliss_digraphs_write_dot(BlissGraph *graph, FILE *fp); 119 120 121 /** 122 * Return the number of vertices in the graph. 123 */ 124 unsigned int bliss_digraphs_get_nof_vertices(BlissGraph *graph); 125 126 127 /** 128 * Add a new vertex with color \a c in the graph \a graph and return its index. 129 * The vertex indices are always in the range 130 * [0,bliss::bliss_digraphs_get_nof_vertices(\a bliss)-1]. 131 */ 132 unsigned int bliss_digraphs_add_vertex(BlissGraph *graph, unsigned int c); 133 134 135 /** 136 * Add a new undirected edge in the graph. 137 * \a v1 and \a v2 are vertex indices returned by bliss_digraphs_add_vertex(). 138 * If duplicate edges are added, they will be ignored (however, they are not 139 * necessarily physically ignored immediately but may consume memory for 140 * a while so please try to avoid adding duplicate edges whenever possible). 141 */ 142 void bliss_digraphs_add_edge(BlissGraph *graph, unsigned int v1, unsigned int v2); 143 144 145 /** 146 * Compare two graphs according to a total order. 147 * Return -1, 0, or 1 if the first graph was smaller than, equal to, 148 * or greater than, resp., the other graph. 149 * If 0 is returned, then the graphs have the same number vertices, 150 * the vertices in them are colored in the same way, and they contain 151 * the same edges; that is, the graphs are equal. 152 */ 153 int bliss_digraphs_cmp(BlissGraph *graph1, BlissGraph *graph2); 154 155 156 /** 157 * Get a hash value for the graph. 158 */ 159 unsigned int bliss_digraphs_hash(BlissGraph *graph); 160 161 162 /** 163 * Permute the graph with the given permutation \a perm. 164 * Returns the permuted graph, the original graph is not modified. 165 * The argument \a perm should be an array of 166 * N=bliss::bliss_digraphs_get_nof_vertices(\a graph) elements describing 167 * a bijection on {0,...,N-1}. 168 */ 169 BlissGraph *bliss_digraphs_permute(BlissGraph *graph, const unsigned int *perm); 170 171 172 /** 173 * Find a set of generators for the automorphism group of the graph. 174 * The hook function \a hook (if non-null) is called each time a new generator 175 * for the automorphism group is found. 176 * The first argument \a user_param for the hook function is 177 * the \a hook_user_param argument, 178 * the second argument \a N is the length of the automorphism (equal to 179 * bliss::bliss_digraphs_get_nof_vertices(\a graph)) and 180 * the third argument \a aut is the automorphism (a bijection on {0,...,N-1}). 181 * The memory for the automorphism \a aut will be invalidated immediately 182 * after the return from the hook; 183 * if you want to use the automorphism later, you have to take a copy of it. 184 * Do not call bliss_digraphs_* functions in the hook. 185 * If \a stats is non-null, then some search statistics are copied there. 186 */ 187 void 188 bliss_digraphs_find_automorphisms(BlissGraph *graph, 189 void (*hook)(void *user_param, 190 unsigned int N, 191 const unsigned int *aut), 192 void *hook_user_param, 193 BlissStats *stats); 194 195 196 /** 197 * Otherwise the same as bliss_digraphs_find_automorphisms() except that 198 * a canonical labeling for the graph (a bijection on {0,...,N-1}) is returned. 199 * The returned canonical labeling will remain valid only until 200 * the next call to a bliss_digraphs_* function with the exception that 201 * bliss_digraphs_permute() can be called without invalidating the labeling. 202 * To compute the canonical version of a graph, call this function and 203 * then bliss_digraphs_permute() with the returned canonical labeling. 204 * Note that the computed canonical version may depend on the applied version 205 * of bliss. 206 */ 207 const unsigned int * 208 bliss_digraphs_find_canonical_labeling(BlissGraph *graph, 209 void (*hook)(void *user_param, 210 unsigned int N, 211 const unsigned int *aut), 212 void *hook_user_param, 213 BlissStats *stats); 214 215 216 // Clean up memory allocated by a used BlissStats 217 void bliss_digraphs_free_blissstats(BlissStats *stats); 218 219 #endif 220