|
SNAP Library 2.0, User Reference
2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
|
SNAP Library 2.0, User Reference
2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
00001 00002 // Node Data 00003 // TNodeData has to implement the following methods: 00004 // class TNodeData { 00005 // public: 00006 // TNodeData() { } 00007 // TNodeData(TSIn& SIn) { } 00008 // void Save(TSOut& SOut) const { } 00009 // }; 00010 00011 //#////////////////////////////////////////////// 00013 template <class TNodeData> 00014 class TNodeNet { 00015 public: 00016 typedef TNodeData TNodeDat; 00017 typedef TNodeNet<TNodeData> TNet; 00018 typedef TPt<TNet> PNet; 00019 public: 00020 class TNode { 00021 private: 00022 TInt Id; 00023 TNodeData NodeDat; 00024 TIntV InNIdV, OutNIdV; 00025 public: 00026 TNode() : Id(-1), NodeDat(), InNIdV(), OutNIdV() { } 00027 TNode(const int& NId) : Id(NId), NodeDat(), InNIdV(), OutNIdV() { } 00028 TNode(const int& NId, const TNodeData& NodeData) : Id(NId), NodeDat(NodeData), InNIdV(), OutNIdV() { } 00029 TNode(const TNode& Node) : Id(Node.Id), NodeDat(Node.NodeDat), InNIdV(Node.InNIdV), OutNIdV(Node.OutNIdV) { } 00030 TNode(TSIn& SIn) : Id(SIn), NodeDat(SIn), InNIdV(SIn), OutNIdV(SIn) { } 00031 void Save(TSOut& SOut) const { Id.Save(SOut); NodeDat.Save(SOut); InNIdV.Save(SOut); OutNIdV.Save(SOut); } 00032 int GetId() const { return Id; } 00033 int GetDeg() const { return GetInDeg() + GetOutDeg(); } 00034 int GetInDeg() const { return InNIdV.Len(); } 00035 int GetOutDeg() const { return OutNIdV.Len(); } 00036 const TNodeData& GetDat() const { return NodeDat; } 00037 TNodeData& GetDat() { return NodeDat; } 00038 int GetInNId(const int& NodeN) const { return InNIdV[NodeN]; } 00039 int GetOutNId(const int& NodeN) const { return OutNIdV[NodeN]; } 00040 int GetNbrNId(const int& NodeN) const { return NodeN<GetOutDeg() ? GetOutNId(NodeN):GetInNId(NodeN-GetOutDeg()); } 00041 bool IsInNId(const int& NId) const { return InNIdV.SearchBin(NId) != -1; } 00042 bool IsOutNId(const int& NId) const { return OutNIdV.SearchBin(NId) != -1; } 00043 bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); } 00044 bool operator < (const TNode& Node) const { return NodeDat < Node.NodeDat; } 00045 friend class TNodeNet<TNodeData>; 00046 }; 00047 00049 class TNodeI { 00050 private: 00051 typedef typename THash<TInt, TNode>::TIter THashIter; 00052 THashIter NodeHI; 00053 TNodeNet *Net; 00054 public: 00055 TNodeI() : NodeHI(), Net(NULL) { } 00056 TNodeI(const THashIter& NodeHIter, const TNodeNet* NetPt) : NodeHI(NodeHIter), Net((TNodeNet *) NetPt) { } 00057 TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Net(NodeI.Net) { } 00058 TNodeI& operator = (const TNodeI& NodeI) { NodeHI=NodeI.NodeHI; Net=NodeI.Net; return *this; } 00060 TNodeI& operator++ (int) { NodeHI++; return *this; } 00061 bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; } 00062 bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; } 00063 00065 int GetId() const { return NodeHI.GetDat().GetId(); } 00067 int GetDeg() const { return NodeHI.GetDat().GetDeg(); } 00069 int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); } 00071 int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); } 00073 00075 int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); } 00077 00079 int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); } 00081 00083 int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); } 00085 bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); } 00087 bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); } 00089 bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); } 00090 const TNodeData& operator () () const { return NodeHI.GetDat().NodeDat; } 00091 TNodeData& operator () () { return NodeHI.GetDat().GetDat(); } 00092 const TNodeData& GetDat() const { return NodeHI.GetDat().GetDat(); } 00093 TNodeData& GetDat() { return NodeHI.GetDat().GetDat(); } 00094 const TNodeData& GetInNDat(const int& NodeN) const { return Net->GetNDat(GetInNId(NodeN)); } 00095 TNodeData& GetInNDat(const int& NodeN) { return Net->GetNDat(GetInNId(NodeN)); } 00096 const TNodeData& GetOutNDat(const int& NodeN) const { return Net->GetNDat(GetOutNId(NodeN)); } 00097 TNodeData& GetOutNDat(const int& NodeN) { return Net->GetNDat(GetOutNId(NodeN)); } 00098 const TNodeData& GetNbrNDat(const int& NodeN) const { return Net->GetNDat(GetNbrNId(NodeN)); } 00099 TNodeData& GetNbrNDat(const int& NodeN) { return Net->GetNDat(GetNbrNId(NodeN)); } 00100 friend class TNodeNet<TNodeData>; 00101 }; 00102 00104 class TEdgeI { 00105 private: 00106 TNodeI CurNode, EndNode; 00107 int CurEdge; 00108 public: 00109 TEdgeI() : CurNode(), EndNode(), CurEdge(0) { } 00110 TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { } 00111 TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { } 00112 TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; } 00114 TEdgeI& operator++ (int) { CurEdge++; if (CurEdge >= CurNode.GetOutDeg()) { CurEdge=0; CurNode++; 00115 while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } return *this; } 00116 bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); } 00117 bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; } 00119 int GetId() const { return -1; } 00121 int GetSrcNId() const { return CurNode.GetId(); } 00123 int GetDstNId() const { return CurNode.GetOutNId(CurEdge); } 00124 const TNodeData& GetSrcNDat() const { return CurNode.GetDat(); } 00125 TNodeData& GetDstNDat() { return CurNode.GetOutNDat(CurEdge); } 00126 friend class TNodeNet<TNodeData>; 00127 }; 00128 00129 protected: 00130 TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); } 00131 00132 protected: 00133 TCRef CRef; 00134 TInt MxNId; 00135 THash<TInt, TNode> NodeH; 00136 00137 public: 00138 TNodeNet() : CRef(), MxNId(0), NodeH() { } 00140 explicit TNodeNet(const int& Nodes, const int& Edges) : MxNId(0) { Reserve(Nodes, Edges); } 00141 TNodeNet(const TNodeNet& NodeNet) : MxNId(NodeNet.MxNId), NodeH(NodeNet.NodeH) { } 00143 TNodeNet(TSIn& SIn) : MxNId(SIn), NodeH(SIn) { } 00144 virtual ~TNodeNet() { } 00146 virtual void Save(TSOut& SOut) const { MxNId.Save(SOut); NodeH.Save(SOut); } 00148 static PNet New() { return PNet(new TNodeNet()); } 00150 static PNet Load(TSIn& SIn) { return PNet(new TNodeNet(SIn)); } 00152 bool HasFlag(const TGraphFlag& Flag) const; 00153 TNodeNet& operator = (const TNodeNet& NodeNet) { 00154 if (this!=&NodeNet) { NodeH=NodeNet.NodeH; MxNId=NodeNet.MxNId; } return *this; } 00155 // nodes 00157 int GetNodes() const { return NodeH.Len(); } 00159 00163 int AddNode(int NId = -1); 00165 00169 int AddNode(int NId, const TNodeData& NodeDat); 00171 int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId(), NodeId.GetDat()); } 00173 00175 void DelNode(const int& NId); 00177 void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); } 00179 bool IsNode(const int& NId) const { return NodeH.IsKey(NId); } 00181 TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); } 00183 TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); } 00185 TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); } 00187 const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); } 00189 void SetNDat(const int& NId, const TNodeData& NodeDat); 00191 TNodeData& GetNDat(const int& NId) { return NodeH.GetDat(NId).NodeDat; } 00193 const TNodeData& GetNDat(const int& NId) const { return NodeH.GetDat(NId).NodeDat; } 00195 int GetMxNId() const { return MxNId; } 00196 00197 // edges 00199 int GetEdges() const; 00201 00207 int AddEdge(const int& SrcNId, const int& DstNId); 00209 int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); } 00211 00215 void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true); 00217 bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const; 00219 TEdgeI BegEI() const { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0) NI++; return TEdgeI(NI, EndNI()); } 00221 TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); } 00223 TEdgeI GetEI(const int& EId) const; // not supported 00225 TEdgeI GetEI(const int& SrcNId, const int& DstNId) const; 00226 00228 int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); } 00230 TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); } 00232 void GetNIdV(TIntV& NIdV) const; 00233 00235 bool Empty() const { return GetNodes()==0; } 00237 void Clr(const bool& DoDel=true, const bool& ResetDat=true) { 00238 MxNId = 0; NodeH.Clr(DoDel, -1, ResetDat); } 00240 void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) { NodeH.Gen(Nodes/2); } } 00242 void SortNIdById(const bool& Asc=true) { NodeH.SortByKey(Asc); } 00244 void SortNIdByDat(const bool& Asc=true) { NodeH.SortByDat(Asc); } 00246 00251 void Defrag(const bool& OnlyNodeLinks=false); 00253 00256 bool IsOk(const bool& ThrowExcept=true) const; 00257 00258 friend class TPt<TNodeNet<TNodeData> >; 00259 }; 00260 00261 // set flags 00262 namespace TSnap { 00263 template <class TNodeData> struct IsDirected<TNodeNet<TNodeData> > { enum { Val = 1 }; }; 00264 template <class TNodeData> struct IsNodeDat<TNodeNet<TNodeData> > { enum { Val = 1 }; }; 00265 } 00266 00267 template <class TNodeData> 00268 bool TNodeNet<TNodeData>::HasFlag(const TGraphFlag& Flag) const { 00269 return HasGraphFlag(typename TNet, Flag); 00270 } 00271 00272 template <class TNodeData> 00273 int TNodeNet<TNodeData>::AddNode(int NId) { 00274 if (NId == -1) { 00275 NId = MxNId; MxNId++; 00276 } else { 00277 IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId)); 00278 MxNId = TMath::Mx(NId+1, MxNId()); 00279 } 00280 NodeH.AddDat(NId, TNode(NId)); 00281 return NId; 00282 } 00283 00284 template <class TNodeData> 00285 int TNodeNet<TNodeData>::AddNode(int NId, const TNodeData& NodeDat) { 00286 if (NId == -1) { 00287 NId = MxNId; MxNId++; 00288 } else { 00289 IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId)); 00290 MxNId = TMath::Mx(NId+1, MxNId()); 00291 } 00292 NodeH.AddDat(NId, TNode(NId, NodeDat)); 00293 return NId; 00294 } 00295 00296 template <class TNodeData> 00297 void TNodeNet<TNodeData>::DelNode(const int& NId) { 00298 { TNode& Node = GetNode(NId); 00299 for (int e = 0; e < Node.GetOutDeg(); e++) { 00300 const int nbr = Node.GetOutNId(e); 00301 if (nbr == NId) { continue; } 00302 TNode& N = GetNode(nbr); 00303 int n = N.InNIdV.SearchBin(NId); 00304 if (n!= -1) { N.InNIdV.Del(n); } 00305 } 00306 for (int e = 0; e < Node.GetInDeg(); e++) { 00307 const int nbr = Node.GetInNId(e); 00308 if (nbr == NId) { continue; } 00309 TNode& N = GetNode(nbr); 00310 int n = N.OutNIdV.SearchBin(NId); 00311 if (n!= -1) { N.OutNIdV.Del(n); } 00312 } } 00313 NodeH.DelKey(NId); 00314 } 00315 00316 template <class TNodeData> 00317 void TNodeNet<TNodeData>::SetNDat(const int& NId, const TNodeData& NodeDat) { 00318 IAssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist.", NId).CStr()); 00319 NodeH.GetDat(NId).NodeDat = NodeDat; 00320 } 00321 00322 template <class TNodeData> 00323 int TNodeNet<TNodeData>::GetEdges() const { 00324 int edges=0; 00325 for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N);) { 00326 edges+=NodeH[N].GetOutDeg(); } 00327 return edges; 00328 } 00329 00330 template <class TNodeData> 00331 int TNodeNet<TNodeData>::AddEdge(const int& SrcNId, const int& DstNId) { 00332 IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr()); 00333 if (IsEdge(SrcNId, DstNId)) { return -2; } 00334 GetNode(SrcNId).OutNIdV.AddSorted(DstNId); 00335 GetNode(DstNId).InNIdV.AddSorted(SrcNId); 00336 return -1; // edge id 00337 } 00338 00339 template <class TNodeData> 00340 void TNodeNet<TNodeData>::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) { 00341 IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr()); 00342 GetNode(SrcNId).OutNIdV.DelIfIn(DstNId); 00343 GetNode(DstNId).InNIdV.DelIfIn(SrcNId); 00344 if (! IsDir) { 00345 GetNode(DstNId).OutNIdV.DelIfIn(SrcNId); 00346 GetNode(SrcNId).InNIdV.DelIfIn(DstNId); 00347 } 00348 } 00349 00350 template <class TNodeData> 00351 bool TNodeNet<TNodeData>::IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) const { 00352 if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; } 00353 if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); } 00354 else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); } 00355 } 00356 00357 template <class TNodeData> 00358 void TNodeNet<TNodeData>::GetNIdV(TIntV& NIdV) const { 00359 NIdV.Reserve(GetNodes(), 0); 00360 for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) { 00361 NIdV.Add(NodeH.GetKey(N)); } 00362 } 00363 00364 template <class TNodeData> 00365 typename TNodeNet<TNodeData>::TEdgeI TNodeNet<TNodeData>::GetEI(const int& SrcNId, const int& DstNId) const { 00366 const TNodeI SrcNI = GetNI(SrcNId); 00367 const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId); 00368 if (NodeN == -1) { return EndEI(); } 00369 return TEdgeI(SrcNI, EndNI(), NodeN); 00370 } 00371 00372 template <class TNodeData> 00373 void TNodeNet<TNodeData>::Defrag(const bool& OnlyNodeLinks) { 00374 for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) { 00375 TNode& Node = NodeH[n]; 00376 Node.InNIdV.Pack(); Node.OutNIdV.Pack(); 00377 } 00378 if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { 00379 NodeH.Defrag(); } 00380 } 00381 00382 template <class TNodeData> 00383 bool TNodeNet<TNodeData>::IsOk(const bool& ThrowExcept) const { 00384 bool RetVal = true; 00385 for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) { 00386 const TNode& Node = NodeH[N]; 00387 if (! Node.OutNIdV.IsSorted()) { 00388 const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId()); 00389 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00390 } 00391 if (! Node.InNIdV.IsSorted()) { 00392 const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId()); 00393 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00394 } 00395 // check out-edges 00396 int prevNId = -1; 00397 for (int e = 0; e < Node.GetOutDeg(); e++) { 00398 if (! IsNode(Node.GetOutNId(e))) { 00399 const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.", 00400 Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e)); 00401 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00402 } 00403 if (e > 0 && prevNId == Node.GetOutNId(e)) { 00404 const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.", 00405 Node.GetId(), Node.GetId(), Node.GetOutNId(e)); 00406 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00407 } 00408 prevNId = Node.GetOutNId(e); 00409 } 00410 // check in-edges 00411 prevNId = -1; 00412 for (int e = 0; e < Node.GetInDeg(); e++) { 00413 if (! IsNode(Node.GetInNId(e))) { 00414 const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.", 00415 Node.GetId(), Node.GetInNId(e), Node.GetInNId(e)); 00416 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00417 } 00418 if (e > 0 && prevNId == Node.GetInNId(e)) { 00419 const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.", 00420 Node.GetId(), Node.GetId(), Node.GetInNId(e)); 00421 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00422 } 00423 prevNId = Node.GetInNId(e); 00424 } 00425 } 00426 return RetVal; 00427 } 00428 00430 // Common network types 00431 typedef TNodeNet<TInt> TIntNNet; 00432 typedef TPt<TIntNNet> PIntNNet; 00433 typedef TNodeNet<TFlt> TFltNNet; 00434 typedef TPt<TFltNNet> PFltNNet; 00435 typedef TNodeNet<TStr> TStrNNet; 00436 typedef TPt<TStrNNet> PStrNNet; 00437 00438 //#////////////////////////////////////////////// 00440 template <class TNodeData, class TEdgeData> 00441 class TNodeEDatNet { 00442 public: 00443 typedef TNodeData TNodeDat; 00444 typedef TEdgeData TEdgeDat; 00445 typedef TNodeEDatNet<TNodeData, TEdgeData> TNet; 00446 typedef TPt<TNet> PNet; 00447 typedef TVec<TPair<TInt, TEdgeData> > TNIdDatPrV; 00448 public: 00449 class TNode { 00450 private: 00451 TInt Id; 00452 TNodeData NodeDat; 00453 TIntV InNIdV; 00454 TNIdDatPrV OutNIdV; 00455 public: 00456 TNode() : Id(-1), NodeDat(), InNIdV(), OutNIdV() { } 00457 TNode(const int& NId) : Id(NId), NodeDat(), InNIdV(), OutNIdV() { } 00458 TNode(const int& NId, const TNodeData& NodeData) : Id(NId), NodeDat(NodeData), InNIdV(), OutNIdV() { } 00459 TNode(const TNode& Node) : Id(Node.Id), NodeDat(Node.NodeDat), InNIdV(Node.InNIdV), OutNIdV(Node.OutNIdV) { } 00460 TNode(TSIn& SIn) : Id(SIn), NodeDat(SIn), InNIdV(SIn), OutNIdV(SIn) { } 00461 void Save(TSOut& SOut) const { Id.Save(SOut); NodeDat.Save(SOut); InNIdV.Save(SOut); OutNIdV.Save(SOut); } 00462 int GetId() const { return Id; } 00463 int GetDeg() const { return GetInDeg() + GetOutDeg(); } 00464 int GetInDeg() const { return InNIdV.Len(); } 00465 int GetOutDeg() const { return OutNIdV.Len(); } 00466 const TNodeData& GetDat() const { return NodeDat; } 00467 TNodeData& GetDat() { return NodeDat; } 00468 int GetInNId(const int& EdgeN) const { return InNIdV[EdgeN]; } 00469 int GetOutNId(const int& EdgeN) const { return OutNIdV[EdgeN].Val1; } 00470 int GetNbrNId(const int& EdgeN) const { return EdgeN<GetOutDeg() ? GetOutNId(EdgeN):GetInNId(EdgeN-GetOutDeg()); } 00471 TEdgeData& GetOutEDat(const int& EdgeN) { return OutNIdV[EdgeN].Val2; } 00472 const TEdgeData& GetOutEDat(const int& EdgeN) const { return OutNIdV[EdgeN].Val2; } 00473 bool IsInNId(const int& NId) const { return InNIdV.SearchBin(NId)!=-1; } 00474 bool IsOutNId(const int& NId) const { return TNodeEDatNet::GetNIdPos(OutNIdV, NId)!=-1; } 00475 bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); } 00476 bool operator < (const TNode& Node) const { return NodeDat < Node.NodeDat; } 00477 friend class TNodeEDatNet<TNodeData, TEdgeData>; 00478 }; 00479 00481 class TNodeI { 00482 private: 00483 typedef typename THash<TInt, TNode>::TIter THashIter; 00484 THashIter NodeHI; 00485 TNodeEDatNet *Net; 00486 public: 00487 TNodeI() : NodeHI(), Net(NULL) { } 00488 TNodeI(const THashIter& NodeHIter, const TNodeEDatNet* NetPt) : NodeHI(NodeHIter), Net((TNodeEDatNet *) NetPt) { } 00489 TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Net(NodeI.Net) { } 00490 TNodeI& operator = (const TNodeI& NodeI) { NodeHI=NodeI.NodeHI; Net=NodeI.Net; return *this; } 00492 TNodeI& operator++ (int) { NodeHI++; return *this; } 00493 bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; } 00494 bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; } 00495 00497 int GetId() const { return NodeHI.GetDat().GetId(); } 00499 int GetDeg() const { return NodeHI.GetDat().GetDeg(); } 00501 int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); } 00503 int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); } 00505 00507 int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); } 00509 00511 int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); } 00513 00515 int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); } 00517 bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); } 00519 bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); } 00521 bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); } 00522 // node data 00523 const TNodeData& operator () () const { return NodeHI.GetDat().NodeDat; } 00524 TNodeData& operator () () { return NodeHI.GetDat().GetDat(); } 00525 const TNodeData& GetDat() const { return NodeHI.GetDat().GetDat(); } 00526 TNodeData& GetDat() { return NodeHI.GetDat().GetDat(); } 00527 const TNodeData& GetOutNDat(const int& NodeN) const { return Net->GetNDat(GetOutNId(NodeN)); } 00528 TNodeData& GetOutNDat(const int& NodeN) { return Net->GetNDat(GetOutNId(NodeN)); } 00529 const TNodeData& GetInNDat(const int& NodeN) const { return Net->GetNDat(GetInNId(NodeN)); } 00530 TNodeData& GetInNDat(const int& NodeN) { return Net->GetNDat(GetInNId(NodeN)); } 00531 const TNodeData& GetNbrNDat(const int& NodeN) const { return Net->GetNDat(GetNbrNId(NodeN)); } 00532 TNodeData& GetNbrNDat(const int& NodeN) { return Net->GetNDat(GetNbrNId(NodeN)); } 00533 // edge data 00534 TEdgeData& GetOutEDat(const int& EdgeN) { return NodeHI.GetDat().GetOutEDat(EdgeN); } 00535 const TEdgeData& GetOutEDat(const int& EdgeN) const { return NodeHI.GetDat().GetOutEDat(EdgeN); } 00536 TEdgeData& GetInEDat(const int& EdgeN) { return Net->GetEDat(GetInNId(EdgeN), GetId()); } 00537 const TEdgeData& GetInEDat(const int& EdgeN) const { return Net->GetEDat(GetInNId(EdgeN), GetId()); } 00538 TEdgeData& GetNbrEDat(const int& EdgeN) { return EdgeN<GetOutDeg() ? GetOutEDat(EdgeN) : GetInEDat(EdgeN-GetOutDeg()); } 00539 const TEdgeData& GetNbrEDat(const int& EdgeN) const { return EdgeN<GetOutDeg() ? GetOutEDat(EdgeN) : GetInEDat(EdgeN-GetOutDeg()); } 00540 friend class TNodeEDatNet<TNodeData, TEdgeData>; 00541 }; 00542 00544 class TEdgeI { 00545 private: 00546 TNodeI CurNode, EndNode; 00547 int CurEdge; 00548 public: 00549 TEdgeI() : CurNode(), EndNode(), CurEdge(0) { } 00550 TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { } 00551 TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { } 00552 TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; } 00554 TEdgeI& operator++ (int) { CurEdge++; if (CurEdge >= CurNode.GetOutDeg()) { CurEdge=0; CurNode++; 00555 while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } return *this; } 00556 bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); } 00557 bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; } 00559 int GetId() const { return -1; } 00561 int GetSrcNId() const { return CurNode.GetId(); } 00563 int GetDstNId() const { return CurNode.GetOutNId(CurEdge); } 00564 TEdgeData& operator () () { return CurNode.GetOutEDat(CurEdge); } 00565 const TEdgeData& operator () () const { return CurNode.GetOutEDat(CurEdge); } 00566 TEdgeData& GetDat() { return CurNode.GetOutEDat(CurEdge); } 00567 const TEdgeData& GetDat() const { return CurNode.GetOutEDat(CurEdge); } 00568 TNodeData& GetSrcNDat() { return CurNode(); } 00569 const TNodeData& GetSrcNDat() const { return CurNode(); } 00570 TNodeData& GetDstNDat() { return CurNode.GetOutNDat(CurEdge); } 00571 const TNodeData& GetDstNDat() const { return CurNode.GetOutNDat(CurEdge); } 00572 friend class TNodeEDatNet<TNodeData, TEdgeData>; 00573 }; 00574 00575 protected: 00576 TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); } 00577 static int GetNIdPos(const TVec<TPair<TInt, TEdgeData> >& NIdV, const int& NId); 00578 protected: 00579 TCRef CRef; 00580 TInt MxNId; 00581 THash<TInt, TNode> NodeH; 00582 public: 00583 TNodeEDatNet() : CRef(), MxNId(0), NodeH() { } 00585 explicit TNodeEDatNet(const int& Nodes, const int& Edges) : MxNId(0) { Reserve(Nodes, Edges); } 00586 TNodeEDatNet(const TNodeEDatNet& NodeNet) : MxNId(NodeNet.MxNId), NodeH(NodeNet.NodeH) { } 00588 TNodeEDatNet(TSIn& SIn) : MxNId(SIn), NodeH(SIn) { } 00589 virtual ~TNodeEDatNet() { } 00591 virtual void Save(TSOut& SOut) const { MxNId.Save(SOut); NodeH.Save(SOut); } 00593 static PNet New() { return PNet(new TNet()); } 00595 static PNet Load(TSIn& SIn) { return PNet(new TNet(SIn)); } 00597 bool HasFlag(const TGraphFlag& Flag) const; 00598 TNodeEDatNet& operator = (const TNodeEDatNet& NodeNet) { if (this!=&NodeNet) { 00599 NodeH=NodeNet.NodeH; MxNId=NodeNet.MxNId; } return *this; } 00600 // nodes 00602 int GetNodes() const { return NodeH.Len(); } 00604 00608 int AddNode(int NId = -1); 00610 00614 int AddNode(int NId, const TNodeData& NodeDat); 00616 int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId(), NodeId.GetDat()); } 00618 00620 void DelNode(const int& NId); 00622 void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); } 00624 bool IsNode(const int& NId) const { return NodeH.IsKey(NId); } 00626 TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); } 00628 TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); } 00630 TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); } 00632 const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); } 00634 void SetNDat(const int& NId, const TNodeData& NodeDat); 00636 TNodeData& GetNDat(const int& NId) { return NodeH.GetDat(NId).NodeDat; } 00638 const TNodeData& GetNDat(const int& NId) const { return NodeH.GetDat(NId).NodeDat; } 00640 int GetMxNId() const { return MxNId; } 00641 00642 // edges 00644 int GetEdges() const; 00646 00652 int AddEdge(const int& SrcNId, const int& DstNId); 00654 00660 int AddEdge(const int& SrcNId, const int& DstNId, const TEdgeData& EdgeDat); 00662 int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), EdgeI()); } 00664 00668 void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true); 00670 bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const; 00672 TEdgeI BegEI() const { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0) NI++; return TEdgeI(NI, EndNI()); } 00674 TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); } 00676 TEdgeI GetEI(const int& EId) const; // not supported 00678 TEdgeI GetEI(const int& SrcNId, const int& DstNId) const; 00680 void SetEDat(const int& SrcNId, const int& DstNId, const TEdgeData& EdgeDat); 00682 00684 bool GetEDat(const int& SrcNId, const int& DstNId, TEdgeData& EdgeDat) const; 00686 TEdgeData& GetEDat(const int& SrcNId, const int& DstNId); 00688 const TEdgeData& GetEDat(const int& SrcNId, const int& DstNId) const; 00690 void SetAllEDat(const TEdgeData& EdgeDat); 00691 00693 int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); } 00695 TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); } 00697 void GetNIdV(TIntV& NIdV) const; 00698 00700 bool Empty() const { return GetNodes()==0; } 00702 void Clr(const bool& DoDel=true, const bool& ResetDat=true) { 00703 MxNId = 0; NodeH.Clr(DoDel, -1, ResetDat); } 00705 void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) { NodeH.Gen(Nodes/2); } } 00707 void SortNIdById(const bool& Asc=true) { NodeH.SortByKey(Asc); } 00709 void SortNIdByDat(const bool& Asc=true) { NodeH.SortByDat(Asc); } 00711 00716 void Defrag(const bool& OnlyNodeLinks=false); 00718 00721 bool IsOk(const bool& ThrowExcept=true) const; 00722 00723 friend class TPt<TNodeEDatNet<TNodeData, TEdgeData> >; 00724 }; 00725 00726 // set flags 00727 namespace TSnap { 00728 template <class TNodeData, class TEdgeData> struct IsDirected<TNodeEDatNet<TNodeData, TEdgeData> > { enum { Val = 1 }; }; 00729 template <class TNodeData, class TEdgeData> struct IsNodeDat<TNodeEDatNet<TNodeData, TEdgeData> > { enum { Val = 1 }; }; 00730 template <class TNodeData, class TEdgeData> struct IsEdgeDat<TNodeEDatNet<TNodeData, TEdgeData> > { enum { Val = 1 }; }; 00731 } 00732 00733 template <class TNodeData, class TEdgeData> 00734 bool TNodeEDatNet<TNodeData, TEdgeData>::HasFlag(const TGraphFlag& Flag) const { 00735 return HasGraphFlag(typename TNet, Flag); 00736 } 00737 00738 template <class TNodeData, class TEdgeData> 00739 int TNodeEDatNet<TNodeData, TEdgeData>::GetNIdPos(const TVec<TPair<TInt, TEdgeData> >& NIdV, const int& NId) { 00740 int LValN=0, RValN = NIdV.Len()-1; 00741 while (RValN >= LValN) { 00742 const int ValN = (LValN+RValN)/2; 00743 const int CurNId = NIdV[ValN].Val1; 00744 if (NId == CurNId) { return ValN; } 00745 if (NId < CurNId) { RValN=ValN-1; } 00746 else { LValN=ValN+1; } 00747 } 00748 return -1; 00749 } 00750 00751 template <class TNodeData, class TEdgeData> 00752 int TNodeEDatNet<TNodeData, TEdgeData>::AddNode(int NId) { 00753 if (NId == -1) { 00754 NId = MxNId; MxNId++; 00755 } else { 00756 IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId)); 00757 MxNId = TMath::Mx(NId+1, MxNId()); 00758 } 00759 NodeH.AddDat(NId, TNode(NId)); 00760 return NId; 00761 } 00762 00763 template <class TNodeData, class TEdgeData> 00764 int TNodeEDatNet<TNodeData, TEdgeData>::AddNode(int NId, const TNodeData& NodeDat) { 00765 if (NId == -1) { 00766 NId = MxNId; MxNId++; 00767 } else { 00768 IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId)); 00769 MxNId = TMath::Mx(NId+1, MxNId()); 00770 } 00771 NodeH.AddDat(NId, TNode(NId, NodeDat)); 00772 return NId; 00773 } 00774 00775 template <class TNodeData, class TEdgeData> 00776 void TNodeEDatNet<TNodeData, TEdgeData>::SetNDat(const int& NId, const TNodeData& NodeDat) { 00777 IAssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist.", NId).CStr()); 00778 NodeH.GetDat(NId).NodeDat = NodeDat; 00779 } 00780 00781 template <class TNodeData, class TEdgeData> 00782 void TNodeEDatNet<TNodeData, TEdgeData>::DelNode(const int& NId) { 00783 const TNode& Node = GetNode(NId); 00784 for (int out = 0; out < Node.GetOutDeg(); out++) { 00785 const int nbr = Node.GetOutNId(out); 00786 if (nbr == NId) { continue; } 00787 TIntV& NIdV = GetNode(nbr).InNIdV; 00788 const int pos = NIdV.SearchBin(NId); 00789 if (pos != -1) { NIdV.Del(pos); } 00790 } 00791 for (int in = 0; in < Node.GetInDeg(); in++) { 00792 const int nbr = Node.GetInNId(in); 00793 if (nbr == NId) { continue; } 00794 TNIdDatPrV& NIdDatV = GetNode(nbr).OutNIdV; 00795 const int pos = GetNIdPos(NIdDatV, NId); 00796 if (pos != -1) { NIdDatV.Del(pos); } 00797 } 00798 NodeH.DelKey(NId); 00799 } 00800 00801 template <class TNodeData, class TEdgeData> 00802 int TNodeEDatNet<TNodeData, TEdgeData>::GetEdges() const { 00803 int edges=0; 00804 for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) { 00805 edges+=NodeH[N].GetOutDeg(); } 00806 return edges; 00807 } 00808 00809 template <class TNodeData, class TEdgeData> 00810 int TNodeEDatNet<TNodeData, TEdgeData>::AddEdge(const int& SrcNId, const int& DstNId) { 00811 return AddEdge(SrcNId, DstNId, TEdgeData()); 00812 } 00813 00814 template <class TNodeData, class TEdgeData> 00815 int TNodeEDatNet<TNodeData, TEdgeData>::AddEdge(const int& SrcNId, const int& DstNId, const TEdgeData& EdgeDat) { 00816 IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr()); 00817 //IAssert(! IsEdge(SrcNId, DstNId)); 00818 if (IsEdge(SrcNId, DstNId)) { 00819 GetEDat(SrcNId, DstNId) = EdgeDat; 00820 return -2; 00821 } 00822 GetNode(SrcNId).OutNIdV.AddSorted(TPair<TInt, TEdgeData>(DstNId, EdgeDat)); 00823 GetNode(DstNId).InNIdV.AddSorted(SrcNId); 00824 return -1; // edge id 00825 } 00826 00827 template <class TNodeData, class TEdgeData> 00828 void TNodeEDatNet<TNodeData, TEdgeData>::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) { 00829 IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr()); 00830 int pos = GetNIdPos(GetNode(SrcNId).OutNIdV, DstNId); 00831 if (pos != -1) { GetNode(SrcNId).OutNIdV.Del(pos); } 00832 pos = GetNode(DstNId).InNIdV.SearchBin(SrcNId); 00833 if (pos != -1) { GetNode(DstNId).InNIdV.Del(pos); } 00834 if (! IsDir) { 00835 pos = GetNIdPos(GetNode(DstNId).OutNIdV, SrcNId); 00836 if (pos != -1) { GetNode(DstNId).OutNIdV.Del(pos); } 00837 pos = GetNode(SrcNId).InNIdV.SearchBin(DstNId); 00838 if (pos != -1) { GetNode(SrcNId).InNIdV.Del(pos); } 00839 } 00840 } 00841 00842 template <class TNodeData, class TEdgeData> 00843 bool TNodeEDatNet<TNodeData, TEdgeData>::IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) const { 00844 if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; } 00845 if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); } 00846 else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); } 00847 } 00848 00849 template <class TNodeData, class TEdgeData> 00850 void TNodeEDatNet<TNodeData, TEdgeData>::SetEDat(const int& SrcNId, const int& DstNId, const TEdgeData& EdgeDat) { 00851 IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr()); 00852 IAssertR(IsEdge(SrcNId, DstNId), TStr::Fmt("Edge between %d and %d does not exist.", SrcNId, DstNId).CStr()); 00853 GetEDat(SrcNId, DstNId) = EdgeDat; 00854 } 00855 00856 template <class TNodeData, class TEdgeData> 00857 bool TNodeEDatNet<TNodeData, TEdgeData>::GetEDat(const int& SrcNId, const int& DstNId, TEdgeData& EdgeDat) const { 00858 if (! IsEdge(SrcNId, DstNId)) { return false; } 00859 const TNode& N = GetNode(SrcNId); 00860 EdgeDat = N.GetOutEDat(GetNIdPos(N.OutNIdV, DstNId)); 00861 return true; 00862 } 00863 00864 template <class TNodeData, class TEdgeData> 00865 TEdgeData& TNodeEDatNet<TNodeData, TEdgeData>::GetEDat(const int& SrcNId, const int& DstNId) { 00866 Assert(IsEdge(SrcNId, DstNId)); 00867 TNode& N = GetNode(SrcNId); 00868 return N.GetOutEDat(GetNIdPos(N.OutNIdV, DstNId)); 00869 } 00870 00871 template <class TNodeData, class TEdgeData> 00872 const TEdgeData& TNodeEDatNet<TNodeData, TEdgeData>::GetEDat(const int& SrcNId, const int& DstNId) const { 00873 Assert(IsEdge(SrcNId, DstNId)); 00874 const TNode& N = GetNode(SrcNId); 00875 return N.GetOutEDat(GetNIdPos(N.OutNIdV, DstNId)); 00876 } 00877 00878 template <class TNodeData, class TEdgeData> 00879 void TNodeEDatNet<TNodeData, TEdgeData>::SetAllEDat(const TEdgeData& EdgeDat) { 00880 for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) { 00881 EI() = EdgeDat; 00882 } 00883 } 00884 00885 template <class TNodeData, class TEdgeData> 00886 typename TNodeEDatNet<TNodeData, TEdgeData>::TEdgeI TNodeEDatNet<TNodeData, TEdgeData>::GetEI(const int& SrcNId, const int& DstNId) const { 00887 const TNodeI SrcNI = GetNI(SrcNId); 00888 int NodeN = -1; 00889 //SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId); 00890 const TNIdDatPrV& NIdDatV = SrcNI.NodeHI.GetDat().OutNIdV; 00891 int LValN=0, RValN=NIdDatV.Len()-1; 00892 while (RValN>=LValN){ 00893 int ValN=(LValN+RValN)/2; 00894 if (DstNId==NIdDatV[ValN].Val1){ NodeN=ValN; break; } 00895 if (DstNId<NIdDatV[ValN].Val1){RValN=ValN-1;} else {LValN=ValN+1;} 00896 } 00897 if (NodeN == -1) { return EndEI(); } 00898 else { return TEdgeI(SrcNI, EndNI(), NodeN); } 00899 } 00900 00901 template <class TNodeData, class TEdgeData> 00902 void TNodeEDatNet<TNodeData, TEdgeData>::GetNIdV(TIntV& NIdV) const { 00903 NIdV.Reserve(GetNodes(), 0); 00904 for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) { 00905 NIdV.Add(NodeH.GetKey(N)); } 00906 } 00907 00908 template <class TNodeData, class TEdgeData> 00909 void TNodeEDatNet<TNodeData, TEdgeData>::Defrag(const bool& OnlyNodeLinks) { 00910 for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n);) { 00911 TNode& Node = NodeH[n]; 00912 Node.InNIdV.Pack(); Node.OutNIdV.Pack(); 00913 } 00914 if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { 00915 NodeH.Defrag(); 00916 } 00917 } 00918 00919 template <class TNodeData, class TEdgeData> 00920 bool TNodeEDatNet<TNodeData, TEdgeData>::IsOk(const bool& ThrowExcept) const { 00921 bool RetVal = true; 00922 for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) { 00923 const TNode& Node = NodeH[N]; 00924 if (! Node.OutNIdV.IsSorted()) { 00925 const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId()); 00926 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00927 } 00928 if (! Node.InNIdV.IsSorted()) { 00929 const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId()); 00930 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00931 } 00932 // check out-edges 00933 int prevNId = -1; 00934 for (int e = 0; e < Node.GetOutDeg(); e++) { 00935 if (! IsNode(Node.GetOutNId(e))) { 00936 const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.", 00937 Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e)); 00938 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00939 } 00940 if (e > 0 && prevNId == Node.GetOutNId(e)) { 00941 const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.", 00942 Node.GetId(), Node.GetId(), Node.GetOutNId(e)); 00943 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00944 } 00945 prevNId = Node.GetOutNId(e); 00946 } 00947 // check in-edges 00948 prevNId = -1; 00949 for (int e = 0; e < Node.GetInDeg(); e++) { 00950 if (! IsNode(Node.GetInNId(e))) { 00951 const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.", 00952 Node.GetId(), Node.GetInNId(e), Node.GetInNId(e)); 00953 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00954 } 00955 if (e > 0 && prevNId == Node.GetInNId(e)) { 00956 const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.", 00957 Node.GetId(), Node.GetId(), Node.GetInNId(e)); 00958 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 00959 } 00960 prevNId = Node.GetInNId(e); 00961 } 00962 } 00963 return RetVal; 00964 } 00965 00967 // Common network types 00968 typedef TNodeEDatNet<TInt, TInt> TIntNEDNet; 00969 typedef TPt<TIntNEDNet> PIntNEDNet; 00970 typedef TNodeEDatNet<TInt, TFlt> TIntFltNEDNet; 00971 typedef TPt<TIntFltNEDNet> PIntFltNEDNet; 00972 typedef TNodeEDatNet<TStr, TInt> TStrIntNEDNet; 00973 typedef TPt<TStrIntNEDNet> PStrIntNEDNet; 00974 00975 //#////////////////////////////////////////////// 00977 template <class TNodeData, class TEdgeData> 00978 class TNodeEdgeNet { 00979 public: 00980 typedef TNodeData TNodeDat; 00981 typedef TEdgeData TEdgeDat; 00982 typedef TNodeEdgeNet<TNodeData, TEdgeData> TNet; 00983 typedef TPt<TNet> PNet; 00984 public: 00985 class TNode { 00986 private: 00987 TInt Id; 00988 TIntV InEIdV, OutEIdV; 00989 TNodeData NodeDat; 00990 public: 00991 TNode() : Id(-1), InEIdV(), OutEIdV(), NodeDat() { } 00992 TNode(const int& NId) : Id(NId), InEIdV(), OutEIdV(), NodeDat() { } 00993 TNode(const int& NId, const TNodeData& NodeData) : Id(NId), InEIdV(), OutEIdV(), NodeDat(NodeData) { } 00994 TNode(const TNode& Node) : Id(Node.Id), InEIdV(Node.InEIdV), OutEIdV(Node.OutEIdV), NodeDat(Node.NodeDat) { } 00995 TNode(TSIn& SIn) : Id(SIn), InEIdV(SIn), OutEIdV(SIn), NodeDat(SIn) { } 00996 void Save(TSOut& SOut) const { Id.Save(SOut); InEIdV.Save(SOut); OutEIdV.Save(SOut); NodeDat.Save(SOut); } 00997 bool operator < (const TNode& Node) const { return NodeDat < Node.NodeDat; } 00998 int GetId() const { return Id; } 00999 int GetDeg() const { return GetInDeg() + GetOutDeg(); } 01000 int GetInDeg() const { return InEIdV.Len(); } 01001 int GetOutDeg() const { return OutEIdV.Len(); } 01002 const TNodeData& GetDat() const { return NodeDat; } 01003 TNodeData& GetDat() { return NodeDat; } 01004 int GetInEId(const int& NodeN) const { return InEIdV[NodeN]; } 01005 int GetOutEId(const int& NodeN) const { return OutEIdV[NodeN]; } 01006 int GetNbrEId(const int& EdgeN) const { return EdgeN<GetOutDeg()?GetOutEId(EdgeN):GetInEId(EdgeN-GetOutDeg()); } 01007 bool IsInEId(const int& EId) const { return InEIdV.SearchBin(EId) != -1; } 01008 bool IsOutEId(const int& EId) const { return OutEIdV.SearchBin(EId) != -1; } 01009 bool IsNbrEId(const int& EId) const { return IsInEId(EId) || IsOutEId(EId); } 01010 friend class TNodeEdgeNet<TNodeData, TEdgeData>; 01011 }; 01012 01013 class TEdge { 01014 private: 01015 TInt Id, SrcNId, DstNId; 01016 TEdgeData EdgeDat; 01017 public: 01018 TEdge() : Id(-1), SrcNId(-1), DstNId(-1), EdgeDat() { } 01019 TEdge(const int& EId, const int& SourceNId, const int& DestNId) : Id(EId), SrcNId(SourceNId), DstNId(DestNId), EdgeDat() { } 01020 TEdge(const int& EId, const int& SourceNId, const int& DestNId, const TEdgeData& EdgeData) : Id(EId), SrcNId(SourceNId), DstNId(DestNId), EdgeDat(EdgeData) { } 01021 TEdge(const TEdge& Edge) : Id(Edge.Id), SrcNId(Edge.SrcNId), DstNId(Edge.DstNId), EdgeDat(Edge.EdgeDat) { } 01022 TEdge(TSIn& SIn) : Id(SIn), SrcNId(SIn), DstNId(SIn), EdgeDat(SIn) { } 01023 void Save(TSOut& SOut) const { Id.Save(SOut); SrcNId.Save(SOut); DstNId.Save(SOut); EdgeDat.Save(SOut); } 01024 bool operator < (const TEdge& Edge) const { return EdgeDat < Edge.EdgeDat; } 01025 int GetId() const { return Id; } 01026 int GetSrcNId() const { return SrcNId; } 01027 int GetDstNId() const { return DstNId; } 01028 const TEdgeData& GetDat() const { return EdgeDat; } 01029 TEdgeData& GetDat() { return EdgeDat; } 01030 friend class TNodeEdgeNet; 01031 }; 01032 01034 class TNodeI { 01035 private: 01036 typedef typename THash<TInt, TNode>::TIter THashIter; 01037 THashIter NodeHI; 01038 TNodeEdgeNet *Net; 01039 public: 01040 TNodeI() : NodeHI(), Net(NULL) { } 01041 TNodeI(const THashIter& NodeHIter, const TNodeEdgeNet* NetPt) : NodeHI(NodeHIter), Net((TNodeEdgeNet *)NetPt) { } 01042 TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Net(NodeI.Net) { } 01043 TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; Net=NodeI.Net; return *this; } 01045 TNodeI& operator++ (int) { NodeHI++; return *this; } 01046 bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; } 01047 bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; } 01049 int GetId() const { return NodeHI.GetDat().GetId(); } 01051 int GetDeg() const { return NodeHI.GetDat().GetDeg(); } 01053 int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); } 01055 int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); } 01057 01059 int GetInNId(const int& EdgeN) const { return Net->GetEdge(NodeHI.GetDat().GetInEId(EdgeN)).GetSrcNId(); } 01061 01063 int GetOutNId(const int& EdgeN) const { return Net->GetEdge(NodeHI.GetDat().GetOutEId(EdgeN)).GetDstNId(); } 01065 01067 int GetNbrNId(const int& EdgeN) const { const TEdge& E = Net->GetEdge(NodeHI.GetDat().GetNbrEId(EdgeN)); 01068 return GetId()==E.GetSrcNId() ? E.GetDstNId():E.GetSrcNId(); } 01070 bool IsInNId(const int& NId) const; 01072 bool IsOutNId(const int& NId) const; 01074 bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); } 01075 // node data 01076 const TNodeData& operator () () const { return NodeHI.GetDat().GetDat(); } 01077 TNodeData& operator () () { return NodeHI.GetDat().GetDat(); } 01078 const TNodeData& GetDat() const { return NodeHI.GetDat().GetDat(); } 01079 TNodeData& GetDat() { return NodeHI.GetDat().GetDat(); } 01080 const TNodeData& GetInNDat(const int& EdgeN) const { return Net->GetNDat(GetInNId(EdgeN)); } 01081 TNodeData& GetInNDat(const int& EdgeN) { return Net->GetNodeDat(GetInNId(EdgeN)); } 01082 const TNodeData& GetOutNDat(const int& EdgeN) const { return Net->GetNDat(GetOutNId(EdgeN)); } 01083 TNodeData& GetOutNDat(const int& EdgeN) { return Net->GetNDat(GetOutNId(EdgeN)); } 01084 const TNodeData& GetNbrNDat(const int& EdgeN) const { return Net->GetNDat(GetNbrNId(EdgeN)); } 01085 TNodeData& GetNbrNDat(const int& EdgeN) { return Net->GetNDat(GetNbrNId(EdgeN)); } 01086 // edges 01088 int GetInEId(const int& EdgeN) const { return NodeHI.GetDat().GetInEId(EdgeN); } 01090 int GetOutEId(const int& EdgeN) const { return NodeHI.GetDat().GetOutEId(EdgeN); } 01092 int GetNbrEId(const int& EdgeN) const { return NodeHI.GetDat().GetNbrEId(EdgeN); } 01094 bool IsInEId(const int& EId) const { return NodeHI.GetDat().IsInEId(EId); } 01096 bool IsOutEId(const int& EId) const { return NodeHI.GetDat().IsOutEId(EId); } 01098 bool IsNbrEId(const int& EId) const { return NodeHI.GetDat().IsNbrEId(EId); } 01099 // edge data 01100 TEdgeDat& GetInEDat(const int& EdgeN) { return Net->GetEDat(GetInEId(EdgeN)); } 01101 const TEdgeDat& GetInEDat(const int& EdgeN) const { return Net->GetEDat(GetInEId(EdgeN)); } 01102 TEdgeDat& GetOutEDat(const int& EdgeN) { return Net->GetEDat(GetOutEId(EdgeN)); } 01103 const TEdgeDat& GetOutEDat(const int& EdgeN) const { return Net->GetEDat(GetOutEId(EdgeN)); } 01104 TEdgeDat& GetNbrEDat(const int& EdgeN) { return Net->GetEDat(GetNbrEId(EdgeN)); } 01105 const TEdgeDat& GetNbrEDat(const int& EdgeN) const { return Net->GetEDat(GetNbrEId(EdgeN)); } 01106 friend class TNodeEdgeNet; 01107 }; 01108 01110 class TEdgeI { 01111 private: 01112 typedef typename THash<TInt, TEdge>::TIter THashIter; 01113 THashIter EdgeHI; 01114 TNodeEdgeNet *Net; 01115 public: 01116 TEdgeI() : EdgeHI(), Net(NULL) { } 01117 TEdgeI(const THashIter& EdgeHIter, const TNodeEdgeNet *NetPt) : EdgeHI(EdgeHIter), Net((TNodeEdgeNet *) NetPt) { } 01118 TEdgeI(const TEdgeI& EdgeI) : EdgeHI(EdgeI.EdgeHI), Net(EdgeI.Net) { } 01119 TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { EdgeHI=EdgeI.EdgeHI; Net=EdgeI.Net; } return *this; } 01120 TEdgeI& operator++ (int) { EdgeHI++; return *this; } 01121 bool operator < (const TEdgeI& EdgeI) const { return EdgeHI < EdgeI.EdgeHI; } 01122 bool operator == (const TEdgeI& EdgeI) const { return EdgeHI == EdgeI.EdgeHI; } 01124 int GetId() const { return EdgeHI.GetDat().GetId(); } 01126 int GetSrcNId() const { return EdgeHI.GetDat().GetSrcNId(); } 01128 int GetDstNId() const { return EdgeHI.GetDat().GetDstNId(); } 01129 const TEdgeData& operator () () const { return EdgeHI.GetDat().GetDat(); } 01130 TEdgeData& operator () () { return EdgeHI.GetDat().GetDat(); } 01131 const TEdgeData& GetDat() const { return EdgeHI.GetDat().GetDat(); } 01132 TEdgeData& GetDat() { return EdgeHI.GetDat().GetDat(); } 01133 const TNodeData& GetSrcNDat() const { return Net->GetNDat(GetSrcNId()); } 01134 TNodeData& GetSrcNDat() { return Net->GetNDat(GetSrcNId()); } 01135 const TNodeData& GetDstNDat() const { return Net->GetNDat(GetDstNId()); } 01136 TNodeData& GetDstNDat() { return Net->GetNDat(GetDstNId()); } 01137 friend class TNodeEdgeNet; 01138 }; 01139 01140 private: 01141 TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); } 01142 const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); } 01143 const TNode& GetNodeKId(const int& NodeKeyId) const { return NodeH[NodeKeyId]; } 01144 TEdge& GetEdge(const int& EId) { return EdgeH.GetDat(EId); } 01145 const TEdge& GetEdge(const int& EId) const { return EdgeH.GetDat(EId); } 01146 const TEdge& GetEdgeKId(const int& EdgeKeyId) const { return EdgeH[EdgeKeyId]; } 01147 protected: 01148 TCRef CRef; 01149 TInt MxNId, MxEId; 01150 THash<TInt, TNode> NodeH; 01151 THash<TInt, TEdge> EdgeH; 01152 public: 01153 TNodeEdgeNet() : CRef(), MxNId(0), MxEId(0) { } 01155 explicit TNodeEdgeNet(const int& Nodes, const int& Edges) : CRef(), MxNId(0), MxEId(0) { Reserve(Nodes, Edges); } 01156 TNodeEdgeNet(const TNodeEdgeNet& Net) : MxNId(Net.MxNId), MxEId(Net.MxEId), NodeH(Net.NodeH), EdgeH(Net.EdgeH) { } 01158 TNodeEdgeNet(TSIn& SIn) : MxNId(SIn), MxEId(SIn), NodeH(SIn), EdgeH(SIn) { } 01159 virtual ~TNodeEdgeNet() { } 01161 virtual void Save(TSOut& SOut) const { MxNId.Save(SOut); MxEId.Save(SOut); NodeH.Save(SOut); EdgeH.Save(SOut); } 01163 static PNet New() { return PNet(new TNet()); } 01165 static PNet Load(TSIn& SIn) { return PNet(new TNet(SIn)); } 01167 bool HasFlag(const TGraphFlag& Flag) const; 01168 TNodeEdgeNet& operator = (const TNodeEdgeNet& Net) { 01169 if (this!=&Net) { NodeH=Net.NodeH; EdgeH=Net.EdgeH; MxNId=Net.MxNId; MxEId=Net.MxEId; } return *this; } 01170 // nodes 01172 int GetNodes() const { return NodeH.Len(); } 01174 01178 int AddNode(int NId = -1); 01180 01184 int AddNode(int NId, const TNodeData& NodeDat); 01186 int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId(), NodeId.GetDat()); } 01188 01190 void DelNode(const int& NId); 01192 void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); } 01194 bool IsNode(const int& NId) const { return NodeH.IsKey(NId); } 01196 TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); } 01198 TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); } 01200 TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); } 01202 void SetNDat(const int& NId, const TNodeData& NodeDat); 01204 TNodeData& GetNDat(const int& NId) { return NodeH.GetDat(NId).NodeDat; } 01206 const TNodeData& GetNDat(const int& NId) const { return NodeH.GetDat(NId).NodeDat; } 01208 int GetMxNId() const { return MxNId; } 01209 01210 // edges 01212 int GetEdges() const { return EdgeH.Len(); } 01214 int GetUniqEdges(const bool& IsDir=true) const; 01216 01221 int AddEdge(const int& SrcNId, const int& DstNId, int EId = -1); 01223 01228 int AddEdge(const int& SrcNId, const int& DstNId, int EId, const TEdgeData& EdgeDat); 01230 int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), EdgeI.GetId(), EdgeI.GetDat()); } 01232 void DelEdge(const int& EId); 01234 01238 void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true); 01240 bool IsEdge(const int& EId) const { return EdgeH.IsKey(EId); } 01242 bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const { int EId; return IsEdge(SrcNId, DstNId, EId, IsDir); } 01244 bool IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir = true) const; 01245 int GetEId(const int& SrcNId, const int& DstNId) const { int EId; return IsEdge(SrcNId, DstNId, EId)?EId:-1; } 01247 TEdgeI BegEI() const { return TEdgeI(EdgeH.BegI(), this); } 01249 TEdgeI EndEI() const { return TEdgeI(EdgeH.EndI(), this); } 01250 // TODO document TNodeEdgeNet::GetEI() 01251 TEdgeI GetEI(const int& EId) const { return TEdgeI(EdgeH.GetI(EId), this); } 01252 // TODO document TNodeEdgeNet::GetEI() 01253 TEdgeI GetEI(const int& SrcNId, const int& DstNId) const { return GetEI(GetEId(SrcNId, DstNId)); } 01255 void SetEDat(const int& EId, const TEdgeData& EdgeDat); 01257 TEdgeData& GetEDat(const int& EId) { return EdgeH.GetDat(EId).EdgeDat; } 01259 const TEdgeData& GetEDat(const int& EId) const { return EdgeH.GetDat(EId).EdgeDat; } 01261 void SetAllEDat(const TEdgeData& EdgeDat); 01262 01264 int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); } 01266 TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); } 01268 int GetRndEId(TRnd& Rnd=TInt::Rnd) { return EdgeH.GetKey(EdgeH.GetRndKeyId(Rnd, 0.8)); } 01270 TEdgeI GetRndEI(TRnd& Rnd=TInt::Rnd) { return GetEI(GetRndEId(Rnd)); } 01272 void GetNIdV(TIntV& NIdV) const; 01274 void GetEIdV(TIntV& EIdV) const; 01275 01277 bool Empty() const { return GetNodes()==0; } 01279 void Clr() { MxNId=0; MxEId=0; NodeH.Clr(); EdgeH.Clr(); } 01281 void Reserve(const int& Nodes, const int& Edges) { 01282 if (Nodes>0) { NodeH.Gen(Nodes/2); } if (Edges>0) { EdgeH.Gen(Edges/2); } } 01284 void SortNIdById(const bool& Asc=true) { NodeH.SortByKey(Asc); } 01286 void SortNIdByDat(const bool& Asc=true) { NodeH.SortByDat(Asc); } 01288 void SortEIdById(const bool& Asc=true) { EdgeH.SortByKey(Asc); } 01290 void SortEIdByDat(const bool& Asc=true) { EdgeH.SortByDat(Asc); } 01292 01297 void Defrag(const bool& OnlyNodeLinks=false); 01299 01302 bool IsOk(const bool& ThrowExcept=true) const; 01303 01304 friend class TPt<TNodeEdgeNet<TNodeData, TEdgeData> >; 01305 }; 01306 01307 // set flags 01308 namespace TSnap { 01309 template <class TNodeData, class TEdgeData> struct IsMultiGraph<TNodeEdgeNet<TNodeData, TEdgeData> > { enum { Val = 1 }; }; 01310 template <class TNodeData, class TEdgeData> struct IsDirected<TNodeEdgeNet<TNodeData, TEdgeData> > { enum { Val = 1 }; }; 01311 template <class TNodeData, class TEdgeData> struct IsNodeDat<TNodeEdgeNet<TNodeData, TEdgeData> > { enum { Val = 1 }; }; 01312 template <class TNodeData, class TEdgeData> struct IsEdgeDat<TNodeEdgeNet<TNodeData, TEdgeData> > { enum { Val = 1 }; }; 01313 } 01314 01315 template <class TNodeData, class TEdgeData> 01316 bool TNodeEdgeNet<TNodeData, TEdgeData>::HasFlag(const TGraphFlag& Flag) const { 01317 return HasGraphFlag(typename TNet, Flag); 01318 } 01319 01320 template <class TNodeData, class TEdgeData> 01321 bool TNodeEdgeNet<TNodeData, TEdgeData>::TNodeI::IsInNId(const int& NId) const { 01322 const TNode& Node = NodeHI.GetDat(); 01323 for (int edge = 0; edge < Node.GetInDeg(); edge++) { 01324 if (NId == Net->GetEdge(Node.GetInEId(edge)).GetSrcNId()) 01325 return true; 01326 } 01327 return false; 01328 } 01329 01330 template <class TNodeData, class TEdgeData> 01331 bool TNodeEdgeNet<TNodeData, TEdgeData>::TNodeI::IsOutNId(const int& NId) const { 01332 const TNode& Node = NodeHI.GetDat(); 01333 for (int edge = 0; edge < Node.GetOutDeg(); edge++) { 01334 if (NId == Net->GetEdge(Node.GetOutEId(edge)).GetDstNId()) 01335 return true; 01336 } 01337 return false; 01338 } 01339 01340 template <class TNodeData, class TEdgeData> 01341 int TNodeEdgeNet<TNodeData, TEdgeData>::AddNode(int NId) { 01342 if (NId == -1) { 01343 NId = MxNId; MxNId++; 01344 } else { 01345 IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId)); 01346 MxNId = TMath::Mx(NId+1, MxNId()); 01347 } 01348 NodeH.AddDat(NId, TNode(NId)); 01349 return NId; 01350 } 01351 01352 template <class TNodeData, class TEdgeData> 01353 int TNodeEdgeNet<TNodeData, TEdgeData>::AddNode(int NId, const TNodeData& NodeDat) { 01354 if (NId == -1) { 01355 NId = MxNId; MxNId++; 01356 } else { 01357 IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId)); 01358 MxNId = TMath::Mx(NId+1, MxNId()); 01359 } 01360 NodeH.AddDat(NId, TNode(NId, NodeDat)); 01361 return NId; 01362 } 01363 01364 template <class TNodeData, class TEdgeData> 01365 void TNodeEdgeNet<TNodeData, TEdgeData>::DelNode(const int& NId) { 01366 const TNode& Node = GetNode(NId); 01367 for (int out = 0; out < Node.GetOutDeg(); out++) { 01368 const int EId = Node.GetOutEId(out); 01369 const TEdge& Edge = GetEdge(EId); 01370 IAssert(Edge.GetSrcNId() == NId); 01371 GetNode(Edge.GetDstNId()).InEIdV.DelIfIn(EId); 01372 EdgeH.DelKey(EId); 01373 } 01374 for (int in = 0; in < Node.GetInDeg(); in++) { 01375 const int EId = Node.GetInEId(in); 01376 const TEdge& Edge = GetEdge(EId); 01377 IAssert(Edge.GetDstNId() == NId); 01378 GetNode(Edge.GetSrcNId()).OutEIdV.DelIfIn(EId); 01379 EdgeH.DelKey(EId); 01380 } 01381 NodeH.DelKey(NId); 01382 } 01383 01384 template <class TNodeData, class TEdgeData> 01385 void TNodeEdgeNet<TNodeData, TEdgeData>::SetNDat(const int& NId, const TNodeData& NodeDat) { 01386 IAssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist.", NId).CStr()); 01387 NodeH.GetDat(NId).NodeDat = NodeDat; 01388 } 01389 01390 template <class TNodeData, class TEdgeData> 01391 int TNodeEdgeNet<TNodeData, TEdgeData>::GetUniqEdges(const bool& IsDir) const { 01392 TIntPrSet UniqESet(GetEdges()); 01393 for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) { 01394 const int Src = EI.GetSrcNId(); 01395 const int Dst = EI.GetDstNId(); 01396 if (IsDir) { UniqESet.AddKey(TIntPr(Src, Dst)); } 01397 else { UniqESet.AddKey(TIntPr(TMath::Mn(Src, Dst), TMath::Mx(Src, Dst))); } 01398 } 01399 return UniqESet.Len(); 01400 } 01401 01402 template <class TNodeData, class TEdgeData> 01403 int TNodeEdgeNet<TNodeData, TEdgeData>::AddEdge(const int& SrcNId, const int& DstNId, int EId) { 01404 if (EId == -1) { EId = MxEId; MxEId++; } 01405 else { MxEId = TMath::Mx(EId+1, MxEId()); } 01406 IAssertR(!IsEdge(EId), TStr::Fmt("EdgeId %d already exists", EId)); 01407 IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr()); 01408 EdgeH.AddDat(EId, TEdge(EId, SrcNId, DstNId)); 01409 GetNode(SrcNId).OutEIdV.AddSorted(EId); 01410 GetNode(DstNId).InEIdV.AddSorted(EId); 01411 return EId; 01412 } 01413 01414 template <class TNodeData, class TEdgeData> 01415 int TNodeEdgeNet<TNodeData, TEdgeData>::AddEdge(const int& SrcNId, const int& DstNId, int EId, const TEdgeData& EdgeDat) { 01416 if (EId == -1) { EId = MxEId; MxEId++; } 01417 else { MxEId = TMath::Mx(EId+1, MxEId()); } 01418 IAssertR(!IsEdge(EId), TStr::Fmt("EdgeId %d already exists", EId)); 01419 IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr()); 01420 EdgeH.AddDat(EId, TEdge(EId, SrcNId, DstNId, EdgeDat)); 01421 GetNode(SrcNId).OutEIdV.AddSorted(EId); 01422 GetNode(DstNId).InEIdV.AddSorted(EId); 01423 return EId; 01424 } 01425 01426 template <class TNodeData, class TEdgeData> 01427 void TNodeEdgeNet<TNodeData, TEdgeData>::DelEdge(const int& EId) { 01428 IAssert(IsEdge(EId)); 01429 const int SrcNId = GetEdge(EId).GetSrcNId(); 01430 const int DstNId = GetEdge(EId).GetDstNId(); 01431 GetNode(SrcNId).OutEIdV.DelIfIn(EId); 01432 GetNode(DstNId).InEIdV.DelIfIn(EId); 01433 EdgeH.DelKey(EId); 01434 } 01435 01436 template <class TNodeData, class TEdgeData> 01437 void TNodeEdgeNet<TNodeData, TEdgeData>::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) { 01438 int EId; 01439 IAssert(IsEdge(SrcNId, DstNId, EId, IsDir)); 01440 GetNode(SrcNId).OutEIdV.DelIfIn(EId); 01441 GetNode(DstNId).InEIdV.DelIfIn(EId); 01442 EdgeH.DelKey(EId); 01443 } 01444 01445 template <class TNodeData, class TEdgeData> 01446 bool TNodeEdgeNet<TNodeData, TEdgeData>::IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir) const { 01447 if (! IsNode(SrcNId)) { return false; } 01448 if (! IsNode(DstNId)) { return false; } 01449 const TNode& SrcNode = GetNode(SrcNId); 01450 for (int edge = 0; edge < SrcNode.GetOutDeg(); edge++) { 01451 const TEdge& Edge = GetEdge(SrcNode.GetOutEId(edge)); 01452 if (DstNId == Edge.GetDstNId()) { 01453 EId = Edge.GetId(); return true; } 01454 } 01455 if (! IsDir) { 01456 for (int edge = 0; edge < SrcNode.GetInDeg(); edge++) { 01457 const TEdge& Edge = GetEdge(SrcNode.GetInEId(edge)); 01458 if (DstNId == Edge.GetSrcNId()) { 01459 EId = Edge.GetId(); return true; } 01460 } 01461 } 01462 return false; 01463 } 01464 01465 template <class TNodeData, class TEdgeData> 01466 void TNodeEdgeNet<TNodeData, TEdgeData>::SetEDat(const int& EId, const TEdgeData& EdgeDat) { 01467 IAssertR(IsEdge(EId), TStr::Fmt("EdgeId %d does not exist.", EId).CStr()); 01468 GetEI(EId).GetDat() = EdgeDat; 01469 } 01470 01471 template <class TNodeData, class TEdgeData> 01472 void TNodeEdgeNet<TNodeData, TEdgeData>::SetAllEDat(const TEdgeData& EdgeDat) { 01473 for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) { 01474 EI() = EdgeDat; 01475 } 01476 } 01477 01478 01479 template <class TNodeData, class TEdgeData> 01480 void TNodeEdgeNet<TNodeData, TEdgeData>::GetNIdV(TIntV& NIdV) const { 01481 NIdV.Gen(GetNodes(), 0); 01482 for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N);) { 01483 NIdV.Add(NodeH.GetKey(N)); 01484 } 01485 } 01486 01487 template <class TNodeData, class TEdgeData> 01488 void TNodeEdgeNet<TNodeData, TEdgeData>::GetEIdV(TIntV& EIdV) const { 01489 EIdV.Gen(GetEdges(), 0); 01490 for (int E=EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E);) { 01491 EIdV.Add(EdgeH.GetKey(E)); 01492 } 01493 } 01494 01495 template <class TNodeData, class TEdgeData> 01496 void TNodeEdgeNet<TNodeData, TEdgeData>::Defrag(const bool& OnlyNodeLinks) { 01497 for (int kid = NodeH.FFirstKeyId(); NodeH.FNextKeyId(kid);) { 01498 TNode& Node = NodeH[kid]; 01499 Node.InEIdV.Pack(); Node.OutEIdV.Pack(); 01500 } 01501 if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); } 01502 if (! OnlyNodeLinks && ! EdgeH.IsKeyIdEqKeyN()) { EdgeH.Defrag(); } 01503 } 01504 01505 template <class TNodeData, class TEdgeData> 01506 bool TNodeEdgeNet<TNodeData, TEdgeData>::IsOk(const bool& ThrowExcept) const { 01507 bool RetVal = true; 01508 for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) { 01509 const TNode& Node = NodeH[N]; 01510 if (! Node.OutEIdV.IsSorted()) { 01511 const TStr Msg = TStr::Fmt("Out-edge list of node %d is not sorted.", Node.GetId()); 01512 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 01513 } 01514 if (! Node.InEIdV.IsSorted()) { 01515 const TStr Msg = TStr::Fmt("In-edge list of node %d is not sorted.", Node.GetId()); 01516 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 01517 } 01518 // check out-edge ids 01519 int prevEId = -1; 01520 for (int e = 0; e < Node.GetOutDeg(); e++) { 01521 if (! IsEdge(Node.GetOutEId(e))) { 01522 const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.", Node.GetOutEId(e), Node.GetId()); 01523 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 01524 } 01525 if (e > 0 && prevEId == Node.GetOutEId(e)) { 01526 const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetOutEId(e)); 01527 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 01528 } 01529 prevEId = Node.GetOutEId(e); 01530 } 01531 // check in-edge ids 01532 prevEId = -1; 01533 for (int e = 0; e < Node.GetInDeg(); e++) { 01534 if (! IsEdge(Node.GetInEId(e))) { 01535 const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.", Node.GetInEId(e), Node.GetId()); 01536 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 01537 } 01538 if (e > 0 && prevEId == Node.GetInEId(e)) { 01539 const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetInEId(e)); 01540 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 01541 } 01542 prevEId = Node.GetInEId(e); 01543 } 01544 } 01545 for (int E = EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E); ) { 01546 const TEdge& Edge = EdgeH[E]; 01547 if (! IsNode(Edge.GetSrcNId())) { 01548 const TStr Msg = TStr::Fmt("Edge %d source node %d does not exist.", Edge.GetId(), Edge.GetSrcNId()); 01549 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 01550 } 01551 if (! IsNode(Edge.GetDstNId())) { 01552 const TStr Msg = TStr::Fmt("Edge %d destination node %d does not exist.", Edge.GetId(), Edge.GetDstNId()); 01553 if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; 01554 } 01555 } 01556 return RetVal; 01557 } 01558 01560 // Common Node-Edge Network Types 01561 typedef TNodeEdgeNet<TInt, TInt> TIntNENet; 01562 typedef TPt<TIntNENet> PIntNENet; 01563 typedef TNodeEdgeNet<TFlt, TFlt> TFltNENet; 01564 typedef TPt<TFltNENet> PFltNENet;
1.8.0 
