-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathalgorithm2.h
162 lines (132 loc) · 6.09 KB
/
algorithm2.h
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
/* algorithm2.h - Header File
*
* An algorithm for finding an initial devision.
*
* Our goal is to find a vector "s", that represents a division of graph G, that maximizes the modularity Q.
* To divide a group, we look at the additional change, DQ, to the modularity.
*
* We obtain the leading eigen-vector of B^[g], i.e., the eigen-vector of B^[g] with the largest eigenvalue.
* Then, vertices whose corresponding elements are positive go in one group, and the rest of the vertices go in the other.
*
* Division of G into two groups (s) is a vector of {+1,-1} where for each vertex i:
* s[i] = +1 if it belongs to the first group, and s[i] = -1 if it belongs to the second.
*
* The algorithm is called from algorithm3, and modifies the input "s" vector according to the algorithm's steps.
*/
#ifndef ALGORITHM2_H_
#define ALGORITHM2_H_
#include "graph.h"
#include "BHatMatrix.h"
/* ------------------------------------- Main Algorithm -------------------------------------- */
/* Divide a graph into two.
* If the eigen-value calculated during the algorithm is negative (< EPSILON),
* the "out" indicator holds "-1" for "no division".
* In any other case, the algorithm calculates the division and represents it with the values {-1,1} in s.
*
* @param BHatMatrix - a pointer to the current B-Hat matrix.
* @param graph - a pointer to the current group.
* @param vector of doubles - a pointer to the division vector.
* @param integer pointer - an indicator to the existence of a possible division.
*/
void divisionGraphToTwo(BHatMatrix*, graph*, double*, int*);
/* ----------------------------------- F Vector Calculation ----------------------------------- */
/* Computing and updating the F vector corresponding to the B[g] matrix.
* The function calculates the vector, for each group created after the division.
*
* @param BHatMatrix - a pointer to the current B-Hat matrix.
* @param graph - a pointer to the current group.
*/
void calcFVector(BHatMatrix*, graph*);
/* --------------------------------- Eigen - Pair Calculation --------------------------------- */
/* Computing the leading eigen-pair of a diagonalizable matrix B^[g] using power iteration.
* Power iteration uses matrix-vector multiplications to find the dominant eigen-vector,
* the eigen-vector with the largest absolute eigenvalue.
* In order to find the dominant eigen-vector, we use matrix shifting.
*
* We perform the algorithm on B^[g] shifted matrix.
* The function returns the eigen-vector of the shifted matrix,
* and updates the eigen-value pointer to the eigen-value of the shifted matrix minus the matrix norm.
*
* @param BHatMatrix - a pointer to the current B-Hat matrix.
* @param graph - a pointer to the current group.
* @param pointer to a double - a pointer to the eigen value.
*
* @return the matrix B^[g] dominant eigen vector
*/
double* findEigenValue(BHatMatrix*, graph*, double*);
/*
* The function sets random values to an input vector, according to a given graph.
*
* @param vector of doubles - pre allocated empty vector
* @param graph - a pointer to the current group
*/
void creatRandomVector(double*, graph*);
/*
* The function calculates the dot product between the degrees vector and another vector.
*
* @param graph - a pointer to the current group
* @param vector of integers - the original graph degrees vector
* @param vector of doubles - a vector to perform the dot product calculation with
*
* @return dot product result
*/
double calcDotProductInt(graph*, int*, double*);
/*
* The function calculates the dot product between two vectors.
*
* @param graph - a pointer to the current group
* @param vector of doubles - a vector to perform the dot product calculation with
* @param vector of doubles - a vector to perform the dot product calculation with
*
* @return dot product result
*/
double calcDotProduct(graph*, double*, double*);
/*
* The function checks if all the differences between each corresponding pair of values in the previous vector and another one
* are smaller than epsilon (0.00001)
*
* @param graph - a pointer to the current group
* @param vector of doubles - a vector for the difference check
* @param vector of doubles - another vector for the difference check
* @param double - a macro representing the epsilon value
*
* @return 1 if the difference between the vectors isn't small enough, 0 otherwise
*/
int checkDifference(graph*, double*, double*, double);
/*
* The function normalizes a given vector, by dividing its values by its norm
*
* @param graph - a pointer to the current group
* @param vector of doubles - a vector to normalize
* @param double - the given vector's norm
*/
void divideByNorm(graph*, double*, double);
/* ----------------------------------- S Vector Calculation ----------------------------------- */
/*
* The function sets the values in a given s vector to {-1,+1} according to the positivity (>EPSILON)
* of the values in the corresponding places in a provided eigen-vector
*
* @param vector of doubles - an eigen-vector
* @param graph - a pointer to the current group
* @param vector of doubles - the division vector
*/
void computeS(double*, graph*, double*);
/*
* The function creates a trivial division.
* If DQ<0 -> there is no division and the algorithm sets "s" to its initial values from the beginning of the algorithm.
*
* @param graph - a pointer to the current group
* @param vector of doubles - the division vector
*/
void createTrivialS(graph*, double*);
/* ----------------------------------- DQ Value Calculation ----------------------------------- */
/*
* The function computes the DQ value according to the formula: (0.5) * (s^T) * B^[g] * s
* DQ represents the difference in the modularity value of the given group.
*
* @param vector of doubles - the division vector
* @param graph - a pointer to the current group
* @param BHatMatrix - a pointer to the current B-Hat matrix.
*/
double computeDQ(double*, graph*, BHatMatrix*);
#endif