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_STRUCTURAL_H 25 #define IGRAPH_STRUCTURAL_H 26 27 #include "igraph_decls.h" 28 #include "igraph_constants.h" 29 #include "igraph_types.h" 30 #include "igraph_vector.h" 31 #include "igraph_matrix.h" 32 #include "igraph_datatype.h" 33 #include "igraph_iterators.h" 34 #include "igraph_attributes.h" 35 #include "igraph_sparsemat.h" 36 37 __BEGIN_DECLS 38 39 /* -------------------------------------------------- */ 40 /* Basic query functions */ 41 /* -------------------------------------------------- */ 42 43 IGRAPH_EXPORT int igraph_are_connected(const igraph_t *graph, igraph_integer_t v1, igraph_integer_t v2, igraph_bool_t *res); 44 IGRAPH_EXPORT int igraph_count_multiple(const igraph_t *graph, igraph_vector_t *res, igraph_es_t es); 45 IGRAPH_EXPORT int igraph_density(const igraph_t *graph, igraph_real_t *res, 46 igraph_bool_t loops); 47 IGRAPH_EXPORT int igraph_diversity(igraph_t *graph, const igraph_vector_t *weights, 48 igraph_vector_t *res, const igraph_vs_t vs); 49 IGRAPH_EXPORT int igraph_girth(const igraph_t *graph, igraph_integer_t *girth, 50 igraph_vector_t *circle); 51 IGRAPH_EXPORT int igraph_has_loop(const igraph_t *graph, igraph_bool_t *res); 52 IGRAPH_EXPORT int igraph_has_multiple(const igraph_t *graph, igraph_bool_t *res); 53 IGRAPH_EXPORT int igraph_is_loop(const igraph_t *graph, igraph_vector_bool_t *res, 54 igraph_es_t es); 55 IGRAPH_EXPORT int igraph_is_multiple(const igraph_t *graph, igraph_vector_bool_t *res, 56 igraph_es_t es); 57 IGRAPH_EXPORT int igraph_is_mutual(igraph_t *graph, igraph_vector_bool_t *res, igraph_es_t es); 58 IGRAPH_EXPORT int igraph_is_simple(const igraph_t *graph, igraph_bool_t *res); 59 IGRAPH_EXPORT int igraph_is_tree(const igraph_t *graph, igraph_bool_t *res, igraph_integer_t *root, igraph_neimode_t mode); 60 IGRAPH_EXPORT int igraph_maxdegree(const igraph_t *graph, igraph_integer_t *res, 61 igraph_vs_t vids, igraph_neimode_t mode, 62 igraph_bool_t loops); 63 IGRAPH_EXPORT int igraph_reciprocity(const igraph_t *graph, igraph_real_t *res, 64 igraph_bool_t ignore_loops, 65 igraph_reciprocity_t mode); 66 IGRAPH_EXPORT int igraph_strength(const igraph_t *graph, igraph_vector_t *res, 67 const igraph_vs_t vids, igraph_neimode_t mode, 68 igraph_bool_t loops, const igraph_vector_t *weights); 69 IGRAPH_EXPORT int igraph_sort_vertex_ids_by_degree(const igraph_t *graph, 70 igraph_vector_t *outvids, 71 igraph_vs_t vids, 72 igraph_neimode_t mode, 73 igraph_bool_t loops, 74 igraph_order_t order, 75 igraph_bool_t only_indices); 76 77 /* -------------------------------------------------- */ 78 /* Structural properties */ 79 /* -------------------------------------------------- */ 80 81 IGRAPH_EXPORT int igraph_minimum_spanning_tree(const igraph_t *graph, igraph_vector_t *res, 82 const igraph_vector_t *weights); 83 IGRAPH_EXPORT int igraph_minimum_spanning_tree_unweighted(const igraph_t *graph, 84 igraph_t *mst); 85 IGRAPH_EXPORT int igraph_minimum_spanning_tree_prim(const igraph_t *graph, igraph_t *mst, 86 const igraph_vector_t *weights); 87 IGRAPH_EXPORT int igraph_random_spanning_tree(const igraph_t *graph, igraph_vector_t *res, 88 igraph_integer_t vid); 89 90 IGRAPH_EXPORT int igraph_subcomponent(const igraph_t *graph, igraph_vector_t *res, igraph_real_t vid, 91 igraph_neimode_t mode); 92 93 IGRAPH_EXPORT int igraph_unfold_tree(const igraph_t *graph, igraph_t *tree, 94 igraph_neimode_t mode, const igraph_vector_t *roots, 95 igraph_vector_t *vertex_index); 96 97 IGRAPH_EXPORT int igraph_maximum_cardinality_search(const igraph_t *graph, 98 igraph_vector_t *alpha, 99 igraph_vector_t *alpham1); 100 IGRAPH_EXPORT int igraph_is_chordal(const igraph_t *graph, 101 const igraph_vector_t *alpha, 102 const igraph_vector_t *alpham1, 103 igraph_bool_t *chordal, 104 igraph_vector_t *fill_in, 105 igraph_t *newgraph); 106 IGRAPH_EXPORT int igraph_avg_nearest_neighbor_degree(const igraph_t *graph, 107 igraph_vs_t vids, 108 igraph_neimode_t mode, 109 igraph_neimode_t neighbor_degree_mode, 110 igraph_vector_t *knn, 111 igraph_vector_t *knnk, 112 const igraph_vector_t *weights); 113 114 IGRAPH_EXPORT int igraph_feedback_arc_set(const igraph_t *graph, igraph_vector_t *result, 115 const igraph_vector_t *weights, igraph_fas_algorithm_t algo); 116 117 /* -------------------------------------------------- */ 118 /* Spectral Properties */ 119 /* -------------------------------------------------- */ 120 121 IGRAPH_EXPORT int igraph_laplacian(const igraph_t *graph, igraph_matrix_t *res, 122 igraph_sparsemat_t *sparseres, 123 igraph_bool_t normalized, 124 const igraph_vector_t *weights); 125 126 __END_DECLS 127 128 #endif 129