TUndirFFire Class Reference

Simulates a single Forest Fire on a undirected graph starting for a given starting node (does not densify!). More...

#include <ff.h>

Public Member Functions
	TUndirFFire (const double &_BurnProb=0.3)
void	SetGraph (const PUNGraph &GraphPt)
PUNGraph	GetGraph () const
int	GetNBurned () const
int	GetBurnedNId (const int &n) const
int	BurnGeoFire (const int &StartNId)
TFfGGen::TStopReason	AddNodes (const int &GraphNodes, const bool &FloodStop=true)

Private Attributes
TRnd	Rnd
PUNGraph	Graph
double	BurnProb
TIntSet	BurnedSet
TIntV	BurningNIdV
TIntV	NewBurnedNIdV
TIntV	AliveNIdV

Detailed Description

Simulates a single Forest Fire on a undirected graph starting for a given starting node (does not densify!).

Definition at line 132 of file ff.h.

Constructor & Destructor Documentation

TUndirFFire::TUndirFFire ( const double &  _BurnProb = 0.3 )

inline

Definition at line 140 of file ff.h.

: Graph(TUNGraph::New()), BurnProb(_BurnProb) { }

Member Function Documentation

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

Definition at line 784 of file ff.cpp.

                                                                                     {
  printf("\n***Undirected GEO ForestFire: graph(%d,%d) add %d nodes, burn prob %.3f\n", 
    Graph->GetNodes(), Graph->GetEdges(), GraphNodes, BurnProb);
  TExeTm ExeTm;
  int Burned1=0, Burned2=0, Burned3=0; // last 3 fire sizes
  TIntPrV NodesEdgesV;
  // create initial set of nodes
  if (Graph.Empty()) { Graph = PUNGraph::New(); }
  if (Graph->GetNodes() == 0) { Graph->AddNode(); }
  int NEdges = Graph->GetEdges();
  // forest fire
  for (int NNodes = Graph->GetNodes()+1; NNodes <= GraphNodes; NNodes++) {
    const int NewNId = Graph->AddNode(-1);
    IAssert(NewNId == Graph->GetNodes()-1); // node ids have to be 0...N
    const int StartNId = Rnd.GetUniDevInt(NewNId);
    const int NBurned = BurnGeoFire(StartNId);
    // add edges to burned nodes
    for (int e = 0; e < NBurned; e++) {
      Graph->AddEdge(NewNId, GetBurnedNId(e)); }
    NEdges += NBurned;
    Burned1=Burned2;  Burned2=Burned3;  Burned3=NBurned;
    if (NNodes % Kilo(1) == 0) {
      printf("(%d, %d)    burned: [%d,%d,%d]  [%s]\n", NNodes, NEdges, Burned1, Burned2, Burned3, ExeTm.GetStr()); 
      NodesEdgesV.Add(TIntPr(NNodes, NEdges));
    }
    if (FloodStop && NEdges>1000 && NEdges/double(NNodes)>100.0) { // average node degree is more than 50
      printf("!!! FLOOD. G(%6d, %6d)\n", NNodes, NEdges);  return TFfGGen::srFlood; }
  }
  printf("\n");
  IAssert(Graph->GetEdges() == NEdges);
  return TFfGGen::srOk;
}

int TUndirFFire::BurnGeoFire

(

const int &

StartNId

)

Definition at line 745 of file ff.cpp.

                                                {
  BurnedSet.Clr(false);
  BurningNIdV.Clr(false);  
  NewBurnedNIdV.Clr(false);
  AliveNIdV.Clr(false);
  const TUNGraph& G = *Graph;
  int NBurned = 1;
  BurnedSet.AddKey(StartNId);
  BurningNIdV.Add(StartNId);
  while (! BurningNIdV.Empty()) {
    for (int node = 0; node < BurningNIdV.Len(); node++) {
      const int& BurningNId = BurningNIdV[node];
      const TUNGraph::TNodeI& Node = G.GetNI(BurningNId);
      // find unburned links
      AliveNIdV.Clr(false); // unburned links
      for (int e = 0; e < Node.GetOutDeg(); e++) {
        const int OutNId = Node.GetOutNId(e);
        if (! BurnedSet.IsKey(OutNId)) {
          AliveNIdV.Add(OutNId); }
      }
      // number of links to burn (geometric coin). Can also burn 0 links
      const int BurnNLinks = Rnd.GetGeoDev(1.0-BurnProb) - 1;
      if (! AliveNIdV.Empty() && BurnNLinks > 0) {
        AliveNIdV.Shuffle(Rnd);
        for (int i = 0; i < TMath::Mn(BurnNLinks, AliveNIdV.Len()); i++) {
          BurnedSet.AddKey(AliveNIdV[i]);
          NewBurnedNIdV.Add(AliveNIdV[i]);
          NBurned++;
        }
      }
    }
    BurningNIdV.Swap(NewBurnedNIdV);   // each node is burning just 1 time step
    // BurningNIdV.AddV(NewBurnedNIdV);   // all nodes are burning eternally
    NewBurnedNIdV.Clr(false);
  }
  IAssert(BurnedSet.Len() == NBurned);
  return NBurned;
}

int TUndirFFire::GetBurnedNId ( const int &  n ) const

inline

Definition at line 144 of file ff.h.

{ return BurnedSet[n]; }

PUNGraph TUndirFFire::GetGraph ( ) const

inline

Definition at line 142 of file ff.h.

{ return Graph; }

int TUndirFFire::GetNBurned ( ) const

inline

Definition at line 143 of file ff.h.

{ return BurnedSet.Len(); }

void TUndirFFire::SetGraph ( const PUNGraph &  GraphPt )

inline

Definition at line 141 of file ff.h.

{ Graph = GraphPt; }

Member Data Documentation

TIntV TUndirFFire::AliveNIdV

private

Definition at line 138 of file ff.h.

TIntSet TUndirFFire::BurnedSet

private

Definition at line 137 of file ff.h.

TIntV TUndirFFire::BurningNIdV

private

Definition at line 138 of file ff.h.

double TUndirFFire::BurnProb

private

Definition at line 136 of file ff.h.

PUNGraph TUndirFFire::Graph

private

Definition at line 135 of file ff.h.

TIntV TUndirFFire::NewBurnedNIdV

private

Definition at line 138 of file ff.h.

TRnd TUndirFFire::Rnd

private

Definition at line 134 of file ff.h.

---

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

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