SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
subgraph.h
Go to the documentation of this file.
1 
5 namespace TSnap {
7 
9 // Convert between graph types and get subgraphs
10 
11 // node subgraphs
13 
18 template<class PGraph> PGraph GetSubGraph(const PGraph& Graph, const TIntV& NIdV);
20 
25 template<class PGraph> PGraph GetSubGraphRenumber(const PGraph& Graph, const TIntV& NIdV);
27 
35 PUNGraph GetSubGraph(const PUNGraph& Graph, const TIntV& NIdV, const bool& RenumberNodes=false);
36 // Returns an induced subgraph of a directed graph Graph with NIdV nodes with an optional node renumbering. ##TSnap::GetSubGraph-2
37 PNGraph GetSubGraph(const PNGraph& Graph, const TIntV& NIdV, const bool& RenumberNodes=false);
38 // TODO ROK 2012/08/15 PNGraph GetSubGraph is not documented by doxygen.
39 // It is combined with PUNGraph GetSubGraph.
40 
41 // edge subgraphs
43 
52 template<class PGraph> PGraph GetESubGraph(const PGraph& Graph, const TIntV& EIdV);
53 // Returns a subgraph of graph Graph with EdgeV edges. ##TSnap::GetESubGraph-1
54 template<class PGraph> PGraph GetESubGraph(const PGraph& Graph, const TIntPrV& EdgeV);
55 // TODO ROK 2012/08/15 PGraph GetESubGraph TIntPrV is not documented by doxygen.
56 // It is combined with PGraph GetESubGraph TIntV.
58 
71 template<class PGraph, class TEdgeDat> PGraph GetEDatSubGraph(const PGraph& Graph, const TEdgeDat& EDat, const int& Cmp);
73 
87 template<class PGraph, class TEdgeDat> PGraph GetEDatSubGraph(const PGraph& Graph, const TIntV& NIdV, const TEdgeDat& EDat, const int& Cmp);
88 
89 // convert between the graphs. Does NOT copy the data
91 
102 template<class POutGraph, class PInGraph> POutGraph ConvertGraph(const PInGraph& InGraph, const bool& RenumberNodes=false);
104 
115 template<class POutGraph, class PInGraph> POutGraph ConvertSubGraph(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes=false);
116 // TODO RS 2012/08/14 find out why TSnap::ConvertSubGraph<PUNGraph>(NGraph, NIdV, true) aborts
118 
129 template<class POutGraph, class PInGraph> POutGraph ConvertESubGraph(const PInGraph& InGraph, const TIntV& EIdV, const bool& RenumberNodes=false);
130 // does not work on multigraphs
131 
132 // get random (induced) subgraphs
134 
137 template<class PGraph> PGraph GetRndSubGraph(const PGraph& Graph, const int& NNodes);
139 
142 template<class PGraph> PGraph GetRndESubGraph(const PGraph& Graph, const int& NEdges);
143 
144 // Get 1st degree egonet of a center node
146 PUNGraph GetEgonet(const PUNGraph& Graph, const int CtrNId, int& ArndEdgesX);
148 PNGraph GetEgonet(const PNGraph& Graph, const int CtrNId, int& InEgoEdgesX, int& OutEgoEdgesX);
149 
150 // Get egonet for given radius
152 template<class PGraph> PGraph GetEgonetHop(const PGraph &Graph, const int CtrNId, const int Radius);
154 template<class PGraph> PGraph GetInEgonetHop(const PGraph& Graph, const int CtrNId, const int Radius);
156 template<class PGraph> PGraph GetOutEgonetHop(const PGraph &Graph, const int CtrNId, const int Radius);
157 
159 PNEANet GetEgonetAttr(const PNEANet &Graph, const int CtrNId, const int Radius);
161 PNEANet GetInEgonetAttr(const PNEANet &Graph, const int CtrNId, const int Radius);
163 PNEANet GetOutEgonetAttr(const PNEANet &Graph, const int CtrNId, const int Radius);
164 
166 template<class PGraph> PGraph GetInEgonetSub(const PGraph &Graph, const int CtrNId, const int Radius, const int MaxNum = 2, const float percent = -1.0);
168 PNEANet GetInEgonetSubAttr(const PNEANet &Graph, const int CtrNId, const int Radius, const int MaxNum, const float percent);
169 
170 //Modifies DstGraph so that it is the union of SrcGraph and DstGraph and returns a copy of DstGraph
171 template<class PGraph> PGraph GetGraphUnion(PGraph& DstGraph, const PGraph& SrcGraph);
172 //Modifies DstGraph with attributes so that it is the union of SrcGraph and DstGraph and returns a copy of DstGraph
173 PNEANet GetGraphUnionAttr(PNEANet &DstGraph, const PNEANet &SrcGraph);
174 
176 // Implementation
177 namespace TSnapDetail {
178 // Slow for small sub-graphs as it traverses all the edges of Graph
179 template <class PGraph, bool IsMultiGraph>
180 struct TGetSubGraph {
181  static PGraph Do(const PGraph& Graph, const TIntV& NIdV) {
182  PGraph NewGraphPt = PGraph::TObj::New();
183  typename PGraph::TObj& NewGraph = *NewGraphPt;
184  NewGraph.Reserve(NIdV.Len(), -1);
185  for (int n = 0; n < NIdV.Len(); n++) {
186  if (Graph->IsNode(NIdV[n])) {
187  NewGraph.AddNode(Graph->GetNI(NIdV[n])); }
188  }
189  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
190  if (NewGraph.IsNode(EI.GetSrcNId()) && NewGraph.IsNode(EI.GetDstNId())) {
191  NewGraph.AddEdge(EI); }
192  }
193  NewGraph.Defrag();
194  return NewGraphPt;
195  }
196 };
197 
198 template <class PGraph>
199 struct TGetSubGraph<PGraph, false> { // not multigraph
200  static PGraph Do(const PGraph& Graph, const TIntV& NIdV) {
201  CAssert(! HasGraphFlag(typename PGraph::TObj, gfMultiGraph));
202  PGraph NewGraphPt = PGraph::TObj::New();
203  typename PGraph::TObj& NewGraph = *NewGraphPt;
204  NewGraph.Reserve(NIdV.Len(), -1);
205  TIntSet NodeSet;
206  for (int n = 0; n < NIdV.Len(); n++) {
207  if (! HasGraphFlag(typename PGraph::TObj, gfNodeDat)) {
208  if (Graph->IsNode(NIdV[n])) { NewGraph.AddNode(NIdV[n]); NodeSet.AddKey(NIdV[n]); } }
209  else {
210  if (Graph->IsNode(NIdV[n])) { NewGraph.AddNode(Graph->GetNI(NIdV[n])); NodeSet.AddKey(NIdV[n]); } }
211  }
212  for (int n = 0; n < NodeSet.Len(); n++) {
213  const int SrcNId = NodeSet[n];
214  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(SrcNId);
215  for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
216  const int OutNId = NI.GetOutNId(edge);
217  if (NewGraph.IsNode(OutNId)) {
218  if (! HasGraphFlag(typename PGraph::TObj, gfEdgeDat)) {
219  NewGraph.AddEdge(SrcNId, OutNId); }
220  else {
221  NewGraph.AddEdge(Graph->GetEI(SrcNId, OutNId)); } // also copy data
222  }
223  }
224  }
225  NewGraph.Defrag();
226  return NewGraphPt;
227  }
228 };
229 }; // TSnapDetail
230 
231 template<class PGraph>
232 PGraph GetSubGraph(const PGraph& Graph, const TIntV& NIdV) {
234  ::Do(Graph, NIdV);
235 }
236 
237 template<class PGraph>
238 PGraph GetSubGraphRenumber(const PGraph& Graph, const TIntV& NIdV) {
239  return GetSubGraph(Graph, NIdV, true);
240 }
241 
242 template<class PGraph>
243 PGraph GetESubGraph(const PGraph& Graph, const TIntV& EIdV) {
244  CAssert(HasGraphFlag(typename PGraph::TObj, gfMultiGraph));
245  PGraph NewGraphPt = PGraph::TObj::New();
246  typename PGraph::TObj& NewGraph = *NewGraphPt;
247  NewGraph.Reserve(-1, EIdV.Len());
248  for (int edge = 0; edge < EIdV.Len(); edge++) {
249  const int EId = EIdV[edge];
250  IAssert(Graph->IsEdge(EId));
251  const typename PGraph::TObj::TEdgeI EI = Graph->GetEI(EId);
252  if (! NewGraph.IsNode(EI.GetSrcNId())) {
253  NewGraph.AddNode(Graph->GetNI(EI.GetSrcNId()));
254  }
255  if (! NewGraph.IsNode(EI.GetDstNId())) {
256  NewGraph.AddNode(Graph->GetNI(EI.GetDstNId()));
257  }
258  NewGraph.AddEdge(EI);
259  }
260  return NewGraphPt;
261 }
262 
263 template<class PGraph>
264 PGraph GetESubGraph(const PGraph& Graph, const TIntPrV& EdgeV) {
265  PGraph NewGraphPt = PGraph::TObj::New();
266  typename PGraph::TObj& NewGraph = *NewGraphPt;
267  NewGraph.Reserve(-1, EdgeV.Len());
268 
269  for (int edge = 0; edge < EdgeV.Len(); edge++) {
270  const int SrcNId = EdgeV[edge].Val1;
271  const int DstNId = EdgeV[edge].Val2;
272  if (! NewGraph.IsNode(SrcNId)) {
273  NewGraph.AddNode(Graph->GetNI(SrcNId));
274  }
275  if (! NewGraph.IsNode(DstNId)) {
276  NewGraph.AddNode(Graph->GetNI(DstNId));
277  }
278 
279  NewGraph.AddEdge(SrcNId, DstNId);
280  }
281  return NewGraphPt;
282 }
283 
284 // Get a subgraph on NIdV nodes, where edge data is Cmp (-1:less, 0:equal, 1:greater) than EDat
285 template<class PGraph, class TEdgeDat>
286 PGraph GetEDatSubGraph(const PGraph& Graph, const TEdgeDat& EDat, const int& Cmp) {
287  CAssert(HasGraphFlag(typename PGraph::TObj, gfEdgeDat));
288  PGraph NewGraphPt = PGraph::TObj::New();
289  typename PGraph::TObj& NewGraph = *NewGraphPt;
290  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
291  if ((Cmp==1 && EI()>EDat) || (Cmp==-1 && EI()<EDat) || (Cmp==0 && EI()==EDat)) {
292  if (! NewGraph.IsNode(EI.GetSrcNId())) {
293  NewGraph.AddNode(Graph->GetNI(EI.GetSrcNId()));
294  }
295  if (! NewGraph.IsNode(EI.GetDstNId())) {
296  NewGraph.AddNode(Graph->GetNI(EI.GetDstNId()));
297  }
298  NewGraph.AddEdge(EI);
299  }
300  }
301  return NewGraphPt;
302 }
303 
304 // Get a subgraph on NIdV nodes, where edge data is Cmp (-1:less, 0:equal, 1:greater) than EDat
305 template<class PGraph, class TEdgeDat>
306 PGraph GetEDatSubGraph(const PGraph& Graph, const TIntV& NIdV, const TEdgeDat& EDat, const int& Cmp) {
307  CAssert(HasGraphFlag(typename PGraph::TObj, gfEdgeDat));
308  PGraph NewGraphPt = PGraph::TObj::New();
309  typename PGraph::TObj& NewGraph = *NewGraphPt;
310  NewGraph.Reserve(NIdV.Len(), -1);
311  for (int n = 0; n < NIdV.Len(); n++) {
312  NewGraph.AddNode(Graph->GetNI(NIdV[n]));
313  }
314  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
315  if (NewGraph.IsNode(EI.GetSrcNId()) && NewGraph.IsNode(EI.GetDstNId()) &&
316  ((Cmp==1 && EI()>EDat)|| (Cmp==-1 && EI()<EDat) || (Cmp==0 && EI()==EDat))) {
317  NewGraph.AddEdge(EI); }
318  }
319  NewGraph.Defrag();
320  return NewGraphPt;
321 }
322 
323 // Converts between different types of graphs/networks
324 // Node/edge data is not copied between the graphs.
325 template<class POutGraph, class PInGraph>
326 POutGraph ConvertGraph(const PInGraph& InGraph, const bool& RenumberNodes) {
327  POutGraph OutGraphPt = POutGraph::TObj::New();
328  typename POutGraph::TObj& OutGraph = *OutGraphPt;
329  OutGraph.Reserve(InGraph->GetNodes(), InGraph->GetEdges());
330  if (! RenumberNodes) {
331  for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
332  OutGraph.AddNode(NI.GetId());
333  }
334  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
335  OutGraph.AddEdge(EI.GetSrcNId(), EI.GetDstNId());
336  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) { // add edge in the other direction
337  OutGraph.AddEdge(EI.GetDstNId(), EI.GetSrcNId()); }
338  }
339  } else { // renumber nodes so that node ids are 0...N-1
340  TIntSet NIdSet(InGraph->GetNodes());
341  for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
342  const int nid = NIdSet.AddKey(NI.GetId());
343  OutGraph.AddNode(nid);
344  }
345  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
346  const int SrcNId = NIdSet.GetKeyId(EI.GetSrcNId());
347  const int DstNId = NIdSet.GetKeyId(EI.GetDstNId());
348  OutGraph.AddEdge(SrcNId, DstNId);
349  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
350  OutGraph.AddEdge(DstNId, SrcNId); }
351  }
352  }
353  //OutGraph.Defrag();
354  return OutGraphPt;
355 }
356 
357 namespace TSnapDetail {
358 // Slow for small sub-graphs as it traverses all the edges of Graph
359 template <class POutGraph, class PInGraph, bool IsMultiGraph>
361  static POutGraph Do(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes) {
362  POutGraph OutGraphPt = POutGraph::TObj::New();
363  typename POutGraph::TObj& OutGraph = *OutGraphPt;
364  if (! RenumberNodes) {
365  for (int n = 0; n < NIdV.Len(); n++) {
366  OutGraph.AddNode(NIdV[n]);
367  }
368  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
369  if (! OutGraph.IsNode(EI.GetSrcNId()) || ! OutGraph.IsNode(EI.GetDstNId())) { continue; }
370  OutGraph.AddEdge(EI.GetSrcNId(), EI.GetDstNId());
371  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
372  OutGraph.AddEdge(EI.GetDstNId(), EI.GetSrcNId());
373  }
374  }
375  } else { // renumber nodes so that node ids are 0...N-1
376  TIntSet NIdSet(InGraph->GetNodes());
377  for (int n = 0; n < NIdV.Len(); n++) {
378  const int NId = NIdSet.AddKey(NIdV[n]);
379  OutGraph.AddNode(NId);
380  }
381  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
382  const int SrcNId = NIdSet.GetKeyId(EI.GetSrcNId());
383  const int DstNId = NIdSet.GetKeyId(EI.GetDstNId());
384  if (! OutGraph.IsNode(SrcNId) || ! OutGraph.IsNode(DstNId)) { continue; }
385  OutGraph.AddEdge(SrcNId, DstNId);
386  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
387  OutGraph.AddEdge(DstNId, SrcNId);
388  }
389  }
390  }
391  OutGraph.Defrag();
392  return OutGraphPt;
393  }
394 };
395 
396 template <class POutGraph, class PInGraph>
397 struct TConvertSubGraph<POutGraph, PInGraph, false> { // InGraph is not multigraph
398  static POutGraph Do(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes) {
399  POutGraph OutGraphPt = POutGraph::TObj::New();
400  typename POutGraph::TObj& OutGraph = *OutGraphPt;
401  if (! RenumberNodes) {
402  for (int n = 0; n < NIdV.Len(); n++) {
403  OutGraph.AddNode(NIdV[n]); }
404  for (int n = 0; n < NIdV.Len(); n++) {
405  typename PInGraph::TObj::TNodeI NI = InGraph->GetNI(NIdV[n]);
406  for (int e = 0; e < NI.GetOutDeg(); e++) {
407  const int dst = NI.GetOutNId(e);
408  if (! OutGraph.IsNode(dst)) { continue; }
409  OutGraph.AddEdge(NIdV[n], dst);
410  }
411  }
412  } else { // renumber nodes so that node ids are 0...N-1
413  TIntSet NIdSet(InGraph->GetNodes());
414  for (int n = 0; n < NIdV.Len(); n++) {
415  const int NId = NIdSet.AddKey(NIdV[n]);
416  OutGraph.AddNode(NId);
417  }
418  for (int n = 0; n < NIdV.Len(); n++) {
419  typename PInGraph::TObj::TNodeI NI = InGraph->GetNI(NIdV[n]);
420  const int src = NIdSet.GetKey(NIdV[n]);
421  for (int e = 0; e < NI.GetOutDeg(); e++) {
422  const int dst = NIdSet.GetKey(NI.GetOutNId(e));
423  if (! OutGraph.IsNode(dst)) { continue; }
424  OutGraph.AddEdge(src, dst);
425  }
426  }
427  }
428  OutGraph.Defrag();
429  return OutGraphPt;
430  }
431 };
432 } // TSnapDetail
433 
434 // May be slow as it traverses all the edges of the in-graph to create the sub-graph
435 template<class POutGraph, class PInGraph>
436 POutGraph ConvertSubGraph(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes) {
438 }
439 
440 template<class POutGraph, class PInGraph>
441 POutGraph ConvertESubGraph(const PInGraph& InGraph, const TIntV& EIdV, const bool& RenumberNodes) {
442  CAssert(HasGraphFlag(typename PInGraph::TObj, gfMultiGraph)); // needs to have explicit edges
443  POutGraph NewGraphPt = POutGraph::TObj::New();
444  typename POutGraph::TObj& NewGraph = *NewGraphPt;
445  NewGraph.Reserve(-1, EIdV.Len());
446  if (! RenumberNodes) {
447  for (int edge = 0; edge < EIdV.Len(); edge++) {
448  const int EId = EIdV[edge];
449  IAssert(InGraph->IsEdge(EId));
450  const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
451  const int SrcNId = EI.GetSrcNId();
452  const int DstNId = EI.GetDstNId();
453  if (! NewGraph.IsNode(SrcNId)) {
454  NewGraph.AddNode(SrcNId); }
455  if (! NewGraph.IsNode(DstNId)) {
456  NewGraph.AddNode(DstNId); }
457  NewGraph.AddEdge(SrcNId, DstNId);
458  }
459  } else {
460  // renumber nodes so that node ids are 0...N-1
461  TIntSet NIdSet(InGraph->GetNodes());
462  for (int edge = 0; edge < EIdV.Len(); edge++) {
463  const int EId = EIdV[edge];
464  IAssert(InGraph->IsEdge(EId));
465  const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
466  const int SrcNId = NIdSet.AddKey(EI.GetSrcNId()); // map node ids
467  const int DstNId = NIdSet.AddKey(EI.GetDstNId());
468  if (! NewGraph.IsNode(SrcNId)) {
469  NewGraph.AddNode(SrcNId); }
470  if (! NewGraph.IsNode(DstNId)) {
471  NewGraph.AddNode(DstNId); }
472  NewGraph.AddEdge(SrcNId, DstNId);
473  }
474  }
475  return NewGraphPt;
476 }
477 
478 template<class PGraph>
479 PGraph GetRndSubGraph(const PGraph& Graph, const int& NNodes) {
480  IAssert(NNodes <= Graph->GetNodes());
481  TIntV NIdV;
482  Graph->GetNIdV(NIdV);
483  NIdV.Shuffle(TInt::Rnd);
484  NIdV.Del(NNodes, NIdV.Len()-1);
485  IAssert(NIdV.Len() == NNodes);
486  return GetSubGraph(Graph, NIdV);
487 }
488 
489 template<class PGraph>
490 PGraph GetRndESubGraph(const PGraph& Graph, const int& NEdges) {
491  CAssert(! HasGraphFlag(typename PGraph::TObj, gfMultiGraph));
492  TIntPrV EdgeV(Graph->GetEdges(), 0);
493  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
494  EdgeV.Add(TIntPr(EI.GetSrcNId(), EI.GetDstNId()));
495  }
496  EdgeV.Shuffle(TInt::Rnd);
497  EdgeV.Del(NEdges, EdgeV.Len()-1);
498  IAssert(EdgeV.Len() == NEdges);
499  return GetESubGraph(Graph, EdgeV);
500 }
501 
502 
503 // Egonet templatized functions
504 
505 template<class PGraph>
506 PGraph GetEgonetHop(const PGraph &Graph, const int CtrNId, const int Radius) {
507  PGraph NewGraphPt = PGraph::TObj::New();
508  typename PGraph::TObj& NewGraph = *NewGraphPt;
509  TSnapQueue<int> Queue1;
510  TSnapQueue<int> Queue2;
511  TSnapQueue<int> tempSwapQueue;
512  NewGraph.AddNode(CtrNId);
513  Queue1.Clr(false);
514  Queue1.Push(CtrNId);
515  for (int r = 0; r < Radius; ++r) {
516  while (!Queue1.Empty()) {
517  const int NId = Queue1.Top();
518  Queue1.Pop();
519  const typename PGraph::TObj::TNodeI &Node = Graph->GetNI(NId);
520  for (int i = 0; i < Node.GetInDeg(); ++i) {
521  const int InNId = Node.GetInNId(i);
522  if (!NewGraph.IsNode(InNId)) {
523  NewGraph.AddNode(InNId);
524  Queue2.Push(InNId);
525  }
526  if (!NewGraph.IsEdge(InNId, NId)) {
527  NewGraph.AddEdge(InNId, NId);
528  }
529  }
530  for (int i = 0; i < Node.GetOutDeg(); ++i) {
531  const int OutNId = Node.GetOutNId(i);
532  if (!NewGraph.IsNode(OutNId)) {
533  NewGraph.AddNode(OutNId);
534  Queue2.Push(OutNId);
535  }
536  if (!NewGraph.IsEdge(NId, OutNId)) {
537  NewGraph.AddEdge(NId, OutNId);
538  }
539  }
540  for (int i = 0; i < Node.GetInDeg(); ++i) {
541  int InNId = Node.GetInNId(i);
542  const typename PGraph::TObj::TNodeI &InNode = Graph->GetNI(InNId);
543  for (int j = 0; j < InNode.GetInDeg(); ++j) {
544  int NbrInNId = InNode.GetInNId(j);
545  if (NewGraph.IsNode(NbrInNId)) {
546  if (!NewGraph.IsEdge(NbrInNId, InNId)) {
547  NewGraph.AddEdge(NbrInNId, InNId);
548  }
549  }
550  }
551  for (int j = 0; j < InNode.GetOutDeg(); ++j) {
552  int NbrOutNId = InNode.GetOutNId(j);
553  if (NewGraph.IsNode(NbrOutNId)) {
554  if (!NewGraph.IsEdge(InNId, NbrOutNId)) {
555  NewGraph.AddEdge(InNId, NbrOutNId);
556  }
557  }
558  }
559  }
560  for (int i = 0; i < Node.GetOutDeg(); ++i) {
561  int OutNId = Node.GetOutNId(i);
562  const typename PGraph::TObj::TNodeI &OutNode = Graph->GetNI(OutNId);
563  for (int j = 0; j < OutNode.GetInDeg(); ++j) {
564  int NbrInNId = OutNode.GetInNId(j);
565  if (NewGraph.IsNode(NbrInNId)) {
566  if (!NewGraph.IsEdge(NbrInNId, OutNId)) {
567  NewGraph.AddEdge(NbrInNId, OutNId);
568  }
569  }
570  }
571  for (int j = 0; j < OutNode.GetOutDeg(); ++j) {
572  int NbrOutNId = OutNode.GetOutNId(j);
573  if (NewGraph.IsNode(NbrOutNId)) {
574  if (!NewGraph.IsEdge(OutNId, NbrOutNId)) {
575  NewGraph.AddEdge(OutNId, NbrOutNId);
576  }
577  }
578  }
579  }
580  }
581  tempSwapQueue = Queue1;
582  Queue1 = Queue2;
583  Queue2 = tempSwapQueue;
584  }
585  return NewGraphPt;
586 }
587 
588 template<class PGraph>
589 PGraph GetInEgonetHop(const PGraph &Graph, const int CtrNId, const int Radius) {
590  PGraph NewGraphPt = PGraph::TObj::New();
591  typename PGraph::TObj& NewGraph = *NewGraphPt;
592  TSnapQueue<int> Queue1;
593  TSnapQueue<int> Queue2;
594  TSnapQueue<int> tempSwapQueue;
595  NewGraph.AddNode(CtrNId);
596  Queue1.Clr(false);
597  Queue1.Push(CtrNId);
598  for (int r = 0; r < Radius; ++r) {
599  while (!Queue1.Empty()) {
600  const int NId = Queue1.Top();
601  Queue1.Pop();
602  const typename PGraph::TObj::TNodeI &Node = Graph->GetNI(NId);
603  for (int i = 0; i < Node.GetInDeg(); ++i) {
604  const int InNId = Node.GetInNId(i);
605  if (!NewGraph.IsNode(InNId)) {
606  NewGraph.AddNode(InNId);
607  Queue2.Push(InNId);
608  }
609  if (!NewGraph.IsEdge(InNId, NId)) {
610  NewGraph.AddEdge(InNId, NId);
611  }
612  }
613  for (int i = 0; i < Node.GetInDeg(); ++i) {
614  int InNId = Node.GetInNId(i);
615  const typename PGraph::TObj::TNodeI &InNode = Graph->GetNI(InNId);
616  for (int j = 0; j < InNode.GetInDeg(); ++j) {
617  int NbrInNId = InNode.GetInNId(j);
618  if (NewGraph.IsNode(NbrInNId)) {
619  if (!NewGraph.IsEdge(NbrInNId, InNId)) {
620  NewGraph.AddEdge(NbrInNId, InNId);
621  }
622  }
623  }
624  for (int j = 0; j < InNode.GetOutDeg(); ++j) {
625  int NbrOutNId = InNode.GetOutNId(j);
626  if (NewGraph.IsNode(NbrOutNId)) {
627  if (!NewGraph.IsEdge(InNId, NbrOutNId)) {
628  NewGraph.AddEdge(InNId, NbrOutNId);
629  }
630  }
631  }
632  }
633  }
634  tempSwapQueue = Queue1;
635  Queue1 = Queue2;
636  Queue2 = tempSwapQueue;
637  }
638  return NewGraphPt;
639 }
640 
641 template<class PGraph>
642 PGraph GetOutEgonetHop(const PGraph &Graph, const int CtrNId, const int Radius) {
643  PGraph NewGraphPt = PGraph::TObj::New();
644  typename PGraph::TObj& NewGraph = *NewGraphPt;
645  TSnapQueue<int> Queue1;
646  TSnapQueue<int> Queue2;
647  TSnapQueue<int> tempSwapQueue;
648  NewGraph.AddNode(CtrNId);
649  Queue1.Clr(false);
650  Queue1.Push(CtrNId);
651  for (int r = 0; r < Radius; ++r) {
652  while (!Queue1.Empty()) {
653  const int NId = Queue1.Top();
654  Queue1.Pop();
655  const typename PGraph::TObj::TNodeI &Node = Graph->GetNI(NId);
656  for (int i = 0; i < Node.GetOutDeg(); ++i) {
657  const int OutNId = Node.GetOutNId(i);
658  if (!NewGraph.IsNode(OutNId)) {
659  NewGraph.AddNode(OutNId);
660  Queue2.Push(OutNId);
661  }
662  if (!NewGraph.IsEdge(NId, OutNId)) {
663  NewGraph.AddEdge(NId, OutNId);
664  }
665  }
666  for (int i = 0; i < Node.GetOutDeg(); ++i) {
667  int OutNId = Node.GetOutNId(i);
668  const typename PGraph::TObj::TNodeI &OutNode = Graph->GetNI(OutNId);
669  for (int j = 0; j < OutNode.GetInDeg(); ++j) {
670  int NbrInNId = OutNode.GetInNId(j);
671  if (NewGraph.IsNode(NbrInNId)) {
672  if (!NewGraph.IsEdge(NbrInNId, OutNId)) {
673  NewGraph.AddEdge(NbrInNId, OutNId);
674  }
675  }
676  }
677  for (int j = 0; j < OutNode.GetOutDeg(); ++j) {
678  int NbrOutNId = OutNode.GetOutNId(j);
679  if (NewGraph.IsNode(NbrOutNId)) {
680  if (!NewGraph.IsEdge(OutNId, NbrOutNId)) {
681  NewGraph.AddEdge(OutNId, NbrOutNId);
682  }
683  }
684  }
685  }
686  }
687  tempSwapQueue = Queue1;
688  Queue1 = Queue2;
689  Queue2 = tempSwapQueue;
690  }
691  return NewGraphPt;
692 }
693 
694 template<class PGraph>
695 PGraph GetInEgonetSub(const PGraph &Graph, const int CtrNId, const int Radius, const int MaxNum, const float percent) {
696  PGraph NewGraphPt = PGraph::TObj::New();
697  typename PGraph::TObj& NewGraph = *NewGraphPt;
698  TSnapQueue<int> Queue1;
699  TSnapQueue<int> Queue2;
700  TSnapQueue<int> tempSwapQueue;
701  TSnapQueue<int> sampleQueue;
702  NewGraph.AddNode(CtrNId);
703  Queue1.Clr(false);
704  Queue1.Push(CtrNId);
705  bool usePercent = (percent != -1.0);
706  int numSamples = MaxNum;
707  for (int r = 0; r < Radius; ++r) {
708  while (!Queue1.Empty()) {
709  const int NId = Queue1.Top();
710  Queue1.Pop();
711  const typename PGraph::TObj::TNodeI &Node = Graph->GetNI(NId);
712  sampleQueue.Clr(true);
713  for (int i = 0; i < Node.GetInDeg(); ++i) {
714  const int InNId = Node.GetInNId(i);
715  if (!NewGraph.IsNode(InNId)) {
716  sampleQueue.Push(InNId);
717  }
718  }
719  if (usePercent) {
720  numSamples = (int) (percent * sampleQueue.Len());
721  }
722  sampleQueue.Sample(numSamples);
723  for (int i = 0; i < numSamples && !sampleQueue.Empty(); ++i) {
724  const int InNId = sampleQueue.Top();
725  sampleQueue.Pop();
726  if (!NewGraph.IsNode(InNId)) {
727  NewGraph.AddNode(InNId);
728  Queue2.Push(InNId);
729  }
730  if (!NewGraph.IsEdge(InNId, NId)) {
731  NewGraph.AddEdge(InNId, NId);
732  }
733  }
734  for (int i = 0; i < Node.GetInDeg(); ++i) {
735  int InNId = Node.GetInNId(i);
736  if (!NewGraph.IsNode(InNId)) { continue; }
737  const typename PGraph::TObj::TNodeI &InNode = Graph->GetNI(InNId);
738  for (int j = 0; j < InNode.GetInDeg(); ++j) {
739  int NbrInNId = InNode.GetInNId(j);
740  if (NewGraph.IsNode(NbrInNId)) {
741  if (!NewGraph.IsEdge(NbrInNId, InNId)) {
742  NewGraph.AddEdge(NbrInNId, InNId);
743  }
744  }
745  }
746  for (int j = 0; j < InNode.GetOutDeg(); ++j) {
747  int NbrOutNId = InNode.GetOutNId(j);
748  if (NewGraph.IsNode(NbrOutNId)) {
749  if (!NewGraph.IsEdge(InNId, NbrOutNId)) {
750  NewGraph.AddEdge(InNId, NbrOutNId);
751  }
752  }
753  }
754  }
755  }
756  tempSwapQueue = Queue1;
757  Queue1 = Queue2;
758  Queue2 = tempSwapQueue;
759  }
760  return NewGraphPt;
761 }
762 
763 template<class PGraph>
764 PGraph GetGraphUnion(PGraph& DstGraph, const PGraph& SrcGraph) {
765  for (typename PGraph::TObj::TNodeI NI = SrcGraph->BegNI(); NI < SrcGraph->EndNI(); NI++) {
766  if (! DstGraph->IsNode(NI.GetId())){
767  DstGraph->AddNode(NI.GetId());
768  }
769  }
770  for (typename PGraph::TObj::TEdgeI EI = SrcGraph->BegEI(); EI < SrcGraph->EndEI(); EI++) {
771  if (! HasGraphFlag(typename PGraph::TObj, gfMultiGraph)){
772  if (! DstGraph->IsEdge(EI.GetSrcNId(), EI.GetDstNId())){
773  DstGraph->AddEdge(EI.GetSrcNId(), EI.GetDstNId());
774  }
775  }
776  else{
777  if (! DstGraph->IsEdge(EI.GetSrcNId(), EI.GetDstNId()) || ! DstGraph->IsEdge(EI.GetId())){
778  if (! DstGraph->IsEdge(EI.GetId())){
779  DstGraph->AddEdge(EI.GetSrcNId(), EI.GetDstNId(), EI.GetId());
780  }else{
781  DstGraph->AddEdge(EI.GetSrcNId(), EI.GetDstNId());
782  }
783  }
784  }
785  }
786  return DstGraph;
787 }
788 
789 } // namespace TSnap
#define IAssert(Cond)
Definition: bd.h:262
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
Main namespace for all the Snap global entities.
Definition: alg.h:1
void Defrag()
Definition: shash.h:1366
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
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
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
PGraph GetEgonetHop(const PGraph &Graph, const int CtrNId, const int Radius)
Returns the egonet of node CtrNId as center for a Graph for a given radius.
Definition: subgraph.h:506
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static TRnd Rnd
Definition: dt.h:1146
PNEANet GetGraphUnionAttr(PNEANet &DstGraph, const PNEANet &SrcGraph)
Definition: subgraph.cpp:521
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
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
PGraph GetInEgonetSub(const PGraph &Graph, const int CtrNId, const int Radius, const int MaxNum=2, const float percent=-1.0)
Returns the randomly sampled in-egonet with nodes sampled based on percentage, if percent != -1...
Definition: subgraph.h:695
POutGraph ConvertSubGraph(const PInGraph &InGraph, const TIntV &NIdV, const bool &RenumberNodes=false)
Returns an induced subgraph of graph InGraph with NIdV nodes with an optional node renumbering...
Definition: subgraph.h:436
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
static PGraph Do(const PGraph &Graph, const TIntV &NIdV)
Definition: subgraph.h:181
network with data on edges
Definition: gbase.h:16
PGraph GetRndESubGraph(const PGraph &Graph, const int &NEdges)
Returns a random subgraph of graph Graph with NEdges edges.
Definition: subgraph.h:490
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
static POutGraph Do(const PInGraph &InGraph, const TIntV &NIdV, const bool &RenumberNodes)
Definition: subgraph.h:361
static PGraph Do(const PGraph &Graph, const TIntV &NIdV)
Definition: subgraph.h:200
int AddKey(const TKey &Key)
Definition: shash.h:1254
static POutGraph Do(const PInGraph &InGraph, const TIntV &NIdV, const bool &RenumberNodes)
Definition: subgraph.h:398
int Len() const
Returns the number of elements in the queue.
Definition: gbase.h:201
PGraph GetSubGraphRenumber(const PGraph &Graph, const TIntV &NIdV)
Returns an induced subgraph of graph Graph with NIdV nodes with an node renumbering.
Definition: subgraph.h:238
void Clr(const bool &DoDel=true)
Deletes all elements from the queue.
Definition: gbase.h:194
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
PGraph GetGraphUnion(PGraph &DstGraph, const PGraph &SrcGraph)
Definition: subgraph.h:764
#define CAssert(Cond)
Definition: bd.h:302
int Len() const
Definition: shash.h:1121
PGraph GetEDatSubGraph(const PGraph &Graph, const TEdgeDat &EDat, const int &Cmp)
Returns a subgraph of graph Graph with edges where edge data matches the parameters.
Definition: subgraph.h:286
void Sample(const int num, TRnd &Rnd=TInt::Rnd)
Definition: gbase.h:181
POutGraph ConvertESubGraph(const PInGraph &InGraph, const TIntV &EIdV, const bool &RenumberNodes=false)
Returns a subgraph of graph InGraph with EIdV edges with an optional node renumbering.
Definition: subgraph.h:441
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
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:209
Definition: bd.h:196
PGraph GetOutEgonetHop(const PGraph &Graph, const int CtrNId, const int Radius)
Returns the out-egonet of node CtrNId as center in directed graph Graph for a given radius...
Definition: subgraph.h:642
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
PGraph GetESubGraph(const PGraph &Graph, const TIntV &EIdV)
Returns a subgraph of graph Graph with EIdV edges.
Definition: subgraph.h:243
PGraph GetRndSubGraph(const PGraph &Graph, const int &NNodes)
Returns an induced random subgraph of graph Graph with NNodes nodes.
Definition: subgraph.h:479
network with data on nodes
Definition: gbase.h:15
PGraph GetInEgonetHop(const PGraph &Graph, const int CtrNId, const int Radius)
Returns the in-egonet of node CtrNId as center in directed graph Graph for a given radius...
Definition: subgraph.h:589
POutGraph ConvertGraph(const PInGraph &InGraph, const bool &RenumberNodes=false)
Performs conversion of graph InGraph with an optional node renumbering.
Definition: subgraph.h:326
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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