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

#include <ff.h>

Collaboration diagram for TUndirFFire:

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.

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

TUndirFFire::BurnProb

double BurnProb

Definition: ff.h:136

TUndirFFire::Graph

PUNGraph Graph

Definition: ff.h:135

TUNGraph::New

static PUNGraph New()

Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().

Definition: graph.h:172

Member Function Documentation

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

Definition at line 784 of file ff.cpp.

References TVec< TVal, TSizeTy >::Add(), TUNGraph::AddEdge(), TUNGraph::AddNode(), BurnGeoFire(), BurnProb, TPt< TRec >::Empty(), GetBurnedNId(), TUNGraph::GetEdges(), TUNGraph::GetNodes(), TRnd::GetUniDevInt(), Graph, IAssert, Kilo, TPt< TRec >::New(), Rnd, TFfGGen::srFlood, and TFfGGen::srOk.

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

Here is the call graph for this function:

int TUndirFFire::BurnGeoFire ( const int & StartNId )

Definition at line 745 of file ff.cpp.

References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), AliveNIdV, BurnedSet, BurningNIdV, BurnProb, TVec< TVal, TSizeTy >::Clr(), THashSet< TKey, THashFunc >::Clr(), TVec< TVal, TSizeTy >::Empty(), TRnd::GetGeoDev(), TUNGraph::GetNI(), TUNGraph::TNodeI::GetOutDeg(), TUNGraph::TNodeI::GetOutNId(), Graph, IAssert, THashSet< TKey, THashFunc >::IsKey(), TVec< TVal, TSizeTy >::Len(), THashSet< TKey, THashFunc >::Len(), TMath::Mn(), NewBurnedNIdV, Rnd, TVec< TVal, TSizeTy >::Shuffle(), and TVec< TVal, TSizeTy >::Swap().

Referenced by AddNodes().

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