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
ggen.h
Go to the documentation of this file.
00001 // TODO ROK, Jure included basic documentation, finalize reference doc
00002 
00004 // Graph Generators
00005 namespace TSnap {
00006 
00008 // Deterministic graphs
00010 template <class PGraph> PGraph GenGrid(const int& Rows, const int& Cols, const bool& IsDir=true);
00012 template <class PGraph> PGraph GenStar(const int& Nodes, const bool& IsDir=true);
00014 template <class PGraph> PGraph GenCircle(const int& Nodes, const int& NodeOutDeg=1, const bool& IsDir=true);
00016 template <class PGraph> PGraph GenFull(const int& Nodes);
00018 template <class PGraph> PGraph GenTree(const int& Fanout, const int& Levels, const bool& IsDir=true, const bool& ChildPointsToParent=true);
00020 template <class PGraph> PGraph GenBaraHierar(const int& Levels, const bool& IsDir=true);
00021 
00023 // Random graphs
00024 
00026 template <class PGraph> PGraph GenRndGnm(const int& Nodes, const int& Edges, const bool& IsDir=true, TRnd& Rnd=TInt::Rnd);
00028 PBPGraph GenRndBipart(const int& LeftNodes, const int& RightNodes, const int& Edges, TRnd& Rnd=TInt::Rnd);
00030 PUNGraph GenRndDegK(const int& Nodes, const int& NodeDeg, const int& NSwitch=100, TRnd& Rnd=TInt::Rnd);
00032 PUNGraph GenRndPowerLaw(const int& Nodes, const double& PowerExp, const bool& ConfModel=true, TRnd& Rnd=TInt::Rnd);
00034 PUNGraph GenDegSeq(const TIntV& DegSeqV, TRnd& Rnd=TInt::Rnd);
00036 PUNGraph GenPrefAttach(const int& Nodes, const int& NodeOutDeg, TRnd& Rnd=TInt::Rnd);
00038 PUNGraph GenGeoPrefAttach(const int& Nodes, const int& OutDeg, const double& Beta, TRnd& Rnd=TInt::Rnd);
00040 PUNGraph GenSmallWorld(const int& Nodes, const int& NodeOutDeg, const double& RewireProb, TRnd& Rnd=TInt::Rnd);
00042 PUNGraph GenConfModel(const TIntV& DegSeqV, TRnd& Rnd=TInt::Rnd);
00044 PUNGraph GenRewire(const PUNGraph& Graph, const int& NSwitch=100, TRnd& Rnd=TInt::Rnd);
00046 PNGraph  GenRewire(const PNGraph& Graph, const int& NSwitch=100, TRnd& Rnd=TInt::Rnd);
00048 PBPGraph GenRewire(const PBPGraph& Graph, const int& NSwitch=100, TRnd& Rnd=TInt::Rnd);
00050 PNGraph GenForestFire(const int& Nodes, const double& FwdProb, const double& BckProb);
00052 PNGraph GenCopyModel(const int& Nodes, const double& Beta, TRnd& Rnd=TInt::Rnd);
00054 PNGraph GenRMat(const int& Nodes, const int& Edges, const double& A, const double& B, const double& C, TRnd& Rnd=TInt::Rnd);
00056 PNGraph GenRMatEpinions();
00057 
00059 // Implementation
00060 template <class PGraph>
00061 PGraph GenGrid(const int& Rows, const int& Cols, const bool& IsDir) {
00062   PGraph GraphPt = PGraph::New();
00063   typename PGraph::TObj& Graph = *GraphPt;
00064   Graph.Reserve(Rows*Cols, 4*Rows*Cols);
00065   int node, r, c;
00066   for (node = 0; node < Rows * Cols; node++) {
00067     Graph.AddNode(node); }
00068   for (r = 0; r < Rows; r++) {
00069     for (c = 0; c < Cols; c++) {
00070       const int nodeId = Cols*r + c;
00071       if (r < Rows-1) { // bottom node
00072         Graph.AddEdge(nodeId, nodeId+Cols); 
00073         if (Graph.HasFlag(gfDirected) && ! IsDir) { 
00074           Graph.AddEdge(nodeId+Cols-1, nodeId); }
00075       }
00076       if (c < Cols-1) { // right node
00077         Graph.AddEdge(nodeId, nodeId+1); 
00078         if (Graph.HasFlag(gfDirected) && ! IsDir) { 
00079           Graph.AddEdge(nodeId+1, nodeId); }
00080       }
00081     }
00082   }
00083   return GraphPt;
00084 }
00085 
00086 template <class PGraph>
00087 PGraph GenStar(const int& Nodes, const bool& IsDir) {
00088   PGraph Graph = PGraph::TObj::New();
00089   Graph->Reserve(Nodes, Nodes);
00090   Graph->AddNode(0);
00091   for (int n = 1; n < Nodes; n++) {
00092     Graph->AddNode(n);
00093     Graph->AddEdge(0, n);
00094     if (Graph->HasFlag(gfDirected) && ! IsDir) { Graph->AddEdge(n, 0); }
00095   }
00096   return Graph;
00097 }
00098 
00099 template <class PGraph>
00100 PGraph GenCircle(const int& Nodes, const int& NodeOutDeg, const bool& IsDir) {
00101   PGraph Graph = PGraph::TObj::New();
00102   Graph->Reserve(Nodes, Nodes*NodeOutDeg);
00103   for (int n = 0; n < Nodes; n++) {
00104     Graph->AddNode(n); }
00105   for (int n = 0; n < Nodes; n++) {
00106     for (int x = 0; x < NodeOutDeg; x++) {
00107       Graph->AddEdge(n, (n+x+1) % Nodes);
00108       if (Graph->HasFlag(gfDirected) && ! IsDir) { Graph->AddEdge((n+x) % Nodes, n); }
00109     }
00110   }
00111   return Graph;
00112 }
00113 
00114 template <class PGraph>
00115 PGraph GenFull(const int& Nodes) {
00116   PGraph Graph = PGraph::TObj::New();
00117   Graph->Reserve(Nodes, Nodes*Nodes);
00118   for (int n = 0; n < Nodes; n++) {
00119     Graph->AddNode(n); }
00120   for (int n1 = 0; n1 < Nodes; n1++) {
00121     for (int n2 = 0; n2 < Nodes; n2++) {
00122       if (n1 != n2) { Graph->AddEdge(n1, n2); }
00123     }
00124   }
00125   return Graph;
00126 }
00127 
00128 template <class PGraph>
00129 PGraph GenTree(const int& Fanout, const int& Levels, const bool& IsDir, const bool& ChildPointsToParent) {
00130   const int Nodes = (int) (pow(double(Fanout), double(Levels+1)) - 1) / (Fanout - 1);
00131   const int Edges = Nodes - 1;
00132   PGraph GraphPt = PGraph::New();
00133   typename PGraph::TObj& Graph = *GraphPt;
00134   Graph.Reserve(Nodes, Edges);
00135   int node;
00136   for (node = 0; node < Nodes; node++) {
00137     Graph.AddNode(node); }
00138   // non-leaf nodes
00139   for (node = 0; node < (int) Nodes - (int) pow(double(Fanout), double(Levels)); node++) {
00140     for (int edge = 1; edge <= Fanout; edge++) {
00141       if (IsDir) {
00142         if (ChildPointsToParent) { Graph.AddEdge(Fanout*node+edge, node); }
00143         else { Graph.AddEdge(node, Fanout*node+edge); }
00144       } else {
00145         Graph.AddEdge(node, Fanout*node+edge); // link children
00146         Graph.AddEdge(Fanout*node+edge, node);
00147       }
00148     }
00149   }
00150   return GraphPt;
00151 }
00152 
00158 
00166 
00169 template <class PGraph>
00170 PGraph GenBaraHierar(const int& Levels, const bool& IsDir) {
00171   const int Nodes = (int) TMath::Round(TMath::Power(5, Levels));
00172   PGraph GraphPt = PGraph::New();
00173   typename PGraph::TObj& Graph = *GraphPt;
00174   Graph.Reserve(Nodes, -1);
00175   // base graph
00176   for (int i = 0; i < 5; i++) { Graph.AddNode(i); }
00177   Graph.AddEdge(1,2);  Graph.AddEdge(2,3);
00178   Graph.AddEdge(3,4);  Graph.AddEdge(4,1);
00179   Graph.AddEdge(1,0);  Graph.AddEdge(3,0);
00180   Graph.AddEdge(2,0);  Graph.AddEdge(4,0);
00181   // expansion
00182   const int CenterId = 0;
00183   for (int lev = 1; lev < Levels+1; lev++) {
00184     const int MxNId = Graph.GetNodes();
00185     // make 4 duplicate copies
00186     for (int d = 0; d < 4; d++) {
00187       for (int n = 0; n < MxNId; n++) { Graph.AddNode(); }
00188       for (int n = 0; n < MxNId; n++) {
00189         typename PGraph::TObj::TNodeI NI = Graph.GetNI(n);
00190         const int SrcId = n+MxNId*(d+1);
00191         for (int e = 0; e < NI.GetOutDeg(); e++) {
00192           Graph.AddEdge(SrcId, NI.GetOutNId(e)+MxNId*(d+1));
00193         }
00194       }
00195     }
00196     // add edges to the center
00197     //const int LevPow = (int)TMath::Round(TMath::Power(5,lev-1));
00198     for (int n = MxNId; n < Graph.GetNodes(); n++) {
00199       typename PGraph::TObj::TNodeI NI = Graph.GetNI(n);
00200       const int SrcId = n;
00201       int Pow = 1;  bool Skip = false;
00202       for (int p = 1; p <= lev; p++) {
00203         if (SrcId % (5*Pow) < Pow) { Skip=true; break; }
00204         Pow *= 5;
00205       }
00206       if (Skip) { continue; }
00207       Graph.AddEdge(SrcId, CenterId);
00208     }
00209   }
00210   return GraphPt;
00211 }
00212 
00213 template <class PGraph>
00214 PGraph GenRndGnm(const int& Nodes, const int& Edges, const bool& IsDir, TRnd& Rnd) {
00215   PGraph GraphPt = PGraph::New();
00216   typename PGraph::TObj& Graph = *GraphPt;
00217   Graph.Reserve(Nodes, Edges);
00218   IAssertR(Nodes * (Nodes-1) / 2 * (IsDir ? 2 : 1) >= Edges, TStr::Fmt("Not enough nodes (%d), for edges (%d).", Nodes, Edges));
00219   for (int node = 0; node < Nodes; node++) {
00220     IAssert(Graph.AddNode(node) == node);
00221   }
00222   for (int edge = 0; edge < Edges; ) {
00223     const int SrcNId = Rnd.GetUniDevInt(Nodes);
00224     const int DstNId = Rnd.GetUniDevInt(Nodes);
00225     if (SrcNId != DstNId && Graph.AddEdge(SrcNId, DstNId) != -2) { // is new edge
00226       if (! IsDir) { Graph.AddEdge(DstNId, SrcNId); }
00227       edge++;
00228     }
00229   }
00230   return GraphPt;
00231 }
00232 
00233 namespace TSnapDetail {
00235 template <class PGraph>
00236 TIntPr GetRndEdgeNonAdjNode(const PGraph& Graph, int NId1, int NId2) {
00237   typename PGraph::TObj::TNodeI NI1, NI2;
00238   int OutDeg = -1;
00239   do {
00240     NI1 = Graph->GetRndNI();
00241     OutDeg = NI1.GetOutDeg();
00242   } while (OutDeg == 0);
00243   NI2 = Graph->GetNI(NI1.GetOutNId(TInt::Rnd.GetUniDevInt(OutDeg)));
00244   int runs = 0;
00245   while (NI1.IsNbrNId(NId1) || NI1.IsNbrNId(NId2) || NI2.IsNbrNId(NId1) || NI2.IsNbrNId(NId2) || NI1.GetId()==NI2.GetId()) {
00246     do {
00247       NI1 = Graph->GetRndNI();
00248       OutDeg = NI1.GetOutDeg();
00249     } while (OutDeg == 0);
00250     NI2 = Graph->GetNI(NI1.GetOutNId(TInt::Rnd.GetUniDevInt(OutDeg)));
00251     if (runs++ == 1000) { return TIntPr(-1, -1); }
00252   }
00253   return TIntPr(NI1.GetId(), NI2.GetId());
00254 }
00255 
00256 } // namespace TSnapDetail
00257 
00258 }; // namespace TSnap