#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 TIntV &	GetBurnedNIdV () 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.

: Rnd(1), Graph(), FwdBurnProb(0.0), BckBurnProb(0.0), ProbDecay(1.0) { }

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.

                                                                                                                                                 :
    Rnd(RndSeed), Graph(GraphPt), FwdBurnProb(ForwBurnProb), BckBurnProb(BackBurnProb), ProbDecay(DecayProb) { }

Member Function Documentation

void TForestFire::BurnExpFire ( )

Definition at line 21 of file ff.cpp.

                              {
  const double OldFwdBurnProb = FwdBurnProb;
  const double OldBckBurnProb = BckBurnProb;
  const int NInfect = InfectNIdV.Len();
  const TNGraph& G = *Graph;
  TIntH BurnedNIdH;               // burned nodes
  TIntV BurningNIdV = InfectNIdV; // currently burning nodes
  TIntV NewBurnedNIdV;            // nodes newly burned in current step
  bool HasAliveNbrs;              // has unburned neighbors
  int NBurned = NInfect, NDiedFire=0;
  for (int i = 0; i < InfectNIdV.Len(); i++) {
    BurnedNIdH.AddDat(InfectNIdV[i]); }
  NBurnedTmV.Clr(false);  NBurningTmV.Clr(false);  NewBurnedTmV.Clr(false);
  for (int time = 0; ; time++) {
    NewBurnedNIdV.Clr(false);
    // for each burning node
    for (int node = 0; node < BurningNIdV.Len(); node++) {
      const int& BurningNId = BurningNIdV[node];
      const TNGraph::TNodeI Node = G.GetNI(BurningNId);
      HasAliveNbrs = false;
      NDiedFire = 0;
      // burn forward links  (out-links)
      for (int e = 0; e < Node.GetOutDeg(); e++) {
        const int OutNId = Node.GetOutNId(e);
        if (! BurnedNIdH.IsKey(OutNId)) { // not yet burned
          HasAliveNbrs = true;
          if (Rnd.GetUniDev() < FwdBurnProb) {
            BurnedNIdH.AddDat(OutNId);  NewBurnedNIdV.Add(OutNId);  NBurned++; }
        }
      }
      // burn backward links (in-links)
      if (BckBurnProb > 0.0) {
        for (int e = 0; e < Node.GetInDeg(); e++) {
          const int InNId = Node.GetInNId(e);
          if (! BurnedNIdH.IsKey(InNId)) { // not yet burned
            HasAliveNbrs = true;
            if (Rnd.GetUniDev() < BckBurnProb) {
              BurnedNIdH.AddDat(InNId);  NewBurnedNIdV.Add(InNId);  NBurned++; }
          }
        }
      }
      if (! HasAliveNbrs) { NDiedFire++; }
    }
    NBurnedTmV.Add(NBurned);
    NBurningTmV.Add(BurningNIdV.Len() - NDiedFire);
    NewBurnedTmV.Add(NewBurnedNIdV.Len());
    //BurningNIdV.AddV(NewBurnedNIdV);   // node is burning eternally
    BurningNIdV.Swap(NewBurnedNIdV);    // node is burning just 1 time step
    if (BurningNIdV.Empty()) break;
    FwdBurnProb = FwdBurnProb * ProbDecay;
    BckBurnProb = BckBurnProb * ProbDecay;
  }
  BurnedNIdV.Gen(BurnedNIdH.Len(), 0);
  for (int i = 0; i < BurnedNIdH.Len(); i++) {
    BurnedNIdV.Add(BurnedNIdH.GetKey(i)); }
  FwdBurnProb = OldFwdBurnProb;
  BckBurnProb = OldBckBurnProb;
}

void TForestFire::BurnGeoFire ( )

Definition at line 82 of file ff.cpp.

                              {
  const double OldFwdBurnProb=FwdBurnProb;
  const double OldBckBurnProb=BckBurnProb;
  const int& NInfect = InfectNIdV.Len();
  const TNGraph& G = *Graph;
  TIntH BurnedNIdH;               // burned nodes
  TIntV BurningNIdV = InfectNIdV; // currently burning nodes
  TIntV NewBurnedNIdV;            // nodes newly burned in current step
  bool HasAliveInNbrs, HasAliveOutNbrs; // has unburned neighbors
  TIntV AliveNIdV;                // NIds of alive neighbors
  int NBurned = NInfect, time;
  for (int i = 0; i < InfectNIdV.Len(); i++) {
    BurnedNIdH.AddDat(InfectNIdV[i]); }
  NBurnedTmV.Clr(false);  NBurningTmV.Clr(false);  NewBurnedTmV.Clr(false);
  for (time = 0; ; time++) {
    NewBurnedNIdV.Clr(false);
    for (int node = 0; node < BurningNIdV.Len(); node++) {
      const int& BurningNId = BurningNIdV[node];
      const TNGraph::TNodeI Node = G.GetNI(BurningNId);
      // find unburned links
      HasAliveOutNbrs = false;
      AliveNIdV.Clr(false); // unburned links
      for (int e = 0; e < Node.GetOutDeg(); e++) {
        const int OutNId = Node.GetOutNId(e);
        if (! BurnedNIdH.IsKey(OutNId)) {
          HasAliveOutNbrs = true;  AliveNIdV.Add(OutNId); }
      }
      // number of links to burn (geometric coin). Can also burn 0 links
      const int BurnNFwdLinks = Rnd.GetGeoDev(1.0-FwdBurnProb) - 1;
      if (HasAliveOutNbrs && BurnNFwdLinks > 0) {
        AliveNIdV.Shuffle(Rnd);
        for (int i = 0; i < TMath::Mn(BurnNFwdLinks, AliveNIdV.Len()); i++) {
          BurnedNIdH.AddDat(AliveNIdV[i]);
          NewBurnedNIdV.Add(AliveNIdV[i]);  NBurned++; }
      }
      // backward links
      if (BckBurnProb > 0.0) {
        // find unburned links
        HasAliveInNbrs = false;
        AliveNIdV.Clr(false);
        for (int e = 0; e < Node.GetInDeg(); e++) {
          const int InNId = Node.GetInNId(e);
          if (! BurnedNIdH.IsKey(InNId)) {
            HasAliveInNbrs = true;  AliveNIdV.Add(InNId); }
        }
         // number of links to burn (geometric coin). Can also burn 0 links
        const int BurnNBckLinks = Rnd.GetGeoDev(1.0-BckBurnProb) - 1;
        if (HasAliveInNbrs && BurnNBckLinks > 0) {
          AliveNIdV.Shuffle(Rnd);
          for (int i = 0; i < TMath::Mn(BurnNBckLinks, AliveNIdV.Len()); i++) {
            BurnedNIdH.AddDat(AliveNIdV[i]);
            NewBurnedNIdV.Add(AliveNIdV[i]);  NBurned++; }
        }
      }
    }
    NBurnedTmV.Add(NBurned);  NBurningTmV.Add(BurningNIdV.Len());  NewBurnedTmV.Add(NewBurnedNIdV.Len());
    // BurningNIdV.AddV(NewBurnedNIdV);   // node is burning eternally
    BurningNIdV.Swap(NewBurnedNIdV);   // node is burning just 1 time step
    if (BurningNIdV.Empty()) break;
    FwdBurnProb = FwdBurnProb * ProbDecay;
    BckBurnProb = BckBurnProb * ProbDecay;
  }
  BurnedNIdV.Gen(BurnedNIdH.Len(), 0);
  for (int i = 0; i < BurnedNIdH.Len(); i++) {
    BurnedNIdV.Add(BurnedNIdH.GetKey(i)); }
  FwdBurnProb = OldFwdBurnProb;
  BckBurnProb = OldBckBurnProb;
}

PNGraph TForestFire::GenGraph	(	const int &	Nodes,
		const double &	FwdProb,
		const double &	BckProb
	)		`[static]`

Definition at line 250 of file ff.cpp.

                                                                                            {
  TFfGGen Ff(false, 1, FwdProb, BckProb, 1.0, 0.0, 0.0);
  Ff.GenGraph(Nodes);
  return Ff.GetGraph();
}

int TForestFire::GetBurned ( ) const [inline]

Definition at line 36 of file ff.h.

{ return BurnedNIdV.Len(); }

int TForestFire::GetBurnedNId ( const int & NIdN ) const [inline]

Definition at line 37 of file ff.h.

{ return BurnedNIdV[NIdN]; }

const TIntV& TForestFire::GetBurnedNIdV ( ) const [inline]

Definition at line 38 of file ff.h.

{ return BurnedNIdV; }

void TForestFire::GetBurnedNIdV ( TIntV & NIdV ) const [inline]

Definition at line 39 of file ff.h.

{ NIdV = BurnedNIdV; }

int TForestFire::GetFireTm ( ) const [inline]

Definition at line 35 of file ff.h.

{ return NBurnedTmV.Len(); } // time of fire

PNGraph TForestFire::GetGraph ( ) const [inline]

Definition at line 23 of file ff.h.

{ return Graph; }

void TForestFire::Infect ( const int & NodeId ) [inline]

Definition at line 27 of file ff.h.

{ InfectNIdV.Gen(1,1);  InfectNIdV[0] = NodeId; }

void TForestFire::Infect ( const TIntV & InfectedNIdV ) [inline]

Definition at line 28 of file ff.h.

{ InfectNIdV = InfectedNIdV; }

void TForestFire::InfectAll ( )

Definition at line 3 of file ff.cpp.

                            {
  InfectNIdV.Gen(Graph->GetNodes());
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    InfectNIdV.Add(NI.GetId()); }
}

void TForestFire::InfectRnd ( const int & NInfect )

Definition at line 9 of file ff.cpp.

                                              {
  IAssert(NInfect < Graph->GetNodes());
  TIntV NIdV(Graph->GetNodes(), 0);
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    NIdV.Add(NI.GetId()); }
  NIdV.Shuffle(Rnd);
  InfectNIdV.Gen(NInfect, 0);
  for (int i = 0; i < NInfect; i++) {
    InfectNIdV.Add(NIdV[i]); }
}

void TForestFire::PlotFire	(	const TStr &	FNmPref,
		const TStr &	Desc,
		const bool &	PlotAllBurned = `false`
	)

Definition at line 240 of file ff.cpp.

                                                                                           {
  TGnuPlot GnuPlot(FNmPref, TStr::Fmt("%s. ForestFire. G(%d, %d). Fwd:%g  Bck:%g  NInfect:%d",
    Desc.CStr(), Graph->GetNodes(), Graph->GetEdges(), FwdBurnProb(), BckBurnProb(), InfectNIdV.Len()));
  GnuPlot.SetXYLabel("TIME EPOCH", "Number of NODES");
  if (PlotAllBurned) GnuPlot.AddPlot(NBurnedTmV, gpwLinesPoints, "All burned nodes till time");
  GnuPlot.AddPlot(NBurningTmV, gpwLinesPoints, "Burning nodes at time");
  GnuPlot.AddPlot(NewBurnedTmV, gpwLinesPoints, "Newly burned nodes at time");
  GnuPlot.SavePng(TFile::GetUniqueFNm(TStr::Fmt("fireSz.%s_#.png", FNmPref.CStr())));
}

void TForestFire::SetBurnProb	(	const double &	ForwBurnProb,
		const double &	BackBurnProb
	)		`[inline]`

Definition at line 24 of file ff.h.

{ FwdBurnProb=ForwBurnProb;  BckBurnProb=BackBurnProb; }

void TForestFire::SetGraph ( const PNGraph & GraphPt ) [inline]

Definition at line 22 of file ff.h.

{ Graph = GraphPt; }

void TForestFire::SetProbDecay ( const double & DecayProb ) [inline]

Definition at line 25 of file ff.h.

{ ProbDecay = DecayProb; }

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:

snap-core/ff.h
snap-core/ff.cpp

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation