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

#include <ff.h>

Collaboration diagram for TForestFire:

List of all members.

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

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

Definition at line 21 of file ff.cpp.

References TVec< TVal >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), BckBurnProb, BurnedNIdV, TVec< TVal >::Clr(), TVec< TVal >::Empty(), FwdBurnProb, TVec< TVal >::Gen(), TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), THash< TKey, TDat, THashFunc >::GetKey(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TRnd::GetUniDev(), Graph, InfectNIdV, THash< TKey, TDat, THashFunc >::IsKey(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal >::Len(), NBurnedTmV, NBurningTmV, NewBurnedTmV, ProbDecay, Rnd, and TVec< TVal >::Swap().

Referenced by TFfGGen::AddNodes().

                              {
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 82 of file ff.cpp.

References TVec< TVal >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), BckBurnProb, BurnedNIdV, TVec< TVal >::Clr(), TVec< TVal >::Empty(), FwdBurnProb, TVec< TVal >::Gen(), TRnd::GetGeoDev(), TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), THash< TKey, TDat, THashFunc >::GetKey(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), Graph, InfectNIdV, THash< TKey, TDat, THashFunc >::IsKey(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal >::Len(), TMath::Mn(), NBurnedTmV, NBurningTmV, NewBurnedTmV, ProbDecay, Rnd, TVec< TVal >::Shuffle(), and TVec< TVal >::Swap().

Referenced by TFfGGen::AddNodes().

                              {
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 250 of file ff.cpp.

References TFfGGen::GenGraph(), and TFfGGen::GetGraph().

Referenced by TSnap::GenForestFire().

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

Here is the call graph for this function:

Here is the caller graph for this function:

int TForestFire::GetBurned ( ) const [inline]

Definition at line 36 of file ff.h.

References BurnedNIdV, and TVec< TVal >::Len().

Referenced by TFfGGen::AddNodes().

{ return BurnedNIdV.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 37 of file ff.h.

References BurnedNIdV.

Referenced by TFfGGen::AddNodes().

{ return BurnedNIdV[NIdN]; }

Here is the caller graph for this function:

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

Definition at line 38 of file ff.h.

References BurnedNIdV.

{ return BurnedNIdV; }
void TForestFire::GetBurnedNIdV ( TIntV NIdV) const [inline]

Definition at line 39 of file ff.h.

References BurnedNIdV.

{ NIdV = BurnedNIdV; }
int TForestFire::GetFireTm ( ) const [inline]

Definition at line 35 of file ff.h.

References TVec< TVal >::Len(), and NBurnedTmV.

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

Here is the call graph for this function:

PNGraph TForestFire::GetGraph ( ) const [inline]

Definition at line 23 of file ff.h.

References Graph.

{ return Graph; }
void TForestFire::Infect ( const int &  NodeId) [inline]

Definition at line 27 of file ff.h.

References TVec< TVal >::Gen(), and InfectNIdV.

Referenced by TFfGGen::AddNodes().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 28 of file ff.h.

References InfectNIdV.

{ InfectNIdV = InfectedNIdV; }

Definition at line 3 of file ff.cpp.

References TVec< TVal >::Add(), TNGraph::BegNI(), TNGraph::EndNI(), TVec< TVal >::Gen(), TNGraph::GetNodes(), Graph, and InfectNIdV.

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

Here is the call graph for this function:

void TForestFire::InfectRnd ( const int &  NInfect)

Definition at line 9 of file ff.cpp.

References TVec< TVal >::Add(), TNGraph::BegNI(), TNGraph::EndNI(), TVec< TVal >::Gen(), TNGraph::GetNodes(), Graph, IAssert, InfectNIdV, and Rnd.

                                              {
  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]); }
}

Here is the call graph for this function:

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

Definition at line 240 of file ff.cpp.

References TGnuPlot::AddPlot(), BckBurnProb, TStr::CStr(), TStr::Fmt(), FwdBurnProb, TNGraph::GetEdges(), TNGraph::GetNodes(), TFile::GetUniqueFNm(), gpwLinesPoints, Graph, InfectNIdV, TVec< TVal >::Len(), NBurnedTmV, NBurningTmV, NewBurnedTmV, TGnuPlot::SavePng(), and TGnuPlot::SetXYLabel().

                                                                                           {
  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())));
}

Here is the call graph for this function:

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

Definition at line 24 of file ff.h.

References BckBurnProb, and FwdBurnProb.

{ FwdBurnProb=ForwBurnProb;  BckBurnProb=BackBurnProb; }
void TForestFire::SetGraph ( const PNGraph GraphPt) [inline]

Definition at line 22 of file ff.h.

References Graph.

{ Graph = GraphPt; }
void TForestFire::SetProbDecay ( const double &  DecayProb) [inline]

Definition at line 25 of file ff.h.

References ProbDecay.

{ ProbDecay = DecayProb; }

Member Data Documentation

Definition at line 10 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), PlotFire(), and SetBurnProb().

Definition at line 12 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), GetBurned(), GetBurnedNId(), and GetBurnedNIdV().

Definition at line 10 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), PlotFire(), and SetBurnProb().

Definition at line 9 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), GetGraph(), InfectAll(), InfectRnd(), PlotFire(), and SetGraph().

Definition at line 11 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), Infect(), InfectAll(), InfectRnd(), and PlotFire().

Definition at line 14 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), GetFireTm(), and PlotFire().

Definition at line 14 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), and PlotFire().

Definition at line 14 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), and PlotFire().

Definition at line 10 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), and SetProbDecay().

Definition at line 8 of file ff.h.

Referenced by BurnExpFire(), BurnGeoFire(), and InfectRnd().


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