SNAP Library 3.0, Developer Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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>

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) { }
double BurnProb
Definition: ff.h:136
PUNGraph Graph
Definition: ff.h:135
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:155

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.

784  {
785  printf("\n***Undirected GEO ForestFire: graph(%d,%d) add %d nodes, burn prob %.3f\n",
786  Graph->GetNodes(), Graph->GetEdges(), GraphNodes, BurnProb);
787  TExeTm ExeTm;
788  int Burned1=0, Burned2=0, Burned3=0; // last 3 fire sizes
789  TIntPrV NodesEdgesV;
790  // create initial set of nodes
791  if (Graph.Empty()) { Graph = PUNGraph::New(); }
792  if (Graph->GetNodes() == 0) { Graph->AddNode(); }
793  int NEdges = Graph->GetEdges();
794  // forest fire
795  for (int NNodes = Graph->GetNodes()+1; NNodes <= GraphNodes; NNodes++) {
796  const int NewNId = Graph->AddNode(-1);
797  IAssert(NewNId == Graph->GetNodes()-1); // node ids have to be 0...N
798  const int StartNId = Rnd.GetUniDevInt(NewNId);
799  const int NBurned = BurnGeoFire(StartNId);
800  // add edges to burned nodes
801  for (int e = 0; e < NBurned; e++) {
802  Graph->AddEdge(NewNId, GetBurnedNId(e)); }
803  NEdges += NBurned;
804  Burned1=Burned2; Burned2=Burned3; Burned3=NBurned;
805  if (NNodes % Kilo(1) == 0) {
806  printf("(%d, %d) burned: [%d,%d,%d] [%s]\n", NNodes, NEdges, Burned1, Burned2, Burned3, ExeTm.GetStr());
807  NodesEdgesV.Add(TIntPr(NNodes, NEdges));
808  }
809  if (FloodStop && NEdges>1000 && NEdges/double(NNodes)>100.0) { // average node degree is more than 50
810  printf("!!! FLOOD. G(%6d, %6d)\n", NNodes, NEdges); return TFfGGen::srFlood; }
811  }
812  printf("\n");
813  IAssert(Graph->GetEdges() == NEdges);
814  return TFfGGen::srOk;
815 }
#define IAssert(Cond)
Definition: bd.h:262
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
Definition: tm.h:355
#define Kilo(n)
Definition: gbase.h:3
static TPt New()
Definition: bd.h:479
bool Empty() const
Definition: bd.h:501
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
double BurnProb
Definition: ff.h:136
int BurnGeoFire(const int &StartNId)
Definition: ff.cpp:745
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:168
PUNGraph Graph
Definition: ff.h:135
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
TRnd Rnd
Definition: ff.h:134
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
int GetBurnedNId(const int &n) const
Definition: ff.h:144

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().

745  {
746  BurnedSet.Clr(false);
747  BurningNIdV.Clr(false);
748  NewBurnedNIdV.Clr(false);
749  AliveNIdV.Clr(false);
750  const TUNGraph& G = *Graph;
751  int NBurned = 1;
752  BurnedSet.AddKey(StartNId);
753  BurningNIdV.Add(StartNId);
754  while (! BurningNIdV.Empty()) {
755  for (int node = 0; node < BurningNIdV.Len(); node++) {
756  const int& BurningNId = BurningNIdV[node];
757  const TUNGraph::TNodeI& Node = G.GetNI(BurningNId);
758  // find unburned links
759  AliveNIdV.Clr(false); // unburned links
760  for (int e = 0; e < Node.GetOutDeg(); e++) {
761  const int OutNId = Node.GetOutNId(e);
762  if (! BurnedSet.IsKey(OutNId)) {
763  AliveNIdV.Add(OutNId); }
764  }
765  // number of links to burn (geometric coin). Can also burn 0 links
766  const int BurnNLinks = Rnd.GetGeoDev(1.0-BurnProb) - 1;
767  if (! AliveNIdV.Empty() && BurnNLinks > 0) {
769  for (int i = 0; i < TMath::Mn(BurnNLinks, AliveNIdV.Len()); i++) {
772  NBurned++;
773  }
774  }
775  }
776  BurningNIdV.Swap(NewBurnedNIdV); // each node is burning just 1 time step
777  // BurningNIdV.AddV(NewBurnedNIdV); // all nodes are burning eternally
778  NewBurnedNIdV.Clr(false);
779  }
780  IAssert(BurnedSet.Len() == NBurned);
781  return NBurned;
782 }
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
#define IAssert(Cond)
Definition: bd.h:262
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TIntSet BurnedSet
Definition: ff.h:137
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
double BurnProb
Definition: ff.h:136
TIntV NewBurnedNIdV
Definition: ff.h:138
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:90
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
Undirected graph.
Definition: graph.h:32
PUNGraph Graph
Definition: ff.h:135
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:213
TIntV AliveNIdV
Definition: ff.h:138
int AddKey(const TKey &Key)
Definition: shash.h:1254
TIntV BurningNIdV
Definition: ff.h:138
int Len() const
Definition: shash.h:1121
TRnd Rnd
Definition: ff.h:134
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:102
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1271
int GetGeoDev(const double &Prb)
Definition: dt.h:45
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574

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().

144 { return BurnedSet[n]; }
TIntSet BurnedSet
Definition: ff.h:137

Here is the caller graph for this function:

PUNGraph TUndirFFire::GetGraph ( ) const
inline

Definition at line 142 of file ff.h.

References Graph.

142 { return Graph; }
PUNGraph Graph
Definition: ff.h:135
int TUndirFFire::GetNBurned ( ) const
inline

Definition at line 143 of file ff.h.

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

143 { return BurnedSet.Len(); }
TIntSet BurnedSet
Definition: ff.h:137
int Len() const
Definition: shash.h:1121

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.

141 { Graph = GraphPt; }
PUNGraph Graph
Definition: ff.h:135

Member Data Documentation

TIntV TUndirFFire::AliveNIdV
private

Definition at line 138 of file ff.h.

Referenced by BurnGeoFire().

TIntSet TUndirFFire::BurnedSet
private

Definition at line 137 of file ff.h.

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

TIntV TUndirFFire::BurningNIdV
private

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().

PUNGraph TUndirFFire::Graph
private

Definition at line 135 of file ff.h.

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

TIntV TUndirFFire::NewBurnedNIdV
private

Definition at line 138 of file ff.h.

Referenced by BurnGeoFire().

TRnd TUndirFFire::Rnd
private

Definition at line 134 of file ff.h.

Referenced by AddNodes(), and BurnGeoFire().


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