SNAP Library 3.0, User 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
Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | Private Attributes | List of all members
TFfGGen Class Reference

#include <ff.h>

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

enum TFfGGen::TStopReason
Enumerator
srUndef 
srOk 
srFlood 
srTimeLimit 

Definition at line 51 of file ff.h.

51 { srUndef, srOk, srFlood, srTimeLimit } TStopReason;
TFfGGen::TStopReason
TStopReason
Definition: ff.h:51

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 }
TFfGGen::Graph
PNGraph Graph
Definition: ff.h:54
TFfGGen::BurnExpFire
TBool BurnExpFire
Definition: ff.h:56
TFfGGen::BckBurnProb
TFlt BckBurnProb
Definition: ff.h:58
TFfGGen::OrphanProb
TFlt OrphanProb
Definition: ff.h:59
TFfGGen::ProbDecay
TFlt ProbDecay
Definition: ff.h:58
TFfGGen::FwdBurnProb
TFlt FwdBurnProb
Definition: ff.h:58
TFfGGen::Take2AmbProb
TFlt Take2AmbProb
Definition: ff.h:59
TFfGGen::StartNodes
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.

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);
285  TForestFire ForestFire(Graph, FwdBurnProb, BckBurnProb, ProbDecay, 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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TFfGGen::Graph
PNGraph Graph
Definition: ff.h:54
TFfGGen::BurnExpFire
TBool BurnExpFire
Definition: ff.h:56
TExeTm
Definition: tm.h:355
Kilo
#define Kilo(n)
Definition: gbase.h:3
TRnd
Definition: dt.h:11
TPt< TNGraph >::New
static TPt New()
Definition: bd.h:479
TFfGGen::BckBurnProb
TFlt BckBurnProb
Definition: ff.h:58
TPt::Empty
bool Empty() const
Definition: bd.h:501
TNGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TFfGGen::OrphanProb
TFlt OrphanProb
Definition: ff.h:59
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TFfGGen::ProbDecay
TFlt ProbDecay
Definition: ff.h:58
TForestFire
Definition: ff.h:6
TFfGGen::TimeLimitSec
static int TimeLimitSec
Definition: ff.h:52
TNGraph::AddEdge
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
TExeTm::GetSecs
double GetSecs() const
Definition: tm.h:366
TFfGGen::FwdBurnProb
TFlt FwdBurnProb
Definition: ff.h:58
TVec< TInt >::GetV
static TVec< TInt, TSizeTy > GetV(const TInt &Val1)
Returns a vector on element Val1.
Definition: ds.h:817
TFfGGen::Take2AmbProb
TFlt Take2AmbProb
Definition: ff.h:59
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
TFfGGen::StartNodes
TInt StartNodes
Definition: ff.h:57
void TFfGGen::Clr ( )
inline

Definition at line 66 of file ff.h.

66 { Graph->Clr(); }
TFfGGen::Graph
PNGraph Graph
Definition: ff.h:54
TNGraph::Clr
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:532
void TFfGGen::GenFFGraphs ( const double &  FProb,
const double &  BProb,
const TStr &  FNm 
)
static

Definition at line 358 of file ff.cpp.

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++) {
371  PGStatVec GV = TGStatVec::New(tmuNodes, TGStat::AllStat());
372  FF.GenGraph(NNodes, GV, true);
373  for (int i = 0; i < GV->Len(); i++) {
374  if (i == GAtTmV.Len()) {
375  GAtTmV.Add(TGStatVec::New(tmuNodes, TGStat::AllStat()));
376  }
377  GAtTmV[i]->Add(GV->At(i));
378  }
379  IAssert(GAtTmV.Len() == GV->Len());
380  }
381  PGStatVec AvgStat = TGStatVec::New(tmuNodes, TGStat::AllStat());
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TGStat::AllStat
static TFSet AllStat()
Definition: gstat.cpp:401
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
tmuNodes
Definition: tm.h:14
TGStat::NDiamRuns
static int NDiamRuns
Definition: gstat.h:38
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TPt
Definition: bd.h:196
gsvNodes
Definition: gstat.h:16
TGStatVec::New
static PGStatVec New(const TTmUnit &_TmUnit=tmu1Sec)
Definition: gstat.cpp:426
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TFfGGen
Definition: ff.h:49
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
TFfGGen::TStopReason TFfGGen::GenGraph ( const int &  GraphNodes,
const bool &  FloodStop = true 
)

Definition at line 327 of file ff.cpp.

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

Definition at line 332 of file ff.cpp.

332  {
333  int GrowthStatNodes = 100;
334  Graph = PNGraph::New();
335  AddNodes(StartNodes);
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 }
TFfGGen::Graph
PNGraph Graph
Definition: ff.h:54
TPt< TNGraph >::New
static TPt New()
Definition: bd.h:479
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
TFfGGen::TStopReason
TStopReason
Definition: ff.h:51
TFfGGen::AddNodes
TStopReason AddNodes(const int &GraphNodes, const bool &FloodStop=true)
Definition: ff.cpp:272
TSecTm
Definition: tm.h:81
TFfGGen::StartNodes
TInt StartNodes
Definition: ff.h:57
PNGraph TFfGGen::GetGraph ( ) const
inline

Definition at line 64 of file ff.h.

64 { return Graph; }
TFfGGen::Graph
PNGraph Graph
Definition: ff.h:54
TStr TFfGGen::GetParamStr ( ) const

Definition at line 267 of file ff.cpp.

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

Definition at line 346 of file ff.cpp.

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 }
TFfGGen::Graph
PNGraph Graph
Definition: ff.h:54
TNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
TNGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
TFltPr
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
TStr::CStr
char * CStr()
Definition: dt.h:476
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
void TFfGGen::SetGraph ( const PNGraph &  NGraph)
inline

Definition at line 65 of file ff.h.

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

Member Data Documentation

TFlt TFfGGen::BckBurnProb
private

Definition at line 58 of file ff.h.

TBool TFfGGen::BurnExpFire
private

Definition at line 56 of file ff.h.

TFlt TFfGGen::FwdBurnProb
private

Definition at line 58 of file ff.h.

PNGraph TFfGGen::Graph
private

Definition at line 54 of file ff.h.

TFlt TFfGGen::OrphanProb
private

Definition at line 59 of file ff.h.

TFlt TFfGGen::ProbDecay
private

Definition at line 58 of file ff.h.

TInt TFfGGen::StartNodes
private

Definition at line 57 of file ff.h.

TFlt TFfGGen::Take2AmbProb
private

Definition at line 59 of file ff.h.

int TFfGGen::TimeLimitSec = 30*60
static

Definition at line 52 of file ff.h.

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