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
|
/*
igraph library.
Copyright (C) 2009-2025 The igraph development team <igraph@igraph.org>
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, see <https://www.gnu.org/licenses/>.
*/
#ifndef IGRAPH_STRUCTURAL_H
#define IGRAPH_STRUCTURAL_H
#include "igraph_decls.h"
#include "igraph_datatype.h"
#include "igraph_error.h"
#include "igraph_constants.h"
#include "igraph_iterators.h"
#include "igraph_matrix.h"
#include "igraph_sparsemat.h"
#include "igraph_types.h"
#include "igraph_vector.h"
IGRAPH_BEGIN_C_DECLS
/* -------------------------------------------------- */
/* Basic query functions */
/* -------------------------------------------------- */
IGRAPH_EXPORT igraph_error_t igraph_are_adjacent(const igraph_t *graph, igraph_int_t v1, igraph_int_t v2, igraph_bool_t *res);
IGRAPH_EXPORT igraph_error_t igraph_count_multiple(const igraph_t *graph, igraph_vector_int_t *res, igraph_es_t es);
IGRAPH_EXPORT igraph_error_t igraph_count_multiple_1(const igraph_t *graph, igraph_int_t *res, igraph_int_t eid);
IGRAPH_EXPORT igraph_error_t igraph_density(const igraph_t *graph, const igraph_vector_t *weights,
igraph_real_t *res, igraph_bool_t loops);
IGRAPH_EXPORT igraph_error_t igraph_diversity(const igraph_t *graph, const igraph_vector_t *weights,
igraph_vector_t *res, igraph_vs_t vs);
IGRAPH_EXPORT igraph_error_t igraph_girth(const igraph_t *graph, igraph_real_t *girth,
igraph_vector_int_t *circle);
IGRAPH_EXPORT igraph_error_t igraph_has_loop(const igraph_t *graph, igraph_bool_t *res);
IGRAPH_EXPORT igraph_error_t igraph_has_multiple(const igraph_t *graph, igraph_bool_t *res);
IGRAPH_EXPORT igraph_error_t igraph_count_loops(const igraph_t *graph, igraph_int_t *loop_count);
IGRAPH_EXPORT igraph_error_t igraph_is_loop(const igraph_t *graph, igraph_vector_bool_t *res,
igraph_es_t es);
IGRAPH_EXPORT igraph_error_t igraph_is_multiple(const igraph_t *graph, igraph_vector_bool_t *res,
igraph_es_t es);
IGRAPH_EXPORT igraph_error_t igraph_is_mutual(const igraph_t *graph, igraph_vector_bool_t *res, igraph_es_t es, igraph_bool_t loops);
IGRAPH_EXPORT igraph_error_t igraph_has_mutual(const igraph_t *graph, igraph_bool_t *res, igraph_bool_t loops);
IGRAPH_EXPORT igraph_error_t igraph_is_simple(const igraph_t *graph, igraph_bool_t *res, igraph_bool_t directed);
IGRAPH_EXPORT igraph_error_t igraph_is_tree(const igraph_t *graph, igraph_bool_t *res, igraph_int_t *root, igraph_neimode_t mode);
IGRAPH_EXPORT igraph_error_t igraph_is_acyclic(const igraph_t *graph, igraph_bool_t *res);
IGRAPH_EXPORT igraph_error_t igraph_is_forest(const igraph_t *graph, igraph_bool_t *res,
igraph_vector_int_t *roots, igraph_neimode_t mode);
IGRAPH_EXPORT igraph_error_t igraph_maxdegree(const igraph_t *graph, igraph_int_t *res,
igraph_vs_t vids, igraph_neimode_t mode,
igraph_loops_t loops);
IGRAPH_EXPORT igraph_error_t igraph_mean_degree(const igraph_t *graph, igraph_real_t *res,
igraph_bool_t loops);
IGRAPH_EXPORT igraph_error_t igraph_reciprocity(const igraph_t *graph, igraph_real_t *res,
igraph_bool_t ignore_loops,
igraph_reciprocity_t mode);
IGRAPH_EXPORT igraph_error_t igraph_strength(
const igraph_t *graph, igraph_vector_t *res, igraph_vs_t vids,
igraph_neimode_t mode, igraph_loops_t loops, const igraph_vector_t *weights
);
IGRAPH_EXPORT igraph_error_t igraph_sort_vertex_ids_by_degree(
const igraph_t *graph, igraph_vector_int_t *outvids, igraph_vs_t vids,
igraph_neimode_t mode, igraph_loops_t loops, igraph_order_t order,
igraph_bool_t only_indices
);
IGRAPH_EXPORT igraph_error_t igraph_is_perfect(const igraph_t *graph, igraph_bool_t *perfect);
/* -------------------------------------------------- */
/* Structural properties */
/* -------------------------------------------------- */
IGRAPH_EXPORT igraph_error_t igraph_is_complete(const igraph_t *graph, igraph_bool_t *res);
IGRAPH_EXPORT igraph_error_t igraph_is_clique(const igraph_t *graph, igraph_vs_t candidate,
igraph_bool_t directed, igraph_bool_t *res);
IGRAPH_EXPORT igraph_error_t igraph_is_independent_vertex_set(const igraph_t *graph, igraph_vs_t candidate,
igraph_bool_t *res);
IGRAPH_EXPORT igraph_error_t igraph_minimum_spanning_tree(
const igraph_t *graph, igraph_vector_int_t *res,
const igraph_vector_t *weights, igraph_mst_algorithm_t method);
IGRAPH_EXPORT igraph_error_t igraph_random_spanning_tree(const igraph_t *graph, igraph_vector_int_t *res,
igraph_int_t vid);
IGRAPH_EXPORT igraph_error_t igraph_subcomponent(const igraph_t *graph, igraph_vector_int_t *res, igraph_int_t vid,
igraph_neimode_t mode);
IGRAPH_EXPORT igraph_error_t igraph_unfold_tree(const igraph_t *graph, igraph_t *tree,
igraph_neimode_t mode, const igraph_vector_int_t *roots,
igraph_vector_int_t *vertex_index);
IGRAPH_EXPORT igraph_error_t igraph_maximum_cardinality_search(const igraph_t *graph,
igraph_vector_int_t *alpha,
igraph_vector_int_t *alpham1);
IGRAPH_EXPORT igraph_error_t igraph_is_chordal(const igraph_t *graph,
const igraph_vector_int_t *alpha,
const igraph_vector_int_t *alpham1,
igraph_bool_t *chordal,
igraph_vector_int_t *fill_in,
igraph_t *newgraph);
IGRAPH_EXPORT igraph_error_t igraph_avg_nearest_neighbor_degree(const igraph_t *graph,
igraph_vs_t vids,
igraph_neimode_t mode,
igraph_neimode_t neighbor_degree_mode,
igraph_vector_t *knn,
igraph_vector_t *knnk,
const igraph_vector_t *weights);
IGRAPH_EXPORT igraph_error_t igraph_degree_correlation_vector(
const igraph_t *graph, const igraph_vector_t *weights,
igraph_vector_t *knnk,
igraph_neimode_t from_mode, igraph_neimode_t to_mode,
igraph_bool_t directed_neighbors);
IGRAPH_EXPERIMENTAL IGRAPH_EXPORT igraph_error_t igraph_rich_club_sequence(
const igraph_t *graph,
const igraph_vector_t *weights,
igraph_vector_t *res,
const igraph_vector_int_t *vertex_order,
igraph_bool_t normalized,
igraph_bool_t loops,
igraph_bool_t directed);
/* -------------------------------------------------- */
/* Spectral Properties */
/* -------------------------------------------------- */
/**
* \typedef igraph_laplacian_normalization_t
* \brief Normalization methods for a Laplacian matrix.
*
* Normalization methods for \ref igraph_get_laplacian() and
* \ref igraph_get_laplacian_sparse(). In the following, \c A refers to the
* (possibly weighted) adjacency matrix and \c D is a diagonal matrix containing
* degrees (unweighted case) or strengths (weighted case). Out-, in- or total degrees
* are used according to the \p mode parameter.
*
* \enumval IGRAPH_LAPLACIAN_UNNORMALIZED Unnormalized Laplacian, <code>L = D - A</code>.
* \enumval IGRAPH_LAPLACIAN_SYMMETRIC Symmetrically normalized Laplacian, <code>L = I - D^(-1/2) A D^(-1/2)</code>.
* \enumval IGRAPH_LAPLACIAN_LEFT Left-stochastic normalized Laplacian, <code>L = I - D^-1 A</code>.
* \enumval IGRAPH_LAPLACIAN_RIGHT Right-stochastic normalized Laplacian, <code>L = I - A D^-1</code>.
*/
typedef enum {
IGRAPH_LAPLACIAN_UNNORMALIZED = 0,
IGRAPH_LAPLACIAN_SYMMETRIC = 1,
IGRAPH_LAPLACIAN_LEFT = 2,
IGRAPH_LAPLACIAN_RIGHT = 3
} igraph_laplacian_normalization_t;
IGRAPH_EXPORT igraph_error_t igraph_get_laplacian(
const igraph_t *graph, igraph_matrix_t *res, igraph_neimode_t mode,
igraph_laplacian_normalization_t normalization,
const igraph_vector_t *weights
);
IGRAPH_EXPORT igraph_error_t igraph_get_laplacian_sparse(
const igraph_t *graph, igraph_sparsemat_t *sparseres, igraph_neimode_t mode,
igraph_laplacian_normalization_t normalization,
const igraph_vector_t *weights
);
IGRAPH_END_C_DECLS
#endif
|
