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
TForestFire Class Reference

#include <ff.h>

Public Member Functions

 TForestFire ()
 
 TForestFire (const PNGraph &GraphPt, const double &ForwBurnProb, const double &BackBurnProb, const double &DecayProb=1.0, const int &RndSeed=1)
 
void SetGraph (const PNGraph &GraphPt)
 
PNGraph GetGraph () const
 
void SetBurnProb (const double &ForwBurnProb, const double &BackBurnProb)
 
void SetProbDecay (const double &DecayProb)
 
void Infect (const int &NodeId)
 
void Infect (const TIntV &InfectedNIdV)
 
void InfectAll ()
 
void InfectRnd (const int &NInfect)
 
void BurnExpFire ()
 
void BurnGeoFire ()
 
int GetFireTm () const
 
int GetBurned () const
 
int GetBurnedNId (const int &NIdN) const
 
const TIntVGetBurnedNIdV () const
 
void GetBurnedNIdV (TIntV &NIdV) const
 
void PlotFire (const TStr &FNmPref, const TStr &Desc, const bool &PlotAllBurned=false)
 

Static Public Member Functions

static PNGraph GenGraph (const int &Nodes, const double &FwdProb, const double &BckProb)
 

Private Member Functions

 UndefCopyAssign (TForestFire)
 

Private Attributes

TRnd Rnd
 
PNGraph Graph
 
TFlt FwdBurnProb
 
TFlt BckBurnProb
 
TFlt ProbDecay
 
TIntV InfectNIdV
 
TIntV BurnedNIdV
 
TIntV NBurnedTmV
 
TIntV NBurningTmV
 
TIntV NewBurnedTmV
 

Detailed Description

Simulates a single Forest Fire on a directed graph starting for a given starting node. 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 6 of file ff.h.

Constructor & Destructor Documentation

TForestFire::TForestFire ( )
inline

Definition at line 18 of file ff.h.

18 : Rnd(1), Graph(), FwdBurnProb(0.0), BckBurnProb(0.0), ProbDecay(1.0) { }
TRnd Rnd
Definition: ff.h:8
TFlt BckBurnProb
Definition: ff.h:10
TFlt ProbDecay
Definition: ff.h:10
TFlt FwdBurnProb
Definition: ff.h:10
PNGraph Graph
Definition: ff.h:9
TForestFire::TForestFire ( const PNGraph GraphPt,
const double &  ForwBurnProb,
const double &  BackBurnProb,
const double &  DecayProb = 1.0,
const int &  RndSeed = 1 
)
inline

Definition at line 19 of file ff.h.

19  :
20  Rnd(RndSeed), Graph(GraphPt), FwdBurnProb(ForwBurnProb), BckBurnProb(BackBurnProb), ProbDecay(DecayProb) { }
TRnd Rnd
Definition: ff.h:8
TFlt BckBurnProb
Definition: ff.h:10
TFlt ProbDecay
Definition: ff.h:10
TFlt FwdBurnProb
Definition: ff.h:10
PNGraph Graph
Definition: ff.h:9

Member Function Documentation

void TForestFire::BurnExpFire ( )

Definition at line 21 of file ff.cpp.

21  {
22  const double OldFwdBurnProb = FwdBurnProb;
23  const double OldBckBurnProb = BckBurnProb;
24  const int NInfect = InfectNIdV.Len();
25  const TNGraph& G = *Graph;
26  TIntH BurnedNIdH; // burned nodes
27  TIntV BurningNIdV = InfectNIdV; // currently burning nodes
28  TIntV NewBurnedNIdV; // nodes newly burned in current step
29  bool HasAliveNbrs; // has unburned neighbors
30  int NBurned = NInfect, NDiedFire=0;
31  for (int i = 0; i < InfectNIdV.Len(); i++) {
32  BurnedNIdH.AddDat(InfectNIdV[i]); }
33  NBurnedTmV.Clr(false); NBurningTmV.Clr(false); NewBurnedTmV.Clr(false);
34  for (int time = 0; ; time++) {
35  NewBurnedNIdV.Clr(false);
36  // for each burning node
37  for (int node = 0; node < BurningNIdV.Len(); node++) {
38  const int& BurningNId = BurningNIdV[node];
39  const TNGraph::TNodeI Node = G.GetNI(BurningNId);
40  HasAliveNbrs = false;
41  NDiedFire = 0;
42  // burn forward links (out-links)
43  for (int e = 0; e < Node.GetOutDeg(); e++) {
44  const int OutNId = Node.GetOutNId(e);
45  if (! BurnedNIdH.IsKey(OutNId)) { // not yet burned
46  HasAliveNbrs = true;
47  if (Rnd.GetUniDev() < FwdBurnProb) {
48  BurnedNIdH.AddDat(OutNId); NewBurnedNIdV.Add(OutNId); NBurned++; }
49  }
50  }
51  // burn backward links (in-links)
52  if (BckBurnProb > 0.0) {
53  for (int e = 0; e < Node.GetInDeg(); e++) {
54  const int InNId = Node.GetInNId(e);
55  if (! BurnedNIdH.IsKey(InNId)) { // not yet burned
56  HasAliveNbrs = true;
57  if (Rnd.GetUniDev() < BckBurnProb) {
58  BurnedNIdH.AddDat(InNId); NewBurnedNIdV.Add(InNId); NBurned++; }
59  }
60  }
61  }
62  if (! HasAliveNbrs) { NDiedFire++; }
63  }
64  NBurnedTmV.Add(NBurned);
65  NBurningTmV.Add(BurningNIdV.Len() - NDiedFire);
66  NewBurnedTmV.Add(NewBurnedNIdV.Len());
67  //BurningNIdV.AddV(NewBurnedNIdV); // node is burning eternally
68  BurningNIdV.Swap(NewBurnedNIdV); // node is burning just 1 time step
69  if (BurningNIdV.Empty()) break;
72  }
73  BurnedNIdV.Gen(BurnedNIdH.Len(), 0);
74  for (int i = 0; i < BurnedNIdH.Len(); i++) {
75  BurnedNIdV.Add(BurnedNIdH.GetKey(i)); }
76  FwdBurnProb = OldFwdBurnProb;
77  BckBurnProb = OldBckBurnProb;
78 }
TIntV InfectNIdV
Definition: ff.h:11
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:483
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIntV NBurnedTmV
Definition: ff.h:14
TIntV NBurningTmV
Definition: ff.h:14
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
TRnd Rnd
Definition: ff.h:8
TFlt BckBurnProb
Definition: ff.h:10
Directed graph.
Definition: graph.h:307
TFlt ProbDecay
Definition: ff.h:10
TFlt FwdBurnProb
Definition: ff.h:10
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:362
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
double GetUniDev()
Definition: dt.h:30
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:360
bool IsKey(const TKey &Key) const
Definition: hash.h:216
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:368
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TIntV BurnedNIdV
Definition: ff.h:12
PNGraph Graph
Definition: ff.h:9
int Len() const
Definition: hash.h:186
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
TIntV NewBurnedTmV
Definition: ff.h:14
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:372
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
void TForestFire::BurnGeoFire ( )

Definition at line 82 of file ff.cpp.

82  {
83  const double OldFwdBurnProb=FwdBurnProb;
84  const double OldBckBurnProb=BckBurnProb;
85  const int& NInfect = InfectNIdV.Len();
86  const TNGraph& G = *Graph;
87  TIntH BurnedNIdH; // burned nodes
88  TIntV BurningNIdV = InfectNIdV; // currently burning nodes
89  TIntV NewBurnedNIdV; // nodes newly burned in current step
90  bool HasAliveInNbrs, HasAliveOutNbrs; // has unburned neighbors
91  TIntV AliveNIdV; // NIds of alive neighbors
92  int NBurned = NInfect, time;
93  for (int i = 0; i < InfectNIdV.Len(); i++) {
94  BurnedNIdH.AddDat(InfectNIdV[i]); }
95  NBurnedTmV.Clr(false); NBurningTmV.Clr(false); NewBurnedTmV.Clr(false);
96  for (time = 0; ; time++) {
97  NewBurnedNIdV.Clr(false);
98  for (int node = 0; node < BurningNIdV.Len(); node++) {
99  const int& BurningNId = BurningNIdV[node];
100  const TNGraph::TNodeI Node = G.GetNI(BurningNId);
101  // find unburned links
102  HasAliveOutNbrs = false;
103  AliveNIdV.Clr(false); // unburned links
104  for (int e = 0; e < Node.GetOutDeg(); e++) {
105  const int OutNId = Node.GetOutNId(e);
106  if (! BurnedNIdH.IsKey(OutNId)) {
107  HasAliveOutNbrs = true; AliveNIdV.Add(OutNId); }
108  }
109  // number of links to burn (geometric coin). Can also burn 0 links
110  const int BurnNFwdLinks = Rnd.GetGeoDev(1.0-FwdBurnProb) - 1;
111  if (HasAliveOutNbrs && BurnNFwdLinks > 0) {
112  AliveNIdV.Shuffle(Rnd);
113  for (int i = 0; i < TMath::Mn(BurnNFwdLinks, AliveNIdV.Len()); i++) {
114  BurnedNIdH.AddDat(AliveNIdV[i]);
115  NewBurnedNIdV.Add(AliveNIdV[i]); NBurned++; }
116  }
117  // backward links
118  if (BckBurnProb > 0.0) {
119  // find unburned links
120  HasAliveInNbrs = false;
121  AliveNIdV.Clr(false);
122  for (int e = 0; e < Node.GetInDeg(); e++) {
123  const int InNId = Node.GetInNId(e);
124  if (! BurnedNIdH.IsKey(InNId)) {
125  HasAliveInNbrs = true; AliveNIdV.Add(InNId); }
126  }
127  // number of links to burn (geometric coin). Can also burn 0 links
128  const int BurnNBckLinks = Rnd.GetGeoDev(1.0-BckBurnProb) - 1;
129  if (HasAliveInNbrs && BurnNBckLinks > 0) {
130  AliveNIdV.Shuffle(Rnd);
131  for (int i = 0; i < TMath::Mn(BurnNBckLinks, AliveNIdV.Len()); i++) {
132  BurnedNIdH.AddDat(AliveNIdV[i]);
133  NewBurnedNIdV.Add(AliveNIdV[i]); NBurned++; }
134  }
135  }
136  }
137  NBurnedTmV.Add(NBurned); NBurningTmV.Add(BurningNIdV.Len()); NewBurnedTmV.Add(NewBurnedNIdV.Len());
138  // BurningNIdV.AddV(NewBurnedNIdV); // node is burning eternally
139  BurningNIdV.Swap(NewBurnedNIdV); // node is burning just 1 time step
140  if (BurningNIdV.Empty()) break;
143  }
144  BurnedNIdV.Gen(BurnedNIdH.Len(), 0);
145  for (int i = 0; i < BurnedNIdH.Len(); i++) {
146  BurnedNIdV.Add(BurnedNIdH.GetKey(i)); }
147  FwdBurnProb = OldFwdBurnProb;
148  BckBurnProb = OldBckBurnProb;
149 }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TIntV InfectNIdV
Definition: ff.h:11
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:483
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIntV NBurnedTmV
Definition: ff.h:14
TIntV NBurningTmV
Definition: ff.h:14
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
TRnd Rnd
Definition: ff.h:8
TFlt BckBurnProb
Definition: ff.h:10
Directed graph.
Definition: graph.h:307
TFlt ProbDecay
Definition: ff.h:10
TFlt FwdBurnProb
Definition: ff.h:10
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:362
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1271
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
int GetGeoDev(const double &Prb)
Definition: dt.h:45
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:360
bool IsKey(const TKey &Key) const
Definition: hash.h:216
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:368
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TIntV BurnedNIdV
Definition: ff.h:12
PNGraph Graph
Definition: ff.h:9
int Len() const
Definition: hash.h:186
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
TIntV NewBurnedTmV
Definition: ff.h:14
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:372
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
PNGraph TForestFire::GenGraph ( const int &  Nodes,
const double &  FwdProb,
const double &  BckProb 
)
static

Definition at line 250 of file ff.cpp.

250  {
251  TFfGGen Ff(false, 1, FwdProb, BckProb, 1.0, 0.0, 0.0);
252  Ff.GenGraph(Nodes);
253  return Ff.GetGraph();
254 }
Definition: ff.h:49
int TForestFire::GetBurned ( ) const
inline

Definition at line 36 of file ff.h.

36 { return BurnedNIdV.Len(); }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIntV BurnedNIdV
Definition: ff.h:12
int TForestFire::GetBurnedNId ( const int &  NIdN) const
inline

Definition at line 37 of file ff.h.

37 { return BurnedNIdV[NIdN]; }
TIntV BurnedNIdV
Definition: ff.h:12
const TIntV& TForestFire::GetBurnedNIdV ( ) const
inline

Definition at line 38 of file ff.h.

38 { return BurnedNIdV; }
TIntV BurnedNIdV
Definition: ff.h:12
void TForestFire::GetBurnedNIdV ( TIntV NIdV) const
inline

Definition at line 39 of file ff.h.

39 { NIdV = BurnedNIdV; }
TIntV BurnedNIdV
Definition: ff.h:12
int TForestFire::GetFireTm ( ) const
inline

Definition at line 35 of file ff.h.

35 { return NBurnedTmV.Len(); } // time of fire
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIntV NBurnedTmV
Definition: ff.h:14
PNGraph TForestFire::GetGraph ( ) const
inline

Definition at line 23 of file ff.h.

23 { return Graph; }
PNGraph Graph
Definition: ff.h:9
void TForestFire::Infect ( const int &  NodeId)
inline

Definition at line 27 of file ff.h.

27 { InfectNIdV.Gen(1,1); InfectNIdV[0] = NodeId; }
TIntV InfectNIdV
Definition: ff.h:11
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
void TForestFire::Infect ( const TIntV InfectedNIdV)
inline

Definition at line 28 of file ff.h.

28 { InfectNIdV = InfectedNIdV; }
TIntV InfectNIdV
Definition: ff.h:11
void TForestFire::InfectAll ( )

Definition at line 3 of file ff.cpp.

3  {
5  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
6  InfectNIdV.Add(NI.GetId()); }
7 }
TIntV InfectNIdV
Definition: ff.h:11
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
PNGraph Graph
Definition: ff.h:9
void TForestFire::InfectRnd ( const int &  NInfect)

Definition at line 9 of file ff.cpp.

9  {
10  IAssert(NInfect < Graph->GetNodes());
11  TIntV NIdV(Graph->GetNodes(), 0);
12  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
13  NIdV.Add(NI.GetId()); }
14  NIdV.Shuffle(Rnd);
15  InfectNIdV.Gen(NInfect, 0);
16  for (int i = 0; i < NInfect; i++) {
17  InfectNIdV.Add(NIdV[i]); }
18 }
#define IAssert(Cond)
Definition: bd.h:262
TIntV InfectNIdV
Definition: ff.h:11
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
TRnd Rnd
Definition: ff.h:8
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
PNGraph Graph
Definition: ff.h:9
void TForestFire::PlotFire ( const TStr FNmPref,
const TStr Desc,
const bool &  PlotAllBurned = false 
)

Definition at line 240 of file ff.cpp.

240  {
241  TGnuPlot GnuPlot(FNmPref, TStr::Fmt("%s. ForestFire. G(%d, %d). Fwd:%g Bck:%g NInfect:%d",
243  GnuPlot.SetXYLabel("TIME EPOCH", "Number of NODES");
244  if (PlotAllBurned) GnuPlot.AddPlot(NBurnedTmV, gpwLinesPoints, "All burned nodes till time");
245  GnuPlot.AddPlot(NBurningTmV, gpwLinesPoints, "Burning nodes at time");
246  GnuPlot.AddPlot(NewBurnedTmV, gpwLinesPoints, "Newly burned nodes at time");
247  GnuPlot.SavePng(TFile::GetUniqueFNm(TStr::Fmt("fireSz.%s_#.png", FNmPref.CStr())));
248 }
TIntV InfectNIdV
Definition: ff.h:11
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIntV NBurnedTmV
Definition: ff.h:14
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
TIntV NBurningTmV
Definition: ff.h:14
static TStr GetUniqueFNm(const TStr &FNm)
Definition: fl.cpp:1225
TFlt BckBurnProb
Definition: ff.h:10
TFlt FwdBurnProb
Definition: ff.h:10
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
char * CStr()
Definition: dt.h:476
PNGraph Graph
Definition: ff.h:9
TIntV NewBurnedTmV
Definition: ff.h:14
void TForestFire::SetBurnProb ( const double &  ForwBurnProb,
const double &  BackBurnProb 
)
inline

Definition at line 24 of file ff.h.

24 { FwdBurnProb=ForwBurnProb; BckBurnProb=BackBurnProb; }
TFlt BckBurnProb
Definition: ff.h:10
TFlt FwdBurnProb
Definition: ff.h:10
void TForestFire::SetGraph ( const PNGraph GraphPt)
inline

Definition at line 22 of file ff.h.

22 { Graph = GraphPt; }
PNGraph Graph
Definition: ff.h:9
void TForestFire::SetProbDecay ( const double &  DecayProb)
inline

Definition at line 25 of file ff.h.

25 { ProbDecay = DecayProb; }
TFlt ProbDecay
Definition: ff.h:10
TForestFire::UndefCopyAssign ( TForestFire  )
private

Member Data Documentation

TFlt TForestFire::BckBurnProb
private

Definition at line 10 of file ff.h.

TIntV TForestFire::BurnedNIdV
private

Definition at line 12 of file ff.h.

TFlt TForestFire::FwdBurnProb
private

Definition at line 10 of file ff.h.

PNGraph TForestFire::Graph
private

Definition at line 9 of file ff.h.

TIntV TForestFire::InfectNIdV
private

Definition at line 11 of file ff.h.

TIntV TForestFire::NBurnedTmV
private

Definition at line 14 of file ff.h.

TIntV TForestFire::NBurningTmV
private

Definition at line 14 of file ff.h.

TIntV TForestFire::NewBurnedTmV
private

Definition at line 14 of file ff.h.

TFlt TForestFire::ProbDecay
private

Definition at line 10 of file ff.h.

TRnd TForestFire::Rnd
private

Definition at line 8 of file ff.h.


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