SNAP Library 2.2, Developer Reference  2014-03-11 19:15:55
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
subgraph.h
Go to the documentation of this file.
00001 
00005 
00006 namespace TSnap {
00007 
00009 // Convert between graph types and get subgraphs
00010 
00011 // node subgraphs
00013 
00018 template<class PGraph> PGraph GetSubGraph(const PGraph& Graph, const TIntV& NIdV);
00020 
00028 PUNGraph GetSubGraph(const PUNGraph& Graph, const TIntV& NIdV, const bool& RenumberNodes=false);
00029 // Returns an induced subgraph of a directed graph Graph with NIdV nodes with an optional node renumbering. ##TSnap::GetSubGraph-2
00030 PNGraph GetSubGraph(const PNGraph& Graph, const TIntV& NIdV, const bool& RenumberNodes=false);
00031 // TODO ROK 2012/08/15 PNGraph GetSubGraph is not documented by doxygen.
00032 //  It is combined with PUNGraph GetSubGraph.
00033 
00034 // edge subgraphs
00036 
00045 template<class PGraph> PGraph GetESubGraph(const PGraph& Graph, const TIntV& EIdV);
00046 // Returns a subgraph of graph Graph with EdgeV edges. ##TSnap::GetESubGraph-1
00047 template<class PGraph> PGraph GetESubGraph(const PGraph& Graph, const TIntPrV& EdgeV);
00048 // TODO ROK 2012/08/15 PGraph GetESubGraph TIntPrV is not documented by doxygen.
00049 //  It is combined with PGraph GetESubGraph TIntV.
00051 
00064 template<class PGraph, class TEdgeDat> PGraph GetEDatSubGraph(const PGraph& Graph, const TEdgeDat& EDat, const int& Cmp);
00066 
00080 template<class PGraph, class TEdgeDat> PGraph GetEDatSubGraph(const PGraph& Graph, const TIntV& NIdV, const TEdgeDat& EDat, const int& Cmp);
00081 
00082 // convert between the graphs. Does NOT copy the data
00084 
00095 template<class POutGraph, class PInGraph> POutGraph ConvertGraph(const PInGraph& InGraph, const bool& RenumberNodes=false);
00097 
00108 template<class POutGraph, class PInGraph> POutGraph ConvertSubGraph(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes=false);
00109 // TODO RS 2012/08/14 find out why TSnap::ConvertSubGraph<PUNGraph>(NGraph, NIdV, true) aborts
00111 
00122 template<class POutGraph, class PInGraph> POutGraph ConvertESubGraph(const PInGraph& InGraph, const TIntV& EIdV, const bool& RenumberNodes=false);
00123 // does not work on multigraphs
00124 
00125 // get random (induced) subgraphs 
00127 
00130 template<class PGraph> PGraph GetRndSubGraph(const PGraph& Graph, const int& NNodes);
00132 
00135 template<class PGraph> PGraph GetRndESubGraph(const PGraph& Graph, const int& NEdges);
00136 
00138 // Implementation
00139 namespace TSnapDetail {
00140 // Slow for small sub-graphs as it traverses all the edges of Graph
00141 template <class PGraph, bool IsMultiGraph>
00142 struct TGetSubGraph {
00143   static PGraph Do(const PGraph& Graph, const TIntV& NIdV) {
00144     PGraph NewGraphPt = PGraph::TObj::New();
00145     typename PGraph::TObj& NewGraph = *NewGraphPt;
00146     NewGraph.Reserve(NIdV.Len(), -1);
00147     for (int n = 0; n < NIdV.Len(); n++) {
00148       if (Graph->IsNode(NIdV[n])) {
00149         NewGraph.AddNode(Graph->GetNI(NIdV[n])); }
00150     }
00151     for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
00152       if (NewGraph.IsNode(EI.GetSrcNId()) && NewGraph.IsNode(EI.GetDstNId())) {
00153         NewGraph.AddEdge(EI); }
00154     }
00155     NewGraph.Defrag();
00156     return NewGraphPt;
00157   }
00158 };
00159 
00160 template <class PGraph> 
00161 struct TGetSubGraph<PGraph, false> { // not multigraph
00162   static PGraph Do(const PGraph& Graph, const TIntV& NIdV) {
00163     CAssert(! HasGraphFlag(typename PGraph::TObj, gfMultiGraph));
00164     PGraph NewGraphPt = PGraph::TObj::New();
00165     typename PGraph::TObj& NewGraph = *NewGraphPt;
00166     NewGraph.Reserve(NIdV.Len(), -1);
00167     TIntSet NodeSet;
00168     for (int n = 0; n < NIdV.Len(); n++) {
00169       if (! HasGraphFlag(typename PGraph::TObj, gfNodeDat)) {
00170         if (Graph->IsNode(NIdV[n])) { NewGraph.AddNode(NIdV[n]); NodeSet.AddKey(NIdV[n]); } }
00171       else {
00172         if (Graph->IsNode(NIdV[n])) { NewGraph.AddNode(Graph->GetNI(NIdV[n])); NodeSet.AddKey(NIdV[n]); } }
00173     }
00174     for (int n = 0; n < NodeSet.Len(); n++) {
00175       const int SrcNId = NodeSet[n];
00176       const typename PGraph::TObj::TNodeI NI = Graph->GetNI(SrcNId);
00177       for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
00178         const int OutNId = NI.GetOutNId(edge);
00179         if (NewGraph.IsNode(OutNId)) {
00180           if (! HasGraphFlag(typename PGraph::TObj, gfEdgeDat)) { 
00181             NewGraph.AddEdge(SrcNId, OutNId); }
00182           else { 
00183             NewGraph.AddEdge(Graph->GetEI(SrcNId, OutNId)); } // also copy data
00184         }
00185       }
00186     }
00187     NewGraph.Defrag();
00188     return NewGraphPt;
00189   }
00190 };
00191 }; // TSnapDetail
00192 
00193 template<class PGraph> 
00194 PGraph GetSubGraph(const PGraph& Graph, const TIntV& NIdV) {
00195   return TSnapDetail::TGetSubGraph<PGraph, HasGraphFlag(typename PGraph::TObj, gfMultiGraph)>
00196     ::Do(Graph, NIdV);
00197 }
00198 
00199 template<class PGraph> 
00200 PGraph GetESubGraph(const PGraph& Graph, const TIntV& EIdV) {
00201   CAssert(HasGraphFlag(typename PGraph::TObj, gfMultiGraph));
00202   PGraph NewGraphPt = PGraph::TObj::New();
00203   typename PGraph::TObj& NewGraph = *NewGraphPt;
00204   NewGraph.Reserve(-1, EIdV.Len());
00205   for (int edge = 0; edge < EIdV.Len(); edge++) {
00206     const int EId = EIdV[edge];
00207     IAssert(Graph->IsEdge(EId));
00208     const typename PGraph::TObj::TEdgeI EI = Graph->GetEI(EId);
00209     if (! NewGraph.IsNode(EI.GetSrcNId())) {
00210       NewGraph.AddNode(Graph->GetNI(EI.GetSrcNId())); 
00211     }
00212     if (! NewGraph.IsNode(EI.GetDstNId())) {
00213       NewGraph.AddNode(Graph->GetNI(EI.GetDstNId())); 
00214     }
00215     NewGraph.AddEdge(EI);
00216   }
00217   return NewGraphPt;
00218 }
00219 
00220 template<class PGraph> 
00221 PGraph GetESubGraph(const PGraph& Graph, const TIntPrV& EdgeV) {
00222   PGraph NewGraphPt = PGraph::TObj::New();
00223   typename PGraph::TObj& NewGraph = *NewGraphPt;
00224   NewGraph.Reserve(-1, EdgeV.Len());
00225   for (int edge = 0; edge < EdgeV.Len(); edge++) {
00226     const int SrcNId = EdgeV[edge].Val1;
00227     const int DstNId = EdgeV[edge].Val2;
00228     const typename PGraph::TObj::TEdgeI EI = Graph->GetEI(SrcNId, DstNId);
00229     if (! NewGraph.IsNode(EI.GetSrcNId())) {
00230       NewGraph.AddNode(Graph->GetNI(EI.GetSrcNId())); 
00231     }
00232     if (! NewGraph.IsNode(EI.GetDstNId())) {
00233       NewGraph.AddNode(Graph->GetNI(EI.GetDstNId())); 
00234     }
00235     NewGraph.AddEdge(EI);
00236   }
00237   return NewGraphPt;
00238 }
00239 
00240 // Get a subgraph on NIdV nodes, where edge data is Cmp (-1:less, 0:equal, 1:greater) than EDat
00241 template<class PGraph, class TEdgeDat> 
00242 PGraph GetEDatSubGraph(const PGraph& Graph, const TEdgeDat& EDat, const int& Cmp) {
00243   CAssert(HasGraphFlag(typename PGraph::TObj, gfEdgeDat));
00244   PGraph NewGraphPt = PGraph::TObj::New();
00245   typename PGraph::TObj& NewGraph = *NewGraphPt;
00246   for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
00247     if ((Cmp==1 && EI()>EDat) || (Cmp==-1 && EI()<EDat) || (Cmp==0 && EI()==EDat)) {
00248       if (! NewGraph.IsNode(EI.GetSrcNId())) {
00249         NewGraph.AddNode(Graph->GetNI(EI.GetSrcNId()));
00250       }
00251       if (! NewGraph.IsNode(EI.GetDstNId())) {
00252         NewGraph.AddNode(Graph->GetNI(EI.GetDstNId()));
00253       }
00254       NewGraph.AddEdge(EI); 
00255     }
00256   }
00257   return NewGraphPt;
00258 }
00259 
00260 // Get a subgraph on NIdV nodes, where edge data is Cmp (-1:less, 0:equal, 1:greater) than EDat
00261 template<class PGraph, class TEdgeDat> 
00262 PGraph GetEDatSubGraph(const PGraph& Graph, const TIntV& NIdV, const TEdgeDat& EDat, const int& Cmp) {
00263   CAssert(HasGraphFlag(typename PGraph::TObj, gfEdgeDat));
00264   PGraph NewGraphPt = PGraph::TObj::New();
00265   typename PGraph::TObj& NewGraph = *NewGraphPt;
00266   NewGraph.Reserve(NIdV.Len(), -1);
00267   for (int n = 0; n < NIdV.Len(); n++) {
00268     NewGraph.AddNode(Graph->GetNI(NIdV[n])); 
00269   }
00270   for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
00271     if (NewGraph.IsNode(EI.GetSrcNId()) && NewGraph.IsNode(EI.GetDstNId()) &&
00272      ((Cmp==1 && EI()>EDat)|| (Cmp==-1 && EI()<EDat) || (Cmp==0 && EI()==EDat))) {
00273       NewGraph.AddEdge(EI); }
00274   }
00275   NewGraph.Defrag();
00276   return NewGraphPt;
00277 }
00278 
00279 // Converts between different types of graphs/networks
00280 // Node/edge data is not copied between the graphs.
00281 template<class POutGraph, class PInGraph> 
00282 POutGraph ConvertGraph(const PInGraph& InGraph, const bool& RenumberNodes) {
00283   POutGraph OutGraphPt = POutGraph::TObj::New();
00284   typename POutGraph::TObj& OutGraph = *OutGraphPt;
00285   OutGraph.Reserve(InGraph->GetNodes(), InGraph->GetEdges());
00286   if (! RenumberNodes) {
00287     for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
00288       OutGraph.AddNode(NI.GetId());
00289     }
00290     for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
00291       OutGraph.AddEdge(EI.GetSrcNId(), EI.GetDstNId());
00292       if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) { // add edge in the other direction
00293         OutGraph.AddEdge(EI.GetDstNId(), EI.GetSrcNId()); }
00294     }
00295   } else { // renumber nodes so that node ids are 0...N-1
00296     TIntSet NIdSet(InGraph->GetNodes());
00297     for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
00298       const int nid = NIdSet.AddKey(NI.GetId());
00299       OutGraph.AddNode(nid);
00300     }
00301     for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
00302       const int SrcNId = NIdSet.GetKeyId(EI.GetSrcNId());
00303       const int DstNId = NIdSet.GetKeyId(EI.GetDstNId());
00304       OutGraph.AddEdge(SrcNId, DstNId);
00305       if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
00306         OutGraph.AddEdge(DstNId, SrcNId); }
00307     }
00308   }
00309   //OutGraph.Defrag();
00310   return OutGraphPt;
00311 }
00312 
00313 namespace TSnapDetail {
00314 // Slow for small sub-graphs as it traverses all the edges of Graph
00315 template <class POutGraph, class PInGraph, bool IsMultiGraph>
00316 struct TConvertSubGraph {
00317   static POutGraph Do(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes) {
00318     POutGraph OutGraphPt = POutGraph::TObj::New();
00319     typename POutGraph::TObj& OutGraph = *OutGraphPt;
00320     if (! RenumberNodes) {
00321       for (int n = 0; n < NIdV.Len(); n++) {
00322         OutGraph.AddNode(NIdV[n]);
00323       }
00324       for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
00325         if (! OutGraph.IsNode(EI.GetSrcNId()) || ! OutGraph.IsNode(EI.GetDstNId())) { continue; }
00326         OutGraph.AddEdge(EI.GetSrcNId(), EI.GetDstNId());
00327         if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
00328           OutGraph.AddEdge(EI.GetDstNId(), EI.GetSrcNId());
00329         }
00330       }
00331     } else { // renumber nodes so that node ids are 0...N-1
00332       TIntSet NIdSet(InGraph->GetNodes());
00333       for (int n = 0; n < NIdV.Len(); n++) {
00334         const int NId = NIdSet.AddKey(NIdV[n]);
00335         OutGraph.AddNode(NId);
00336       }
00337       for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
00338         const int SrcNId = NIdSet.GetKeyId(EI.GetSrcNId());
00339         const int DstNId = NIdSet.GetKeyId(EI.GetDstNId());
00340         if (! OutGraph.IsNode(SrcNId) || ! OutGraph.IsNode(DstNId)) { continue; }
00341         OutGraph.AddEdge(SrcNId, DstNId);
00342         if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
00343           OutGraph.AddEdge(DstNId, SrcNId);
00344         }
00345       }
00346     }
00347     OutGraph.Defrag();
00348     return OutGraphPt;
00349   }
00350 };
00351 
00352 template <class POutGraph, class PInGraph>
00353 struct TConvertSubGraph<POutGraph, PInGraph, false> { // InGraph is not multigraph
00354   static POutGraph Do(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes) {
00355     POutGraph OutGraphPt = POutGraph::TObj::New();
00356     typename POutGraph::TObj& OutGraph = *OutGraphPt;
00357     if (! RenumberNodes) {
00358       for (int n = 0; n < NIdV.Len(); n++) {
00359         OutGraph.AddNode(NIdV[n]); }
00360       for (int n = 0; n < NIdV.Len(); n++) {
00361         typename PInGraph::TObj::TNodeI NI = InGraph->GetNI(NIdV[n]);
00362         for (int e = 0; e < NI.GetOutDeg(); e++) {
00363           const int dst = NI.GetOutNId(e);
00364           if (! OutGraph.IsNode(dst)) { continue; }
00365           OutGraph.AddEdge(NIdV[n], dst);
00366         }
00367       }
00368     } else { // renumber nodes so that node ids are 0...N-1
00369       TIntSet NIdSet(InGraph->GetNodes());
00370       for (int n = 0; n < NIdV.Len(); n++) {
00371         const int NId = NIdSet.AddKey(NIdV[n]);
00372         OutGraph.AddNode(NId);
00373       }
00374       for (int n = 0; n < NIdV.Len(); n++) {
00375         typename PInGraph::TObj::TNodeI NI = InGraph->GetNI(NIdV[n]);
00376         const int src = NIdSet.GetKey(NIdV[n]);
00377         for (int e = 0; e < NI.GetOutDeg(); e++) {
00378           const int dst = NIdSet.GetKey(NI.GetOutNId(e));
00379           if (! OutGraph.IsNode(dst)) { continue; }
00380           OutGraph.AddEdge(src, dst);
00381         }
00382       }
00383     }
00384     OutGraph.Defrag();
00385     return OutGraphPt;
00386   }
00387 };
00388 } // TSnapDetail
00389 
00390 // May be slow as it traverses all the edges of the in-graph to create the sub-graph
00391 template<class POutGraph, class PInGraph> 
00392 POutGraph ConvertSubGraph(const PInGraph& InGraph, const TIntV& NIdV, const bool& RenumberNodes) {
00393   return TSnapDetail::TConvertSubGraph<POutGraph, PInGraph, HasGraphFlag(typename PInGraph::TObj, gfMultiGraph)>::Do(InGraph, NIdV, RenumberNodes);
00394 }
00395 
00396 template<class POutGraph, class PInGraph> 
00397 POutGraph ConvertESubGraph(const PInGraph& InGraph, const TIntV& EIdV, const bool& RenumberNodes) {
00398   CAssert(HasGraphFlag(typename PInGraph::TObj, gfMultiGraph)); // needs to have explicit edges
00399   POutGraph NewGraphPt = POutGraph::TObj::New();
00400   typename POutGraph::TObj& NewGraph = *NewGraphPt;
00401   NewGraph.Reserve(-1, EIdV.Len());
00402   if (! RenumberNodes) {
00403     for (int edge = 0; edge < EIdV.Len(); edge++) {
00404       const int EId = EIdV[edge];
00405       IAssert(InGraph->IsEdge(EId));
00406       const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
00407       const int SrcNId = EI.GetSrcNId();
00408       const int DstNId = EI.GetDstNId();
00409       if (! NewGraph.IsNode(SrcNId)) {
00410         NewGraph.AddNode(SrcNId); }
00411       if (! NewGraph.IsNode(DstNId)) {
00412         NewGraph.AddNode(DstNId); }
00413       NewGraph.AddEdge(SrcNId, DstNId);
00414     }
00415   } else {
00416     // renumber nodes so that node ids are 0...N-1
00417     TIntSet NIdSet(InGraph->GetNodes());
00418     for (int edge = 0; edge < EIdV.Len(); edge++) {
00419       const int EId = EIdV[edge];
00420       IAssert(InGraph->IsEdge(EId));
00421       const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
00422       const int SrcNId = NIdSet.AddKey(EI.GetSrcNId()); // map node ids
00423       const int DstNId = NIdSet.AddKey(EI.GetDstNId());
00424       if (! NewGraph.IsNode(SrcNId)) {
00425         NewGraph.AddNode(SrcNId); }
00426       if (! NewGraph.IsNode(DstNId)) {
00427         NewGraph.AddNode(DstNId); }
00428       NewGraph.AddEdge(SrcNId, DstNId);
00429     }
00430   }
00431   return NewGraphPt;
00432 }
00433 
00434 template<class PGraph> 
00435 PGraph GetRndSubGraph(const PGraph& Graph, const int& NNodes) {
00436   IAssert(NNodes <= Graph->GetNodes());
00437   TIntV NIdV;
00438   Graph->GetNIdV(NIdV);
00439   NIdV.Shuffle(TInt::Rnd);
00440   NIdV.Del(NNodes, NIdV.Len()-1);
00441   IAssert(NIdV.Len() == NNodes);
00442   return GetSubGraph(Graph, NIdV);
00443 }
00444 
00445 template<class PGraph> 
00446 PGraph GetRndESubGraph(const PGraph& Graph, const int& NEdges) {
00447   CAssert(! HasGraphFlag(typename PGraph::TObj, gfMultiGraph));
00448   TIntPrV EdgeV(Graph->GetEdges(), 0);
00449   for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
00450     EdgeV.Add(TIntPr(EI.GetSrcNId(), EI.GetDstNId()));
00451   }
00452   EdgeV.Shuffle(TInt::Rnd);
00453   EdgeV.Del(NEdges, EdgeV.Len()-1);
00454   IAssert(EdgeV.Len() == NEdges);
00455   return GetESubGraph(Graph, EdgeV);
00456 }
00457 
00458 } // namespace TSnap