SNAP Library , Developer Reference  2013-01-07 14:03:36
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
graph.cpp
Go to the documentation of this file.
00001 
00002 // Undirected Graph
00003 bool TUNGraph::HasFlag(const TGraphFlag& Flag) const {
00004   return HasGraphFlag(TUNGraph::TNet, Flag);
00005 }
00006 
00007 // Add a node of ID NId to the graph.
00008 int TUNGraph::AddNode(int NId) {
00009   if (NId == -1) {
00010     NId = MxNId;  MxNId++;
00011   } else {
00012     IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
00013     MxNId = TMath::Mx(NId+1, MxNId());
00014   }
00015   NodeH.AddDat(NId, TNode(NId));
00016   return NId;
00017 }
00018 
00019 // Add a node of ID NId to the graph and create edges to all nodes in vector NbrNIdV.
00020 int TUNGraph::AddNode(const int& NId, const TIntV& NbrNIdV) {
00021   int NewNId;
00022   if (NId == -1) {
00023     NewNId = MxNId;  MxNId++;
00024   } else {
00025     IAssertR(! IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
00026     NewNId = NId;
00027     MxNId = TMath::Mx(NewNId+1, MxNId());
00028   }
00029   TNode& Node = NodeH.AddDat(NewNId);
00030   Node.Id = NewNId;
00031   Node.NIdV = NbrNIdV;
00032   Node.NIdV.Sort();
00033   NEdges += Node.GetDeg();
00034   return NewNId;
00035 }
00036 
00037 // Add a node of ID NId to the graph and create edges to all nodes in the vector NIdVId in the vector pool Pool).
00038 int TUNGraph::AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& NIdVId) {
00039   int NewNId;
00040   if (NId == -1) {
00041     NewNId = MxNId;  MxNId++;
00042   } else {
00043     IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
00044     NewNId = NId;
00045     MxNId = TMath::Mx(NewNId+1, MxNId());
00046   }
00047   TNode& Node = NodeH.AddDat(NewNId);
00048   Node.Id = NewNId;
00049   Node.NIdV.GenExt(Pool.GetValVPt(NIdVId), Pool.GetVLen(NIdVId));
00050   Node.NIdV.Sort();
00051   NEdges += Node.GetDeg();
00052   return NewNId;
00053 }
00054 
00055 // Delete node of ID NId from the graph.
00056 void TUNGraph::DelNode(const int& NId) {
00057   { AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
00058   TNode& Node = GetNode(NId);
00059   NEdges -= Node.GetDeg();
00060   for (int e = 0; e < Node.GetDeg(); e++) {
00061     const int nbr = Node.GetNbrNId(e);
00062     if (nbr == NId) { continue; }
00063     TNode& N = GetNode(nbr);
00064     const int n = N.NIdV.SearchBin(NId);
00065     IAssert(n != -1); // if NId points to N, then N also should point back
00066     if (n!= -1) { N.NIdV.Del(n); }
00067   } }
00068   NodeH.DelKey(NId);
00069 }
00070 
00071 int TUNGraph::GetEdges() const {
00072   //int Edges = 0;
00073   //for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00074   //  Edges += NodeH[N].GetDeg();
00075   //}
00076   //return Edges/2;
00077   return NEdges;
00078 }
00079 
00080 // Add an edge between SrcNId and DstNId to the graph.
00081 int TUNGraph::AddEdge(const int& SrcNId, const int& DstNId) {
00082   IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
00083   if (IsEdge(SrcNId, DstNId)) { return -2; } // edge already exists
00084   GetNode(SrcNId).NIdV.AddSorted(DstNId);
00085   if (SrcNId!=DstNId) { // not a self edge
00086     GetNode(DstNId).NIdV.AddSorted(SrcNId); }
00087   NEdges++;
00088   return -1; // edge id
00089 }
00090 
00091 // Delete an edge between node IDs SrcNId and DstNId from the graph.
00092 void TUNGraph::DelEdge(const int& SrcNId, const int& DstNId) {
00093   IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
00094   { TNode& N = GetNode(SrcNId);
00095   const int n = N.NIdV.SearchBin(DstNId);
00096   if (n!= -1) { N.NIdV.Del(n);  NEdges--; } }
00097   if (SrcNId != DstNId) { // not a self edge
00098     TNode& N = GetNode(DstNId);
00099     const int n = N.NIdV.SearchBin(SrcNId);
00100     if (n!= -1) { N.NIdV.Del(n); }
00101   }
00102 }
00103 
00104 // Test whether an edge between node IDs SrcNId and DstNId exists the graph.
00105 bool TUNGraph::IsEdge(const int& SrcNId, const int& DstNId) const {
00106   if (! IsNode(SrcNId) || ! IsNode(DstNId)) return false;
00107   return GetNode(SrcNId).IsNbrNId(DstNId);
00108 }
00109 
00110 // Return an iterator referring to edge (SrcNId, DstNId) in the graph.
00111 TUNGraph::TEdgeI TUNGraph::GetEI(const int& SrcNId, const int& DstNId) const {
00112   const int MnNId = TMath::Mn(SrcNId, DstNId);
00113   const int MxNId = TMath::Mx(SrcNId, DstNId);
00114   const TNodeI SrcNI = GetNI(MnNId);
00115   const int NodeN = SrcNI.NodeHI.GetDat().NIdV.SearchBin(MxNId);
00116   IAssert(NodeN != -1);
00117   return TEdgeI(SrcNI, EndNI(), NodeN);
00118 }
00119 
00120 
00121 // Get a vector IDs of all nodes in the graph.
00122 void TUNGraph::GetNIdV(TIntV& NIdV) const {
00123   NIdV.Gen(GetNodes(), 0);
00124   for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00125     NIdV.Add(NodeH.GetKey(N)); }
00126 }
00127 
00128 // Defragment the graph.
00129 void TUNGraph::Defrag(const bool& OnlyNodeLinks) {
00130   for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
00131     NodeH[n].NIdV.Pack();
00132   }
00133   if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
00134     NodeH.Defrag();
00135   }
00136 }
00137 
00138 // Check the graph data structure for internal consistency.
00139 bool TUNGraph::IsOk(const bool& ThrowExcept) const {
00140   bool RetVal = true;
00141   for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00142     const TNode& Node = NodeH[N];
00143     if (! Node.NIdV.IsSorted()) {
00144       const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", Node.GetId());
00145       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
00146       RetVal=false;
00147     }
00148     int prevNId = -1;
00149     for (int e = 0; e < Node.GetDeg(); e++) {
00150       if (! IsNode(Node.GetNbrNId(e))) {
00151         const TStr Msg = TStr::Fmt("Edge %d --> %d: node %d does not exist.",
00152           Node.GetId(), Node.GetNbrNId(e), Node.GetNbrNId(e));
00153         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
00154         RetVal=false;
00155       }
00156       if (e > 0 && prevNId == Node.GetNbrNId(e)) {
00157         const TStr Msg = TStr::Fmt("Node %d has duplicate edge %d --> %d.",
00158           Node.GetId(), Node.GetId(), Node.GetNbrNId(e));
00159         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
00160         RetVal=false;
00161       }
00162       prevNId = Node.GetNbrNId(e);
00163     }
00164   }
00165   int EdgeCnt = 0;
00166   for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) { EdgeCnt++; }
00167   if (EdgeCnt != GetEdges()) {
00168     const TStr Msg = TStr::Fmt("Number of edges counter is corrupted: GetEdges():%d, EdgeCount:%d.", GetEdges(), EdgeCnt);
00169     if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
00170     RetVal=false;
00171   }
00172   return RetVal;
00173 }
00174 
00175 // Print the graph in a human readable form to an output stream OutF.
00176 void TUNGraph::Dump(FILE *OutF) const {
00177   const int NodePlaces = (int) ceil(log10((double) GetNodes()));
00178   fprintf(OutF, "-------------------------------------------------\nUndirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
00179   for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00180     const TNode& Node = NodeH[N];
00181     fprintf(OutF, "  %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
00182     for (int edge = 0; edge < Node.GetDeg(); edge++) {
00183       fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
00184     fprintf(OutF, "\n");
00185   }
00186   fprintf(OutF, "\n");
00187 }
00188 
00189 // Return a small graph on 5 nodes and 5 edges.
00190 PUNGraph TUNGraph::GetSmallGraph() {
00191   PUNGraph Graph = TUNGraph::New();
00192   for (int i = 0; i < 5; i++) { Graph->AddNode(i); }
00193   Graph->AddEdge(0,1);  Graph->AddEdge(0,2);
00194   Graph->AddEdge(0,3);  Graph->AddEdge(0,4);
00195   Graph->AddEdge(1,2);
00196   return Graph;
00197 }
00198 
00200 // Directed Node Graph
00201 bool TNGraph::HasFlag(const TGraphFlag& Flag) const {
00202   return HasGraphFlag(TNGraph::TNet, Flag);
00203 }
00204 
00205 int TNGraph::AddNode(int NId) {
00206   if (NId == -1) {
00207     NId = MxNId;  MxNId++;
00208   } else {
00209     IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
00210     MxNId = TMath::Mx(NId+1, MxNId());
00211   }
00212   NodeH.AddDat(NId, TNode(NId));
00213   return NId;
00214 }
00215 
00216 // add a node with a list of neighbors
00217 // (use TNGraph::IsOk to check whether the graph is consistent)
00218 int TNGraph::AddNode(const int& NId, const TIntV& InNIdV, const TIntV& OutNIdV) {
00219   int NewNId;
00220   if (NId == -1) {
00221     NewNId = MxNId;  MxNId++;
00222   } else {
00223     IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
00224     NewNId = NId;
00225     MxNId = TMath::Mx(NewNId+1, MxNId());
00226   }
00227   TNode& Node = NodeH.AddDat(NewNId);
00228   Node.Id = NewNId;
00229   Node.InNIdV = InNIdV;
00230   Node.OutNIdV = OutNIdV;
00231   Node.InNIdV.Sort();
00232   Node.OutNIdV.Sort();
00233   return NewNId;
00234 }
00235 
00236 // add a node from a vector pool
00237 // (use TNGraph::IsOk to check whether the graph is consistent)
00238 int TNGraph::AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& SrcVId, const int& DstVId) {
00239   int NewNId;
00240   if (NId == -1) {
00241     NewNId = MxNId;  MxNId++;
00242   } else {
00243     IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
00244     NewNId = NId;
00245     MxNId = TMath::Mx(NewNId+1, MxNId());
00246   }
00247   TNode& Node = NodeH.AddDat(NewNId);
00248   Node.Id = NewNId;
00249   Node.InNIdV.GenExt(Pool.GetValVPt(SrcVId), Pool.GetVLen(SrcVId));
00250   Node.OutNIdV.GenExt(Pool.GetValVPt(DstVId), Pool.GetVLen(DstVId));
00251   Node.InNIdV.Sort();
00252   Node.OutNIdV.Sort();
00253   return NewNId;
00254 }
00255 
00256 void TNGraph::DelNode(const int& NId) {
00257   { TNode& Node = GetNode(NId);
00258   for (int e = 0; e < Node.GetOutDeg(); e++) {
00259   const int nbr = Node.GetOutNId(e);
00260   if (nbr == NId) { continue; }
00261     TNode& N = GetNode(nbr);
00262     const int n = N.InNIdV.SearchBin(NId);
00263     if (n!= -1) { N.InNIdV.Del(n); }
00264   }
00265   for (int e = 0; e < Node.GetInDeg(); e++) {
00266   const int nbr = Node.GetInNId(e);
00267   if (nbr == NId) { continue; }
00268     TNode& N = GetNode(nbr);
00269     const int n = N.OutNIdV.SearchBin(NId);
00270     if (n!= -1) { N.OutNIdV.Del(n); }
00271   } }
00272   NodeH.DelKey(NId);
00273 }
00274 
00275 int TNGraph::GetEdges() const {
00276   int edges=0;
00277   for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00278     edges+=NodeH[N].GetOutDeg();
00279   }
00280   return edges;
00281 }
00282 
00283 int TNGraph::AddEdge(const int& SrcNId, const int& DstNId) {
00284   IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
00285   //IAssert(! IsEdge(SrcNId, DstNId));
00286   if (IsEdge(SrcNId, DstNId)) { return -2; }
00287   GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
00288   GetNode(DstNId).InNIdV.AddSorted(SrcNId);
00289   return -1; // edge id
00290 }
00291 
00292 void TNGraph::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) {
00293   IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
00294   { TNode& N = GetNode(SrcNId);
00295   const int n = N.OutNIdV.SearchBin(DstNId);
00296   if (n!= -1) { N.OutNIdV.Del(n); } }
00297   { TNode& N = GetNode(DstNId);
00298   const int n = N.InNIdV.SearchBin(SrcNId);
00299   if (n!= -1) { N.InNIdV.Del(n); } }
00300   if (! IsDir) {
00301     { TNode& N = GetNode(SrcNId);
00302     const int n = N.InNIdV.SearchBin(DstNId);
00303     if (n!= -1) { N.InNIdV.Del(n); } }
00304     { TNode& N = GetNode(DstNId);
00305     const int n = N.OutNIdV.SearchBin(SrcNId);
00306     if (n!= -1) { N.OutNIdV.Del(n); } }
00307   }
00308 }
00309 
00310 bool TNGraph::IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) const {
00311   if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
00312   if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
00313   else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
00314 }
00315 
00316 TNGraph::TEdgeI TNGraph::GetEI(const int& SrcNId, const int& DstNId) const {
00317   const TNodeI SrcNI = GetNI(SrcNId);
00318   const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
00319   IAssert(NodeN != -1);
00320   return TEdgeI(SrcNI, EndNI(), NodeN);
00321 }
00322 
00323 void TNGraph::GetNIdV(TIntV& NIdV) const {
00324   NIdV.Gen(GetNodes(), 0);
00325   for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00326     NIdV.Add(NodeH.GetKey(N)); }
00327 }
00328 
00329 void TNGraph::Defrag(const bool& OnlyNodeLinks) {
00330   for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
00331     TNode& Node = NodeH[n];
00332     Node.InNIdV.Pack();  Node.OutNIdV.Pack();
00333   }
00334   if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); }
00335 }
00336 
00337 // for each node check that their neighbors are also nodes
00338 bool TNGraph::IsOk(const bool& ThrowExcept) const {
00339   bool RetVal = true;
00340   for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00341     const TNode& Node = NodeH[N];
00342     if (! Node.OutNIdV.IsSorted()) {
00343       const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId());
00344       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00345     }
00346     if (! Node.InNIdV.IsSorted()) {
00347       const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId());
00348       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00349     }
00350     // check out-edges
00351     int prevNId = -1;
00352     for (int e = 0; e < Node.GetOutDeg(); e++) {
00353       if (! IsNode(Node.GetOutNId(e))) {
00354         const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.",
00355           Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e));
00356         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00357       }
00358       if (e > 0 && prevNId == Node.GetOutNId(e)) {
00359         const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.",
00360           Node.GetId(), Node.GetId(), Node.GetOutNId(e));
00361         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00362       }
00363       prevNId = Node.GetOutNId(e);
00364     }
00365     // check in-edges
00366     prevNId = -1;
00367     for (int e = 0; e < Node.GetInDeg(); e++) {
00368       if (! IsNode(Node.GetInNId(e))) {
00369         const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.",
00370           Node.GetId(), Node.GetInNId(e), Node.GetInNId(e));
00371         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00372       }
00373       if (e > 0 && prevNId == Node.GetInNId(e)) {
00374         const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.",
00375           Node.GetId(), Node.GetId(), Node.GetInNId(e));
00376         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00377       }
00378       prevNId = Node.GetInNId(e);
00379     }
00380   }
00381   return RetVal;
00382 }
00383 
00384 void TNGraph::Dump(FILE *OutF) const {
00385   const int NodePlaces = (int) ceil(log10((double) GetNodes()));
00386   fprintf(OutF, "-------------------------------------------------\nDirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
00387   for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00388     const TNode& Node = NodeH[N];
00389     fprintf(OutF, "  %*d]\n", NodePlaces, Node.GetId());
00390     fprintf(OutF, "    in [%d]", Node.GetInDeg());
00391     for (int edge = 0; edge < Node.GetInDeg(); edge++) {
00392       fprintf(OutF, " %*d", NodePlaces, Node.GetInNId(edge)); }
00393     fprintf(OutF, "\n    out[%d]", Node.GetOutDeg());
00394     for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
00395       fprintf(OutF, " %*d", NodePlaces, Node.GetOutNId(edge)); }
00396     fprintf(OutF, "\n");
00397   }
00398   fprintf(OutF, "\n");
00399 }
00400 
00401 PNGraph TNGraph::GetSmallGraph() {
00402   PNGraph G = TNGraph::New();
00403   for (int i = 0; i < 5; i++) { G->AddNode(i); }
00404   G->AddEdge(0,1); G->AddEdge(1,2); G->AddEdge(0,2);
00405   G->AddEdge(1,3);
00406   G->AddEdge(3,4);
00407   G->AddEdge(2,3);
00408   return G;
00409 }
00410 
00412 // Node Edge Graph
00413 bool TNEGraph::HasFlag(const TGraphFlag& Flag) const {
00414   return HasGraphFlag(TNEGraph::TNet, Flag);
00415 }
00416 
00417 bool TNEGraph::TNodeI::IsInNId(const int& NId) const {
00418   const TNode& Node = NodeHI.GetDat();
00419   for (int edge = 0; edge < Node.GetInDeg(); edge++) {
00420     if (NId == Graph->GetEdge(Node.GetInEId(edge)).GetSrcNId())
00421       return true;
00422   }
00423   return false;
00424 }
00425 
00426 bool TNEGraph::TNodeI::IsOutNId(const int& NId) const {
00427   const TNode& Node = NodeHI.GetDat();
00428   for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
00429     if (NId == Graph->GetEdge(Node.GetOutEId(edge)).GetDstNId())
00430       return true;
00431   }
00432   return false;
00433 }
00434 
00435 int TNEGraph::AddNode(int NId) {
00436   if (NId == -1) {
00437     NId = MxNId;  MxNId++;
00438   } else {
00439     IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
00440     MxNId = TMath::Mx(NId+1, MxNId());
00441   }
00442   NodeH.AddDat(NId, TNode(NId));
00443   return NId;
00444 }
00445 
00446 void TNEGraph::DelNode(const int& NId) {
00447   const TNode& Node = GetNode(NId);
00448   for (int out = 0; out < Node.GetOutDeg(); out++) {
00449     const int EId = Node.GetOutEId(out);
00450     const TEdge& Edge = GetEdge(EId);
00451     IAssert(Edge.GetSrcNId() == NId);
00452     GetNode(Edge.GetDstNId()).InEIdV.DelIfIn(EId);
00453     EdgeH.DelKey(EId);
00454   }
00455   for (int in = 0; in < Node.GetInDeg(); in++) {
00456     const int EId = Node.GetInEId(in);
00457     const TEdge& Edge = GetEdge(EId);
00458     IAssert(Edge.GetDstNId() == NId);
00459     GetNode(Edge.GetSrcNId()).OutEIdV.DelIfIn(EId);
00460     EdgeH.DelKey(EId);
00461   }
00462   NodeH.DelKey(NId);
00463 }
00464 
00465 int TNEGraph::AddEdge(const int& SrcNId, const int& DstNId, int EId) {
00466   if (EId == -1) { EId = MxEId;  MxEId++; }
00467   else { MxEId = TMath::Mx(EId+1, MxEId()); }
00468   IAssertR(!IsEdge(EId), TStr::Fmt("EdgeId %d already exists", EId));
00469   IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
00470   EdgeH.AddDat(EId, TEdge(EId, SrcNId, DstNId));
00471   GetNode(SrcNId).OutEIdV.AddSorted(EId);
00472   GetNode(DstNId).InEIdV.AddSorted(EId);
00473   return EId;
00474 }
00475 
00476 void TNEGraph::DelEdge(const int& EId) {
00477   IAssert(IsEdge(EId));
00478   const int SrcNId = GetEdge(EId).GetSrcNId();
00479   const int DstNId = GetEdge(EId).GetDstNId();
00480   GetNode(SrcNId).OutEIdV.DelIfIn(EId);
00481   GetNode(DstNId).InEIdV.DelIfIn(EId);
00482   EdgeH.DelKey(EId);
00483 }
00484 
00485 // delete all edges between the two nodes
00486 void TNEGraph::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) {
00487   int EId;
00488   IAssert(IsEdge(SrcNId, DstNId, EId, IsDir)); // there is at least one edge
00489   while (IsEdge(SrcNId, DstNId, EId, IsDir)) {
00490     GetNode(SrcNId).OutEIdV.DelIfIn(EId);
00491     GetNode(DstNId).InEIdV.DelIfIn(EId);
00492   }
00493   EdgeH.DelKey(EId);
00494 }
00495 
00496 bool TNEGraph::IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir) const {
00497   const TNode& SrcNode = GetNode(SrcNId);
00498   for (int edge = 0; edge < SrcNode.GetOutDeg(); edge++) {
00499     const TEdge& Edge = GetEdge(SrcNode.GetOutEId(edge));
00500     if (DstNId == Edge.GetDstNId()) {
00501       EId = Edge.GetId();  return true; }
00502   }
00503   if (! IsDir) {
00504     for (int edge = 0; edge < SrcNode.GetInDeg(); edge++) {
00505     const TEdge& Edge = GetEdge(SrcNode.GetInEId(edge));
00506     if (DstNId == Edge.GetSrcNId()) {
00507       EId = Edge.GetId();  return true; }
00508     }
00509   }
00510   return false;
00511 }
00512 
00513 void TNEGraph::GetNIdV(TIntV& NIdV) const {
00514   NIdV.Gen(GetNodes(), 0);
00515   for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00516     NIdV.Add(NodeH.GetKey(N)); }
00517 }
00518 
00519 void TNEGraph::GetEIdV(TIntV& EIdV) const {
00520   EIdV.Gen(GetEdges(), 0);
00521   for (int E=EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E); ) {
00522     EIdV.Add(EdgeH.GetKey(E));
00523   }
00524 }
00525 
00526 void TNEGraph::Defrag(const bool& OnlyNodeLinks) {
00527   for (int kid = NodeH.FFirstKeyId(); NodeH.FNextKeyId(kid); ) {
00528     TNode& Node = NodeH[kid];
00529     Node.InEIdV.Pack();  Node.OutEIdV.Pack();
00530   }
00531   if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); }
00532   if (! OnlyNodeLinks && ! EdgeH.IsKeyIdEqKeyN()) { EdgeH.Defrag(); }
00533 }
00534 
00535 bool TNEGraph::IsOk(const bool& ThrowExcept) const {
00536 bool RetVal = true;
00537   for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
00538     const TNode& Node = NodeH[N];
00539     if (! Node.OutEIdV.IsSorted()) {
00540       const TStr Msg = TStr::Fmt("Out-edge list of node %d is not sorted.", Node.GetId());
00541       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00542     }
00543     if (! Node.InEIdV.IsSorted()) {
00544       const TStr Msg = TStr::Fmt("In-edge list of node %d is not sorted.", Node.GetId());
00545       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00546     }
00547     // check out-edge ids
00548     int prevEId = -1;
00549     for (int e = 0; e < Node.GetOutDeg(); e++) {
00550       if (! IsEdge(Node.GetOutEId(e))) {
00551         const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.",  Node.GetOutEId(e), Node.GetId());
00552         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00553       }
00554       if (e > 0 && prevEId == Node.GetOutEId(e)) {
00555         const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetOutEId(e));
00556         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00557       }
00558       prevEId = Node.GetOutEId(e);
00559     }
00560     // check in-edge ids
00561     prevEId = -1;
00562     for (int e = 0; e < Node.GetInDeg(); e++) {
00563       if (! IsEdge(Node.GetInEId(e))) {
00564         const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.",  Node.GetInEId(e), Node.GetId());
00565         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00566       }
00567       if (e > 0 && prevEId == Node.GetInEId(e)) {
00568         const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetInEId(e));
00569         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00570       }
00571       prevEId = Node.GetInEId(e);
00572     }
00573   }
00574   for (int E = EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E); ) {
00575     const TEdge& Edge = EdgeH[E];
00576     if (! IsNode(Edge.GetSrcNId())) {
00577       const TStr Msg = TStr::Fmt("Edge %d source node %d does not exist.", Edge.GetId(), Edge.GetSrcNId());
00578       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00579     }
00580     if (! IsNode(Edge.GetDstNId())) {
00581       const TStr Msg = TStr::Fmt("Edge %d destination node %d does not exist.", Edge.GetId(), Edge.GetDstNId());
00582       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
00583     }
00584   }
00585   return RetVal;
00586 }
00587 
00588 void TNEGraph::Dump(FILE *OutF) const {
00589   const int NodePlaces = (int) ceil(log10((double) GetNodes()));
00590   const int EdgePlaces = (int) ceil(log10((double) GetEdges()));
00591   fprintf(OutF, "-------------------------------------------------\nDirected Node-Edge Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
00592   for (TNodeI NodeI = BegNI(); NodeI < EndNI(); NodeI++) {
00593     fprintf(OutF, "  %*d]\n", NodePlaces, NodeI.GetId());
00594     fprintf(OutF, "    in[%d]", NodeI.GetInDeg());
00595     for (int edge = 0; edge < NodeI.GetInDeg(); edge++) {
00596       fprintf(OutF, " %*d", EdgePlaces, NodeI.GetInEId(edge)); }
00597     fprintf(OutF, "\n    out[%d]", NodeI.GetOutDeg());
00598     for (int edge = 0; edge < NodeI.GetOutDeg(); edge++) {
00599       fprintf(OutF, " %*d", EdgePlaces, NodeI.GetOutEId(edge)); }
00600     fprintf(OutF, "\n");
00601   }
00602   for (TEdgeI EdgeI = BegEI(); EdgeI < EndEI(); EdgeI++) {
00603     fprintf(OutF, "  %*d]  %*d  ->  %*d\n", EdgePlaces, EdgeI.GetId(), NodePlaces, EdgeI.GetSrcNId(), NodePlaces, EdgeI.GetDstNId());
00604   }
00605   fprintf(OutF, "\n");
00606 }
00607 
00609 // Bipartite graph
00610 int TBPGraph::AddNode(int NId, const bool& LeftNode) {
00611   if (NId == -1) { NId = MxNId;  MxNId++; }
00612   else if (IsLNode(NId)) { IAssertR(LeftNode, TStr::Fmt("Node with id %s already exists on the 'left'.", NId));  return NId; }
00613   else if (IsRNode(NId)) { IAssertR(! LeftNode, TStr::Fmt("Node with id %s already exists on the 'right'.", NId));  return NId; }
00614   else { MxNId = TMath::Mx(NId+1, MxNId()); }
00615   if (LeftNode) { LeftH.AddDat(NId, TNode(NId)); }
00616   else { RightH.AddDat(NId, TNode(NId)); }
00617   return NId;
00618 }
00619 
00620 // Delete node of ID NId from the bipartite graph.
00621 void TBPGraph::DelNode(const int& NId) {
00622   AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
00623   THash<TInt, TNode>& SrcH = IsLNode(NId) ? LeftH : RightH;
00624   THash<TInt, TNode>& DstH = IsLNode(NId) ? RightH : LeftH;
00625   { TNode& Node = SrcH.GetDat(NId);
00626   for (int e = 0; e < Node.GetOutDeg(); e++) {
00627     const int nbr = Node.GetOutNId(e);
00628     IAssertR(nbr != NId, "Bipartite graph has a loop!");
00629     TNode& N = DstH.GetDat(nbr);
00630     const int n = N.NIdV.SearchBin(NId);
00631     IAssert(n!= -1); 
00632     N.NIdV.Del(n);
00633   } }
00634   SrcH.DelKey(NId);
00635 }
00636 
00637 int TBPGraph::GetEdges() const {
00638   int Edges = 0;
00639   for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
00640     Edges += LeftH[N].GetDeg(); }
00641   return Edges;
00642 }
00643 
00644 int TBPGraph::AddEdge(const int& LeftNId, const int& RightNId) {
00645   const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
00646   const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
00647   IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
00648   IAssertR(LeftNId!=RightNId, "No self-edges are allowed."); 
00649   IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
00650   const int LNId = IsLL ? LeftNId : RightNId; // the real left node
00651   const int RNId = IsLL ? RightNId : LeftNId; // the real right node
00652   if (LeftH.GetDat(LNId).IsOutNId(RNId)) { return -2; } // edge already exists
00653   LeftH.GetDat(LNId).NIdV.AddSorted(RNId);
00654   RightH.GetDat(RNId).NIdV.AddSorted(LNId);
00655   return -1; // edge id
00656 }
00657 
00658 void TBPGraph::DelEdge(const int& LeftNId, const int& RightNId) {
00659   const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
00660   const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
00661   IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
00662   IAssertR(LeftNId!=RightNId, "No self-edges are allowed."); 
00663   IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
00664   const int LNId = IsLL ? LeftNId : RightNId; // the real left node
00665   const int RNId = IsLL ? RightNId : LeftNId; // the real right node
00666   { TIntV& NIdV = LeftH.GetDat(LNId).NIdV;
00667   const int n = NIdV.SearchBin(RNId);
00668   if (n != -1) { NIdV.Del(n); } }
00669   { TIntV& NIdV = RightH.GetDat(RNId).NIdV;
00670   const int n = NIdV.SearchBin(LNId);
00671   if (n != -1) { NIdV.Del(n); } }
00672 }
00673 
00674 bool TBPGraph::IsEdge(const int& LeftNId, const int& RightNId) const {
00675   if (! IsNode(LeftNId) || ! IsNode(RightNId)) { return false; }
00676   return IsLNode(LeftNId) ? LeftH.GetDat(LeftNId).IsOutNId(RightNId) : RightH.GetDat(LeftNId).IsOutNId(RightNId);
00677 }
00678 
00679 TBPGraph::TEdgeI TBPGraph::GetEI(const int& LeftNId, const int& RightNId) const {
00680   const bool IsLL = IsLNode(LeftNId), IsLR = IsRNode(LeftNId);
00681   const bool IsRL = IsLNode(RightNId), IsRR = IsRNode(RightNId);
00682   IAssertR((IsLL||IsLR)&&(IsRL||IsRR), TStr::Fmt("%d or %d is not a node.", LeftNId, RightNId).CStr());
00683   IAssertR(LeftNId!=RightNId, "No self-edges are allowed."); 
00684   IAssertR((IsLL&&!IsLR&&!IsRL&&IsRR)||(!IsLL&&IsLR&&IsRL&&!IsRR), "One node should be on the 'left' and the other on the 'right'.");
00685   const int LNId = IsLL ? LeftNId : RightNId; // the real left node
00686   const int RNId = IsLL ? RightNId : LeftNId; // the real right node
00687   const TNodeI SrcNI = GetNI(LNId);
00688   const int NodeN = SrcNI.LeftHI.GetDat().NIdV.SearchBin(RNId);
00689   IAssertR(NodeN != -1, "Right edge endpoint does not exists!");
00690   return TEdgeI(SrcNI, EndNI(), NodeN);
00691 }
00692 
00693 int TBPGraph::GetRndNId(TRnd& Rnd) { 
00694   const int NNodes = GetNodes();
00695   if (Rnd.GetUniDevInt(NNodes) < GetLNodes()) {
00696     return GetRndLNId(Rnd); }
00697   else {
00698     return GetRndRNId(Rnd); }
00699 }
00700 
00701 int TBPGraph::GetRndLNId(TRnd& Rnd) { 
00702   return LeftH.GetKey(LeftH.GetRndKeyId(Rnd, 0.8)); 
00703 }
00704 
00705 int TBPGraph::GetRndRNId(TRnd& Rnd) { 
00706   return RightH.GetKey(RightH.GetRndKeyId(Rnd, 0.8)); 
00707 }
00708 
00709 void TBPGraph::GetNIdV(TIntV& NIdV) const {
00710   NIdV.Gen(GetNodes(), 0);
00711   for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
00712     NIdV.Add(LeftH.GetKey(N)); }
00713   for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
00714     NIdV.Add(RightH.GetKey(N)); }
00715 }
00716 
00717 void TBPGraph::GetLNIdV(TIntV& NIdV) const {
00718   NIdV.Gen(GetLNodes(), 0);
00719   for (int N=LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
00720     NIdV.Add(LeftH.GetKey(N)); }
00721 }
00722 
00723 void TBPGraph::GetRNIdV(TIntV& NIdV) const {
00724   NIdV.Gen(GetRNodes(), 0);
00725   for (int N=RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
00726     NIdV.Add(RightH.GetKey(N)); }
00727 }
00728 
00729 void TBPGraph::Reserve(const int& Nodes, const int& Edges) { 
00730   if (Nodes>0) { LeftH.Gen(Nodes/2); RightH.Gen(Nodes/2); } 
00731 }
00732 
00733 void TBPGraph::Defrag(const bool& OnlyNodeLinks) {
00734   for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
00735     LeftH[n].NIdV.Pack(); }
00736   for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
00737     RightH[n].NIdV.Pack(); }
00738   if (! OnlyNodeLinks && ! LeftH.IsKeyIdEqKeyN()) { LeftH.Defrag(); }
00739   if (! OnlyNodeLinks && ! RightH.IsKeyIdEqKeyN()) { RightH.Defrag(); }
00740 }
00741 
00742 bool TBPGraph::IsOk(const bool& ThrowExcept) const {
00743   bool RetVal = false;
00744   // edge lists are sorted
00745   for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
00746     if (! LeftH[n].NIdV.IsSorted()) {
00747       const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", LeftH[n].GetId());
00748       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
00749   }
00750   for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
00751     if (! RightH[n].NIdV.IsSorted()) {
00752       const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", RightH[n].GetId());
00753       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
00754   }
00755   // nodes only appear on one side
00756   for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
00757     if (RightH.IsKey(LeftH[n].GetId())) {
00758       const TStr Msg = TStr::Fmt("'Left' node %d also appears on the 'right'.", LeftH[n].GetId());
00759       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
00760   } 
00761   for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
00762     if (LeftH.IsKey(RightH[n].GetId())) {
00763       const TStr Msg = TStr::Fmt("'Right' node %d also appears on the 'left'.", RightH[n].GetId());
00764       if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
00765   }
00766   // edges only point from left to right and right to left
00767   for (int n = LeftH.FFirstKeyId(); LeftH.FNextKeyId(n); ) {
00768     for (int e = 0; e < LeftH[n].NIdV.Len(); e++) {
00769       if (! RightH.IsKey(LeftH[n].NIdV[e]) || ! RightH.GetDat(LeftH[n].NIdV[e]).NIdV.IsIn(LeftH[n].GetId())) {
00770         const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", LeftH[n].GetId(), LeftH[n].NIdV[e]());
00771         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
00772     }
00773   }
00774   for (int n = RightH.FFirstKeyId(); RightH.FNextKeyId(n); ) {
00775     for (int e = 0; e < RightH[n].NIdV.Len(); e++) {
00776       if (! LeftH.IsKey(RightH[n].NIdV[e]) || ! LeftH.GetDat(RightH[n].NIdV[e]).NIdV.IsIn(RightH[n].GetId())) {
00777         const TStr Msg = TStr::Fmt("'Left' node %d does not point to the 'right' node %d.", RightH[n].GetId(), RightH[n].NIdV[e]());
00778         if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false; }
00779     }
00780   }
00781   return RetVal;
00782 }
00783 
00784 void TBPGraph::Dump(FILE *OutF) const {
00785   const int NodePlaces = (int) ceil(log10((double) GetNodes()));
00786   fprintf(OutF, "-------------------------------------------------\nBipartite Graph: nodes: %d+%d=%d, edges: %d\n", GetLNodes(), GetRNodes(), GetNodes(), GetEdges());
00787   for (int N = LeftH.FFirstKeyId(); LeftH.FNextKeyId(N); ) {
00788     const TNode& Node = LeftH[N];
00789     fprintf(OutF, "  %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
00790     for (int edge = 0; edge < Node.GetDeg(); edge++) {
00791       fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
00792     fprintf(OutF, "\n");
00793   }
00794   fprintf(OutF, "\n");
00795   /*// Also dump the 'right' side
00796   fprintf(OutF, "\n");
00797   for (int N = RightH.FFirstKeyId(); RightH.FNextKeyId(N); ) {
00798     const TNode& Node = RightH[N];
00799     fprintf(OutF, "  %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
00800     for (int edge = 0; edge < Node.GetDeg(); edge++) {
00801       fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
00802     fprintf(OutF, "\n");
00803   }
00804   fprintf(OutF, "\n"); //*/
00805 }
00806 
00807 PBPGraph TBPGraph::GetSmallGraph() {
00808   PBPGraph BP = TBPGraph::New();
00809   BP->AddNode(0, true);
00810   BP->AddNode(1, true);
00811   BP->AddNode(2, false);
00812   BP->AddNode(3, false);
00813   BP->AddNode(4, false);
00814   BP->AddEdge(0, 2);
00815   BP->AddEdge(0, 3);
00816   BP->AddEdge(1, 2);
00817   BP->AddEdge(1, 3);
00818   BP->AddEdge(1, 4);
00819   return BP;
00820 }