SNAP Library 4.0, User Reference  2017-07-27 13:18:06
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
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
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
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
#define IAssert(Cond)
Definition: bd.h:262
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
double GetInvParticipRatEig(const TFltV &EigVec)
Definition: gsvd.cpp:401
TPair< TFlt, TInt > TFltIntPr
Definition: ds.h:97
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
Definition: tm.h:355
void GetInvParticipRat(const PUNGraph &Graph, int MaxEigVecs, int TimeLimit, TFltPrV &EigValIprV)
Definition: gsvd.cpp:377
void GetEigVec(const PUNGraph &Graph, TFltV &EigVecV)
Computes the leading eigenvector of the adjacency matrix representing a given undirected Graph...
Definition: gsvd.cpp:336
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
static void SimpleLanczosSVD(const TMatrix &Matrix, const int &CalcSV, TFltV &SngValV, const bool &DoLocalReortoP=false)
Definition: linalg.cpp:1440
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
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
THash< TInt, TNode > NodeH
Definition: graph.h:451
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool IsAllValVNeg(TFltV &ValV, const bool &InvertSign)
Definition: gsvd.cpp:163
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
static void LanczosSVD(const TMatrix &Matrix, int NumSV, int Iters, const TSpSVDReOrtoType &ReOrtoType, TFltV &SgnValV, TFltVV &LeftSgnVecVV, TFltVV &RightSgnVecVV)
Definition: linalg.cpp:1454
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
Definition: dt.h:1383
TNGraphMtx(const PNGraph &GraphPt)
Definition: gsvd.cpp:10
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
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
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TUNGraphMtx(const PUNGraph &GraphPt)
Definition: gsvd.cpp:83
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void PMultiplyT(const TFltVV &B, int ColId, TFltV &Result) const
Definition: gsvd.cpp:47
Definition: gsvd.h:5
int GetRows() const
Definition: linalg.h:45
PNGraph Graph
Definition: gsvd.h:7
void PMultiplyT(const TFltVV &B, int ColId, TFltV &Result) const
Definition: gsvd.cpp:127
#define Assert(Cond)
Definition: bd.h:251
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:542
int GetCols() const
Definition: linalg.h:47
static void Svd1Based(const TFltVV &InMtx1, TFltVV &LSingV, TFltV &SingValV, TFltVV &RSingV)
Definition: xmath.cpp:1252
PUNGraph Graph
Definition: gsvd.h:31
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
TSizeTy GetRows() const
Definition: ds.h:2251
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
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
bool CheckNodeIds()
Definition: gsvd.cpp:76
int GetKeyId(const TKey &Key) const
Definition: hash.h:466
static void SimpleLanczos(const TMatrix &Matrix, const int &NumEig, TFltV &EigValV, const bool &DoLocalReortoP=false, const bool &SvdMatrixProductP=false)
Definition: linalg.cpp:1053
int AddKey(const TKey &Key)
Definition: hash.h:373
void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: gsvd.cpp:99
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
THash< TInt, TNode > NodeH
Definition: graph.h:145
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
void GetCol(const TSizeTy &ColN, TVec< TVal, TSizeTy > &Vec) const
Definition: ds.h:2389
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
void SetAllInvertSign(TFltV &ValV, const double &Val)
Definition: gsvd.cpp:158
bool CheckNodeIds()
Definition: gsvd.cpp:3
const char * GetStr() const
Definition: tm.h:368
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TSizeTy GetCols() const
Definition: ds.h:2252
void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: gsvd.cpp:19
static const double Mn
Definition: dt.h:1387
const TVal & At(const TSizeTy &X, const TSizeTy &Y) const
Definition: ds.h:2255