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
graph.cpp
Go to the documentation of this file.
1 // Undirected Graph
3 bool TUNGraph::HasFlag(const TGraphFlag& Flag) const {
4  return HasGraphFlag(TUNGraph::TNet, Flag);
5 }
6 
7 // Add a node of ID NId to the graph.
8 int TUNGraph::AddNode(int NId) {
9  if (NId == -1) {
10  NId = MxNId; MxNId++;
11  } else {
12  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
13  MxNId = TMath::Mx(NId+1, MxNId());
14  }
15  NodeH.AddDat(NId, TNode(NId));
16  return NId;
17 }
18 
19 // Add a node of ID NId to the graph.
21  if (IsNode(NId)) { return -1;}
22  MxNId = TMath::Mx(NId+1, MxNId());
23  NodeH.AddDat(NId, TNode(NId));
24  return NId;
25 }
26 
27 // Add a node of ID NId to the graph and create edges to all nodes in vector NbrNIdV.
28 int TUNGraph::AddNode(const int& NId, const TIntV& NbrNIdV) {
29  int NewNId;
30  if (NId == -1) {
31  NewNId = MxNId; MxNId++;
32  } else {
33  IAssertR(! IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
34  NewNId = NId;
35  MxNId = TMath::Mx(NewNId+1, MxNId());
36  }
37  TNode& Node = NodeH.AddDat(NewNId);
38  Node.Id = NewNId;
39  Node.NIdV = NbrNIdV;
40  Node.NIdV.Sort();
41  NEdges += Node.GetDeg();
42  for (int i = 0; i < NbrNIdV.Len(); i++) {
43  GetNode(NbrNIdV[i]).NIdV.AddSorted(NewNId);
44  }
45  return NewNId;
46 }
47 
48 // Add a node of ID NId to the graph and create edges to all nodes in the vector NIdVId in the vector pool Pool).
49 int TUNGraph::AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& NIdVId) {
50  int NewNId;
51  if (NId == -1) {
52  NewNId = MxNId; MxNId++;
53  } else {
54  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
55  NewNId = NId;
56  MxNId = TMath::Mx(NewNId+1, MxNId());
57  }
58  TNode& Node = NodeH.AddDat(NewNId);
59  Node.Id = NewNId;
60  Node.NIdV.GenExt(Pool.GetValVPt(NIdVId), Pool.GetVLen(NIdVId));
61  Node.NIdV.Sort();
62  NEdges += Node.GetDeg();
63  return NewNId;
64 }
65 
66 // Delete node of ID NId from the graph.
67 void TUNGraph::DelNode(const int& NId) {
68  { AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
69  TNode& Node = GetNode(NId);
70  NEdges -= Node.GetDeg();
71  for (int e = 0; e < Node.GetDeg(); e++) {
72  const int nbr = Node.GetNbrNId(e);
73  if (nbr == NId) { continue; }
74  TNode& N = GetNode(nbr);
75  const int n = N.NIdV.SearchBin(NId);
76  IAssert(n != -1); // if NId points to N, then N also should point back
77  if (n!= -1) { N.NIdV.Del(n); }
78  } }
79  NodeH.DelKey(NId);
80 }
81 
82 int TUNGraph::GetEdges() const {
83  //int Edges = 0;
84  //for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
85  // Edges += NodeH[N].GetDeg();
86  //}
87  //return Edges/2;
88  return NEdges;
89 }
90 
91 // Add an edge between SrcNId and DstNId to the graph.
92 int TUNGraph::AddEdge(const int& SrcNId, const int& DstNId) {
93  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
94  if (IsEdge(SrcNId, DstNId)) { return -2; } // edge already exists
95  GetNode(SrcNId).NIdV.AddSorted(DstNId);
96  if (SrcNId!=DstNId) { // not a self edge
97  GetNode(DstNId).NIdV.AddSorted(SrcNId); }
98  NEdges++;
99  return -1; // no edge id
100 }
101 
102 // Add an edge between SrcNId and DstNId to the graph.
103 int TUNGraph::AddEdgeUnchecked(const int& SrcNId, const int& DstNId) {
104  GetNode(SrcNId).NIdV.Add(DstNId);
105  if (SrcNId!=DstNId) { // not a self edge
106  GetNode(DstNId).NIdV.Add(SrcNId); }
107  NEdges++;
108  return -1; // no edge id
109 }
110 
111 // Add an edge between SrcNId and DstNId to the graph and create the nodes if they don't yet exist.
112 int TUNGraph::AddEdge2(const int& SrcNId, const int& DstNId) {
113  if (! IsNode(SrcNId)) { AddNode(SrcNId); }
114  if (! IsNode(DstNId)) { AddNode(DstNId); }
115  if (GetNode(SrcNId).IsNbrNId(DstNId)) { return -2; } // edge already exists
116  GetNode(SrcNId).NIdV.AddSorted(DstNId);
117  if (SrcNId!=DstNId) { // not a self edge
118  GetNode(DstNId).NIdV.AddSorted(SrcNId); }
119  NEdges++;
120  return -1; // no edge id
121 }
122 
123 // Delete an edge between node IDs SrcNId and DstNId from the graph.
124 void TUNGraph::DelEdge(const int& SrcNId, const int& DstNId) {
125  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
126  { TNode& N = GetNode(SrcNId);
127  const int n = N.NIdV.SearchBin(DstNId);
128  if (n!= -1) { N.NIdV.Del(n); NEdges--; } }
129  if (SrcNId != DstNId) { // not a self edge
130  TNode& N = GetNode(DstNId);
131  const int n = N.NIdV.SearchBin(SrcNId);
132  if (n!= -1) { N.NIdV.Del(n); }
133  }
134 }
135 
136 // Test whether an edge between node IDs SrcNId and DstNId exists the graph.
137 bool TUNGraph::IsEdge(const int& SrcNId, const int& DstNId) const {
138  if (! IsNode(SrcNId) || ! IsNode(DstNId)) return false;
139  return GetNode(SrcNId).IsNbrNId(DstNId);
140 }
141 
142 // Return an iterator referring to edge (SrcNId, DstNId) in the graph.
143 TUNGraph::TEdgeI TUNGraph::GetEI(const int& SrcNId, const int& DstNId) const {
144  const int MnNId = TMath::Mn(SrcNId, DstNId);
145  const int MxNId = TMath::Mx(SrcNId, DstNId);
146  const TNodeI SrcNI = GetNI(MnNId);
147  const int NodeN = SrcNI.NodeHI.GetDat().NIdV.SearchBin(MxNId);
148  IAssert(NodeN != -1);
149  return TEdgeI(SrcNI, EndNI(), NodeN);
150 }
151 
152 // Get a vector IDs of all nodes in the graph.
153 void TUNGraph::GetNIdV(TIntV& NIdV) const {
154  NIdV.Gen(GetNodes(), 0);
155  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
156  NIdV.Add(NodeH.GetKey(N)); }
157 }
158 
159 // Defragment the graph.
160 void TUNGraph::Defrag(const bool& OnlyNodeLinks) {
161  for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
162  NodeH[n].NIdV.Pack();
163  }
164  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
165  NodeH.Defrag();
166  }
167 }
168 
169 // Check the graph data structure for internal consistency.
170 bool TUNGraph::IsOk(const bool& ThrowExcept) const {
171  bool RetVal = true;
172  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
173  const TNode& Node = NodeH[N];
174  if (! Node.NIdV.IsSorted()) {
175  const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", Node.GetId());
176  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
177  RetVal=false;
178  }
179  int prevNId = -1;
180  for (int e = 0; e < Node.GetDeg(); e++) {
181  if (! IsNode(Node.GetNbrNId(e))) {
182  const TStr Msg = TStr::Fmt("Edge %d --> %d: node %d does not exist.",
183  Node.GetId(), Node.GetNbrNId(e), Node.GetNbrNId(e));
184  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
185  RetVal=false;
186  }
187  if (e > 0 && prevNId == Node.GetNbrNId(e)) {
188  const TStr Msg = TStr::Fmt("Node %d has duplicate edge %d --> %d.",
189  Node.GetId(), Node.GetId(), Node.GetNbrNId(e));
190  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
191  RetVal=false;
192  }
193  prevNId = Node.GetNbrNId(e);
194  }
195  }
196  int EdgeCnt = 0;
197  for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) { EdgeCnt++; }
198  if (EdgeCnt != GetEdges()) {
199  const TStr Msg = TStr::Fmt("Number of edges counter is corrupted: GetEdges():%d, EdgeCount:%d.", GetEdges(), EdgeCnt);
200  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
201  RetVal=false;
202  }
203  return RetVal;
204 }
205 
206 // Print the graph in a human readable form to an output stream OutF.
207 void TUNGraph::Dump(FILE *OutF) const {
208  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
209  fprintf(OutF, "-------------------------------------------------\nUndirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
210  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
211  const TNode& Node = NodeH[N];
212  fprintf(OutF, " %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
213  for (int edge = 0; edge < Node.GetDeg(); edge++) {
214  fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
215  fprintf(OutF, "\n");
216  }
217  fprintf(OutF, "\n");
218 }
219 
220 // Return a small graph on 5 nodes and 5 edges.
222  PUNGraph Graph = TUNGraph::New();
223  for (int i = 0; i < 5; i++) { Graph->AddNode(i); }
224  Graph->AddEdge(0,1); Graph->AddEdge(0,2);
225  Graph->AddEdge(0,3); Graph->AddEdge(0,4);
226  Graph->AddEdge(1,2);
227  return Graph;
228 }
229 
231 // Directed Node Graph
232 bool TNGraph::HasFlag(const TGraphFlag& Flag) const {
233  return HasGraphFlag(TNGraph::TNet, Flag);
234 }
235 
236 int TNGraph::AddNode(int NId) {
237  if (NId == -1) {
238  NId = MxNId; MxNId++;
239  } else {
240  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
241  MxNId = TMath::Mx(NId+1, MxNId());
242  }
243  NodeH.AddDat(NId, TNode(NId));
244  return NId;
245 }
246 
248  if (IsNode(NId)) { return NId;}
249  MxNId = TMath::Mx(NId+1, MxNId());
250  NodeH.AddDat(NId, TNode(NId));
251  return NId;
252 }
253 
254 // add a node with a list of neighbors
255 // (use TNGraph::IsOk to check whether the graph is consistent)
256 int TNGraph::AddNode(const int& NId, const TIntV& InNIdV, const TIntV& OutNIdV) {
257  int NewNId;
258  if (NId == -1) {
259  NewNId = MxNId; MxNId++;
260  } else {
261  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
262  NewNId = NId;
263  MxNId = TMath::Mx(NewNId+1, MxNId());
264  }
265  TNode& Node = NodeH.AddDat(NewNId);
266  Node.Id = NewNId;
267  Node.InNIdV = InNIdV;
268  Node.OutNIdV = OutNIdV;
269  Node.InNIdV.Sort();
270  Node.OutNIdV.Sort();
271  return NewNId;
272 }
273 
274 // add a node from a vector pool
275 // (use TNGraph::IsOk to check whether the graph is consistent)
276 int TNGraph::AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& SrcVId, const int& DstVId) {
277  int NewNId;
278  if (NId == -1) {
279  NewNId = MxNId; MxNId++;
280  } else {
281  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
282  NewNId = NId;
283  MxNId = TMath::Mx(NewNId+1, MxNId());
284  }
285  TNode& Node = NodeH.AddDat(NewNId);
286  Node.Id = NewNId;
287  Node.InNIdV.GenExt(Pool.GetValVPt(SrcVId), Pool.GetVLen(SrcVId));
288  Node.OutNIdV.GenExt(Pool.GetValVPt(DstVId), Pool.GetVLen(DstVId));
289  Node.InNIdV.Sort();
290  Node.OutNIdV.Sort();
291  return NewNId;
292 }
293 
294 void TNGraph::DelNode(const int& NId) {
295  { TNode& Node = GetNode(NId);
296  for (int e = 0; e < Node.GetOutDeg(); e++) {
297  const int nbr = Node.GetOutNId(e);
298  if (nbr == NId) { continue; }
299  TNode& N = GetNode(nbr);
300  const int n = N.InNIdV.SearchBin(NId);
301  if (n!= -1) { N.InNIdV.Del(n); }
302  }
303  for (int e = 0; e < Node.GetInDeg(); e++) {
304  const int nbr = Node.GetInNId(e);
305  if (nbr == NId) { continue; }
306  TNode& N = GetNode(nbr);
307  const int n = N.OutNIdV.SearchBin(NId);
308  if (n!= -1) { N.OutNIdV.Del(n); }
309  } }
310  NodeH.DelKey(NId);
311 }
312 
313 int TNGraph::GetEdges() const {
314  int edges=0;
315  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
316  edges+=NodeH[N].GetOutDeg();
317  }
318  return edges;
319 }
320 
321 int TNGraph::AddEdge(const int& SrcNId, const int& DstNId) {
322  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
323  //IAssert(! IsEdge(SrcNId, DstNId));
324  if (IsEdge(SrcNId, DstNId)) { return -2; }
325  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
326  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
327  return -1; // no edge id
328 }
329 
330 int TNGraph::AddEdgeUnchecked(const int& SrcNId, const int& DstNId) {
331  GetNode(SrcNId).OutNIdV.Add(DstNId);
332  GetNode(DstNId).InNIdV.Add(SrcNId);
333  return -1; // no edge id
334 }
335 
336 int TNGraph::AddEdge2(const int& SrcNId, const int& DstNId) {
337  if (! IsNode(SrcNId)) { AddNode(SrcNId); }
338  if (! IsNode(DstNId)) { AddNode(DstNId); }
339  if (GetNode(SrcNId).IsOutNId(DstNId)) { return -2; } // edge already exists
340  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
341  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
342  return -1; // no edge id
343 }
344 
345 void TNGraph::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) {
346  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
347  { TNode& N = GetNode(SrcNId);
348  const int n = N.OutNIdV.SearchBin(DstNId);
349  if (n!= -1) { N.OutNIdV.Del(n); } }
350  { TNode& N = GetNode(DstNId);
351  const int n = N.InNIdV.SearchBin(SrcNId);
352  if (n!= -1) { N.InNIdV.Del(n); } }
353  if (! IsDir) {
354  { TNode& N = GetNode(SrcNId);
355  const int n = N.InNIdV.SearchBin(DstNId);
356  if (n!= -1) { N.InNIdV.Del(n); } }
357  { TNode& N = GetNode(DstNId);
358  const int n = N.OutNIdV.SearchBin(SrcNId);
359  if (n!= -1) { N.OutNIdV.Del(n); } }
360  }
361 }
362 
363 bool TNGraph::IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) const {
364  if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
365  if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
366  else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
367 }
368 
369 TNGraph::TEdgeI TNGraph::GetEI(const int& SrcNId, const int& DstNId) const {
370  const TNodeI SrcNI = GetNI(SrcNId);
371  const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
372  IAssert(NodeN != -1);
373  return TEdgeI(SrcNI, EndNI(), NodeN);
374 }
375 
376 void TNGraph::GetNIdV(TIntV& NIdV) const {
377  NIdV.Gen(GetNodes(), 0);
378  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
379  NIdV.Add(NodeH.GetKey(N)); }
380 }
381 
382 void TNGraph::Defrag(const bool& OnlyNodeLinks) {
383  for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
384  TNode& Node = NodeH[n];
385  Node.InNIdV.Pack(); Node.OutNIdV.Pack();
386  }
387  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); }
388 }
389 
390 // for each node check that their neighbors are also nodes
391 bool TNGraph::IsOk(const bool& ThrowExcept) const {
392  bool RetVal = true;
393  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
394  const TNode& Node = NodeH[N];
395  if (! Node.OutNIdV.IsSorted()) {
396  const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId());
397  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
398  }
399  if (! Node.InNIdV.IsSorted()) {
400  const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId());
401  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
402  }
403  // check out-edges
404  int prevNId = -1;
405  for (int e = 0; e < Node.GetOutDeg(); e++) {
406  if (! IsNode(Node.GetOutNId(e))) {
407  const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.",
408  Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e));
409  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
410  }
411  if (e > 0 && prevNId == Node.GetOutNId(e)) {
412  const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.",
413  Node.GetId(), Node.GetId(), Node.GetOutNId(e));
414  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
415  }
416  prevNId = Node.GetOutNId(e);
417  }
418  // check in-edges
419  prevNId = -1;
420  for (int e = 0; e < Node.GetInDeg(); e++) {
421  if (! IsNode(Node.GetInNId(e))) {
422  const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.",
423  Node.GetId(), Node.GetInNId(e), Node.GetInNId(e));
424  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
425  }
426  if (e > 0 && prevNId == Node.GetInNId(e)) {
427  const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.",
428  Node.GetId(), Node.GetId(), Node.GetInNId(e));
429  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
430  }
431  prevNId = Node.GetInNId(e);
432  }
433  }
434  return RetVal;
435 }
436 
437 void TNGraph::Dump(FILE *OutF) const {
438  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
439  fprintf(OutF, "-------------------------------------------------\nDirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
440  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
441  const TNode& Node = NodeH[N];
442  fprintf(OutF, " %*d]\n", NodePlaces, Node.GetId());
443  fprintf(OutF, " in [%d]", Node.GetInDeg());
444  for (int edge = 0; edge < Node.GetInDeg(); edge++) {
445  fprintf(OutF, " %*d", NodePlaces, Node.GetInNId(edge)); }
446  fprintf(OutF, "\n out[%d]", Node.GetOutDeg());
447  for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
448  fprintf(OutF, " %*d", NodePlaces, Node.GetOutNId(edge)); }
449  fprintf(OutF, "\n");
450  }
451  fprintf(OutF, "\n");
452 }
453 
455  PNGraph G = TNGraph::New();
456  for (int i = 0; i < 5; i++) { G->AddNode(i); }
457  G->AddEdge(0,1); G->AddEdge(1,2); G->AddEdge(0,2);
458  G->AddEdge(1,3); G->AddEdge(3,4); G->AddEdge(2,3);
459  return G;
460 }
461 
463 // Node Edge Graph
464 bool TNEGraph::HasFlag(const TGraphFlag& Flag) const {
465  return HasGraphFlag(TNEGraph::TNet, Flag);
466 }
467 
468 bool TNEGraph::TNodeI::IsInNId(const int& NId) const {
469  const TNode& Node = NodeHI.GetDat();
470  for (int edge = 0; edge < Node.GetInDeg(); edge++) {
471  if (NId == Graph->GetEdge(Node.GetInEId(edge)).GetSrcNId())
472  return true;
473  }
474  return false;
475 }
476 
477 bool TNEGraph::TNodeI::IsOutNId(const int& NId) const {
478  const TNode& Node = NodeHI.GetDat();
479  for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
480  if (NId == Graph->GetEdge(Node.GetOutEId(edge)).GetDstNId())
481  return true;
482  }
483  return false;
484 }
485 
486 int TNEGraph::AddNode(int NId) {
487  if (NId == -1) {
488  NId = MxNId; MxNId++;
489  } else {
490  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
491  MxNId = TMath::Mx(NId+1, MxNId());
492  }
493  NodeH.AddDat(NId, TNode(NId));
494  return NId;
495 }
496 
497 void TNEGraph::DelNode(const int& NId) {
498  const TNode& Node = GetNode(NId);
499  for (int out = 0; out < Node.GetOutDeg(); out++) {
500  const int EId = Node.GetOutEId(out);
501  const TEdge& Edge = GetEdge(EId);
502  IAssert(Edge.GetSrcNId() == NId);
503  GetNode(Edge.GetDstNId()).InEIdV.DelIfIn(EId);
504  EdgeH.DelKey(EId);
505  }
506  for (int in = 0; in < Node.GetInDeg(); in++) {
507  const int EId = Node.GetInEId(in);
508  const TEdge& Edge = GetEdge(EId);
509  IAssert(Edge.GetDstNId() == NId);
510  GetNode(Edge.GetSrcNId()).OutEIdV.DelIfIn(EId);
511  EdgeH.DelKey(EId);
512  }
513  NodeH.DelKey(NId);
514 }
515 
516 int TNEGraph::AddEdge(const int& SrcNId, const int& DstNId, int EId) {
517  if (EId == -1) { EId = MxEId; MxEId++; }
518  else { MxEId = TMath::Mx(EId+1, MxEId()); }
519  IAssertR(!IsEdge(EId), TStr::Fmt("EdgeId %d already exists", EId));
520  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
521  EdgeH.AddDat(EId, TEdge(EId, SrcNId, DstNId));
522  GetNode(SrcNId).OutEIdV.AddSorted(EId);
523  GetNode(DstNId).InEIdV.AddSorted(EId);
524  return EId;
525 }
526 
527 void TNEGraph::DelEdge(const int& EId) {
528  IAssert(IsEdge(EId));
529  const int SrcNId = GetEdge(EId).GetSrcNId();
530  const int DstNId = GetEdge(EId).GetDstNId();
531  GetNode(SrcNId).OutEIdV.DelIfIn(EId);
532  GetNode(DstNId).InEIdV.DelIfIn(EId);
533  EdgeH.DelKey(EId);
534 }
535 
536 // delete all edges between the two nodes
537 void TNEGraph::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) {
538  int EId;
539  IAssert(IsEdge(SrcNId, DstNId, EId, IsDir)); // there is at least one edge
540  while (IsEdge(SrcNId, DstNId, EId, IsDir)) {
541  GetNode(SrcNId).OutEIdV.DelIfIn(EId);
542  GetNode(DstNId).InEIdV.DelIfIn(EId);
543  }
544  EdgeH.DelKey(EId);
545 }
546 
547 bool TNEGraph::IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir) const {
548  const TNode& SrcNode = GetNode(SrcNId);
549  for (int edge = 0; edge < SrcNode.GetOutDeg(); edge++) {
550  const TEdge& Edge = GetEdge(SrcNode.GetOutEId(edge));
551  if (DstNId == Edge.GetDstNId()) {
552  EId = Edge.GetId(); return true; }
553  }
554  if (! IsDir) {
555  for (int edge = 0; edge < SrcNode.GetInDeg(); edge++) {
556  const TEdge& Edge = GetEdge(SrcNode.GetInEId(edge));
557  if (DstNId == Edge.GetSrcNId()) {
558  EId = Edge.GetId(); return true; }
559  }
560  }
561  return false;
562 }
563 
564 void TNEGraph::GetNIdV(TIntV& NIdV) const {
565  NIdV.Gen(GetNodes(), 0);
566  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
567  NIdV.Add(NodeH.GetKey(N)); }
568 }
569 
570 void TNEGraph::GetEIdV(TIntV& EIdV) const {
571  EIdV.Gen(GetEdges(), 0);
572  for (int E=EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E); ) {
573  EIdV.Add(EdgeH.GetKey(E));
574  }
575 }
576 
577 void TNEGraph::Defrag(const bool& OnlyNodeLinks) {
578  for (int kid = NodeH.FFirstKeyId(); NodeH.FNextKeyId(kid); ) {
579  TNode& Node = NodeH[kid];
580  Node.InEIdV.Pack(); Node.OutEIdV.Pack();
581  }
582  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); }
583  if (! OnlyNodeLinks && ! EdgeH.IsKeyIdEqKeyN()) { EdgeH.Defrag(); }
584 }
585 
586 bool TNEGraph::IsOk(const bool& ThrowExcept) const {
587 bool RetVal = true;
588  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
589  const TNode& Node = NodeH[N];
590  if (! Node.OutEIdV.IsSorted()) {
591  const TStr Msg = TStr::Fmt("Out-edge list of node %d is not sorted.", Node.GetId());
592  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
593  }
594  if (! Node.InEIdV.IsSorted()) {
595  const TStr Msg = TStr::Fmt("In-edge list of node %d is not sorted.", Node.GetId());
596  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
597  }
598  // check out-edge ids
599  int prevEId = -1;
600  for (int e = 0; e < Node.GetOutDeg(); e++) {
601  if (! IsEdge(Node.GetOutEId(e))) {
602  const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.", Node.GetOutEId(e), Node.GetId());
603  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
604  }
605  if (e > 0 && prevEId == Node.GetOutEId(e)) {
606  const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetOutEId(e));
607  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
608  }
609  prevEId = Node.GetOutEId(e);
610  }
611  // check in-edge ids
612  prevEId = -1;
613  for (int e = 0; e < Node.GetInDeg(); e++) {
614  if (! IsEdge(Node.GetInEId(e))) {
615  const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.", Node.GetInEId(e), Node.GetId());
616  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
617  }
618  if (e > 0 && prevEId == Node.GetInEId(e)) {
619  const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetInEId(e));
620  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
621  }
622  prevEId = Node.GetInEId(e);
623  }
624  }
625  for (int E = EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E); ) {
626  const TEdge& Edge = EdgeH[E];
627  if (! IsNode(Edge.GetSrcNId())) {
628  const TStr Msg = TStr::Fmt("Edge %d source node %d does not exist.", Edge.GetId(), Edge.GetSrcNId());
629  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
630  }
631  if (! IsNode(Edge.GetDstNId())) {
632  const TStr Msg = TStr::Fmt("Edge %d destination node %d does not exist.", Edge.GetId(), Edge.GetDstNId());
633  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
634  }
635  }
636  return RetVal;
637 }
638 
639 void TNEGraph::Dump(FILE *OutF) const {
640  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
641  const int EdgePlaces = (int) ceil(log10((double) GetEdges()));
642  fprintf(OutF, "-------------------------------------------------\nDirected Node-Edge Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
643  for (TNodeI NodeI = BegNI(); NodeI < EndNI(); NodeI++) {
644  fprintf(OutF, " %*d]\n", NodePlaces, NodeI.GetId());
645  fprintf(OutF, " in[%d]", NodeI.GetInDeg());
646  for (int edge = 0; edge < NodeI.GetInDeg(); edge++) {
647  fprintf(OutF, " %*d", EdgePlaces, NodeI.GetInEId(edge)); }
648  fprintf(OutF, "\n out[%d]", NodeI.GetOutDeg());
649  for (int edge = 0; edge < NodeI.GetOutDeg(); edge++) {
650  fprintf(OutF, " %*d", EdgePlaces, NodeI.GetOutEId(edge)); }
651  fprintf(OutF, "\n");
652  }
653  for (TEdgeI EdgeI = BegEI(); EdgeI < EndEI(); EdgeI++) {
654  fprintf(OutF, " %*d] %*d -> %*d\n", EdgePlaces, EdgeI.GetId(), NodePlaces, EdgeI.GetSrcNId(), NodePlaces, EdgeI.GetDstNId());
655  }
656  fprintf(OutF, "\n");
657 }
658 
659 // Return a small graph on 5 nodes and 6 edges.
661  PNEGraph Graph = TNEGraph::New();
662  for (int i = 0; i < 5; i++) { Graph->AddNode(i); }
663  Graph->AddEdge(0,1); Graph->AddEdge(0,2);
664  Graph->AddEdge(0,3); Graph->AddEdge(0,4);
665  Graph->AddEdge(1,2); Graph->AddEdge(1,2);
666  return Graph;
667 }
668 
670 // Bipartite graph
671 int TBPGraph::AddNode(int NId, const bool& LeftNode) {
672  if (NId == -1) { NId = MxNId; MxNId++; }
673  else if (IsLNode(NId)) { IAssertR(LeftNode, TStr::Fmt("Node with id %s already exists on the 'left'.", NId)); return NId; }
674  else if (IsRNode(NId)) { IAssertR(! LeftNode, TStr::Fmt("Node with id %s already exists on the 'right'.", NId)); return NId; }
675  else { MxNId = TMath::Mx(NId+1, MxNId()); }
676  if (LeftNode) { LeftH.AddDat(NId, TNode(NId)); }
677  else { RightH.AddDat(NId, TNode(NId)); }
678  return NId;
679 }
680 
681 // Delete node of ID NId from the bipartite graph.
682 void TBPGraph::DelNode(const int& NId) {
683  AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
684  THash<TInt, TNode>& SrcH = IsLNode(NId) ? LeftH : RightH;
685  THash<TInt, TNode>& DstH = IsLNode(NId) ? RightH : LeftH;
686  { TNode& Node = SrcH.GetDat(NId);
687  for (int e = 0; e < Node.GetOutDeg(); e++) {
688  const int nbr = Node.GetOutNId(e);
689  IAssertR(nbr != NId, "Bipartite graph has a loop!");
690  TNode& N = DstH.GetDat(nbr);
691  const int n = N.NIdV.SearchBin(NId);
692  IAssert(n!= -1);
693  N.NIdV.Del(n);
694  } }
695  SrcH.DelKey(NId);
696 }
697 
698 int TBPGraph::GetEdges() const {
699  int Edges = 0;
700  for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
701  Edges += LeftH[N].GetDeg(); }
702  return Edges;
703 }
704 
705 int TBPGraph::AddEdge(const int& LeftNId, const int& RightNId) {
706  const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
707  const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
708  IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
709  IAssertR(LeftNId!=RightNId, "No self-edges are allowed.");
710  IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
711  const int LNId = IsLL ? LeftNId : RightNId; // the real left node
712  const int RNId = IsLL ? RightNId : LeftNId; // the real right node
713  if (LeftH.GetDat(LNId).IsOutNId(RNId)) { return -2; } // edge already exists
714  LeftH.GetDat(LNId).NIdV.AddSorted(RNId);
715  RightH.GetDat(RNId).NIdV.AddSorted(LNId);
716  return -1; // no edge id
717 }
718 
719 void TBPGraph::DelEdge(const int& LeftNId, const int& RightNId) {
720  const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
721  const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
722  IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
723  IAssertR(LeftNId!=RightNId, "No self-edges are allowed.");
724  IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
725  const int LNId = IsLL ? LeftNId : RightNId; // the real left node
726  const int RNId = IsLL ? RightNId : LeftNId; // the real right node
727  { TIntV& NIdV = LeftH.GetDat(LNId).NIdV;
728  const int n = NIdV.SearchBin(RNId);
729  if (n != -1) { NIdV.Del(n); } }
730  { TIntV& NIdV = RightH.GetDat(RNId).NIdV;
731  const int n = NIdV.SearchBin(LNId);
732  if (n != -1) { NIdV.Del(n); } }
733 }
734 
735 bool TBPGraph::IsEdge(const int& LeftNId, const int& RightNId) const {
736  if (! IsNode(LeftNId) || ! IsNode(RightNId)) { return false; }
737  return IsLNode(LeftNId) ? LeftH.GetDat(LeftNId).IsOutNId(RightNId) : RightH.GetDat(LeftNId).IsOutNId(RightNId);
738 }
739 
740 TBPGraph::TEdgeI TBPGraph::GetEI(const int& LeftNId, const int& RightNId) const {
741  const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
742  const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
743  IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
744  IAssertR(LeftNId!=RightNId, "No self-edges are allowed.");
745  IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
746  const int LNId = IsLL ? LeftNId : RightNId; // the real left node
747  const int RNId = IsLL ? RightNId : LeftNId; // the real right node
748  const TNodeI SrcNI = GetNI(LNId);
749  const int NodeN = SrcNI.LeftHI.GetDat().NIdV.SearchBin(RNId);
750  IAssertR(NodeN != -1, "Right edge endpoint does not exists!");
751  return TEdgeI(SrcNI, EndNI(), NodeN);
752 }
753 
755  const int NNodes = GetNodes();
756  if (Rnd.GetUniDevInt(NNodes) < GetLNodes()) {
757  return GetRndLNId(Rnd); }
758  else {
759  return GetRndRNId(Rnd); }
760 }
761 
763  return LeftH.GetKey(LeftH.GetRndKeyId(Rnd, 0.8));
764 }
765 
767  return RightH.GetKey(RightH.GetRndKeyId(Rnd, 0.8));
768 }
769 
770 void TBPGraph::GetNIdV(TIntV& NIdV) const {
771  NIdV.Gen(GetNodes(), 0);
772  for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
773  NIdV.Add(LeftH.GetKey(N)); }
774  for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
775  NIdV.Add(RightH.GetKey(N)); }
776 }
777 
778 void TBPGraph::GetLNIdV(TIntV& NIdV) const {
779  NIdV.Gen(GetLNodes(), 0);
780  for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
781  NIdV.Add(LeftH.GetKey(N)); }
782 }
783 
784 void TBPGraph::GetRNIdV(TIntV& NIdV) const {
785  NIdV.Gen(GetRNodes(), 0);
786  for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
787  NIdV.Add(RightH.GetKey(N)); }
788 }
789 
790 void TBPGraph::Reserve(const int& Nodes, const int& Edges) {
791  if (Nodes>0) { LeftH.Gen(Nodes/2); RightH.Gen(Nodes/2); }
792 }
793 
794 void TBPGraph::Defrag(const bool& OnlyNodeLinks) {
795  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
796  LeftH[n].NIdV.Pack(); }
797  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
798  RightH[n].NIdV.Pack(); }
799  if (! OnlyNodeLinks && ! LeftH.IsKeyIdEqKeyN()) { LeftH.Defrag(); }
800  if (! OnlyNodeLinks && ! RightH.IsKeyIdEqKeyN()) { RightH.Defrag(); }
801 }
802 
803 bool TBPGraph::IsOk(const bool& ThrowExcept) const {
804  bool RetVal = false;
805  // edge lists are sorted
806  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
807  if (! LeftH[n].NIdV.IsSorted()) {
808  const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", LeftH[n].GetId());
809  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
810  }
811  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
812  if (! RightH[n].NIdV.IsSorted()) {
813  const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", RightH[n].GetId());
814  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
815  }
816  // nodes only appear on one side
817  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
818  if (RightH.IsKey(LeftH[n].GetId())) {
819  const TStr Msg = TStr::Fmt("'Left' node %d also appears on the 'right'.", LeftH[n].GetId());
820  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
821  }
822  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
823  if (LeftH.IsKey(RightH[n].GetId())) {
824  const TStr Msg = TStr::Fmt("'Right' node %d also appears on the 'left'.", RightH[n].GetId());
825  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
826  }
827  // edges only point from left to right and right to left
828  for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
829  for (int e = 0; e < LeftH[n].NIdV.Len(); e++) {
830  if (! RightH.IsKey(LeftH[n].NIdV[e]) || ! RightH.GetDat(LeftH[n].NIdV[e]).NIdV.IsIn(LeftH[n].GetId())) {
831  const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", LeftH[n].GetId(), LeftH[n].NIdV[e]());
832  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
833  }
834  }
835  for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
836  for (int e = 0; e < RightH[n].NIdV.Len(); e++) {
837  if (! LeftH.IsKey(RightH[n].NIdV[e]) || ! LeftH.GetDat(RightH[n].NIdV[e]).NIdV.IsIn(RightH[n].GetId())) {
838  const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", RightH[n].GetId(), RightH[n].NIdV[e]());
839  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
840  }
841  }
842  return RetVal;
843 }
844 
845 void TBPGraph::Dump(FILE *OutF) const {
846  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
847  fprintf(OutF, "-------------------------------------------------\nBipartite Graph: nodes: %d+%d=%d, edges: %d\n", GetLNodes(), GetRNodes(), GetNodes(), GetEdges());
848  for (int N = LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
849  const TNode& Node = LeftH[N];
850  fprintf(OutF, " %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
851  for (int edge = 0; edge < Node.GetDeg(); edge++) {
852  fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
853  fprintf(OutF, "\n");
854  }
855  fprintf(OutF, "\n");
856  /*// Also dump the 'right' side
857  fprintf(OutF, "\n");
858  for (int N = RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
859  const TNode& Node = RightH[N];
860  fprintf(OutF, " %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
861  for (int edge = 0; edge < Node.GetDeg(); edge++) {
862  fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
863  fprintf(OutF, "\n");
864  }
865  fprintf(OutF, "\n"); //*/
866 }
867 
869  PBPGraph BP = TBPGraph::New();
870  BP->AddNode(0, true);
871  BP->AddNode(1, true);
872  BP->AddNode(2, false);
873  BP->AddNode(3, false);
874  BP->AddNode(4, false);
875  BP->AddEdge(0, 2);
876  BP->AddEdge(0, 3);
877  BP->AddEdge(1, 2);
878  BP->AddEdge(1, 3);
879  BP->AddEdge(1, 4);
880  return BP;
881 }
882 
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition: graph.cpp:232
#define IAssert(Cond)
Definition: bd.h:262
static PBPGraph GetSmallGraph()
Returns a small graph on 2 'left', 3 'right' nodes and 4 edges.
Definition: graph.cpp:868
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
int GetDeg() const
Definition: graph.h:954
bool DelIfIn(const TVal &Val)
Removes the first occurrence of element Val.
Definition: ds.h:1212
THashIter NodeHI
Definition: graph.h:71
int GetOutDeg() const
Definition: graph.h:364
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a biparite graph of Nodes nodes and Edges edges.
Definition: graph.cpp:790
int GetSrcNId() const
Definition: graph.h:701
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:376
#define IAssertR(Cond, Reason)
Definition: bd.h:265
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: graph.cpp:468
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:497
int AddEdge(const int &SrcNId, const int &DstNId, int EId=-1)
Adds an edge with ID EId between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:516
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graph.cpp:586
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:280
void GetRNIdV(TIntV &NIdV) const
Gets a vector IDs of all 'right' nodes in the bipartite graph.
Definition: graph.cpp:784
Definition: dt.h:11
static PUNGraph GetSmallGraph()
Returns a small graph on 5 nodes and 5 edges.
Definition: graph.cpp:221
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TNode & GetNode(const int &NId)
Definition: graph.h:153
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.cpp:754
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:437
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:876
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:153
int GetNbrNId(const int &NodeN) const
Definition: graph.h:959
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:968
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
THash< TInt, TNode > NodeH
Definition: graph.h:455
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int GetId() const
Definition: graph.h:680
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
int AddEdgeUnchecked(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:330
int GetInDeg() const
Definition: graph.h:682
void GenExt(TVal *_ValT, const TSizeTy &_Vals)
Constructs a vector of _Vals elements of memory array _ValT.
Definition: ds.h:534
TInt NEdges
Definition: graph.h:144
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graph.cpp:391
int GetOutEId(const int &EdgeN) const
Definition: graph.h:685
int AddNode(int NId=-1, const bool &LeftNode=true)
Adds a node of ID NId to the graph.
Definition: graph.cpp:671
Directed multigraph.
Definition: graph.h:665
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:878
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503
THashIter NodeHI
Definition: graph.h:386
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:207
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:766
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
THashIter NodeHI
Definition: graph.h:709
int GetId() const
Definition: graph.h:51
int GetRndLNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'left' node in the graph.
Definition: graph.cpp:762
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:840
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1117
void ErrNotify(const char *NotifyCStr)
Definition: bd.h:74
THash< TInt, TNode > NodeH
Definition: graph.h:797
void Defrag()
Definition: hash.h:555
int GetOutDeg() const
Definition: graph.h:683
TNode & GetNode(const int &NId)
Definition: graph.h:463
int GetOutNId(const int &NodeN) const
Definition: graph.h:958
int GetInDeg() const
Definition: graph.h:363
THash< TInt, TEdge > EdgeH
Definition: graph.h:798
int GetDstNId() const
Definition: graph.h:702
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:294
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:842
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
int GetInEId(const int &EdgeN) const
Definition: graph.h:684
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:844
int GetId() const
Definition: graph.h:361
void DelKey(const TKey &Key)
Definition: hash.h:404
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:564
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:822
THashIter LeftHI
Definition: graph.h:971
TEdge & GetEdge(const int &EId)
Definition: graph.h:792
Undirected graph.
Definition: graph.h:32
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.cpp:477
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:698
TInt MxNId
Definition: graph.h:144
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
static PNEGraph GetSmallGraph()
Returns a small multigraph on 5 nodes and 6 edges.
Definition: graph.cpp:660
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
void DelEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true)
Deletes an edge from node IDs SrcNId to DstNId from the graph.
Definition: graph.cpp:345
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition: graph.cpp:464
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
bool IsEdge(const int &LeftNId, const int &RightNId) const
Tests whether an edge between node IDs LeftNId and RightNId exists in the graph.
Definition: graph.cpp:735
TIntV NIdV
Definition: graph.h:40
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:278
void GetLNIdV(TIntV &NIdV) const
Gets a vector IDs of all 'left' nodes in the bipartite graph.
Definition: graph.cpp:778
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int FFirstKeyId() const
Definition: hash.h:278
int GetOutNId(const int &NodeN) const
Definition: graph.h:366
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:486
void DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:124
int AddNodeUnchecked(int NId=-1)
Adds a node of ID NId to the network, noop if the node already exists.
Definition: graph.cpp:20
TIntV OutEIdV
Definition: graph.h:673
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:639
TIntV NIdV
Definition: graph.h:945
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1519
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:382
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
TNode & GetNode(const int &NId)
Definition: graph.h:790
static PNEGraph New()
Static constructor that returns a pointer to the graph. Call: PNEGraph Graph = TNEGraph::New().
Definition: graph.h:809
int AddEdge(const int &LeftNId, const int &RightNId)
Adds an edge between a node LeftNId on the left and a node RightNId on the right side of the bipartit...
Definition: graph.cpp:705
void DelEdge(const int &LeftNId, const int &RightNId)
Deletes an edge between a node LeftNId on the left and a node RightNId on the right side of the bipar...
Definition: graph.cpp:719
Directed graph.
Definition: graph.h:346
bool IsNbrNId(const int &NId) const
Definition: graph.h:58
int GetNbrNId(const int &NodeN) const
Definition: graph.h:57
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:682
bool IsEdge(const int &EId) const
Tests whether an edge with edge ID EId exists in the graph.
Definition: graph.h:868
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
static PNGraph GetSmallGraph()
Returns a small graph on 5 nodes and 6 edges.
Definition: graph.cpp:454
int GetRndRNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'right' node in the graph.
Definition: graph.cpp:766
Definition: dt.h:412
int AddEdge2(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph. If nodes do not exists, create them.
Definition: graph.cpp:112
THash< TInt, TNode > NodeH
Definition: graph.h:145
void GetEIdV(TIntV &EIdV) const
Gets a vector IDs of all edges in the graph.
Definition: graph.cpp:570
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1323
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1057
int GetId() const
Definition: graph.h:953
enum TGraphFlag_ TGraphFlag
Graph Flags, used for quick testing of graph types.
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.h:849
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:160
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
int GetOutDeg() const
Definition: graph.h:956
const TNEGraph * Graph
Definition: graph.h:710
TIntV InNIdV
Definition: graph.h:354
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:1062
TInt MxNId
Definition: graph.h:796
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
TInt MxNId
Definition: graph.h:454
#define AssertR(Cond, Reason)
Definition: bd.h:258
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition: graph.cpp:3
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the bipartite graph.
Definition: graph.cpp:770
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graph.cpp:170
TIntV OutNIdV
Definition: graph.h:354
int AddNodeUnchecked(int NId=-1)
Adds a node of ID NId to the network, noop if the node already exists.
Definition: graph.cpp:247
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:577
void Dump(FILE *OutF=stdout) const
Print the biparite graph in a human readable form to an output stream OutF.
Definition: graph.cpp:845
char * CStr()
Definition: dt.h:479
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the biparite graph.
Definition: graph.cpp:794
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
void DelEdge(const int &EId)
Deletes an edge with edge ID EId from the graph.
Definition: graph.cpp:527
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int GetInNId(const int &NodeN) const
Definition: graph.h:365
int GetDeg() const
Definition: graph.h:52
bool IsOutNId(const int &NId) const
Definition: graph.h:369
TInt MxEId
Definition: graph.h:796
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
bool IsOk(const bool &ThrowExcept=true) const
Checks the bipartite graph data structure for internal consistency.
Definition: graph.cpp:803
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:67
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:1018
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:706
int AddEdge2(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph. If nodes do not exist, create them.
Definition: graph.cpp:336
void Pack()
Definition: hash.h:289
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:838
int AddEdgeUnchecked(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:103
TIntV InEIdV
Definition: graph.h:673
int GetId() const
Definition: graph.h:700