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.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 
28 PUNGraph GetSubGraph(const PUNGraph& Graph, const TIntV& NIdV, const bool& RenumberNodes=false);
29 // Returns an induced subgraph of a directed graph Graph with NIdV nodes with an optional node renumbering. ##TSnap::GetSubGraph-2
30 PNGraph GetSubGraph(const PNGraph& Graph, const TIntV& NIdV, const bool& RenumberNodes=false);
31 // TODO ROK 2012/08/15 PNGraph GetSubGraph is not documented by doxygen.
32 // It is combined with PUNGraph GetSubGraph.
33 
34 // edge subgraphs
36 
45 template<class PGraph> PGraph GetESubGraph(const PGraph& Graph, const TIntV& EIdV);
46 // Returns a subgraph of graph Graph with EdgeV edges. ##TSnap::GetESubGraph-1
47 template<class PGraph> PGraph GetESubGraph(const PGraph& Graph, const TIntPrV& EdgeV);
48 // TODO ROK 2012/08/15 PGraph GetESubGraph TIntPrV is not documented by doxygen.
49 // It is combined with PGraph GetESubGraph TIntV.
51 
64 template<class PGraph, class TEdgeDat> PGraph GetEDatSubGraph(const PGraph& Graph, const TEdgeDat& EDat, const int& Cmp);
66 
80 template<class PGraph, class TEdgeDat> PGraph GetEDatSubGraph(const PGraph& Graph, const TIntV& NIdV, const TEdgeDat& EDat, const int& Cmp);
81 
82 // convert between the graphs. Does NOT copy the data
84 
95 template<class POutGraph, class PInGraph> POutGraph ConvertGraph(const PInGraph& InGraph, const bool& RenumberNodes=false);
97 
108 template<class POutGraph, class PInGraph> POutGraph ConvertSubGraph(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes=false);
109 // TODO RS 2012/08/14 find out why TSnap::ConvertSubGraph<PUNGraph>(NGraph, NIdV, true) aborts
111 
122 template<class POutGraph, class PInGraph> POutGraph ConvertESubGraph(const PInGraph& InGraph, const TIntV& EIdV, const bool& RenumberNodes=false);
123 // does not work on multigraphs
124 
125 // get random (induced) subgraphs
127 
130 template<class PGraph> PGraph GetRndSubGraph(const PGraph& Graph, const int& NNodes);
132 
135 template<class PGraph> PGraph GetRndESubGraph(const PGraph& Graph, const int& NEdges);
136 
137 // get egonet of a center node
139 PUNGraph GetEgonet(const PUNGraph& Graph, const int CtrNId, int& ArndEdges);
141 PNGraph GetEgonet(const PNGraph& Graph, const int CtrNId, int& InEdges, int& OutEdges);
142 
144 // Implementation
145 namespace TSnapDetail {
146 // Slow for small sub-graphs as it traverses all the edges of Graph
147 template <class PGraph, bool IsMultiGraph>
148 struct TGetSubGraph {
149  static PGraph Do(const PGraph& Graph, const TIntV& NIdV) {
150  PGraph NewGraphPt = PGraph::TObj::New();
151  typename PGraph::TObj& NewGraph = *NewGraphPt;
152  NewGraph.Reserve(NIdV.Len(), -1);
153  for (int n = 0; n < NIdV.Len(); n++) {
154  if (Graph->IsNode(NIdV[n])) {
155  NewGraph.AddNode(Graph->GetNI(NIdV[n])); }
156  }
157  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
158  if (NewGraph.IsNode(EI.GetSrcNId()) && NewGraph.IsNode(EI.GetDstNId())) {
159  NewGraph.AddEdge(EI); }
160  }
161  NewGraph.Defrag();
162  return NewGraphPt;
163  }
164 };
165 
166 template <class PGraph>
167 struct TGetSubGraph<PGraph, false> { // not multigraph
168  static PGraph Do(const PGraph& Graph, const TIntV& NIdV) {
169  CAssert(! HasGraphFlag(typename PGraph::TObj, gfMultiGraph));
170  PGraph NewGraphPt = PGraph::TObj::New();
171  typename PGraph::TObj& NewGraph = *NewGraphPt;
172  NewGraph.Reserve(NIdV.Len(), -1);
173  TIntSet NodeSet;
174  for (int n = 0; n < NIdV.Len(); n++) {
175  if (! HasGraphFlag(typename PGraph::TObj, gfNodeDat)) {
176  if (Graph->IsNode(NIdV[n])) { NewGraph.AddNode(NIdV[n]); NodeSet.AddKey(NIdV[n]); } }
177  else {
178  if (Graph->IsNode(NIdV[n])) { NewGraph.AddNode(Graph->GetNI(NIdV[n])); NodeSet.AddKey(NIdV[n]); } }
179  }
180  for (int n = 0; n < NodeSet.Len(); n++) {
181  const int SrcNId = NodeSet[n];
182  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(SrcNId);
183  for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
184  const int OutNId = NI.GetOutNId(edge);
185  if (NewGraph.IsNode(OutNId)) {
186  if (! HasGraphFlag(typename PGraph::TObj, gfEdgeDat)) {
187  NewGraph.AddEdge(SrcNId, OutNId); }
188  else {
189  NewGraph.AddEdge(Graph->GetEI(SrcNId, OutNId)); } // also copy data
190  }
191  }
192  }
193  NewGraph.Defrag();
194  return NewGraphPt;
195  }
196 };
197 }; // TSnapDetail
198 
199 template<class PGraph>
200 PGraph GetSubGraph(const PGraph& Graph, const TIntV& NIdV) {
202  ::Do(Graph, NIdV);
203 }
204 
205 template<class PGraph>
206 PGraph GetESubGraph(const PGraph& Graph, const TIntV& EIdV) {
207  CAssert(HasGraphFlag(typename PGraph::TObj, gfMultiGraph));
208  PGraph NewGraphPt = PGraph::TObj::New();
209  typename PGraph::TObj& NewGraph = *NewGraphPt;
210  NewGraph.Reserve(-1, EIdV.Len());
211  for (int edge = 0; edge < EIdV.Len(); edge++) {
212  const int EId = EIdV[edge];
213  IAssert(Graph->IsEdge(EId));
214  const typename PGraph::TObj::TEdgeI EI = Graph->GetEI(EId);
215  if (! NewGraph.IsNode(EI.GetSrcNId())) {
216  NewGraph.AddNode(Graph->GetNI(EI.GetSrcNId()));
217  }
218  if (! NewGraph.IsNode(EI.GetDstNId())) {
219  NewGraph.AddNode(Graph->GetNI(EI.GetDstNId()));
220  }
221  NewGraph.AddEdge(EI);
222  }
223  return NewGraphPt;
224 }
225 
226 template<class PGraph>
227 PGraph GetESubGraph(const PGraph& Graph, const TIntPrV& EdgeV) {
228  PGraph NewGraphPt = PGraph::TObj::New();
229  typename PGraph::TObj& NewGraph = *NewGraphPt;
230  NewGraph.Reserve(-1, EdgeV.Len());
231  for (int edge = 0; edge < EdgeV.Len(); edge++) {
232  const int SrcNId = EdgeV[edge].Val1;
233  const int DstNId = EdgeV[edge].Val2;
234  const typename PGraph::TObj::TEdgeI EI = Graph->GetEI(SrcNId, DstNId);
235  if (! NewGraph.IsNode(EI.GetSrcNId())) {
236  NewGraph.AddNode(Graph->GetNI(EI.GetSrcNId()));
237  }
238  if (! NewGraph.IsNode(EI.GetDstNId())) {
239  NewGraph.AddNode(Graph->GetNI(EI.GetDstNId()));
240  }
241  NewGraph.AddEdge(EI);
242  }
243  return NewGraphPt;
244 }
245 
246 // Get a subgraph on NIdV nodes, where edge data is Cmp (-1:less, 0:equal, 1:greater) than EDat
247 template<class PGraph, class TEdgeDat>
248 PGraph GetEDatSubGraph(const PGraph& Graph, const TEdgeDat& EDat, const int& Cmp) {
249  CAssert(HasGraphFlag(typename PGraph::TObj, gfEdgeDat));
250  PGraph NewGraphPt = PGraph::TObj::New();
251  typename PGraph::TObj& NewGraph = *NewGraphPt;
252  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
253  if ((Cmp==1 && EI()>EDat) || (Cmp==-1 && EI()<EDat) || (Cmp==0 && EI()==EDat)) {
254  if (! NewGraph.IsNode(EI.GetSrcNId())) {
255  NewGraph.AddNode(Graph->GetNI(EI.GetSrcNId()));
256  }
257  if (! NewGraph.IsNode(EI.GetDstNId())) {
258  NewGraph.AddNode(Graph->GetNI(EI.GetDstNId()));
259  }
260  NewGraph.AddEdge(EI);
261  }
262  }
263  return NewGraphPt;
264 }
265 
266 // Get a subgraph on NIdV nodes, where edge data is Cmp (-1:less, 0:equal, 1:greater) than EDat
267 template<class PGraph, class TEdgeDat>
268 PGraph GetEDatSubGraph(const PGraph& Graph, const TIntV& NIdV, const TEdgeDat& EDat, const int& Cmp) {
269  CAssert(HasGraphFlag(typename PGraph::TObj, gfEdgeDat));
270  PGraph NewGraphPt = PGraph::TObj::New();
271  typename PGraph::TObj& NewGraph = *NewGraphPt;
272  NewGraph.Reserve(NIdV.Len(), -1);
273  for (int n = 0; n < NIdV.Len(); n++) {
274  NewGraph.AddNode(Graph->GetNI(NIdV[n]));
275  }
276  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
277  if (NewGraph.IsNode(EI.GetSrcNId()) && NewGraph.IsNode(EI.GetDstNId()) &&
278  ((Cmp==1 && EI()>EDat)|| (Cmp==-1 && EI()<EDat) || (Cmp==0 && EI()==EDat))) {
279  NewGraph.AddEdge(EI); }
280  }
281  NewGraph.Defrag();
282  return NewGraphPt;
283 }
284 
285 // Converts between different types of graphs/networks
286 // Node/edge data is not copied between the graphs.
287 template<class POutGraph, class PInGraph>
288 POutGraph ConvertGraph(const PInGraph& InGraph, const bool& RenumberNodes) {
289  POutGraph OutGraphPt = POutGraph::TObj::New();
290  typename POutGraph::TObj& OutGraph = *OutGraphPt;
291  OutGraph.Reserve(InGraph->GetNodes(), InGraph->GetEdges());
292  if (! RenumberNodes) {
293  for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
294  OutGraph.AddNode(NI.GetId());
295  }
296  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
297  OutGraph.AddEdge(EI.GetSrcNId(), EI.GetDstNId());
298  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) { // add edge in the other direction
299  OutGraph.AddEdge(EI.GetDstNId(), EI.GetSrcNId()); }
300  }
301  } else { // renumber nodes so that node ids are 0...N-1
302  TIntSet NIdSet(InGraph->GetNodes());
303  for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
304  const int nid = NIdSet.AddKey(NI.GetId());
305  OutGraph.AddNode(nid);
306  }
307  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
308  const int SrcNId = NIdSet.GetKeyId(EI.GetSrcNId());
309  const int DstNId = NIdSet.GetKeyId(EI.GetDstNId());
310  OutGraph.AddEdge(SrcNId, DstNId);
311  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
312  OutGraph.AddEdge(DstNId, SrcNId); }
313  }
314  }
315  //OutGraph.Defrag();
316  return OutGraphPt;
317 }
318 
319 namespace TSnapDetail {
320 // Slow for small sub-graphs as it traverses all the edges of Graph
321 template <class POutGraph, class PInGraph, bool IsMultiGraph>
323  static POutGraph Do(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes) {
324  POutGraph OutGraphPt = POutGraph::TObj::New();
325  typename POutGraph::TObj& OutGraph = *OutGraphPt;
326  if (! RenumberNodes) {
327  for (int n = 0; n < NIdV.Len(); n++) {
328  OutGraph.AddNode(NIdV[n]);
329  }
330  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
331  if (! OutGraph.IsNode(EI.GetSrcNId()) || ! OutGraph.IsNode(EI.GetDstNId())) { continue; }
332  OutGraph.AddEdge(EI.GetSrcNId(), EI.GetDstNId());
333  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
334  OutGraph.AddEdge(EI.GetDstNId(), EI.GetSrcNId());
335  }
336  }
337  } else { // renumber nodes so that node ids are 0...N-1
338  TIntSet NIdSet(InGraph->GetNodes());
339  for (int n = 0; n < NIdV.Len(); n++) {
340  const int NId = NIdSet.AddKey(NIdV[n]);
341  OutGraph.AddNode(NId);
342  }
343  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
344  const int SrcNId = NIdSet.GetKeyId(EI.GetSrcNId());
345  const int DstNId = NIdSet.GetKeyId(EI.GetDstNId());
346  if (! OutGraph.IsNode(SrcNId) || ! OutGraph.IsNode(DstNId)) { continue; }
347  OutGraph.AddEdge(SrcNId, DstNId);
348  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
349  OutGraph.AddEdge(DstNId, SrcNId);
350  }
351  }
352  }
353  OutGraph.Defrag();
354  return OutGraphPt;
355  }
356 };
357 
358 template <class POutGraph, class PInGraph>
359 struct TConvertSubGraph<POutGraph, PInGraph, false> { // InGraph is not multigraph
360  static POutGraph Do(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes) {
361  POutGraph OutGraphPt = POutGraph::TObj::New();
362  typename POutGraph::TObj& OutGraph = *OutGraphPt;
363  if (! RenumberNodes) {
364  for (int n = 0; n < NIdV.Len(); n++) {
365  OutGraph.AddNode(NIdV[n]); }
366  for (int n = 0; n < NIdV.Len(); n++) {
367  typename PInGraph::TObj::TNodeI NI = InGraph->GetNI(NIdV[n]);
368  for (int e = 0; e < NI.GetOutDeg(); e++) {
369  const int dst = NI.GetOutNId(e);
370  if (! OutGraph.IsNode(dst)) { continue; }
371  OutGraph.AddEdge(NIdV[n], dst);
372  }
373  }
374  } else { // renumber nodes so that node ids are 0...N-1
375  TIntSet NIdSet(InGraph->GetNodes());
376  for (int n = 0; n < NIdV.Len(); n++) {
377  const int NId = NIdSet.AddKey(NIdV[n]);
378  OutGraph.AddNode(NId);
379  }
380  for (int n = 0; n < NIdV.Len(); n++) {
381  typename PInGraph::TObj::TNodeI NI = InGraph->GetNI(NIdV[n]);
382  const int src = NIdSet.GetKey(NIdV[n]);
383  for (int e = 0; e < NI.GetOutDeg(); e++) {
384  const int dst = NIdSet.GetKey(NI.GetOutNId(e));
385  if (! OutGraph.IsNode(dst)) { continue; }
386  OutGraph.AddEdge(src, dst);
387  }
388  }
389  }
390  OutGraph.Defrag();
391  return OutGraphPt;
392  }
393 };
394 } // TSnapDetail
395 
396 // May be slow as it traverses all the edges of the in-graph to create the sub-graph
397 template<class POutGraph, class PInGraph>
398 POutGraph ConvertSubGraph(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes) {
400 }
401 
402 template<class POutGraph, class PInGraph>
403 POutGraph ConvertESubGraph(const PInGraph& InGraph, const TIntV& EIdV, const bool& RenumberNodes) {
404  CAssert(HasGraphFlag(typename PInGraph::TObj, gfMultiGraph)); // needs to have explicit edges
405  POutGraph NewGraphPt = POutGraph::TObj::New();
406  typename POutGraph::TObj& NewGraph = *NewGraphPt;
407  NewGraph.Reserve(-1, EIdV.Len());
408  if (! RenumberNodes) {
409  for (int edge = 0; edge < EIdV.Len(); edge++) {
410  const int EId = EIdV[edge];
411  IAssert(InGraph->IsEdge(EId));
412  const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
413  const int SrcNId = EI.GetSrcNId();
414  const int DstNId = EI.GetDstNId();
415  if (! NewGraph.IsNode(SrcNId)) {
416  NewGraph.AddNode(SrcNId); }
417  if (! NewGraph.IsNode(DstNId)) {
418  NewGraph.AddNode(DstNId); }
419  NewGraph.AddEdge(SrcNId, DstNId);
420  }
421  } else {
422  // renumber nodes so that node ids are 0...N-1
423  TIntSet NIdSet(InGraph->GetNodes());
424  for (int edge = 0; edge < EIdV.Len(); edge++) {
425  const int EId = EIdV[edge];
426  IAssert(InGraph->IsEdge(EId));
427  const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
428  const int SrcNId = NIdSet.AddKey(EI.GetSrcNId()); // map node ids
429  const int DstNId = NIdSet.AddKey(EI.GetDstNId());
430  if (! NewGraph.IsNode(SrcNId)) {
431  NewGraph.AddNode(SrcNId); }
432  if (! NewGraph.IsNode(DstNId)) {
433  NewGraph.AddNode(DstNId); }
434  NewGraph.AddEdge(SrcNId, DstNId);
435  }
436  }
437  return NewGraphPt;
438 }
439 
440 template<class PGraph>
441 PGraph GetRndSubGraph(const PGraph& Graph, const int& NNodes) {
442  IAssert(NNodes <= Graph->GetNodes());
443  TIntV NIdV;
444  Graph->GetNIdV(NIdV);
445  NIdV.Shuffle(TInt::Rnd);
446  NIdV.Del(NNodes, NIdV.Len()-1);
447  IAssert(NIdV.Len() == NNodes);
448  return GetSubGraph(Graph, NIdV);
449 }
450 
451 template<class PGraph>
452 PGraph GetRndESubGraph(const PGraph& Graph, const int& NEdges) {
453  CAssert(! HasGraphFlag(typename PGraph::TObj, gfMultiGraph));
454  TIntPrV EdgeV(Graph->GetEdges(), 0);
455  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
456  EdgeV.Add(TIntPr(EI.GetSrcNId(), EI.GetDstNId()));
457  }
458  EdgeV.Shuffle(TInt::Rnd);
459  EdgeV.Del(NEdges, EdgeV.Len()-1);
460  IAssert(EdgeV.Len() == NEdges);
461  return GetESubGraph(Graph, EdgeV);
462 }
463 
464 } // namespace TSnap
#define IAssert(Cond)
Definition: bd.h:262
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
void Defrag()
Definition: shash.h:1366
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
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
static TRnd Rnd
Definition: dt.h:1143
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
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:398
#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:149
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:452
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:323
static PGraph Do(const PGraph &Graph, const TIntV &NIdV)
Definition: subgraph.h:168
int AddKey(const TKey &Key)
Definition: shash.h:1254
static POutGraph Do(const PInGraph &InGraph, const TIntV &NIdV, const bool &RenumberNodes)
Definition: subgraph.h:360
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
#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:248
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:403
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
Definition: bd.h:196
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:206
PGraph GetRndSubGraph(const PGraph &Graph, const int &NNodes)
Returns an induced random subgraph of graph Graph with NNodes nodes.
Definition: subgraph.h:441
network with data on nodes
Definition: gbase.h:15
POutGraph ConvertGraph(const PInGraph &InGraph, const bool &RenumberNodes=false)
Performs conversion of graph InGraph with an optional node renumbering.
Definition: subgraph.h:288
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602