1 /* -*- mode: C -*- */ 2 /* 3 IGraph library. 4 Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com> 5 334 Harvard street, Cambridge, MA 02139 USA 6 7 This program is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2 of the License, or 10 (at your option) any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301 USA 21 22 */ 23 24 #ifndef IGRAPH_TOPOLOGY_H 25 #define IGRAPH_TOPOLOGY_H 26 27 #include "igraph_decls.h" 28 #include "igraph_constants.h" 29 #include "igraph_datatype.h" 30 #include "igraph_types.h" 31 #include "igraph_vector_ptr.h" 32 33 __BEGIN_DECLS 34 35 /* -------------------------------------------------- */ 36 /* Directed acyclic graphs */ 37 /* -------------------------------------------------- */ 38 39 IGRAPH_EXPORT int igraph_topological_sorting(const igraph_t *graph, igraph_vector_t *res, 40 igraph_neimode_t mode); 41 IGRAPH_EXPORT int igraph_is_dag(const igraph_t *graph, igraph_bool_t *res); 42 IGRAPH_EXPORT int igraph_transitive_closure_dag(const igraph_t *graph, 43 igraph_t *closure); 44 45 /* -------------------------------------------------- */ 46 /* Graph isomorphisms */ 47 /* -------------------------------------------------- */ 48 49 /* Common functions */ 50 IGRAPH_EXPORT int igraph_simplify_and_colorize( 51 const igraph_t *graph, igraph_t *res, 52 igraph_vector_int_t *vertex_color, igraph_vector_int_t *edge_color); 53 54 /* Generic interface */ 55 IGRAPH_EXPORT int igraph_isomorphic(const igraph_t *graph1, const igraph_t *graph2, 56 igraph_bool_t *iso); 57 IGRAPH_EXPORT int igraph_subisomorphic(const igraph_t *graph1, const igraph_t *graph2, 58 igraph_bool_t *iso); 59 60 /* LAD */ 61 IGRAPH_EXPORT int igraph_subisomorphic_lad(const igraph_t *pattern, const igraph_t *target, 62 const igraph_vector_ptr_t *domains, 63 igraph_bool_t *iso, igraph_vector_t *map, 64 igraph_vector_ptr_t *maps, 65 igraph_bool_t induced, int time_limit); 66 67 /* VF2 family*/ 68 /** 69 * \typedef igraph_isohandler_t 70 * Callback type, called when an isomorphism was found 71 * 72 * See the details at the documentation of \ref 73 * igraph_isomorphic_function_vf2(). 74 * \param map12 The mapping from the first graph to the second. 75 * \param map21 The mapping from the second graph to the first, the 76 * inverse of \p map12 basically. 77 * \param arg This extra argument was passed to \ref 78 * igraph_isomorphic_function_vf2() when it was called. 79 * \return Boolean, whether to continue with the isomorphism search. 80 */ 81 82 83 typedef igraph_bool_t igraph_isohandler_t(const igraph_vector_t *map12, 84 const igraph_vector_t *map21, void *arg); 85 86 /** 87 * \typedef igraph_isocompat_t 88 * Callback type, called to check whether two vertices or edges are compatible 89 * 90 * VF2 (subgraph) isomorphism functions can be restricted by defining 91 * relations on the vertices and/or edges of the graphs, and then checking 92 * whether the vertices (edges) match according to these relations. 93 * 94 * </para><para>This feature is implemented by two callbacks, one for 95 * vertices, one for edges. Every time igraph tries to match a vertex (edge) 96 * of the first (sub)graph to a vertex of the second graph, the vertex 97 * (edge) compatibility callback is called. The callback returns a 98 * logical value, giving whether the two vertices match. 99 * 100 * </para><para>Both callback functions are of type \c igraph_isocompat_t. 101 * \param graph1 The first graph. 102 * \param graph2 The second graph. 103 * \param g1_num The id of a vertex or edge in the first graph. 104 * \param g2_num The id of a vertex or edge in the second graph. 105 * \param arg Extra argument to pass to the callback functions. 106 * \return Logical scalar, whether vertex (or edge) \p g1_num in \p graph1 107 * is compatible with vertex (or edge) \p g2_num in \p graph2. 108 */ 109 110 typedef igraph_bool_t igraph_isocompat_t(const igraph_t *graph1, 111 const igraph_t *graph2, 112 const igraph_integer_t g1_num, 113 const igraph_integer_t g2_num, 114 void *arg); 115 116 IGRAPH_EXPORT int igraph_isomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2, 117 const igraph_vector_int_t *vertex_color1, 118 const igraph_vector_int_t *vertex_color2, 119 const igraph_vector_int_t *edge_color1, 120 const igraph_vector_int_t *edge_color2, 121 igraph_bool_t *iso, 122 igraph_vector_t *map12, 123 igraph_vector_t *map21, 124 igraph_isocompat_t *node_compat_fn, 125 igraph_isocompat_t *edge_compat_fn, 126 void *arg); 127 IGRAPH_EXPORT int igraph_isomorphic_function_vf2(const igraph_t *graph1, const igraph_t *graph2, 128 const igraph_vector_int_t *vertex_color1, 129 const igraph_vector_int_t *vertex_color2, 130 const igraph_vector_int_t *edge_color1, 131 const igraph_vector_int_t *edge_color2, 132 igraph_vector_t *map12, igraph_vector_t *map21, 133 igraph_isohandler_t *isohandler_fn, 134 igraph_isocompat_t *node_compat_fn, 135 igraph_isocompat_t *edge_compat_fn, 136 void *arg); 137 IGRAPH_EXPORT int igraph_count_isomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2, 138 const igraph_vector_int_t *vertex_color1, 139 const igraph_vector_int_t *vertex_color2, 140 const igraph_vector_int_t *edge_color1, 141 const igraph_vector_int_t *edge_color2, 142 igraph_integer_t *count, 143 igraph_isocompat_t *node_compat_fn, 144 igraph_isocompat_t *edge_compat_fn, 145 void *arg); 146 IGRAPH_EXPORT int igraph_get_isomorphisms_vf2(const igraph_t *graph1, 147 const igraph_t *graph2, 148 const igraph_vector_int_t *vertex_color1, 149 const igraph_vector_int_t *vertex_color2, 150 const igraph_vector_int_t *edge_color1, 151 const igraph_vector_int_t *edge_color2, 152 igraph_vector_ptr_t *maps, 153 igraph_isocompat_t *node_compat_fn, 154 igraph_isocompat_t *edge_compat_fn, 155 void *arg); 156 157 IGRAPH_EXPORT int igraph_subisomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2, 158 const igraph_vector_int_t *vertex_color1, 159 const igraph_vector_int_t *vertex_color2, 160 const igraph_vector_int_t *edge_color1, 161 const igraph_vector_int_t *edge_color2, 162 igraph_bool_t *iso, 163 igraph_vector_t *map12, 164 igraph_vector_t *map21, 165 igraph_isocompat_t *node_compat_fn, 166 igraph_isocompat_t *edge_compat_fn, 167 void *arg); 168 IGRAPH_EXPORT int igraph_subisomorphic_function_vf2(const igraph_t *graph1, 169 const igraph_t *graph2, 170 const igraph_vector_int_t *vertex_color1, 171 const igraph_vector_int_t *vertex_color2, 172 const igraph_vector_int_t *edge_color1, 173 const igraph_vector_int_t *edge_color2, 174 igraph_vector_t *map12, 175 igraph_vector_t *map21, 176 igraph_isohandler_t *isohandler_fn, 177 igraph_isocompat_t *node_compat_fn, 178 igraph_isocompat_t *edge_compat_fn, 179 void *arg); 180 IGRAPH_EXPORT int igraph_count_subisomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2, 181 const igraph_vector_int_t *vertex_color1, 182 const igraph_vector_int_t *vertex_color2, 183 const igraph_vector_int_t *edge_color1, 184 const igraph_vector_int_t *edge_color2, 185 igraph_integer_t *count, 186 igraph_isocompat_t *node_compat_fn, 187 igraph_isocompat_t *edge_compat_fn, 188 void *arg); 189 IGRAPH_EXPORT int igraph_get_subisomorphisms_vf2(const igraph_t *graph1, 190 const igraph_t *graph2, 191 const igraph_vector_int_t *vertex_color1, 192 const igraph_vector_int_t *vertex_color2, 193 const igraph_vector_int_t *edge_color1, 194 const igraph_vector_int_t *edge_color2, 195 igraph_vector_ptr_t *maps, 196 igraph_isocompat_t *node_compat_fn, 197 igraph_isocompat_t *edge_compat_fn, 198 void *arg); 199 200 /* BLISS family */ 201 /** 202 * \struct igraph_bliss_info_t 203 * Information about a BLISS run 204 * 205 * Some secondary information found by the BLISS algorithm is stored 206 * here. It is useful if you wany to study the internal working of the 207 * algorithm. 208 * \member nof_nodes The number of nodes in the search tree. 209 * \member nof_leaf_nodes The number of leaf nodes in the search tree. 210 * \member nof_bad_nodes Number of bad nodes. 211 * \member nof_canupdates Number of canrep updates. 212 * \member nof_generators Number of generators of the automorphism group. 213 * \member max_level Maximum level. 214 * \member group_size The size of the automorphism group of the graph, 215 * given as a string. It should be deallocated via 216 * \ref igraph_free() if not needed any more. 217 * 218 * See http://www.tcs.hut.fi/Software/bliss/index.html 219 * for details about the algorithm and these parameters. 220 */ 221 typedef struct igraph_bliss_info_t { 222 unsigned long nof_nodes; 223 unsigned long nof_leaf_nodes; 224 unsigned long nof_bad_nodes; 225 unsigned long nof_canupdates; 226 unsigned long nof_generators; 227 unsigned long max_level; 228 char *group_size; 229 } igraph_bliss_info_t; 230 231 /** 232 * \typedef igraph_bliss_sh_t 233 * \brief Splitting heuristics for Bliss. 234 * 235 * \c IGRAPH_BLISS_FL provides good performance for many graphs, and is a reasonable 236 * default choice. \c IGRAPH_BLISS_FSM is recommended for graphs that have some 237 * combinatorial structure, and is the default of the Bliss library's command 238 * line tool. 239 * 240 * \enumval IGRAPH_BLISS_F First non-singleton cell. 241 * \enumval IGRAPH_BLISS_FL First largest non-singleton cell. 242 * \enumval IGRAPH_BLISS_FS First smallest non-singleton cell. 243 * \enumval IGRAPH_BLISS_FM First maximally non-trivially connected 244 * non-singleton cell. 245 * \enumval IGRAPH_BLISS_FLM Largest maximally non-trivially connected 246 * non-singleton cell. 247 * \enumval IGRAPH_BLISS_FSM Smallest maximally non-trivially 248 * connected non-singletion cell. 249 */ 250 251 typedef enum { IGRAPH_BLISS_F = 0, IGRAPH_BLISS_FL, 252 IGRAPH_BLISS_FS, IGRAPH_BLISS_FM, 253 IGRAPH_BLISS_FLM, IGRAPH_BLISS_FSM 254 } igraph_bliss_sh_t; 255 256 IGRAPH_EXPORT int igraph_canonical_permutation(const igraph_t *graph, const igraph_vector_int_t *colors, igraph_vector_t *labeling, 257 igraph_bliss_sh_t sh, igraph_bliss_info_t *info); 258 IGRAPH_EXPORT int igraph_isomorphic_bliss(const igraph_t *graph1, const igraph_t *graph2, 259 const igraph_vector_int_t *colors1, const igraph_vector_int_t *colors2, 260 igraph_bool_t *iso, igraph_vector_t *map12, 261 igraph_vector_t *map21, 262 igraph_bliss_sh_t sh, 263 igraph_bliss_info_t *info1, igraph_bliss_info_t *info2); 264 265 IGRAPH_EXPORT int igraph_automorphisms(const igraph_t *graph, const igraph_vector_int_t *colors, 266 igraph_bliss_sh_t sh, igraph_bliss_info_t *info); 267 268 IGRAPH_EXPORT int igraph_automorphism_group(const igraph_t *graph, const igraph_vector_int_t *colors, igraph_vector_ptr_t *generators, 269 igraph_bliss_sh_t sh, igraph_bliss_info_t *info); 270 271 /* Functions for 3-4 graphs */ 272 IGRAPH_EXPORT int igraph_isomorphic_34(const igraph_t *graph1, const igraph_t *graph2, 273 igraph_bool_t *iso); 274 IGRAPH_EXPORT int igraph_isoclass(const igraph_t *graph, igraph_integer_t *isoclass); 275 IGRAPH_EXPORT int igraph_isoclass_subgraph(const igraph_t *graph, igraph_vector_t *vids, 276 igraph_integer_t *isoclass); 277 IGRAPH_EXPORT int igraph_isoclass_create(igraph_t *graph, igraph_integer_t size, 278 igraph_integer_t number, igraph_bool_t directed); 279 280 281 282 283 __END_DECLS 284 285 #endif 286