SNAP Library 4.0, Developer 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
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 } // namespace TSnap
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:416
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
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
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
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
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:298
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
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:542
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 GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:398
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
Directed graph.
Definition: graph.h:342
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:106
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
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:379
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:606
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
Definition: bd.h:196
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:400
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:408
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412
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