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.

: 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.

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< TUNGraph >::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;
}