SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
subgraph.cpp
Go to the documentation of this file.
1 namespace TSnap {
2 
4 // Graph Algorithms
5 
6 // RenumberNodes ... Renumber node ids in the subgraph to 0...N-1
7 PUNGraph GetSubGraph(const PUNGraph& Graph, const TIntV& NIdV, const bool& RenumberNodes) {
8  //if (! RenumberNodes) { return TSnap::GetSubGraph(Graph, NIdV); }
9  PUNGraph NewGraphPt = TUNGraph::New();
10  TUNGraph& NewGraph = *NewGraphPt;
11  NewGraph.Reserve(NIdV.Len(), -1);
12  TIntSet NIdSet(NIdV.Len());
13  for (int n = 0; n < NIdV.Len(); n++) {
14  if (Graph->IsNode(NIdV[n])) {
15  NIdSet.AddKey(NIdV[n]);
16  if (! RenumberNodes) { NewGraph.AddNode(NIdV[n]); }
17  else { NewGraph.AddNode(NIdSet.GetKeyId(NIdV[n])); }
18  }
19  }
20  if (! RenumberNodes) {
21  for (int n = 0; n < NIdSet.Len(); n++) {
22  const int SrcNId = NIdSet[n];
23  const TUNGraph::TNodeI NI = Graph->GetNI(SrcNId);
24  for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
25  const int OutNId = NI.GetOutNId(edge);
26  if (NIdSet.IsKey(OutNId)) {
27  NewGraph.AddEdge(SrcNId, OutNId); }
28  }
29  }
30  } else {
31  for (int n = 0; n < NIdSet.Len(); n++) {
32  const int SrcNId = NIdSet[n];
33  const TUNGraph::TNodeI NI = Graph->GetNI(SrcNId);
34  for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
35  const int OutNId = NI.GetOutNId(edge);
36  if (NIdSet.IsKey(OutNId)) {
37  NewGraph.AddEdge(NIdSet.GetKeyId(SrcNId), NIdSet.GetKeyId(OutNId)); }
38  }
39  }
40  }
41  return NewGraphPt;
42 }
43 
44 // RenumberNodes ... Renumber node ids in the subgraph to 0...N-1
45 PNGraph GetSubGraph(const PNGraph& Graph, const TIntV& NIdV, const bool& RenumberNodes) {
46  //if (! RenumberNodes) { return TSnap::GetSubGraph(Graph, NIdV); }
47  PNGraph NewGraphPt = TNGraph::New();
48  TNGraph& NewGraph = *NewGraphPt;
49  NewGraph.Reserve(NIdV.Len(), -1);
50  TIntSet NIdSet(NIdV.Len());
51  for (int n = 0; n < NIdV.Len(); n++) {
52  if (Graph->IsNode(NIdV[n])) {
53  NIdSet.AddKey(NIdV[n]);
54  if (! RenumberNodes) { NewGraph.AddNode(NIdV[n]); }
55  else { NewGraph.AddNode(NIdSet.GetKeyId(NIdV[n])); }
56  }
57  }
58  if (! RenumberNodes) {
59  for (int n = 0; n < NIdSet.Len(); n++) {
60  const int SrcNId = NIdSet[n];
61  const TNGraph::TNodeI NI = Graph->GetNI(SrcNId);
62  for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
63  const int OutNId = NI.GetOutNId(edge);
64  if (NIdSet.IsKey(OutNId)) {
65  NewGraph.AddEdge(SrcNId, OutNId); }
66  }
67  }
68  } else {
69  for (int n = 0; n < NIdSet.Len(); n++) {
70  const int SrcNId = NIdSet[n];
71  const TNGraph::TNodeI NI = Graph->GetNI(SrcNId);
72  for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
73  const int OutNId = NI.GetOutNId(edge);
74  if (NIdSet.IsKey(OutNId)) {
75  NewGraph.AddEdge(NIdSet.GetKeyId(SrcNId), NIdSet.GetKeyId(OutNId)); }
76  }
77  }
78  }
79  return NewGraphPt;
80 }
81 
82 PUNGraph GetEgonet(const PUNGraph& Graph, const int CtrNId, int& ArndEdges) {
83  PUNGraph NewGraphPt = TUNGraph::New();
84  TUNGraph& NewGraph = *NewGraphPt;
85  NewGraph.AddNode(CtrNId);
86  const TUNGraph::TNodeI& CtrNode = Graph->GetNI(CtrNId);
87  for (int i = 0; i < CtrNode.GetInDeg(); ++i) {
88  NewGraph.AddNode(CtrNode.GetInNId(i));
89  }
90  ArndEdges = 0;
91  for (int i = 0; i < CtrNode.GetInDeg(); ++i) {
92  int NbrNId = CtrNode.GetInNId(i);
93  const TUNGraph::TNodeI& NbrNode = Graph->GetNI(NbrNId);
94  for (int j = 0; j < NbrNode.GetInDeg(); ++j) {
95  int NbrNbrNId = NbrNode.GetInNId(j);
96  if (NewGraph.IsNode(NbrNbrNId)) {
97  if (!NewGraph.IsEdge(NbrNId, NbrNbrNId)) {
98  NewGraph.AddEdge(NbrNId, NbrNbrNId);
99  }
100  } else {
101  ArndEdges++;
102  }
103  }
104  }
105  return NewGraphPt;
106 }
107 
108 PNGraph GetEgonet(const PNGraph& Graph, const int CtrNId, int& InEdges, int& OutEdges) {
109  PNGraph NewGraphPt = TNGraph::New();
110  TNGraph& NewGraph = *NewGraphPt;
111  NewGraph.AddNode(CtrNId);
112  const TNGraph::TNodeI& CtrNode = Graph->GetNI(CtrNId);
113  for (int i = 0; i < CtrNode.GetDeg(); ++i) {
114  if (!NewGraph.IsNode(CtrNode.GetNbrNId(i))) {
115  NewGraph.AddNode(CtrNode.GetNbrNId(i));
116  }
117  }
118  InEdges = 0;
119  OutEdges = 0;
120  for (int i = 0; i < CtrNode.GetDeg(); ++i) {
121  int NbrNId = CtrNode.GetNbrNId(i);
122  const TNGraph::TNodeI& NbrNode = Graph->GetNI(NbrNId);
123  for (int j = 0; j < NbrNode.GetInDeg(); ++j) {
124  int NbrNbrNId = NbrNode.GetInNId(j);
125  if (NewGraph.IsNode(NbrNbrNId)) {
126  NewGraph.AddEdge(NbrNbrNId, NbrNId);
127  } else {
128  InEdges++;
129  }
130  }
131  for (int j = 0; j < NbrNode.GetOutDeg(); ++j) {
132  int NbrNbrNId = NbrNode.GetOutNId(j);
133  if (NewGraph.IsNode(NbrNbrNId)) {
134  NewGraph.AddEdge(NbrNId, NbrNbrNId);
135  } else {
136  OutEdges++;
137  }
138  }
139  }
140  return NewGraphPt;
141 }
142 
143 void AddNodeWithAttributes(const PNEANet& Graph1, PNEANet& Graph2, const int NId) {
144  Graph2->AddNode(NId);
145  // Copy Int Attributes
146  TStrV IntAttrNames;
147  TIntV IntAttrValues;
148  Graph1->IntAttrNameNI(NId, IntAttrNames);
149  Graph1->IntAttrValueNI(NId, IntAttrValues);
150  for (int i = 0; i < IntAttrNames.Len(); i++) {
151  Graph2->AddIntAttrDatN(NId, IntAttrValues[i], IntAttrNames[i]);
152  }
153  // Copy Float Attributes
154  TStrV FltAttrNames;
155  TFltV FltAttrValues;
156  Graph1->FltAttrNameNI(NId, FltAttrNames);
157  Graph1->FltAttrValueNI(NId, FltAttrValues);
158  for (int i = 0; i < FltAttrNames.Len(); i++) {
159  Graph2->AddFltAttrDatN(NId, FltAttrValues[i], FltAttrNames[i]);
160  }
161  // Copy Str Attributes
162  TStrV StrAttrNames;
163  TStrV StrAttrValues;
164  Graph1->StrAttrNameNI(NId, StrAttrNames);
165  Graph1->StrAttrValueNI(NId, StrAttrValues);
166  for (int i = 0; i < StrAttrNames.Len(); i++) {
167  Graph2->AddStrAttrDatN(NId, StrAttrValues[i], StrAttrNames[i]);
168  }
169  // Copy IntV Attributes
170  TStrV IntVAttrNames;
171  TVec<TIntV> IntVAttrValues;
172  Graph1->IntVAttrNameNI(NId, IntVAttrNames);
173  Graph1->IntVAttrValueNI(NId, IntVAttrValues);
174  for (int i = 0; i < IntVAttrNames.Len(); i++) {
175  Graph2->AddIntVAttrDatN(NId, IntVAttrValues[i], IntVAttrNames[i]);
176  }
177 }
178 
179 void AddEdgeWithAttributes(const PNEANet &Graph1, PNEANet &Graph2, const int EId){
180  const TNEANet::TEdgeI EI = Graph1->GetEI(EId);
181  Graph2->AddEdge(EI);
182  //const int EId = Graph2->GetEId(NId, NbrId);
183  // Copy Int Attributes
184  TStrV IntAttrNames;
185  TIntV IntAttrValues;
186  Graph1->IntAttrNameEI(EId, IntAttrNames);
187  Graph1->IntAttrValueEI(EId, IntAttrValues);
188  for (int i = 0; i < IntAttrNames.Len(); i++) {
189  Graph2->AddIntAttrDatE(EId, IntAttrValues[i], IntAttrNames[i]);
190  }
191  // Copy Float Attributes
192  TStrV FltAttrNames;
193  TFltV FltAttrValues;
194  Graph1->FltAttrNameEI(EId, FltAttrNames);
195  Graph1->FltAttrValueEI(EId, FltAttrValues);
196  for (int i = 0; i < FltAttrNames.Len(); i++) {
197  Graph2->AddFltAttrDatE(EId, FltAttrValues[i], FltAttrNames[i]);
198  }
199  // Copy Str Attributes
200  TStrV StrAttrNames;
201  TStrV StrAttrValues;
202  Graph1->StrAttrNameEI(EId, StrAttrNames);
203  Graph1->StrAttrValueEI(EId, StrAttrValues);
204  for (int i = 0; i < StrAttrNames.Len(); i++) {
205  Graph2->AddStrAttrDatE(EId, StrAttrValues[i], StrAttrNames[i]);
206  }
207  // Copy IntV Attributes
208  TStrV IntVAttrNames;
209  TVec<TIntV> IntVAttrValues;
210  Graph1->IntVAttrNameEI(EId, IntVAttrNames);
211  Graph1->IntVAttrValueEI(EId, IntVAttrValues);
212  for (int i = 0; i < IntVAttrNames.Len(); i++) {
213  Graph2->AddIntVAttrDatE(EId, IntVAttrValues[i], IntVAttrNames[i]);
214  }
215 }
216 
217 void AddEdgeWithAttributes(const PNEANet &Graph1, PNEANet &Graph2, const int NId, const int NbrId) {
218  Graph2->AddEdge(NId, NbrId);
219  const int EId = Graph2->GetEId(NId, NbrId);
220  // Copy Int Attributes
221  TStrV IntAttrNames;
222  TIntV IntAttrValues;
223  Graph1->IntAttrNameEI(EId, IntAttrNames);
224  Graph1->IntAttrValueEI(EId, IntAttrValues);
225  for (int i = 0; i < IntAttrNames.Len(); i++) {
226  Graph2->AddIntAttrDatE(EId, IntAttrValues[i], IntAttrNames[i]);
227  }
228  // Copy Float Attributes
229  TStrV FltAttrNames;
230  TFltV FltAttrValues;
231  Graph1->FltAttrNameEI(EId, FltAttrNames);
232  Graph1->FltAttrValueEI(EId, FltAttrValues);
233  for (int i = 0; i < FltAttrNames.Len(); i++) {
234  Graph2->AddFltAttrDatE(EId, FltAttrValues[i], FltAttrNames[i]);
235  }
236  // Copy Str Attributes
237  TStrV StrAttrNames;
238  TStrV StrAttrValues;
239  Graph1->StrAttrNameEI(EId, StrAttrNames);
240  Graph1->StrAttrValueEI(EId, StrAttrValues);
241  for (int i = 0; i < StrAttrNames.Len(); i++) {
242  Graph2->AddStrAttrDatE(EId, StrAttrValues[i], StrAttrNames[i]);
243  }
244  // Copy IntV Attributes
245  TStrV IntVAttrNames;
246  TVec<TIntV> IntVAttrValues;
247  Graph1->IntVAttrNameEI(EId, IntVAttrNames);
248  Graph1->IntVAttrValueEI(EId, IntVAttrValues);
249  for (int i = 0; i < IntVAttrNames.Len(); i++) {
250  Graph2->AddIntVAttrDatE(EId, IntVAttrValues[i], IntVAttrNames[i]);
251  }
252 }
253 
254 PNEANet GetEgonetAttr(const PNEANet &Graph, const int CtrNId, const int Radius) {
255  PNEANet NewGraphPt = PNEANet::New();
256  TNEANet &NewGraph = *NewGraphPt;
257  TSnapQueue<int> Queue1;
258  TSnapQueue<int> Queue2;
259  TSnapQueue<int> tempSwapQueue;
260  AddNodeWithAttributes(Graph, NewGraphPt, CtrNId);
261  Queue1.Clr(false);
262  Queue1.Push(CtrNId);
263  for (int r = 0; r < Radius; ++r) {
264  while (!Queue1.Empty()) {
265  const int NId = Queue1.Top();
266  Queue1.Pop();
267  const TNEANet::TNodeI &Node = Graph->GetNI(NId);
268  for (int i = 0; i < Node.GetInDeg(); ++i) {
269  const int InNId = Node.GetInNId(i);
270  if (!NewGraph.IsNode(InNId)) {
271  AddNodeWithAttributes(Graph, NewGraphPt, InNId);
272  Queue2.Push(InNId);
273  }
274  const int InEId = Node.GetInEId(i);
275  if (!NewGraph.IsEdge(InEId)) {
276  AddEdgeWithAttributes(Graph, NewGraphPt, InEId);
277  }
278  }
279  for (int i = 0; i < Node.GetOutDeg(); ++i) {
280  const int OutNId = Node.GetOutNId(i);
281  if (!NewGraph.IsNode(OutNId)) {
282  AddNodeWithAttributes(Graph, NewGraphPt, OutNId);
283  Queue2.Push(OutNId);
284  }
285  const int OutEId = Node.GetOutEId(i);
286  if (!NewGraph.IsEdge(OutEId)) {
287  AddEdgeWithAttributes(Graph, NewGraphPt, OutEId);
288  }
289  }
290  for (int i = 0; i < Node.GetInDeg(); ++i) {
291  int InNId = Node.GetInNId(i);
292  const TNEANet::TNodeI &InNode = Graph->GetNI(InNId);
293  for (int j = 0; j < InNode.GetInDeg(); ++j) {
294  int NbrInNId = InNode.GetInNId(j);
295  if (NewGraph.IsNode(NbrInNId)) {
296  const int NbrInEId = InNode.GetInEId(j);
297  if (!NewGraph.IsEdge(NbrInEId)) {
298  AddEdgeWithAttributes(Graph, NewGraphPt, NbrInEId);
299  }
300  }
301  }
302  for (int j = 0; j < InNode.GetOutDeg(); ++j) {
303  int NbrOutNId = InNode.GetOutNId(j);
304  if (NewGraph.IsNode(NbrOutNId)) {
305  const int NbrOutEId = InNode.GetOutEId(j);
306  if (!NewGraph.IsEdge(NbrOutEId)) {
307  AddEdgeWithAttributes(Graph, NewGraphPt, NbrOutEId);
308  }
309  }
310  }
311  }
312  for (int i = 0; i < Node.GetOutDeg(); ++i) {
313  int OutNId = Node.GetOutNId(i);
314  const TNEANet::TNodeI &OutNode = Graph->GetNI(OutNId);
315  for (int j = 0; j < OutNode.GetInDeg(); ++j) {
316  int NbrInNId = OutNode.GetInNId(j);
317  if (NewGraph.IsNode(NbrInNId)) {
318  const int NbrInEId = OutNode.GetInEId(j);
319  if (!NewGraph.IsEdge(NbrInEId)) {
320  AddEdgeWithAttributes(Graph, NewGraphPt, NbrInEId);
321  }
322  }
323  }
324  for (int j = 0; j < OutNode.GetOutDeg(); ++j) {
325  int NbrOutNId = OutNode.GetOutNId(j);
326  if (NewGraph.IsNode(NbrOutNId)) {
327  const int NbrOutEId = OutNode.GetOutEId(j);
328  if (!NewGraph.IsEdge(NbrOutEId)) {
329  AddEdgeWithAttributes(Graph, NewGraphPt, NbrOutEId);
330  }
331  }
332  }
333  }
334  }
335  tempSwapQueue = Queue1;
336  Queue1 = Queue2;
337  Queue2 = tempSwapQueue;
338  }
339  return NewGraphPt;
340 }
341 
342 PNEANet GetInEgonetAttr(const PNEANet &Graph, const int CtrNId, const int Radius) {
343  PNEANet NewGraphPt = PNEANet::New();
344  TNEANet &NewGraph = *NewGraphPt;
345  TSnapQueue<int> Queue1;
346  TSnapQueue<int> Queue2;
347  TSnapQueue<int> tempSwapQueue;
348  AddNodeWithAttributes(Graph, NewGraphPt, CtrNId);
349  Queue1.Clr(false);
350  Queue1.Push(CtrNId);
351  for (int r = 0; r < Radius; ++r) {
352  while (!Queue1.Empty()) {
353  const int NId = Queue1.Top();
354  Queue1.Pop();
355  const TNEANet::TNodeI &Node = Graph->GetNI(NId);
356  for (int i = 0; i < Node.GetInDeg(); ++i) {
357  const int InNId = Node.GetInNId(i);
358  if (!NewGraph.IsNode(InNId)) {
359  AddNodeWithAttributes(Graph, NewGraphPt, InNId);
360  Queue2.Push(InNId);
361  }
362  const int InEId = Node.GetInEId(i);
363  if (!NewGraph.IsEdge(InEId)) {
364  AddEdgeWithAttributes(Graph, NewGraphPt, InEId);
365  }
366  }
367  for (int i = 0; i < Node.GetInDeg(); ++i) {
368  int InNId = Node.GetInNId(i);
369  const TNEANet::TNodeI &InNode = Graph->GetNI(InNId);
370  for (int j = 0; j < InNode.GetInDeg(); ++j) {
371  int NbrInNId = InNode.GetInNId(j);
372  if (NewGraph.IsNode(NbrInNId)) {
373  const int NbrInEId = InNode.GetInEId(j);
374  if (!NewGraph.IsEdge(NbrInEId)) {
375  AddEdgeWithAttributes(Graph, NewGraphPt, NbrInEId);
376  }
377  }
378  }
379  for (int j = 0; j < InNode.GetOutDeg(); ++j) {
380  int NbrOutNId = InNode.GetOutNId(j);
381  if (NewGraph.IsNode(NbrOutNId)) {
382  const int NbrOutEId = InNode.GetOutEId(j);
383  if (!NewGraph.IsEdge(NbrOutEId)) {
384  AddEdgeWithAttributes(Graph, NewGraphPt, NbrOutEId);
385  }
386  }
387  }
388  }
389  }
390  tempSwapQueue = Queue1;
391  Queue1 = Queue2;
392  Queue2 = tempSwapQueue;
393  }
394  return NewGraphPt;
395 }
396 
397 PNEANet GetOutEgonetAttr(const PNEANet &Graph, const int CtrNId, const int Radius) {
398  PNEANet NewGraphPt = PNEANet::New();
399  TNEANet &NewGraph = *NewGraphPt;
400  TSnapQueue<int> Queue1;
401  TSnapQueue<int> Queue2;
402  TSnapQueue<int> tempSwapQueue;
403  AddNodeWithAttributes(Graph, NewGraphPt, CtrNId);
404  Queue1.Clr(false);
405  Queue1.Push(CtrNId);
406  for (int r = 0; r < Radius; ++r) {
407  while (!Queue1.Empty()) {
408  const int NId = Queue1.Top();
409  Queue1.Pop();
410  const TNEANet::TNodeI &Node = Graph->GetNI(NId);
411  for (int i = 0; i < Node.GetOutDeg(); ++i) {
412  const int OutNId = Node.GetOutNId(i);
413  if (!NewGraph.IsNode(OutNId)) {
414  AddNodeWithAttributes(Graph, NewGraphPt, OutNId);
415  Queue2.Push(OutNId);
416  }
417  const int OutEId = Node.GetOutEId(i);
418  if (!NewGraph.IsEdge(OutEId)) {
419  AddEdgeWithAttributes(Graph, NewGraphPt, OutEId);
420  }
421  }
422  for (int i = 0; i < Node.GetOutDeg(); ++i) {
423  int OutNId = Node.GetOutNId(i);
424  const TNEANet::TNodeI &OutNode = Graph->GetNI(OutNId);
425  for (int j = 0; j < OutNode.GetInDeg(); ++j) {
426  int NbrInNId = OutNode.GetInNId(j);
427  if (NewGraph.IsNode(NbrInNId)) {
428  const int InEId = OutNode.GetInEId(j);
429  if (!NewGraph.IsEdge(InEId)) {
430  AddEdgeWithAttributes(Graph, NewGraphPt, InEId);
431  }
432  }
433  }
434  for (int j = 0; j < OutNode.GetOutDeg(); ++j) {
435  int NbrOutNId = OutNode.GetOutNId(j);
436  if (NewGraph.IsNode(NbrOutNId)) {
437  const int OutEId = OutNode.GetOutEId(j);
438  if (!NewGraph.IsEdge(OutEId)) {
439  AddEdgeWithAttributes(Graph, NewGraphPt, OutEId);
440  }
441  }
442  }
443  }
444  }
445  tempSwapQueue = Queue1;
446  Queue1 = Queue2;
447  Queue2 = tempSwapQueue;
448  }
449  return NewGraphPt;
450 }
451 
452 // TODO RS 2020/10/05, multiple edges between two nodes are not handled correctly
453 PNEANet GetInEgonetSubAttr(const PNEANet &Graph, const int CtrNId, const int Radius, const int MaxNum, const float percent) {
454  PNEANet NewGraphPt = TNEANet::New();
455  TNEANet& NewGraph = *NewGraphPt;
456  TSnapQueue<int> Queue1;
457  TSnapQueue<int> Queue2;
458  TSnapQueue<int> tempSwapQueue;
459  TSnapQueue<int> sampleQueue;
460  AddNodeWithAttributes(Graph, NewGraphPt, CtrNId);
461  Queue1.Clr(false);
462  Queue1.Push(CtrNId);
463  bool usePercent = (percent != -1.0);
464  int numSamples = MaxNum;
465  for (int r = 0; r < Radius; ++r) {
466  while (!Queue1.Empty()) {
467  const int NId = Queue1.Top();
468  Queue1.Pop();
469  const TNEANet::TNodeI &Node = Graph->GetNI(NId);
470  sampleQueue.Clr(true);
471  for (int i = 0; i < Node.GetInDeg(); ++i) {
472  const int InNId = Node.GetInNId(i);
473  if (!NewGraph.IsNode(InNId)) {
474  sampleQueue.Push(InNId);
475  }
476  }
477  if (usePercent) {
478  numSamples = (int) (percent * sampleQueue.Len());
479  }
480  sampleQueue.Sample(numSamples);
481  for (int i = 0; i < numSamples && !sampleQueue.Empty(); ++i) {
482  const int InNId = sampleQueue.Top();
483  sampleQueue.Pop();
484  if (!NewGraph.IsNode(InNId)) {
485  AddNodeWithAttributes(Graph, NewGraphPt, InNId);
486  Queue2.Push(InNId);
487  }
488  if (!NewGraph.IsEdge(InNId, NId)) {
489  AddEdgeWithAttributes(Graph, NewGraphPt, InNId, NId);
490  }
491  }
492  for (int i = 0; i < Node.GetInDeg(); ++i) {
493  int InNId = Node.GetInNId(i);
494  if (!NewGraph.IsNode(InNId)) { continue; }
495  const TNEANet::TNodeI &InNode = Graph->GetNI(InNId);
496  for (int j = 0; j < InNode.GetInDeg(); ++j) {
497  int NbrInNId = InNode.GetInNId(j);
498  if (NewGraph.IsNode(NbrInNId)) {
499  if (!NewGraph.IsEdge(NbrInNId, InNId)) {
500  AddEdgeWithAttributes(Graph, NewGraphPt, NbrInNId, InNId);
501  }
502  }
503  }
504  for (int j = 0; j < InNode.GetOutDeg(); ++j) {
505  int NbrOutNId = InNode.GetOutNId(j);
506  if (NewGraph.IsNode(NbrOutNId)) {
507  if (!NewGraph.IsEdge(InNId, NbrOutNId)) {
508  AddEdgeWithAttributes(Graph, NewGraphPt, InNId, NbrOutNId);
509  }
510  }
511  }
512  }
513  }
514  tempSwapQueue = Queue1;
515  Queue1 = Queue2;
516  Queue2 = tempSwapQueue;
517  }
518  return NewGraphPt;
519 }
520 
521 PNEANet GetGraphUnionAttr(PNEANet &DstGraph, const PNEANet &SrcGraph){
522  for (PNEANet::TObj::TNodeI NI = SrcGraph->BegNI(); NI < SrcGraph->EndNI(); NI++) {
523  if (! DstGraph->IsNode(NI.GetId())){
524  AddNodeWithAttributes(SrcGraph, DstGraph, NI.GetId());
525  }
526  }
527  for (PNEANet::TObj::TEdgeI EI = SrcGraph->BegEI(); EI < SrcGraph->EndEI(); EI++) {
528  if (! DstGraph->IsEdge(EI.GetSrcNId(), EI.GetDstNId()) || ! DstGraph->IsEdge(EI.GetId())){
529  if (! DstGraph->IsEdge(EI.GetId())){
530  AddEdgeWithAttributes(SrcGraph, DstGraph, EI.GetId());
531  }else{
532  AddEdgeWithAttributes(SrcGraph, DstGraph, EI.GetSrcNId(), EI.GetDstNId());
533  }
534  }
535  }
536  return DstGraph;
537 }
538 
539 } // namespace TSnap
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:420
Main namespace for all the Snap global entities.
Definition: alg.h:1
int GetOutNId(const int &EdgeN) const
Returns ID of EdgeN-th out-node (the node the current node points to).
Definition: network.h:1821
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:1813
PNEANet GetEgonetAttr(const PNEANet &Graph, const int CtrNId, const int Radius)
Returns the complete egonet of at given radius and copies node and edge attributes.
Definition: subgraph.cpp:254
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
PNEANet GetInEgonetSubAttr(const PNEANet &Graph, const int CtrNId, const int Radius, const int MaxNum, const float percent)
Returns the randomly sampled egonet with nodes sampled based on percentage or raw number...
Definition: subgraph.cpp:453
static TPt New()
Definition: bd.h:479
int GetInNId(const int &EdgeN) const
Returns ID of EdgeN-th in-node (the node pointing to the current node).
Definition: network.h:1817
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
int GetOutEId(const int &EdgeN) const
Returns ID of EdgeN-th out-edge.
Definition: network.h:1835
bool IsEdge(const int &EId) const
Tests whether an edge with edge ID EId exists in the graph.
Definition: network.h:2804
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1792
PNEANet GetGraphUnionAttr(PNEANet &DstGraph, const PNEANet &SrcGraph)
Definition: subgraph.cpp:521
int GetInEId(const int &EdgeN) const
Returns ID of EdgeN-th in-edge.
Definition: network.h:1833
void Pop()
Removes the first element from the queue.
Definition: gbase.h:211
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:199
PNEANet GetInEgonetAttr(const PNEANet &Graph, const int CtrNId, const int Radius)
Returns the in-egonet of at given radius and copies node and edge attributes.
Definition: subgraph.cpp:342
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:94
Undirected graph.
Definition: graph.h:32
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:302
PUNGraph GetSubGraph(const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes)
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumb...
Definition: subgraph.cpp:7
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int AddKey(const TKey &Key)
Definition: shash.h:1254
int GetInDeg() const
Returns in-degree of the current node.
Definition: network.h:1811
int Len() const
Returns the number of elements in the queue.
Definition: gbase.h:201
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:402
Directed multigraph with node edge attributes.
Definition: network.h:1741
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
void Clr(const bool &DoDel=true)
Deletes all elements from the queue.
Definition: gbase.h:194
Directed graph.
Definition: graph.h:346
Edge iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1867
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:106
void Sample(const int num, TRnd &Rnd=TInt::Rnd)
Definition: gbase.h:181
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
PUNGraph GetEgonet(const PUNGraph &Graph, const int CtrNId, int &ArndEdges)
Returns the egonet of node CtrNId as center in undirected graph Graph. And returns number of edges ar...
Definition: subgraph.cpp:82
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:214
int GetInDeg() const
Returns in-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:92
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
void AddNodeWithAttributes(const PNEANet &Graph1, PNEANet &Graph2, const int NId)
Definition: subgraph.cpp:143
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:614
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:209
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:2385
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:404
bool IsEdge(const int &SrcNId, const int &DstNId) const
Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
Definition: graph.cpp:137
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:412
static PNEANet New()
Static cons returns pointer to graph. Ex: PNEANet Graph=TNEANet::New().
Definition: network.h:2226
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
void AddEdgeWithAttributes(const PNEANet &Graph1, PNEANet &Graph2, const int EId)
Definition: subgraph.cpp:179
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:101
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
PNEANet GetOutEgonetAttr(const PNEANet &Graph, const int CtrNId, const int Radius)
Returns the out-egonet of at given radius and copies node and edge attributes.
Definition: subgraph.cpp:397