Graphviz  2.41.20170921.2350
SparseMatrix.h
Go to the documentation of this file.
1 /* $Id$Revision: */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 #ifndef SPARSEMATRIX_H
14 #define SPARSEMATRIX_H
15 
16 #include <general.h>
17 #include <stdio.h>
18 
19 #define SYMMETRY_EPSILON 0.0000001
21 enum {UNMASKED = -10, MASKED = 1};
24 
25 
27  int m; /* row dimension */
28  int n; /* column dimension */
29  int nz;/* The actual length used is nz, for CSR/CSC matrix this is the same as ia[n] */
30  int nzmax; /* the current length of ja and a (if exists) allocated.*/
31  int type; /* whether it is real/complex matrix, or pattern only */
32  int *ia; /* row pointer for CSR format, or row indices for coordinate format. 0-based */
33  int *ja; /* column indices. 0-based */
34  void *a; /* entry values. If NULL, pattern matrix */
35  int format;/* whether it is CSR, CSC, COORD. By default it is in CSR format */
36  int property; /* pattern_symmetric/symmetric/skew/hermitian*/
37  int size;/* size of each entry. This allows for general matrix where each entry is, say, a matrix itself */
38 };
39 
41 
43 
44 /* SparseMatrix_general is more general and allow elements to be
45  any data structure, not just real/int/complex etc */
46 SparseMatrix SparseMatrix_new(int m, int n, int nz, int type, int format);
47 SparseMatrix SparseMatrix_general_new(int m, int n, int nz, int type, size_t sz, int format);
48 
49 /* this version sum repeated entries */
50 SparseMatrix SparseMatrix_from_coordinate_format(SparseMatrix A);
51 /* what_to_sum is SUM_REPEATED_NONE, SUM_REPEATED_ALL, SUM_REPEATED_REAL_PART, SUM_REPEATED_IMAGINARY_PART, SUM_IMGINARY_KEEP_LAST_REAL*/
52 SparseMatrix SparseMatrix_from_coordinate_format_not_compacted(SparseMatrix A, int what_to_sum);
53 
54 SparseMatrix SparseMatrix_from_coordinate_arrays(int nz, int m, int n, int *irn, int *jcn, void *val, int type, size_t sz);
55 SparseMatrix SparseMatrix_from_coordinate_arrays_not_compacted(int nz, int m, int n, int *irn, int *jcn, void *val, int type, size_t sz, int what_to_sum);
56 
57 
58 void SparseMatrix_print(char *, SparseMatrix A);/*print to stdout in Mathematica format*/
59 
60 void SparseMatrix_export(FILE *f, SparseMatrix A);/* export into MM format except the header */
61 
62 SparseMatrix SparseMatrix_import_binary(char *name);
63 SparseMatrix SparseMatrix_import_binary_fp(FILE *f);/* import into a preopenned file */
64 
65 void SparseMatrix_export_binary(char *name, SparseMatrix A, int *flag);
66 void SparseMatrix_export_binary_fp(FILE *f, SparseMatrix A);/* export binary into a file preopened */
67 
68 void SparseMatrix_delete(SparseMatrix A);
69 
70 SparseMatrix SparseMatrix_add(SparseMatrix A, SparseMatrix B);
71 SparseMatrix SparseMatrix_multiply(SparseMatrix A, SparseMatrix B);
72 SparseMatrix SparseMatrix_multiply3(SparseMatrix A, SparseMatrix B, SparseMatrix C);
73 
74 /* For complex matrix:
75  if what_to_sum = SUM_REPEATED_REAL_PART, we find entries {i,j,x + i y} and sum the x's if {i,j,Round(y)} are the same
76  if what_to_sum = SUM_REPEATED_IMAGINARY_PART, we find entries {i,j,x + i y} and sum the y's if {i,j,Round(x)} are the same
77  For other matrix, what_to_sum = SUM_REPEATED_REAL_PART is the same as what_to_sum = SUM_REPEATED_IMAGINARY_PART
78  or what_to_sum = SUM_REPEATED_ALL
79  if what_to_sum = SUM_IMGINARY_KEEP_LAST_REAL, we merge {i,j,R1,I1} and {i,j,R2,I2} into {i,j,R1+R2,I2}. Useful if I1 and I2 are time stamps,
80  . and we use this to indicate that a user watched R1+R2 seconds, last watch is I2.
81 */
83 SparseMatrix SparseMatrix_sum_repeat_entries(SparseMatrix A, int what_to_sum);
84 SparseMatrix SparseMatrix_coordinate_form_add_entries(SparseMatrix A, int nentries, int *irn, int *jcn, void *val);
85 int SparseMatrix_is_symmetric(SparseMatrix A, int test_pattern_symmetry_only);
86 SparseMatrix SparseMatrix_transpose(SparseMatrix A);
87 SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, int pattern_symmetric_only);
88 SparseMatrix SparseMatrix_symmetrize_nodiag(SparseMatrix A, int pattern_symmetric_only);
89 void SparseMatrix_multiply_vector(SparseMatrix A, real *v, real **res, int transposed);/* if v = NULL, v is assumed to be {1,1,...,1}*/
90 SparseMatrix SparseMatrix_remove_diagonal(SparseMatrix A);
91 SparseMatrix SparseMatrix_remove_upper(SparseMatrix A);/* remove diag and upper diag */
92 SparseMatrix SparseMatrix_divide_row_by_degree(SparseMatrix A);
93 SparseMatrix SparseMatrix_get_real_adjacency_matrix_symmetrized(SparseMatrix A); /* symmetric, all entries to 1, diaginal removed */
94 SparseMatrix SparseMatrix_normalize_to_rowsum1(SparseMatrix A);/* for real only! */
95 void SparseMatrix_multiply_dense(SparseMatrix A, int ATranspose, real *v, int vTransposed, real **res, int res_transpose, int dim);
96 SparseMatrix SparseMatrix_apply_fun(SparseMatrix A, double (*fun)(double x));/* for real only! */
97 SparseMatrix SparseMatrix_apply_fun_general(SparseMatrix A, void (*fun)(int i, int j, int n, double *x));/* for real and complex (n=2) */
98 SparseMatrix SparseMatrix_copy(SparseMatrix A);
99 int SparseMatrix_has_diagonal(SparseMatrix A);
100 SparseMatrix SparseMatrix_normalize_by_row(SparseMatrix A);/* divide by max of each row */
101 SparseMatrix SparseMatrix_crop(SparseMatrix A, real epsilon);/*remove any entry <= epsilon*/
102 SparseMatrix SparseMatrix_scaled_by_vector(SparseMatrix A, real *v, int apply_to_row);
103 SparseMatrix SparseMatrix_multiply_by_scaler(SparseMatrix A, real s);
104 SparseMatrix SparseMatrix_make_undirected(SparseMatrix A);/* make it strictly low diag only, and set flag to undirected */
105 int SparseMatrix_connectedQ(SparseMatrix A);
107 real SparseMatrix_pseudo_diameter_weighted(SparseMatrix A0, int root, int aggressive, int *end1, int *end2, int *connectedQ); /* assume real distances, unsymmetric matrix ill be symmetrized */
108 real SparseMatrix_pseudo_diameter_unweighted(SparseMatrix A0, int root, int aggressive, int *end1, int *end2, int *connectedQ); /* assume unit edge length, unsymmetric matrix ill be symmetrized */
109 void SparseMatrix_level_sets(SparseMatrix A, int root, int *nlevel, int **levelset_ptr, int **levelset, int **mask, int reintialize_mask);
110 void SparseMatrix_level_sets_khops(int khops, SparseMatrix A, int root, int *nlevel, int **levelset_ptr, int **levelset, int **mask, int reintialize_mask);
111 void SparseMatrix_weakly_connected_components(SparseMatrix A0, int *ncomp, int **comps, int **comps_ptr);
112 void SparseMatrix_decompose_to_supervariables(SparseMatrix A, int *ncluster, int **cluster, int **clusterp);
113 SparseMatrix SparseMatrix_get_submatrix(SparseMatrix A, int nrow, int ncol, int *rindices, int *cindices);
114 SparseMatrix SparseMatrix_exclude_submatrix(SparseMatrix A, int nrow, int ncol, int *rindices, int *cindices);
115 
116 SparseMatrix SparseMatrix_get_augmented(SparseMatrix A);
117 
118 /* bipartite_options:
119  BIPARTITE_RECT -- turn rectangular matrix into square),
120  BIPARTITE_PATTERN_UNSYM -- pattern unsummetric as bipartite
121  BIPARTITE_UNSYM -- unsymmetric as square
122  BIPARTITE_ALWAYS -- always as square
123 */
124 SparseMatrix SparseMatrix_to_square_matrix(SparseMatrix A, int bipartite_options);
125 
126 SparseMatrix SparseMatrix_largest_component(SparseMatrix A);
127 
128 /* columns with <= threhold entries are deleted */
129 SparseMatrix SparseMatrix_delete_empty_columns(SparseMatrix A, int **new2old, int *nnew, int inplace);
130 SparseMatrix SparseMatrix_delete_sparse_columns(SparseMatrix A, int threshold, int **new2old, int *nnew, int inplace);
131 
132 SparseMatrix SparseMatrix_sort(SparseMatrix A);
133 
134 SparseMatrix SparseMatrix_set_entries_to_real_one(SparseMatrix A);
135 
136 SparseMatrix SparseMatrix_complement(SparseMatrix A, int undirected);
137 
138 int SparseMatrix_k_centers(SparseMatrix D, int weighted, int K, int root,
139  int **centers, int centering, real **dist);
140 
141 int SparseMatrix_k_centers_user(SparseMatrix D, int weighted, int K,
142  int *centers_user, int centering, real **dist);
143 
144 SparseMatrix SparseMatrix_distance_matrix_k_centers(int K, SparseMatrix D, int weighted);
145 
146 int SparseMatrix_distance_matrix(SparseMatrix A, int weighted, real **dist_matrix);
147 SparseMatrix SparseMatrix_distance_matrix_khops(int khops, SparseMatrix A, int weighted);
148 SparseMatrix SparseMatrix_distance_matrix_k_centers(int K, SparseMatrix D, int weighted);
149 
150 void SparseMatrix_kcoreness(SparseMatrix A, int **coreness);/* assign coreness to each node */
151 void SparseMatrix_kcore_decomposition(SparseMatrix A, int *coreness_max0, int **coreness_ptr0, int **coreness_list0);/* return the decomposition */
152 
153 void SparseMatrix_khairness(SparseMatrix A, int **hairness);/* assign hairness to each node */
154 void SparseMatrix_khair_decomposition(SparseMatrix A, int *hairness_max0, int **hairness_ptr0, int **hairness_list0);/* return the decomposition */
155 
156 SparseMatrix SparseMatrix_from_dense(int m, int n, real *x);
157 
158 void SparseMatrix_page_rank(SparseMatrix A, real teleport_probablity, int weighted, real epsilon, real **page_rank);
159 
160 
161 #define SparseMatrix_set_undirected(A) set_flag((A)->property, MATRIX_UNDIRECTED)
162 #define SparseMatrix_set_symmetric(A) set_flag((A)->property, MATRIX_SYMMETRIC)
163 #define SparseMatrix_set_pattern_symmetric(A) set_flag((A)->property, MATRIX_PATTERN_SYMMETRIC)
164 #define SparseMatrix_set_skew(A) set_flag((A)->property, MATRIX_SKEW)
165 #define SparseMatrix_set_hemitian(A) set_flag((A)->property, MATRIX_HERMITIAN)
166 
167 
168 #define SparseMatrix_clear_undirected(A) clear_flag((A)->property, MATRIX_UNDIRECTED)
169 #define SparseMatrix_clear_symmetric(A) clear_flag((A)->property, MATRIX_SYMMETRIC)
170 #define SparseMatrix_clear_pattern_symmetric(A) clear_flag((A)->property, MATRIX_PATTERN_SYMMETRIC)
171 #define SparseMatrix_clear_skew(A) clear_flag((A)->property, MATRIX_SKEW)
172 #define SparseMatrix_clear_hemitian(A) clear_flag((A)->property, MATRIX_HERMITIAN)
173 
174 
175 #define SparseMatrix_known_undirected(A) test_flag((A)->property, MATRIX_UNDIRECTED)
176 #define SparseMatrix_known_symmetric(A) test_flag((A)->property, MATRIX_SYMMETRIC)
177 #define SparseMatrix_known_strucural_symmetric(A) test_flag((A)->property, MATRIX_PATTERN_SYMMETRIC)
178 #define SparseMatrix_known_skew(A) test_flag((A)->property, MATRIX_SKEW)
179 #define SparseMatrix_known_hemitian(A) test_flag((A)->property, MATRIX_HERMITIAN)
180 
181 
182 
183 
184 #endif
SparseMatrix SparseMatrix_get_submatrix(SparseMatrix A, int nrow, int ncol, int *rindices, int *cindices)
void SparseMatrix_export_binary_fp(FILE *f, SparseMatrix A)
Definition: SparseMatrix.c:626
void SparseMatrix_khairness(SparseMatrix A, int **hairness)
SparseMatrix SparseMatrix_multiply3(SparseMatrix A, SparseMatrix B, SparseMatrix C)
SparseMatrix SparseMatrix_import_binary_fp(FILE *f)
Definition: SparseMatrix.c:662
SparseMatrix SparseMatrix_multiply_by_scaler(SparseMatrix A, real s)
SparseMatrix SparseMatrix_sum_repeat_entries(SparseMatrix A, int what_to_sum)
SparseMatrix SparseMatrix_symmetrize_nodiag(SparseMatrix A, int pattern_symmetric_only)
Definition: SparseMatrix.c:163
real SparseMatrix_pseudo_diameter_only(SparseMatrix A)
SparseMatrix SparseMatrix_normalize_to_rowsum1(SparseMatrix A)
void SparseMatrix_page_rank(SparseMatrix A, real teleport_probablity, int weighted, real epsilon, real **page_rank)
SparseMatrix SparseMatrix_to_square_matrix(SparseMatrix A, int bipartite_options)
SparseMatrix SparseMatrix_set_entries_to_real_one(SparseMatrix A)
SparseMatrix SparseMatrix_copy(SparseMatrix A)
SparseMatrix SparseMatrix_scaled_by_vector(SparseMatrix A, real *v, int apply_to_row)
#define C
Definition: pack.c:29
SparseMatrix SparseMatrix_remove_upper(SparseMatrix A)
SparseMatrix SparseMatrix_import_binary(char *name)
Definition: SparseMatrix.c:707
SparseMatrix SparseMatrix_new(int m, int n, int nz, int type, int format)
Definition: SparseMatrix.c:384
SparseMatrix SparseMatrix_exclude_submatrix(SparseMatrix A, int nrow, int ncol, int *rindices, int *cindices)
int SparseMatrix_connectedQ(SparseMatrix A0)
SparseMatrix SparseMatrix_remove_diagonal(SparseMatrix A)
void SparseMatrix_export_binary(char *name, SparseMatrix A, int *flag)
Definition: SparseMatrix.c:646
struct SparseMatrix_struct * SparseMatrix
Definition: SparseMatrix.h:40
void SparseMatrix_multiply_dense(SparseMatrix A, int ATransposed, real *v, int vTransposed, real **res, int res_transposed, int dim)
void SparseMatrix_decompose_to_supervariables(SparseMatrix A, int *ncluster, int **cluster, int **clusterp)
SparseMatrix SparseMatrix_from_coordinate_arrays_not_compacted(int nz, int m, int n, int *irn, int *jcn, void *val0, int type, size_t sz, int what_to_sum)
Definition: SparseMatrix.c:962
int SparseMatrix_has_diagonal(SparseMatrix A)
int SparseMatrix_is_symmetric(SparseMatrix A, int test_pattern_symmetry_only)
Definition: SparseMatrix.c:178
int SparseMatrix_k_centers_user(SparseMatrix D0, int weighted, int K, int *centers_user, int centering, real **dist0)
void SparseMatrix_multiply_vector(SparseMatrix A, real *v, real **res, int transposed)
SparseMatrix SparseMatrix_largest_component(SparseMatrix A)
void SparseMatrix_kcore_decomposition(SparseMatrix A, int *coreness_max0, int **coreness_ptr0, int **coreness_list0)
SparseMatrix SparseMatrix_normalize_by_row(SparseMatrix A)
SparseMatrix SparseMatrix_delete_sparse_columns(SparseMatrix A, int threshold, int **new2old, int *nnew, int inplace)
SparseMatrix SparseMatrix_general_new(int m, int n, int nz, int type, size_t sz, int format)
Definition: SparseMatrix.c:397
void SparseMatrix_print(char *c, SparseMatrix A)
Definition: SparseMatrix.c:536
SparseMatrix SparseMatrix_get_augmented(SparseMatrix A)
void SparseMatrix_kcoreness(SparseMatrix A, int **coreness)
SparseMatrix SparseMatrix_from_coordinate_format_not_compacted(SparseMatrix A, int what_to_sum)
Definition: SparseMatrix.c:812
SparseMatrix SparseMatrix_get_real_adjacency_matrix_symmetrized(SparseMatrix A)
void SparseMatrix_export(FILE *f, SparseMatrix A)
Definition: SparseMatrix.c:778
SparseMatrix SparseMatrix_apply_fun_general(SparseMatrix A, void(*fun)(int i, int j, int n, double *x))
int SparseMatrix_distance_matrix(SparseMatrix D0, int weighted, real **dist0)
SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, int pattern_symmetric_only)
Definition: SparseMatrix.c:151
void SparseMatrix_level_sets(SparseMatrix A, int root, int *nlevel, int **levelset_ptr, int **levelset, int **mask, int reinitialize_mask)
void SparseMatrix_level_sets_khops(int khops, SparseMatrix A, int root, int *nlevel, int **levelset_ptr, int **levelset, int **mask, int reinitialize_mask)
void SparseMatrix_delete(SparseMatrix A)
Definition: SparseMatrix.c:411
Definition: grammar.c:79
SparseMatrix SparseMatrix_from_dense(int m, int n, real *x)
real SparseMatrix_pseudo_diameter_unweighted(SparseMatrix A0, int root, int aggressive, int *end1, int *end2, int *connectedQ)
SparseMatrix SparseMatrix_sort(SparseMatrix A)
Definition: SparseMatrix.c:54
SparseMatrix SparseMatrix_delete_empty_columns(SparseMatrix A, int **new2old, int *nnew, int inplace)
real SparseMatrix_pseudo_diameter_weighted(SparseMatrix A0, int root, int aggressive, int *end1, int *end2, int *connectedQ)
int SparseMatrix_k_centers(SparseMatrix D0, int weighted, int K, int root, int **centers, int centering, real **dist0)
SparseMatrix SparseMatrix_from_coordinate_arrays(int nz, int m, int n, int *irn, int *jcn, void *val0, int type, size_t sz)
Definition: SparseMatrix.c:957
SparseMatrix SparseMatrix_crop(SparseMatrix A, real epsilon)
SparseMatrix SparseMatrix_distance_matrix_k_centers(int K, SparseMatrix D, int weighted)
SparseMatrix SparseMatrix_multiply(SparseMatrix A, SparseMatrix B)
void SparseMatrix_khair_decomposition(SparseMatrix A, int *hairness_max0, int **hairness_ptr0, int **hairness_list0)
SparseMatrix SparseMatrix_make_undirected(SparseMatrix A)
Definition: SparseMatrix.c:62
SparseMatrix SparseMatrix_distance_matrix_khops(int khops, SparseMatrix D0, int weighted)
SparseMatrix SparseMatrix_divide_row_by_degree(SparseMatrix A)
void SparseMatrix_weakly_connected_components(SparseMatrix A0, int *ncomp, int **comps, int **comps_ptr)
double dist(Site *s, Site *t)
Definition: site.c:41
SparseMatrix SparseMatrix_apply_fun(SparseMatrix A, double(*fun)(double x))
SparseMatrix SparseMatrix_add(SparseMatrix A, SparseMatrix B)
Definition: SparseMatrix.c:966
SparseMatrix SparseMatrix_coordinate_form_add_entries(SparseMatrix A, int nentries, int *irn, int *jcn, void *val)
SparseMatrix SparseMatrix_from_coordinate_format(SparseMatrix A)
Definition: SparseMatrix.c:797
SparseMatrix SparseMatrix_transpose(SparseMatrix A)
Definition: SparseMatrix.c:69
SparseMatrix SparseMatrix_complement(SparseMatrix A, int undirected)
#define real
Definition: general.h:34