SNAP Library 4.1, Developer Reference  2018-07-26 16:30:42
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, TFltVFltV& LeftSV, TFltVFltV& 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 void GetEigVec(const PUNGraph& Graph, const int& EigVecs, TFltV& EigValV, TFltVFltV& EigVecV) {
348  const int Nodes = Graph->GetNodes();
349  // Lanczos
350  TUNGraphMtx GraphMtx(Graph);
351  int CalcVals = int(2*EigVecs);
352  if (CalcVals > Nodes) { CalcVals = Nodes; }
353  TFltVV EigVecVV;
354  //while (EigValV.Len() < EigVecs && CalcVals < 10*EigVecs) {
355  try {
356  TSparseSVD::Lanczos(GraphMtx, EigVecs, 2*EigVecs, ssotFull, EigValV, EigVecVV, false); }
357  catch(...) {
358  printf("\n ***EXCEPTION: TRIED %d GOT %d values** \n", CalcVals, EigValV.Len()); }
359  if (EigValV.Len() < EigVecs) {
360  printf(" ***TRIED %d GOT %d values** \n", CalcVals, EigValV.Len()); }
361  // CalcVals += EigVecs;
362  //}
363  TFltIntPrV EigValIdV;
364  for (int i = 0; i < EigValV.Len(); i++) {
365  EigValIdV.Add(TFltIntPr(EigValV[i], i));
366  }
367  EigValIdV.Sort(false);
368  EigValV.Sort(false);
369  for (int v = 0; v < EigValIdV.Len(); v++) { // vector components are not sorted!!!
370  EigVecV.Add();
371  EigVecVV.GetCol(EigValIdV[v].Val2, EigVecV.Last());
372  }
373  IsAllValVNeg(EigVecV[0], true);
374 }
375 
376 // Inverse participation ratio: normalize EigVec to have L2=1 and then I=sum_k EigVec[i]^4
377 // see Spectra of "real-world" graphs: Beyond the semicircle law by Farkas, Derenyi, Barabasi and Vicsek
378 void GetInvParticipRat(const PUNGraph& Graph, int MaxEigVecs, int TimeLimit, TFltPrV& EigValIprV) {
379  TUNGraphMtx GraphMtx(Graph);
380  TFltVV EigVecVV;
381  TFltV EigValV;
382  TExeTm ExeTm;
383  if (MaxEigVecs<=1) { MaxEigVecs=1000; }
384  int EigVecs = TMath::Mn(Graph->GetNodes(), MaxEigVecs);
385  printf("start %d vecs...", EigVecs);
386  try {
387  TSparseSVD::Lanczos2(GraphMtx, EigVecs, TimeLimit, ssotFull, EigValV, EigVecVV, false);
388  } catch(...) {
389  printf("\n ***EXCEPTION: TRIED %d GOT %d values** \n", EigVecs, EigValV.Len()); }
390  printf(" ***TRIED %d GOT %d values in %s\n", EigVecs, EigValV.Len(), ExeTm.GetStr());
391  TFltV EigVec;
392  EigValIprV.Clr();
393  if (EigValV.Empty()) { return; }
394  for (int v = 0; v < EigVecVV.GetCols(); v++) {
395  EigVecVV.GetCol(v, EigVec);
396  EigValIprV.Add(TFltPr(EigValV[v], TSnapDetail::GetInvParticipRatEig(EigVec)));
397  }
398  EigValIprV.Sort();
399 }
400 
401 namespace TSnapDetail {
402 double GetInvParticipRatEig(const TFltV& EigVec) {
403  double Sum2=0.0, Sum4=0.0;
404  for (int i = 0; i < EigVec.Len(); i++) {
405  Sum2 += EigVec[i]*EigVec[i];
406  Sum4 += pow(EigVec[i].Val, 4.0);
407  }
408  return Sum4/(Sum2*Sum2);
409 }
410 } // namespace TSnapDetail
411 
412 }; // 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:402
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:544
TExeTm
Definition: tm.h:355
TSnap::GetInvParticipRat
void GetInvParticipRat(const PUNGraph &Graph, int MaxEigVecs, int TimeLimit, TFltPrV &EigValIprV)
Definition: gsvd.cpp:378
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:451
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
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:499
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
TUNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
TFlt
Definition: dt.h:1383
TNGraphMtx::TNGraphMtx
TNGraphMtx(const PNGraph &GraphPt)
Definition: gsvd.cpp:10
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
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:1022
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:1318
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:542
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:579
TVVec::GetRows
TSizeTy GetRows() const
Definition: ds.h:2252
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:466
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:373
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:546
TUNGraph::NodeH
THash< TInt, TNode > NodeH
Definition: graph.h:145
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TVVec::GetCol
void GetCol(const TSizeTy &ColN, TVec< TVal, TSizeTy > &Vec) const
Definition: ds.h:2390
TUNGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
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:602
TVVec::GetCols
TSizeTy GetCols() const
Definition: ds.h:2253
TNGraphMtx::PMultiply
void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: gsvd.cpp:19
TFlt::Mn
static const double Mn
Definition: dt.h:1387
TVVec::At
const TVal & At(const TSizeTy &X, const TSizeTy &Y) const
Definition: ds.h:2256