SNAP Library 3.0, User Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
gsvd.cpp
Go to the documentation of this file.
1 // Directed Graph Matrix -- sparse {0,1} row matrix
3 bool TNGraphMtx::CheckNodeIds() {
4  for (int NId = 0; NId < Graph->GetNodes(); NId++) {
5  if (! Graph->IsNode(NId)) { return false; }
6  }
7  return true;
8 }
9 
10 TNGraphMtx::TNGraphMtx(const PNGraph& GraphPt) : Graph() {
11  Graph = GraphPt;
12  if (! CheckNodeIds()) {
13  printf(" Renumbering nodes.\n");
14  Graph = TSnap::ConvertGraph<PNGraph>(GraphPt, true);
15  }
16 }
17 
18 // Result = A * B(:,ColId)
19 void TNGraphMtx::PMultiply(const TFltVV& B, int ColId, TFltV& Result) const {
20  const int RowN = GetRows();
21  Assert(B.GetRows() >= RowN && Result.Len() >= RowN);
22  const THash<TInt, TNGraph::TNode>& NodeH = Graph->NodeH;
23  for (int j = 0; j < RowN; j++) {
24  const TIntV& RowV = NodeH[j].OutNIdV;
25  Result[j] = 0.0;
26  for (int i = 0; i < RowV.Len(); i++) {
27  Result[j] += B(RowV[i], ColId);
28  }
29  }
30 }
31 
32 // Result = A * Vec
33 void TNGraphMtx::PMultiply(const TFltV& Vec, TFltV& Result) const {
34  const int RowN = GetRows();
35  Assert(Vec.Len() >= RowN && Result.Len() >= RowN);
36  const THash<TInt, TNGraph::TNode>& NodeH = Graph->NodeH;
37  for (int j = 0; j < RowN; j++) {
38  const TIntV& RowV = NodeH[j].OutNIdV;
39  Result[j] = 0.0;
40  for (int i = 0; i < RowV.Len(); i++) {
41  Result[j] += Vec[RowV[i]];
42  }
43  }
44 }
45 
46 // Result = A' * B(:,ColId)
47 void TNGraphMtx::PMultiplyT(const TFltVV& B, int ColId, TFltV& Result) const {
48  const int ColN = GetCols();
49  Assert(B.GetRows() >= ColN && Result.Len() >= ColN);
50  const THash<TInt, TNGraph::TNode>& NodeH = Graph->NodeH;
51  for (int i = 0; i < ColN; i++) Result[i] = 0.0;
52  for (int j = 0; j < ColN; j++) {
53  const TIntV& RowV = NodeH[j].OutNIdV;
54  for (int i = 0; i < RowV.Len(); i++) {
55  Result[RowV[i]] += B(j, ColId);
56  }
57  }
58 }
59 
60 // Result = A' * Vec
61 void TNGraphMtx::PMultiplyT(const TFltV& Vec, TFltV& Result) const {
62  const int RowN = GetRows();
63  Assert(Vec.Len() >= RowN && Result.Len() >= RowN);
64  const THash<TInt, TNGraph::TNode>& NodeH = Graph->NodeH;
65  for (int i = 0; i < RowN; i++) Result[i] = 0.0;
66  for (int j = 0; j < RowN; j++) {
67  const TIntV& RowV = NodeH[j].OutNIdV;
68  for (int i = 0; i < RowV.Len(); i++) {
69  Result[RowV[i]] += Vec[j];
70  }
71  }
72 }
73 
75 // Undirected Graph Matrix -- sparse {0,1} row matrix
76 bool TUNGraphMtx::CheckNodeIds() {
77  for (int NId = 0; NId < Graph->GetNodes(); NId++) {
78  if (! Graph->IsNode(NId)) { return false; }
79  }
80  return true;
81 }
82 
83 TUNGraphMtx::TUNGraphMtx(const PUNGraph& GraphPt) : Graph() {
84  Graph = GraphPt;
85  if (! CheckNodeIds()) {
86  printf(" Renumbering %d nodes....", GraphPt->GetNodes());
87  TExeTm ExeTm;
88  Graph = TSnap::ConvertGraph<PUNGraph>(GraphPt, true);
89  /*TIntSet NIdSet;
90  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
91  NIdSet.AddKey(NI.GetId());
92  }
93  Graph = TUNGraph::New(); *Graph = *GraphPt; */
94  printf("done [%s]\n", ExeTm.GetStr());
95  }
96 }
97 
98 // Result = A * B(:,ColId)
99 void TUNGraphMtx::PMultiply(const TFltVV& B, int ColId, TFltV& Result) const {
100  const int RowN = GetRows();
101  Assert(B.GetRows() >= RowN && Result.Len() >= RowN);
102  const THash<TInt, TUNGraph::TNode>& NodeH = Graph->NodeH;
103  for (int j = 0; j < RowN; j++) {
104  const TIntV& RowV = NodeH[j].NIdV;
105  Result[j] = 0.0;
106  for (int i = 0; i < RowV.Len(); i++) {
107  Result[j] += B(RowV[i], ColId);
108  }
109  }
110 }
111 
112 // Result = A * Vec
113 void TUNGraphMtx::PMultiply(const TFltV& Vec, TFltV& Result) const {
114  const int RowN = GetRows();
115  Assert(Vec.Len() >= RowN && Result.Len() >= RowN);
116  const THash<TInt, TUNGraph::TNode>& NodeH = Graph->NodeH;
117  for (int j = 0; j < RowN; j++) {
118  const TIntV& RowV = NodeH[j].NIdV;
119  Result[j] = 0.0;
120  for (int i = 0; i < RowV.Len(); i++) {
121  Result[j] += Vec[RowV[i]];
122  }
123  }
124 }
125 
126 // Result = A' * B(:,ColId)
127 void TUNGraphMtx::PMultiplyT(const TFltVV& B, int ColId, TFltV& Result) const {
128  const int ColN = GetCols();
129  Assert(B.GetRows() >= ColN && Result.Len() >= ColN);
130  const THash<TInt, TUNGraph::TNode>& NodeH = Graph->NodeH;
131  for (int i = 0; i < ColN; i++) Result[i] = 0.0;
132  for (int j = 0; j < ColN; j++) {
133  const TIntV& RowV = NodeH[j].NIdV;
134  for (int i = 0; i < RowV.Len(); i++) {
135  Result[RowV[i]] += B(j, ColId);
136  }
137  }
138 }
139 
140 // Result = A' * Vec
141 void TUNGraphMtx::PMultiplyT(const TFltV& Vec, TFltV& Result) const {
142  const int RowN = GetRows();
143  Assert(Vec.Len() >= RowN && Result.Len() >= RowN);
144  const THash<TInt, TUNGraph::TNode>& NodeH = Graph->NodeH;
145  for (int i = 0; i < RowN; i++) Result[i] = 0.0;
146  for (int j = 0; j < RowN; j++) {
147  const TIntV& RowV = NodeH[j].NIdV;
148  for (int i = 0; i < RowV.Len(); i++) {
149  Result[RowV[i]] += Vec[j];
150  }
151  }
152 }
153 
155 // Graphs Singular Value Decomposition
156 namespace TSnap {
157 
158 void SetAllInvertSign(TFltV& ValV, const double& Val) {
159  for (int i = 0; i < ValV.Len(); i++) {
160  ValV[i] = -ValV[i];
161  }
162 }
163 bool IsAllValVNeg(TFltV& ValV, const bool& InvertSign) {
164  bool IsAllNeg=true;
165  for (int i = 0; i < ValV.Len(); i++) {
166  if (ValV[i]>0.0) { IsAllNeg=false; break; }
167  }
168  if (IsAllNeg && InvertSign) {
169  for (int i = 0; i < ValV.Len(); i++) {
170  ValV[i] = -ValV[i]; }
171  }
172  return IsAllNeg;
173 }
174 
175 void GetSngVals(const PNGraph& Graph, const int& SngVals, TFltV& SngValV) {
176  const int Nodes = Graph->GetNodes();
177  IAssert(SngVals > 0);
178  if (Nodes < 100) {
179  // perform full SVD
180  TFltVV AdjMtx(Nodes+1, Nodes+1);
181  TFltVV LSingV, RSingV;
182  TIntH NodeIdH;
183  // create adjecency matrix
184  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
185  NodeIdH.AddKey(NodeI.GetId()); }
186  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
187  const int NodeId = NodeIdH.GetKeyId(NodeI.GetId()) + 1;
188  for (int e = 0; e < NodeI.GetOutDeg(); e++) {
189  const int DstNId = NodeIdH.GetKeyId(NodeI.GetOutNId(e)) + 1; // no self edges
190  if (NodeId != DstNId) AdjMtx.At(NodeId, DstNId) = 1;
191  }
192  }
193  try { // can fail to converge but results seem to be good
194  TSvd::Svd1Based(AdjMtx, LSingV, SngValV, RSingV); }
195  catch(...) {
196  printf("\n***No SVD convergence: G(%d, %d)\n", Nodes, Graph->GetEdges()); }
197  } else {
198  // Lanczos
199  TNGraphMtx GraphMtx(Graph);
200  int CalcVals = int(2*SngVals);
201  //if (CalcVals > Nodes) { CalcVals = int(2*Nodes); }
202  //if (CalcVals > Nodes) { CalcVals = Nodes; }
203  //while (SngValV.Len() < SngVals && CalcVals < 10*SngVals) {
204  try {
205  if (SngVals > 4) {
206  TSparseSVD::SimpleLanczosSVD(GraphMtx, 2*SngVals, SngValV, false); }
207  else { TFltVV LSingV, RSingV; // this is much more precise, but also much slower
208  TSparseSVD::LanczosSVD(GraphMtx, SngVals, 3*SngVals, ssotFull, SngValV, LSingV, RSingV); }
209  }
210  catch(...) {
211  printf("\n ***EXCEPTION: TRIED %d GOT %d values** \n", 2*SngVals, SngValV.Len()); }
212  if (SngValV.Len() < SngVals) {
213  printf(" ***TRIED %d GOT %d values** \n", CalcVals, SngValV.Len()); }
214  // CalcVals += SngVals;
215  //}
216  }
217  SngValV.Sort(false);
218  //if (SngValV.Len() > SngVals) {
219  // SngValV.Del(SngVals, SngValV.Len()-1); }
220  //else {
221  // while (SngValV.Len() < SngVals) SngValV.Add(1e-6); }
222  //IAssert(SngValV.Len() == SngVals);
223 }
224 
225 void GetSngVec(const PNGraph& Graph, TFltV& LeftSV, TFltV& RightSV) {
226  const int Nodes = Graph->GetNodes();
227  TFltVV LSingV, RSingV;
228  TFltV SngValV;
229  if (Nodes < 500) {
230  // perform full SVD
231  TFltVV AdjMtx(Nodes+1, Nodes+1);
232  TIntH NodeIdH;
233  // create adjecency matrix
234  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
235  NodeIdH.AddKey(NodeI.GetId()); }
236  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
237  const int NodeId = NodeIdH.GetKeyId(NodeI.GetId()) + 1;
238  for (int e = 0; e < NodeI.GetOutDeg(); e++) {
239  const int DstNId = NodeIdH.GetKeyId(NodeI.GetOutNId(e)) + 1; // no self edges
240  if (NodeId != DstNId) AdjMtx.At(NodeId, DstNId) = 1;
241  }
242  }
243  try { // can fail to converge but results seem to be good
244  TSvd::Svd1Based(AdjMtx, LSingV, SngValV, RSingV); }
245  catch(...) {
246  printf("\n***No SVD convergence: G(%d, %d)\n", Nodes, Graph->GetEdges()); }
247  } else { // Lanczos
248  TNGraphMtx GraphMtx(Graph);
249  TSparseSVD::LanczosSVD(GraphMtx, 1, 8, ssotFull, SngValV, LSingV, RSingV);
250  }
251  TFlt MxSngVal = TFlt::Mn;
252  int ValN = 0;
253  for (int i = 0; i < SngValV.Len(); i++) {
254  if (MxSngVal < SngValV[i]) { MxSngVal = SngValV[i]; ValN = i; } }
255  LSingV.GetCol(ValN, LeftSV);
256  RSingV.GetCol(ValN, RightSV);
257  IsAllValVNeg(LeftSV, true);
258  IsAllValVNeg(RightSV, true);
259 }
260 
261 void GetSngVec(const PNGraph& Graph, const int& SngVecs, TFltV& SngValV, TVec<TFltV>& LeftSV, TVec<TFltV>& RightSV) {
262  const int Nodes = Graph->GetNodes();
263  SngValV.Clr();
264  LeftSV.Clr();
265  RightSV.Clr();
266  TFltVV LSingV, RSingV;
267  if (Nodes < 100) {
268  // perform full SVD
269  TFltVV AdjMtx(Nodes+1, Nodes+1);
270  TIntH NodeIdH;
271  // create adjecency matrix (1-based)
272  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
273  NodeIdH.AddKey(NodeI.GetId()); }
274  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
275  const int NodeId = NodeIdH.GetKeyId(NodeI.GetId())+1;
276  for (int e = 0; e < NodeI.GetOutDeg(); e++) {
277  const int DstNId = NodeIdH.GetKeyId(NodeI.GetOutNId(e))+1; // no self edges
278  if (NodeId != DstNId) AdjMtx.At(NodeId, DstNId) = 1;
279  }
280  }
281  try { // can fail to converge but results seem to be good
282  TSvd::Svd1Based(AdjMtx, LSingV, SngValV, RSingV);
283  } catch(...) {
284  printf("\n***No SVD convergence: G(%d, %d)\n", Nodes, Graph->GetEdges());
285  }
286  } else { // Lanczos
287  TNGraphMtx GraphMtx(Graph);
288  TSparseSVD::LanczosSVD(GraphMtx, SngVecs, 2*SngVecs, ssotFull, SngValV, LSingV, RSingV);
289  //TGAlg::SaveFullMtx(Graph, "adj_mtx.txt");
290  //TLAMisc::DumpTFltVVMjrSubMtrx(LSingV, LSingV.GetRows(), LSingV.GetCols(), "LSingV2.txt"); // save MTX
291  }
292  TFltIntPrV SngValIdV;
293  for (int i = 0; i < SngValV.Len(); i++) {
294  SngValIdV.Add(TFltIntPr(SngValV[i], i));
295  }
296  SngValIdV.Sort(false);
297  SngValV.Sort(false);
298  for (int v = 0; v < SngValIdV.Len(); v++) {
299  LeftSV.Add();
300  LSingV.GetCol(SngValIdV[v].Val2, LeftSV.Last());
301  RightSV.Add();
302  RSingV.GetCol(SngValIdV[v].Val2, RightSV.Last());
303  }
304  IsAllValVNeg(LeftSV[0], true);
305  IsAllValVNeg(RightSV[0], true);
306 }
307 
308 void GetEigVals(const PUNGraph& Graph, const int& EigVals, TFltV& EigValV) {
309  // Lanczos
310  TUNGraphMtx GraphMtx(Graph);
311  //const int Nodes = Graph->GetNodes();
312  //int CalcVals = int(2*EigVals);
313  //if (CalcVals > Nodes) { CalcVals = Nodes; }
314  //while (EigValV.Len() < EigVals && CalcVals < 3*EigVals) {
315  try {
316  if (EigVals > 4) {
317  TSparseSVD::SimpleLanczos(GraphMtx, 2*EigVals, EigValV, false); }
318  else { TFltVV EigVecVV; // this is much more precise, but also much slower
319  TSparseSVD::Lanczos(GraphMtx, EigVals, 3*EigVals, ssotFull, EigValV, EigVecVV, false); }
320  }
321  catch(...) {
322  printf("\n ***EXCEPTION: TRIED %d GOT %d values** \n", 2*EigVals, EigValV.Len()); }
323  if (EigValV.Len() < EigVals) {
324  printf(" ***TRIED %d GOT %d values** \n", 2*EigVals, EigValV.Len()); }
325  // CalcVals += EigVals;
326  //}
327  EigValV.Sort(false);
328  /*if (EigValV.Len() > EigVals) {
329  EigValV.Del(EigVals, EigValV.Len()-1); }
330  else {
331  while (EigValV.Len() < EigVals) EigValV.Add(1e-6);
332  }
333  IAssert(EigValV.Len() == EigVals);*/
334 }
335 
336 void GetEigVec(const PUNGraph& Graph, TFltV& EigVecV) {
337  TUNGraphMtx GraphMtx(Graph);
338  TFltV EigValV;
339  TFltVV EigVecVV;
340  TSparseSVD::Lanczos(GraphMtx, 1, 8, ssotFull, EigValV, EigVecVV, false);
341  EigVecVV.GetCol(0, EigVecV); // vector components are not sorted!!!
342  IsAllValVNeg(EigVecV, true);
343 }
344 
345 // to get first few eigenvectors
346 void GetEigVec(const PUNGraph& Graph, const int& EigVecs, TFltV& EigValV, TVec<TFltV>& EigVecV) {
347  const int Nodes = Graph->GetNodes();
348  // Lanczos
349  TUNGraphMtx GraphMtx(Graph);
350  int CalcVals = int(2*EigVecs);
351  if (CalcVals > Nodes) { CalcVals = Nodes; }
352  TFltVV EigVecVV;
353  //while (EigValV.Len() < EigVecs && CalcVals < 10*EigVecs) {
354  try {
355  TSparseSVD::Lanczos(GraphMtx, EigVecs, 2*EigVecs, ssotFull, EigValV, EigVecVV, false); }
356  catch(...) {
357  printf("\n ***EXCEPTION: TRIED %d GOT %d values** \n", CalcVals, EigValV.Len()); }
358  if (EigValV.Len() < EigVecs) {
359  printf(" ***TRIED %d GOT %d values** \n", CalcVals, EigValV.Len()); }
360  // CalcVals += EigVecs;
361  //}
362  TFltIntPrV EigValIdV;
363  for (int i = 0; i < EigValV.Len(); i++) {
364  EigValIdV.Add(TFltIntPr(EigValV[i], i));
365  }
366  EigValIdV.Sort(false);
367  EigValV.Sort(false);
368  for (int v = 0; v < EigValIdV.Len(); v++) { // vector components are not sorted!!!
369  EigVecV.Add();
370  EigVecVV.GetCol(EigValIdV[v].Val2, EigVecV.Last());
371  }
372  IsAllValVNeg(EigVecV[0], true);
373 }
374 
375 // Inverse participation ratio: normalize EigVec to have L2=1 and then I=sum_k EigVec[i]^4
376 // see Spectra of "real-world" graphs: Beyond the semicircle law by Farkas, Derenyi, Barabasi and Vicsek
377 void GetInvParticipRat(const PUNGraph& Graph, int MaxEigVecs, int TimeLimit, TFltPrV& EigValIprV) {
378  TUNGraphMtx GraphMtx(Graph);
379  TFltVV EigVecVV;
380  TFltV EigValV;
381  TExeTm ExeTm;
382  if (MaxEigVecs<=1) { MaxEigVecs=1000; }
383  int EigVecs = TMath::Mn(Graph->GetNodes(), MaxEigVecs);
384  printf("start %d vecs...", EigVecs);
385  try {
386  TSparseSVD::Lanczos2(GraphMtx, EigVecs, TimeLimit, ssotFull, EigValV, EigVecVV, false);
387  } catch(...) {
388  printf("\n ***EXCEPTION: TRIED %d GOT %d values** \n", EigVecs, EigValV.Len()); }
389  printf(" ***TRIED %d GOT %d values in %s\n", EigVecs, EigValV.Len(), ExeTm.GetStr());
390  TFltV EigVec;
391  EigValIprV.Clr();
392  if (EigValV.Empty()) { return; }
393  for (int v = 0; v < EigVecVV.GetCols(); v++) {
394  EigVecVV.GetCol(v, EigVec);
395  EigValIprV.Add(TFltPr(EigValV[v], TSnapDetail::GetInvParticipRatEig(EigVec)));
396  }
397  EigValIprV.Sort();
398 }
399 
400 namespace TSnapDetail {
401 double GetInvParticipRatEig(const TFltV& EigVec) {
402  double Sum2=0.0, Sum4=0.0;
403  for (int i = 0; i < EigVec.Len(); i++) {
404  Sum2 += EigVec[i]*EigVec[i];
405  Sum4 += pow(EigVec[i].Val, 4.0);
406  }
407  return Sum4/(Sum2*Sum2);
408 }
409 } // namespace TSnapDetail
410 
411 }; // namespace TSnap
TSnap::GetEigVals
void GetEigVals(const PUNGraph &Graph, const int &EigVals, TFltV &EigValV)
Computes top EigVals eigenvalues of the adjacency matrix representing a given undirected Graph...
Definition: gsvd.cpp:308
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TMath::Mn
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TSnap::TSnapDetail::GetInvParticipRatEig
double GetInvParticipRatEig(const TFltV &EigVec)
Definition: gsvd.cpp:401
TFltIntPr
TPair< TFlt, TInt > TFltIntPr
Definition: ds.h:97
TNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
TExeTm
Definition: tm.h:355
TSnap::GetInvParticipRat
void GetInvParticipRat(const PUNGraph &Graph, int MaxEigVecs, int TimeLimit, TFltPrV &EigValIprV)
Definition: gsvd.cpp:377
TSnap::GetEigVec
void GetEigVec(const PUNGraph &Graph, TFltV &EigVecV)
Computes the leading eigenvector of the adjacency matrix representing a given undirected Graph...
Definition: gsvd.cpp:336
TSparseSVD::Lanczos
static void Lanczos(const TMatrix &Matrix, int NumEig, int Iters, const TSpSVDReOrtoType &ReOrtoType, TFltV &EigValV, TFltVV &EigVecVV, const bool &SvdMatrixProductP=false)
Definition: linalg.cpp:1134
TSparseSVD::SimpleLanczosSVD
static void SimpleLanczosSVD(const TMatrix &Matrix, const int &CalcSV, TFltV &SngValV, const bool &DoLocalReortoP=false)
Definition: linalg.cpp:1440
TSparseSVD::Lanczos2
static void Lanczos2(const TMatrix &Matrix, int MaxNumEig, int MaxSecs, const TSpSVDReOrtoType &ReOrtoType, TFltV &EigValV, TFltVV &EigVecVV, const bool &SvdMatrixProductP=false)
Definition: linalg.cpp:1290
TNGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TNGraph::NodeH
THash< TInt, TNode > NodeH
Definition: graph.h:411
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TSnap::IsAllValVNeg
bool IsAllValVNeg(TFltV &ValV, const bool &InvertSign)
Definition: gsvd.cpp:163
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
TSparseSVD::LanczosSVD
static void LanczosSVD(const TMatrix &Matrix, int NumSV, int Iters, const TSpSVDReOrtoType &ReOrtoType, TFltV &SgnValV, TFltVV &LeftSgnVecVV, TFltVV &RightSgnVecVV)
Definition: linalg.cpp:1454
TVVec::GetCol
void GetCol(const int &ColN, TVec< TVal > &Vec) const
Definition: ds.h:2324
TUNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:168
TFlt
Definition: dt.h:1293
TNGraphMtx::TNGraphMtx
TNGraphMtx(const PNGraph &GraphPt)
Definition: gsvd.cpp:10
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
TSnap::GetSngVec
void GetSngVec(const PNGraph &Graph, TFltV &LeftSV, TFltV &RightSV)
Computes the leading left and right singular vector of the adjacency matrix representing a directed G...
Definition: gsvd.cpp:225
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
TUNGraphMtx::TUNGraphMtx
TUNGraphMtx(const PUNGraph &GraphPt)
Definition: gsvd.cpp:83
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
TNGraphMtx::PMultiplyT
void PMultiplyT(const TFltVV &B, int ColId, TFltV &Result) const
Definition: gsvd.cpp:47
TNGraphMtx
Definition: gsvd.h:5
TMatrix::GetRows
int GetRows() const
Definition: linalg.h:45
TNGraphMtx::Graph
PNGraph Graph
Definition: gsvd.h:7
TUNGraphMtx::PMultiplyT
void PMultiplyT(const TFltVV &B, int ColId, TFltV &Result) const
Definition: gsvd.cpp:127
Assert
#define Assert(Cond)
Definition: bd.h:251
TNGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:477
TMatrix::GetCols
int GetCols() const
Definition: linalg.h:47
TSvd::Svd1Based
static void Svd1Based(const TFltVV &InMtx1, TFltVV &LSingV, TFltV &SingValV, TFltVV &RSingV)
Definition: xmath.cpp:1252
TUNGraphMtx::Graph
PUNGraph Graph
Definition: gsvd.h:31
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:551
TFltPr
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TSnap::GetSngVals
void GetSngVals(const PNGraph &Graph, const int &SngVals, TFltV &SngValV)
Computes largest SngVals singular values of the adjacency matrix representing a directed Graph...
Definition: gsvd.cpp:175
TUNGraphMtx::CheckNodeIds
bool CheckNodeIds()
Definition: gsvd.cpp:76
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:424
TSparseSVD::SimpleLanczos
static void SimpleLanczos(const TMatrix &Matrix, const int &NumEig, TFltV &EigValV, const bool &DoLocalReortoP=false, const bool &SvdMatrixProductP=false)
Definition: linalg.cpp:1053
THash::AddKey
int AddKey(const TKey &Key)
Definition: hash.h:331
TUNGraphMtx::PMultiply
void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: gsvd.cpp:99
TNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
TUNGraph::NodeH
THash< TInt, TNode > NodeH
Definition: graph.h:141
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
TUNGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:207
TSnap::SetAllInvertSign
void SetAllInvertSign(TFltV &ValV, const double &Val)
Definition: gsvd.cpp:158
TNGraphMtx::CheckNodeIds
bool CheckNodeIds()
Definition: gsvd.cpp:3
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TVVec::GetCols
int GetCols() const
Definition: ds.h:2187
TVVec::GetRows
int GetRows() const
Definition: ds.h:2186
TNGraphMtx::PMultiply
void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: gsvd.cpp:19
TVVec::At
const TVal & At(const int &X, const int &Y) const
Definition: ds.h:2190
TFlt::Mn
static const double Mn
Definition: dt.h:1297