SNAP Library 4.0, User 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
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:1168
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: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
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:1728
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:1134
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:476
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