SNAP Library 3.0, Developer Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
TFfGGen Class Reference

#include <ff.h>

Collaboration diagram for TFfGGen:

Public Types

enum  TStopReason { srUndef, srOk, srFlood, srTimeLimit }
 

Public Member Functions

 TFfGGen (const bool &BurnExpFireP, const int &StartNNodes, const double &ForwBurnProb, const double &BackBurnProb, const double &DecayProb, const double &Take2AmbasPrb, const double &OrphanPrb)
 
PNGraph GetGraph () const
 
void SetGraph (const PNGraph &NGraph)
 
void Clr ()
 
TStr GetParamStr () const
 
TStopReason AddNodes (const int &GraphNodes, const bool &FloodStop=true)
 
TStopReason GenGraph (const int &GraphNodes, const bool &FloodStop=true)
 
TStopReason GenGraph (const int &GraphNodes, PGStatVec &EvolStat, const bool &FloodStop=true)
 
void PlotFireSize (const TStr &FNmPref, const TStr &DescStr)
 

Static Public Member Functions

static void GenFFGraphs (const double &FProb, const double &BProb, const TStr &FNm)
 

Static Public Attributes

static int TimeLimitSec = 30*60
 

Private Attributes

PNGraph Graph
 
TBool BurnExpFire
 
TInt StartNodes
 
TFlt FwdBurnProb
 
TFlt BckBurnProb
 
TFlt ProbDecay
 
TFlt Take2AmbProb
 
TFlt OrphanProb
 

Detailed Description

Forest Fire Graph Generator. For more details is "Graph Evolution: Densification and Shrinking Diameters" by J. Leskovec, J. Kleinberg, C. Faloutsos. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1), 2007.

Definition at line 49 of file ff.h.

Member Enumeration Documentation

Enumerator
srUndef 
srOk 
srFlood 
srTimeLimit 

Definition at line 51 of file ff.h.

Constructor & Destructor Documentation

TFfGGen::TFfGGen ( const bool &  BurnExpFireP,
const int &  StartNNodes,
const double &  ForwBurnProb,
const double &  BackBurnProb,
const double &  DecayProb,
const double &  Take2AmbasPrb,
const double &  OrphanPrb 
)

Definition at line 260 of file ff.cpp.

261  :
262  Graph(), BurnExpFire(BurnExpFireP), StartNodes(StartNNodes), FwdBurnProb(ForwBurnProb),
263  BckBurnProb(BackBurnProb), ProbDecay(DecayProb), Take2AmbProb(Take2AmbasPrb), OrphanProb(OrphanPrb) {
264  //IAssert(ProbDecay == 1.0); // do not need Decay any more
265 }
PNGraph Graph
Definition: ff.h:54
TBool BurnExpFire
Definition: ff.h:56
TFlt BckBurnProb
Definition: ff.h:58
TFlt OrphanProb
Definition: ff.h:59
TFlt ProbDecay
Definition: ff.h:58
TFlt FwdBurnProb
Definition: ff.h:58
TFlt Take2AmbProb
Definition: ff.h:59
TInt StartNodes
Definition: ff.h:57

Member Function Documentation

TFfGGen::TStopReason TFfGGen::AddNodes ( const int &  GraphNodes,
const bool &  FloodStop = true 
)

Definition at line 272 of file ff.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), BckBurnProb, TForestFire::BurnExpFire(), BurnExpFire, TForestFire::BurnGeoFire(), TPt< TRec >::Empty(), FwdBurnProb, TForestFire::GetBurned(), TForestFire::GetBurnedNId(), TNGraph::GetEdges(), TNGraph::GetNodes(), TExeTm::GetSecs(), TExeTm::GetStr(), TRnd::GetUniDev(), TRnd::GetUniDevInt(), TVec< TInt >::GetV(), Graph, IAssert, TForestFire::Infect(), Kilo, TPt< TNGraph >::New(), OrphanProb, ProbDecay, srFlood, srOk, srTimeLimit, StartNodes, Take2AmbProb, and TimeLimitSec.

Referenced by GenGraph().

272  {
273  printf("\n***ForestFire: %s Nodes:%d StartNodes:%d Take2AmbProb:%g\n", BurnExpFire?"ExpFire":"GeoFire", GraphNodes, StartNodes(), Take2AmbProb());
274  printf(" FwdBurnP:%g BckBurnP:%g ProbDecay:%g Orphan:%g\n", FwdBurnProb(), BckBurnProb(), ProbDecay(), OrphanProb());
275  TExeTm ExeTm;
276  int Burned1=0, Burned2=0, Burned3=0; // last 3 fire sizes
277  // create initial set of nodes
278  if (Graph.Empty()) { Graph = PNGraph::New(); }
279  if (Graph->GetNodes() == 0) {
280  for (int n = 0; n < StartNodes; n++) { Graph->AddNode(); }
281  }
282  int NEdges = Graph->GetEdges();
283  // forest fire
284  TRnd Rnd(0);
286  // add nodes
287  for (int NNodes = Graph->GetNodes()+1; NNodes <= GraphNodes; NNodes++) {
288  const int NewNId = Graph->AddNode(-1);
289  IAssert(NewNId == Graph->GetNodes()-1); // node ids have to be 0...N
290  // not an Orphan (burn fire)
291  if (OrphanProb == 0.0 || Rnd.GetUniDev() > OrphanProb) {
292  // infect ambassadors
293  if (Take2AmbProb == 0.0 || Rnd.GetUniDev() > Take2AmbProb || NewNId < 2) {
294  ForestFire.Infect(Rnd.GetUniDevInt(NewNId)); // take 1 ambassador
295  } else {
296  const int AmbassadorNId1 = Rnd.GetUniDevInt(NewNId);
297  int AmbassadorNId2 = Rnd.GetUniDevInt(NewNId);
298  while (AmbassadorNId1 == AmbassadorNId2) {
299  AmbassadorNId2 = Rnd.GetUniDevInt(NewNId); }
300  ForestFire.Infect(TIntV::GetV(AmbassadorNId1, AmbassadorNId2)); // take 2 ambassadors
301  }
302  // burn fire
303  if (BurnExpFire) { ForestFire.BurnExpFire(); }
304  else { ForestFire.BurnGeoFire(); }
305  // add edges to burned nodes
306  for (int e = 0; e < ForestFire.GetBurned(); e++) {
307  Graph->AddEdge(NewNId, ForestFire.GetBurnedNId(e));
308  NEdges++;
309  }
310  Burned1=Burned2; Burned2=Burned3; Burned3=ForestFire.GetBurned();
311  } else {
312  // Orphan (zero out-links)
313  Burned1=Burned2; Burned2=Burned3; Burned3=0;
314  }
315  if (NNodes % Kilo(1) == 0) {
316  printf("(%d, %d) burned: [%d,%d,%d] [%s]\n", NNodes, NEdges, Burned1, Burned2, Burned3, ExeTm.GetStr()); }
317  if (FloodStop && NEdges>GraphNodes && (NEdges/double(NNodes)>1000.0)) { // average node degree is more than 500
318  printf(". FLOOD. G(%6d, %6d)\n", NNodes, NEdges); return srFlood; }
319  if (NNodes % 1000 == 0 && TimeLimitSec > 0 && ExeTm.GetSecs() > TimeLimitSec) {
320  printf(". TIME LIMIT. G(%d, %d)\n", Graph->GetNodes(), Graph->GetEdges());
321  return srTimeLimit; }
322  }
323  IAssert(Graph->GetEdges() == NEdges);
324  return srOk;
325 }
#define IAssert(Cond)
Definition: bd.h:262
PNGraph Graph
Definition: ff.h:54
TBool BurnExpFire
Definition: ff.h:56
Definition: tm.h:355
#define Kilo(n)
Definition: gbase.h:3
Definition: dt.h:11
static TPt New()
Definition: bd.h:479
TFlt BckBurnProb
Definition: ff.h:58
bool Empty() const
Definition: bd.h:501
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TFlt OrphanProb
Definition: ff.h:59
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TFlt ProbDecay
Definition: ff.h:58
Definition: ff.h:6
static int TimeLimitSec
Definition: ff.h:52
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
double GetSecs() const
Definition: tm.h:366
TFlt FwdBurnProb
Definition: ff.h:58
static TVec< TInt, TSizeTy > GetV(const TInt &Val1)
Returns a vector on element Val1.
Definition: ds.h:817
TFlt Take2AmbProb
Definition: ff.h:59
const char * GetStr() const
Definition: tm.h:368
TInt StartNodes
Definition: ff.h:57

Here is the call graph for this function:

Here is the caller graph for this function:

void TFfGGen::Clr ( )
inline

Definition at line 66 of file ff.h.

References TNGraph::Clr(), and Graph.

66 { Graph->Clr(); }
PNGraph Graph
Definition: ff.h:54
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:532

Here is the call graph for this function:

void TFfGGen::GenFFGraphs ( const double &  FProb,
const double &  BProb,
const TStr FNm 
)
static

Definition at line 358 of file ff.cpp.

References TVec< TVal, TSizeTy >::Add(), TGStat::AllStat(), TStr::Fmt(), GenGraph(), gsvNodes, IAssert, TVec< TVal, TSizeTy >::Len(), TGStat::NDiamRuns, TGStatVec::New(), and tmuNodes.

358  {
359  const int NRuns = 10;
360  const int NNodes = 10000;
361  TGStat::NDiamRuns = 10;
362  //const double FProb = 0.35, BProb = 0.20; // ff1
363  //const double FProb = 0.37, BProb = 0.32; // ff2
364  //const double FProb = 0.37, BProb = 0.325; // ff22
365  //const double FProb = 0.37, BProb = 0.33; // ff3
366  //const double FProb = 0.37, BProb = 0.35; // ff4
367  //const double FProb = 0.38, BProb = 0.35; // ff5
368  TVec<PGStatVec> GAtTmV;
369  TFfGGen FF(false, 1, FProb, BProb, 1.0, 0, 0);
370  for (int r = 0; r < NRuns; r++) {
372  FF.GenGraph(NNodes, GV, true);
373  for (int i = 0; i < GV->Len(); i++) {
374  if (i == GAtTmV.Len()) {
376  }
377  GAtTmV[i]->Add(GV->At(i));
378  }
379  IAssert(GAtTmV.Len() == GV->Len());
380  }
382  for (int i = 0; i < GAtTmV.Len(); i++) {
383  AvgStat->Add(GAtTmV[i]->GetAvgGStat(false));
384  }
385  AvgStat->PlotAllVsX(gsvNodes, FNm, TStr::Fmt("Forest Fire: F:%g B:%g (%d runs)", FProb, BProb, NRuns));
386  AvgStat->Last()->PlotAll(FNm, TStr::Fmt("Forest Fire: F:%g B:%g (%d runs)", FProb, BProb, NRuns));
387 }
#define IAssert(Cond)
Definition: bd.h:262
static TFSet AllStat()
Definition: gstat.cpp:401
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
Definition: tm.h:14
static int NDiamRuns
Definition: gstat.h:38
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
Definition: bd.h:196
Definition: gstat.h:16
static PGStatVec New(const TTmUnit &_TmUnit=tmu1Sec)
Definition: gstat.cpp:426
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
Definition: ff.h:49
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429

Here is the call graph for this function:

TFfGGen::TStopReason TFfGGen::GenGraph ( const int &  GraphNodes,
const bool &  FloodStop = true 
)

Definition at line 327 of file ff.cpp.

References AddNodes(), Graph, and TPt< TNGraph >::New().

Referenced by GenFFGraphs(), TForestFire::GenGraph(), and main().

327  {
328  Graph = PNGraph::New();
329  return AddNodes(GraphNodes, FloodStop);
330 }
PNGraph Graph
Definition: ff.h:54
static TPt New()
Definition: bd.h:479
TStopReason AddNodes(const int &GraphNodes, const bool &FloodStop=true)
Definition: ff.cpp:272

Here is the call graph for this function:

Here is the caller graph for this function:

TFfGGen::TStopReason TFfGGen::GenGraph ( const int &  GraphNodes,
PGStatVec EvolStat,
const bool &  FloodStop = true 
)

Definition at line 332 of file ff.cpp.

References AddNodes(), TNGraph::GetNodes(), Graph, TPt< TNGraph >::New(), srOk, srUndef, and StartNodes.

332  {
333  int GrowthStatNodes = 100;
334  Graph = PNGraph::New();
336  TStopReason SR = srUndef;
337  while (Graph->GetNodes() < GraphNodes) {
338  SR = AddNodes(GrowthStatNodes, FloodStop);
339  if (SR != srOk) { return SR; }
340  EvolStat->Add(Graph, TSecTm(Graph->GetNodes()));
341  GrowthStatNodes = int(1.5*GrowthStatNodes);
342  }
343  return SR;
344 }
PNGraph Graph
Definition: ff.h:54
static TPt New()
Definition: bd.h:479
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
TStopReason
Definition: ff.h:51
TStopReason AddNodes(const int &GraphNodes, const bool &FloodStop=true)
Definition: ff.cpp:272
Definition: tm.h:81
TInt StartNodes
Definition: ff.h:57

Here is the call graph for this function:

PNGraph TFfGGen::GetGraph ( ) const
inline

Definition at line 64 of file ff.h.

References Graph.

Referenced by TForestFire::GenGraph(), and main().

64 { return Graph; }
PNGraph Graph
Definition: ff.h:54

Here is the caller graph for this function:

TStr TFfGGen::GetParamStr ( ) const

Definition at line 267 of file ff.cpp.

References BckBurnProb, BurnExpFire, TStr::Fmt(), FwdBurnProb, OrphanProb, ProbDecay, StartNodes, and Take2AmbProb.

267  {
268  return TStr::Fmt("%s FWD:%g BCK:%g, StartNds:%d, Take2:%g, Orphan:%g, ProbDecay:%g",
270 }
TBool BurnExpFire
Definition: ff.h:56
TFlt BckBurnProb
Definition: ff.h:58
TFlt OrphanProb
Definition: ff.h:59
TFlt ProbDecay
Definition: ff.h:58
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TFlt FwdBurnProb
Definition: ff.h:58
TFlt Take2AmbProb
Definition: ff.h:59
TInt StartNodes
Definition: ff.h:57

Here is the call graph for this function:

void TFfGGen::PlotFireSize ( const TStr FNmPref,
const TStr DescStr 
)

Definition at line 346 of file ff.cpp.

References TVec< TVal, TSizeTy >::Add(), TGnuPlot::AddPlot(), TNGraph::BegNI(), TStr::CStr(), TNGraph::EndNI(), TStr::Fmt(), TNGraph::GetEdges(), TNGraph::GetNodes(), gpwImpulses, Graph, TGnuPlot::SavePng(), TGnuPlot::SetXYLabel(), and TVec< TVal, TSizeTy >::Sort().

346  {
347  TGnuPlot GnuPlot("fs."+FNmPref, TStr::Fmt("%s. Fire size. G(%d, %d)",
348  DescStr.CStr(), Graph->GetNodes(), Graph->GetEdges()));
349  GnuPlot.SetXYLabel("Vertex id (iterations)", "Fire size (node out-degree)");
350  TFltPrV IdToOutDegV;
351  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
352  IdToOutDegV.Add(TFltPr(NI.GetId(), NI.GetOutDeg())); }
353  IdToOutDegV.Sort();
354  GnuPlot.AddPlot(IdToOutDegV, gpwImpulses, "Node out-degree");
355  GnuPlot.SavePng();
356 }
PNGraph Graph
Definition: ff.h:54
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
char * CStr()
Definition: dt.h:476
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429

Here is the call graph for this function:

void TFfGGen::SetGraph ( const PNGraph NGraph)
inline

Definition at line 65 of file ff.h.

References Graph.

65 { Graph = NGraph; }
PNGraph Graph
Definition: ff.h:54

Member Data Documentation

TFlt TFfGGen::BckBurnProb
private

Definition at line 58 of file ff.h.

Referenced by AddNodes(), and GetParamStr().

TBool TFfGGen::BurnExpFire
private

Definition at line 56 of file ff.h.

Referenced by AddNodes(), and GetParamStr().

TFlt TFfGGen::FwdBurnProb
private

Definition at line 58 of file ff.h.

Referenced by AddNodes(), and GetParamStr().

PNGraph TFfGGen::Graph
private

Definition at line 54 of file ff.h.

Referenced by AddNodes(), Clr(), GenGraph(), GetGraph(), PlotFireSize(), and SetGraph().

TFlt TFfGGen::OrphanProb
private

Definition at line 59 of file ff.h.

Referenced by AddNodes(), and GetParamStr().

TFlt TFfGGen::ProbDecay
private

Definition at line 58 of file ff.h.

Referenced by AddNodes(), and GetParamStr().

TInt TFfGGen::StartNodes
private

Definition at line 57 of file ff.h.

Referenced by AddNodes(), GenGraph(), and GetParamStr().

TFlt TFfGGen::Take2AmbProb
private

Definition at line 59 of file ff.h.

Referenced by AddNodes(), and GetParamStr().

int TFfGGen::TimeLimitSec = 30*60
static

Definition at line 52 of file ff.h.

Referenced by AddNodes().


The documentation for this class was generated from the following files: