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
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:946
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:360
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:693
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:276
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:477
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:868
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:951
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:960
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:451
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:672
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:674
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:677
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:657
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:870
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
THashIter NodeHI
Definition: graph.h:382
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:758
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
THashIter NodeHI
Definition: graph.h:701
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:832
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:789
void Defrag()
Definition: hash.h:555
int GetOutDeg() const
Definition: graph.h:675
TNode & GetNode(const int &NId)
Definition: graph.h:459
int GetOutNId(const int &NodeN) const
Definition: graph.h:950
int GetInDeg() const
Definition: graph.h:359
THash< TInt, TEdge > EdgeH
Definition: graph.h:790
int GetDstNId() const
Definition: graph.h:694
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:834
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
int GetInEId(const int &EdgeN) const
Definition: graph.h:676
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:836
int GetId() const
Definition: graph.h:357
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:814
THashIter LeftHI
Definition: graph.h:963
TEdge & GetEdge(const int &EId)
Definition: graph.h:784
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:1730
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:426
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:1728
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:542
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:274
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:362
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:665
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:937
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:782
static PNEGraph New()
Static constructor that returns a pointer to the graph. Call: PNEGraph Graph = TNEGraph::New().
Definition: graph.h:801
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:342
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:860
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
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:945
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:841
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
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:948
const TNEGraph * Graph
Definition: graph.h:702
TIntV InNIdV
Definition: graph.h:350
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:1054
TInt MxNId
Definition: graph.h:788
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
TInt MxNId
Definition: graph.h:450
#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:350
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:476
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:361
int GetDeg() const
Definition: graph.h:52
bool IsOutNId(const int &NId) const
Definition: graph.h:365
TInt MxEId
Definition: graph.h:788
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:1010
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:698
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:830
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:665
int GetId() const
Definition: graph.h:692