SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
graphmp.cpp
Go to the documentation of this file.
1 #ifdef GCC_ATOMIC
3 
5 // Directed Node Graph MP
6 bool TNGraphMP::HasFlag(const TGraphFlag& Flag) const {
7  return HasGraphFlag(TNGraphMP::TNet, Flag);
8 }
9 
10 int TNGraphMP::AddNode(int NId) {
11  if (NId == -1) {
12  NId = MxNId; MxNId++;
13  } else {
14  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
15  MxNId = TMath::Mx(NId+1, MxNId());
16  }
17  NodeH.AddDat(NId, TNode(NId));
18  return NId;
19 }
20 
22  if (IsNode(NId)) { return NId;}
23  MxNId = TMath::Mx(NId+1, MxNId());
24  NodeH.AddDat(NId, TNode(NId));
25  return NId;
26 }
27 
28 // add a node with a list of neighbors
29 // (use TNGraphMP::IsOk to check whether the graph is consistent)
30 int TNGraphMP::AddNode(const int& NId, const TIntV& InNIdV, const TIntV& OutNIdV) {
31  int NewNId;
32  if (NId == -1) {
33  NewNId = MxNId; MxNId++;
34  } else {
35  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
36  NewNId = NId;
37  MxNId = TMath::Mx(NewNId+1, MxNId());
38  }
39  TNode& Node = NodeH.AddDat(NewNId);
40  Node.Id = NewNId;
41  Node.InNIdV = InNIdV;
42  Node.OutNIdV = OutNIdV;
43  Node.InNIdV.Sort();
44  Node.OutNIdV.Sort();
45  return NewNId;
46 }
47 
48 // add a node from a vector pool
49 // (use TNGraphMP::IsOk to check whether the graph is consistent)
50 int TNGraphMP::AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& SrcVId, const int& DstVId) {
51  int NewNId;
52  if (NId == -1) {
53  NewNId = MxNId; MxNId++;
54  } else {
55  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
56  NewNId = NId;
57  MxNId = TMath::Mx(NewNId+1, MxNId());
58  }
59  TNode& Node = NodeH.AddDat(NewNId);
60  Node.Id = NewNId;
61  Node.InNIdV.GenExt(Pool.GetValVPt(SrcVId), Pool.GetVLen(SrcVId));
62  Node.OutNIdV.GenExt(Pool.GetValVPt(DstVId), Pool.GetVLen(DstVId));
63  Node.InNIdV.Sort();
64  Node.OutNIdV.Sort();
65  return NewNId;
66 }
67 
68 void TNGraphMP::DelNode(const int& NId) {
69 #if 0
70  { TNode& Node = GetNode(NId);
71  for (int e = 0; e < Node.GetOutDeg(); e++) {
72  const int nbr = Node.GetOutNId(e);
73  if (nbr == NId) { continue; }
74  TNode& N = GetNode(nbr);
75  const int n = N.InNIdV.SearchBin(NId);
76  if (n!= -1) { N.InNIdV.Del(n); }
77  }
78  for (int e = 0; e < Node.GetInDeg(); e++) {
79  const int nbr = Node.GetInNId(e);
80  if (nbr == NId) { continue; }
81  TNode& N = GetNode(nbr);
82  const int n = N.OutNIdV.SearchBin(NId);
83  if (n!= -1) { N.OutNIdV.Del(n); }
84  } }
85  NodeH.DelKey(NId);
86 #endif
87 }
88 
89 int TNGraphMP::GetEdges() const {
90  int edges=0;
91  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
92  edges+=NodeH[N].GetOutDeg();
93  }
94  return edges;
95 }
96 
97 int TNGraphMP::AddEdge(const int& SrcNId, const int& DstNId) {
98  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
99  //IAssert(! IsEdge(SrcNId, DstNId));
100  if (IsEdge(SrcNId, DstNId)) { return -2; }
101  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
102  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
103  return -1; // edge id
104 }
105 
106 int TNGraphMP::AddEdgeUnchecked(const int& SrcNId, const int& DstNId) {
107  GetNode(SrcNId).OutNIdV.Add(DstNId);
108  GetNode(DstNId).InNIdV.Add(SrcNId);
109  return -1; // edge id
110 }
111 
112 void TNGraphMP::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) {
113  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
114  { TNode& N = GetNode(SrcNId);
115  const int n = N.OutNIdV.SearchBin(DstNId);
116  if (n!= -1) { N.OutNIdV.Del(n); } }
117  { TNode& N = GetNode(DstNId);
118  const int n = N.InNIdV.SearchBin(SrcNId);
119  if (n!= -1) { N.InNIdV.Del(n); } }
120  if (! IsDir) {
121  { TNode& N = GetNode(SrcNId);
122  const int n = N.InNIdV.SearchBin(DstNId);
123  if (n!= -1) { N.InNIdV.Del(n); } }
124  { TNode& N = GetNode(DstNId);
125  const int n = N.OutNIdV.SearchBin(SrcNId);
126  if (n!= -1) { N.OutNIdV.Del(n); } }
127  }
128 }
129 
130 bool TNGraphMP::IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) const {
131  if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
132  if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
133  else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
134 }
135 
136 TNGraphMP::TEdgeI TNGraphMP::GetEI(const int& SrcNId, const int& DstNId) const {
137  const TNodeI SrcNI = GetNI(SrcNId);
138  const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
139  IAssert(NodeN != -1);
140  return TEdgeI(SrcNI, EndNI(), NodeN);
141 }
142 
143 void TNGraphMP::GetNIdV(TIntV& NIdV) const {
144  NIdV.Gen(GetNodes(), 0);
145  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
146  NIdV.Add(NodeH.GetKey(N)); }
147 }
148 
149 void TNGraphMP::Defrag(const bool& OnlyNodeLinks) {
150 #if 0
151  for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
152  TNode& Node = NodeH[n];
153  Node.InNIdV.Pack(); Node.OutNIdV.Pack();
154  }
155  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); }
156 #endif
157 }
158 
159 // for each node check that their neighbors are also nodes
160 bool TNGraphMP::IsOk(const bool& ThrowExcept) const {
161  bool RetVal = true;
162  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
163  const TNode& Node = NodeH[N];
164  if (! Node.OutNIdV.IsSorted()) {
165  const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId());
166  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
167  }
168  if (! Node.InNIdV.IsSorted()) {
169  const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId());
170  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
171  }
172  // check out-edges
173  int prevNId = -1;
174  for (int e = 0; e < Node.GetOutDeg(); e++) {
175  if (! IsNode(Node.GetOutNId(e))) {
176  const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.",
177  Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e));
178  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
179  }
180  if (e > 0 && prevNId == Node.GetOutNId(e)) {
181  const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.",
182  Node.GetId(), Node.GetId(), Node.GetOutNId(e));
183  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
184  }
185  prevNId = Node.GetOutNId(e);
186  }
187  // check in-edges
188  prevNId = -1;
189  for (int e = 0; e < Node.GetInDeg(); e++) {
190  if (! IsNode(Node.GetInNId(e))) {
191  const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.",
192  Node.GetId(), Node.GetInNId(e), Node.GetInNId(e));
193  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
194  }
195  if (e > 0 && prevNId == Node.GetInNId(e)) {
196  const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.",
197  Node.GetId(), Node.GetId(), Node.GetInNId(e));
198  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
199  }
200  prevNId = Node.GetInNId(e);
201  }
202  }
203  return RetVal;
204 }
205 
206 void TNGraphMP::Dump(FILE *OutF) const {
207  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
208  fprintf(OutF, "-------------------------------------------------\nDirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
209  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
210  const TNode& Node = NodeH[N];
211  fprintf(OutF, " %*d]\n", NodePlaces, Node.GetId());
212  fprintf(OutF, " in [%d]", Node.GetInDeg());
213  for (int edge = 0; edge < Node.GetInDeg(); edge++) {
214  fprintf(OutF, " %*d", NodePlaces, Node.GetInNId(edge)); }
215  fprintf(OutF, "\n out[%d]", Node.GetOutDeg());
216  for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
217  fprintf(OutF, " %*d", NodePlaces, Node.GetOutNId(edge)); }
218  fprintf(OutF, "\n");
219  }
220  fprintf(OutF, "\n");
221 }
222 
225  for (int i = 0; i < 5; i++) { G->AddNode(i); }
226  G->AddEdge(0,1); G->AddEdge(1,2); G->AddEdge(0,2);
227  G->AddEdge(1,3);
228  G->AddEdge(3,4);
229  G->AddEdge(2,3);
230  return G;
231 }
232 
233 
234 int TNGraphMP::AddOutEdge1(int& SrcIdx, const int& SrcNId, const int& DstNId) {
235  bool Found;
236  int SrcKeyId;
237 
238  //SrcKeyId = NodeH.AddKey2(SrcIdx, SrcNId, Found);
239  SrcKeyId = NodeH.AddKey12(SrcIdx, SrcNId, Found);
240  if (!Found) {
241  NodeH[SrcKeyId] = TNode(SrcNId);
242  //MxNId = TMath::Mx(SrcNId+1, MxNId());
243  }
244  //GetNode(SrcNId).OutNIdV.Add(DstNId);
245  //NodeH[SrcKeyId].OutNIdV.Add1(DstNId);
246 
247  // TODO:RS, edge lists need to be sorted at the end
248 
249  SrcIdx = SrcKeyId;
250  return Found;
251 }
252 
253 int TNGraphMP::AddInEdge1(int& DstIdx, const int& SrcNId, const int& DstNId) {
254  bool Found;
255  int DstKeyId;
256 
257  //DstKeyId = NodeH.AddKey2(DstIdx, DstNId, Found);
258  DstKeyId = NodeH.AddKey12(DstIdx, DstNId, Found);
259  if (!Found) {
260  NodeH[DstKeyId] = TNode(DstNId);
261  //MxNId = TMath::Mx(DstNId+1, MxNId());
262  }
263  //GetNode(DstNId).InNIdV.Add(SrcNId);
264  //NodeH[DstKeyId].InNIdV.Add1(SrcNId);
265 
266  // TODO:RS, edge lists need to be sorted at the end
267 
268  DstIdx = DstKeyId;
269  return Found;
270 }
271 
272 void TNGraphMP::AddOutEdge2(const int& SrcNId, const int& DstNId) {
273  NodeH[NodeH.GetKeyId(SrcNId)].OutNIdV.AddMP(DstNId);
274 }
275 
276 void TNGraphMP::AddInEdge2(const int& SrcNId, const int& DstNId) {
277  NodeH[NodeH.GetKeyId(DstNId)].InNIdV.AddMP(SrcNId);
278 }
279 
280 // add a node with a list of neighbors
281 // (use TNGraphMP::IsOk to check whether the graph is consistent)
282 void TNGraphMP::AddNodeWithEdges(const TInt& NId, TIntV& InNIdV, TIntV& OutNIdV) {
283  int NodeIdx = abs((NId.GetPrimHashCd()) % Reserved());
284  int NodeKeyId = NodeH.AddKey13(NodeIdx, NId);
285  NodeH[NodeKeyId] = TNode(NId);
286  NodeH[NodeKeyId].InNIdV.MoveFrom(InNIdV);
287  NodeH[NodeKeyId].OutNIdV.MoveFrom(OutNIdV);
288 }
289 #endif // GCC_ATOMIC
290 
#define IAssert(Cond)
Definition: bd.h:262
int GetPrimHashCd() const
Definition: dt.h:1171
void AddOutEdge2(const int &SrcNId, const int &DstNId)
Definition: graphmp.cpp:272
int GetInDeg() const
Definition: graphmp.h:44
#define IAssertR(Cond, Reason)
Definition: bd.h:265
int GetOutNId(const int &NodeN) const
Definition: graphmp.h:47
int AddOutEdge1(int &SrcIdx, const int &SrcNId, const int &DstNId)
Definition: graphmp.cpp:234
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graphmp.h:201
TIntV OutNIdV
Definition: graphmp.h:35
static PNGraphMP New()
Static constructor that returns a pointer to the graph. Call: PNGraphMP Graph = TNGraphMP::New().
Definition: graphmp.h:141
void GenExt(TVal *_ValT, const TSizeTy &_Vals)
Constructs a vector of _Vals elements of memory array _ValT.
Definition: ds.h:534
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graphmp.cpp:68
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: graphmp.cpp:112
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graphmp.cpp:206
int GetEdges() const
Returns the number of edges in the graph.
Definition: graphmp.cpp:89
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
int GetInNId(const int &NodeN) const
Definition: graphmp.h:46
int GetOutDeg() const
Definition: graphmp.h:45
int AddEdgeUnchecked(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph without performing checks.
Definition: graphmp.cpp:106
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graphmp.cpp:149
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
void AddInEdge2(const int &SrcNId, const int &DstNId)
Definition: graphmp.cpp:276
TIntV InNIdV
Definition: graphmp.h:35
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graphmp.h:199
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graphmp.h:195
Directed graph for multi-threaded operations.
Definition: graphmp.h:27
TEdgeI GetEI(const int &SrcNId, const int &DstNId) const
Returns an iterator referring to edge (SrcNId, DstNId) in the graph.
Definition: graphmp.cpp:136
int AddInEdge1(int &DstIdx, const int &SrcNId, const int &DstNId)
Definition: graphmp.cpp:253
bool FNextKeyId(int &KeyId) const
Definition: hashmp.h:484
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graphmp.h:102
Node iterator. Only forward iteration (operator++) is supported.
Definition: graphmp.h:58
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1519
void AddNodeWithEdges(const TInt &NId, TIntV &InNIdV, TIntV &OutNIdV)
Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV...
Definition: graphmp.cpp:282
Definition: dt.h:1137
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition: graphmp.cpp:6
THashIter NodeHI
Definition: graphmp.h:61
int GetId() const
Definition: graphmp.h:42
THashMP< TInt, TNode > NodeH
Definition: graphmp.h:127
bool IsOutNId(const int &NId) const
Definition: graphmp.h:50
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graphmp.cpp:160
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graphmp.cpp:143
Definition: dt.h:412
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
enum TGraphFlag_ TGraphFlag
Graph Flags, used for quick testing of graph types.
int FFirstKeyId() const
Definition: hashmp.h:207
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
TInt MxNId
Definition: graphmp.h:126
Definition: bd.h:196
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graphmp.h:154
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
int AddKey12(const int &Idx, const TKey &Key, bool &Found)
Definition: hashmp.h:307
int AddKey13(const int &Idx, const TKey &Key)
Definition: hashmp.h:358
static PNGraphMP GetSmallGraph()
Returns a small graph on 5 nodes and 6 edges.
Definition: graphmp.cpp:223
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graphmp.cpp:10
char * CStr()
Definition: dt.h:479
int Reserved() const
Definition: graphmp.h:206
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TDat & AddDat(const TKey &Key)
Definition: hashmp.h:181
int AddNodeUnchecked(int NId=-1)
Adds a node of ID NId to the graph without performing checks.
Definition: graphmp.cpp:21
int GetKeyId(const TKey &Key) const
Definition: hashmp.h:459
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: graphmp.cpp:130
TNode & GetNode(const int &NId)
Definition: graphmp.h:129
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph.
Definition: graphmp.cpp:97
const TKey & GetKey(const int &KeyId) const
Definition: hashmp.h:185