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

#include <ff.h>

Collaboration diagram for TUndirFFire:

List of all members.

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 >::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 >::Add(), THashSet< TKey, THashFunc >::AddKey(), AliveNIdV, BurnedSet, BurningNIdV, BurnProb, TVec< TVal >::Clr(), THashSet< TKey, THashFunc >::Clr(), TVec< TVal >::Empty(), TRnd::GetGeoDev(), TUNGraph::GetNI(), TUNGraph::TNodeI::GetOutDeg(), TUNGraph::TNodeI::GetOutNId(), Graph, IAssert, THashSet< TKey, THashFunc >::IsKey(), TVec< TVal >::Len(), THashSet< TKey, THashFunc >::Len(), TMath::Mn(), NewBurnedNIdV, Rnd, TVec< TVal >::Shuffle(), and TVec< TVal >::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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int TUndirFFire::GetBurnedNId ( const int &  n) const [inline]

Definition at line 144 of file ff.h.

References BurnedSet.

Referenced by AddNodes().

{ return BurnedSet[n]; }

Here is the caller graph for this function:

PUNGraph TUndirFFire::GetGraph ( ) const [inline]

Definition at line 142 of file ff.h.

References Graph.

{ return Graph; }
int TUndirFFire::GetNBurned ( ) const [inline]

Definition at line 143 of file ff.h.

References BurnedSet, and THashSet< TKey, THashFunc >::Len().

{ return BurnedSet.Len(); }

Here is the call graph for this function:

void TUndirFFire::SetGraph ( const PUNGraph GraphPt) [inline]

Definition at line 141 of file ff.h.

References Graph.

{ Graph = GraphPt; }

Member Data Documentation

Definition at line 138 of file ff.h.

Referenced by BurnGeoFire().

Definition at line 137 of file ff.h.

Referenced by BurnGeoFire(), GetBurnedNId(), and GetNBurned().

Definition at line 138 of file ff.h.

Referenced by BurnGeoFire().

double TUndirFFire::BurnProb [private]

Definition at line 136 of file ff.h.

Referenced by AddNodes(), and BurnGeoFire().

Definition at line 135 of file ff.h.

Referenced by AddNodes(), BurnGeoFire(), GetGraph(), and SetGraph().

Definition at line 138 of file ff.h.

Referenced by BurnGeoFire().

Definition at line 134 of file ff.h.

Referenced by AddNodes(), and BurnGeoFire().


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