#include <ff.h>

Public Types
enum	TStopReason { srUndef, srOk, srFlood, srTimeLimit }
Public Member Functions
	TFfGGen (const bool &BurnExpFireP, const int &StartNNodes, const double &ForwBurnProb, const double &BackBurnProb, const double &DecayProb, const double &Take2AmbasPrb, const double &OrphanPrb)
PNGraph	GetGraph () const
void	SetGraph (const PNGraph &NGraph)
void	Clr ()
TStr	GetParamStr () const
TStopReason	AddNodes (const int &GraphNodes, const bool &FloodStop=true)
TStopReason	GenGraph (const int &GraphNodes, const bool &FloodStop=true)
TStopReason	GenGraph (const int &GraphNodes, PGStatVec &EvolStat, const bool &FloodStop=true)
void	PlotFireSize (const TStr &FNmPref, const TStr &DescStr)
Static Public Member Functions
static void	GenFFGraphs (const double &FProb, const double &BProb, const TStr &FNm)
Static Public Attributes
static int	TimeLimitSec = 30*60
Private Attributes
PNGraph	Graph
TBool	BurnExpFire
TInt	StartNodes
TFlt	FwdBurnProb
TFlt	BckBurnProb
TFlt	ProbDecay
TFlt	Take2AmbProb
TFlt	OrphanProb

Detailed Description

Forest Fire Graph Generator. For more details is "Graph Evolution: Densification and Shrinking Diameters" by J. Leskovec, J. Kleinberg, C. Faloutsos. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1), 2007.

Definition at line 49 of file ff.h.

Member Enumeration Documentation

enum TFfGGen::TStopReason

Enumerator:

srUndef
srOk
srFlood
srTimeLimit

Definition at line 51 of file ff.h.

{ srUndef, srOk, srFlood, srTimeLimit } TStopReason;

Constructor & Destructor Documentation

TFfGGen::TFfGGen	(	const bool &	BurnExpFireP,
		const int &	StartNNodes,
		const double &	ForwBurnProb,
		const double &	BackBurnProb,
		const double &	DecayProb,
		const double &	Take2AmbasPrb,
		const double &	OrphanPrb
	)

Definition at line 260 of file ff.cpp.

                                                                                                                            :
 Graph(), BurnExpFire(BurnExpFireP), StartNodes(StartNNodes), FwdBurnProb(ForwBurnProb),
 BckBurnProb(BackBurnProb), ProbDecay(DecayProb), Take2AmbProb(Take2AmbasPrb), OrphanProb(OrphanPrb) {
  //IAssert(ProbDecay == 1.0); // do not need Decay any more
}

Member Function Documentation

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

Definition at line 272 of file ff.cpp.

                                                                                 {
  printf("\n***ForestFire:  %s  Nodes:%d  StartNodes:%d  Take2AmbProb:%g\n", BurnExpFire?"ExpFire":"GeoFire", GraphNodes, StartNodes(), Take2AmbProb());
  printf("                FwdBurnP:%g  BckBurnP:%g  ProbDecay:%g  Orphan:%g\n", FwdBurnProb(), BckBurnProb(), ProbDecay(), OrphanProb());
  TExeTm ExeTm;
  int Burned1=0, Burned2=0, Burned3=0; // last 3 fire sizes
  // create initial set of nodes
  if (Graph.Empty()) { Graph = PNGraph::New(); }
  if (Graph->GetNodes() == 0) {
    for (int n = 0; n < StartNodes; n++) { Graph->AddNode(); }
  }
  int NEdges = Graph->GetEdges();
  // forest fire
  TRnd Rnd(0);
  TForestFire ForestFire(Graph, FwdBurnProb, BckBurnProb, ProbDecay, 0);
  // add nodes
  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
    // not an Orphan (burn fire)
    if (OrphanProb == 0.0 || Rnd.GetUniDev() > OrphanProb) {
      // infect ambassadors
      if (Take2AmbProb == 0.0 || Rnd.GetUniDev() > Take2AmbProb || NewNId < 2) {
        ForestFire.Infect(Rnd.GetUniDevInt(NewNId)); // take 1 ambassador
      } else {
        const int AmbassadorNId1 = Rnd.GetUniDevInt(NewNId);
        int AmbassadorNId2 = Rnd.GetUniDevInt(NewNId);
        while (AmbassadorNId1 == AmbassadorNId2) {
          AmbassadorNId2 = Rnd.GetUniDevInt(NewNId); }
        ForestFire.Infect(TIntV::GetV(AmbassadorNId1, AmbassadorNId2)); // take 2 ambassadors
      }
      // burn fire
      if (BurnExpFire) { ForestFire.BurnExpFire(); }
      else { ForestFire.BurnGeoFire(); }
      // add edges to burned nodes
      for (int e = 0; e < ForestFire.GetBurned(); e++) {
        Graph->AddEdge(NewNId, ForestFire.GetBurnedNId(e));
        NEdges++;
      }
      Burned1=Burned2;  Burned2=Burned3;  Burned3=ForestFire.GetBurned();
    } else {
      // Orphan (zero out-links)
      Burned1=Burned2;  Burned2=Burned3;  Burned3=0;
    }
    if (NNodes % Kilo(1) == 0) {
      printf("(%d, %d)  burned: [%d,%d,%d]  [%s]\n", NNodes, NEdges, Burned1, Burned2, Burned3, ExeTm.GetStr()); }
    if (FloodStop && NEdges>GraphNodes && (NEdges/double(NNodes)>1000.0)) { // average node degree is more than 500
      printf(". FLOOD. G(%6d, %6d)\n", NNodes, NEdges);  return srFlood; }
    if (NNodes % 1000 == 0 && TimeLimitSec > 0 && ExeTm.GetSecs() > TimeLimitSec) {
      printf(". TIME LIMIT. G(%d, %d)\n", Graph->GetNodes(), Graph->GetEdges());
      return srTimeLimit; }
  }
  IAssert(Graph->GetEdges() == NEdges);
  return srOk;
}

void TFfGGen::Clr ( ) [inline]

Definition at line 66 of file ff.h.

{ Graph->Clr(); }

void TFfGGen::GenFFGraphs	(	const double &	FProb,
		const double &	BProb,
		const TStr &	FNm
	)		`[static]`

Definition at line 358 of file ff.cpp.

                                                                                   {
  const int NRuns = 10;
  const int NNodes = 10000;
  TGStat::NDiamRuns = 10;
  //const double FProb = 0.35, BProb = 0.20;  // ff1
  //const double FProb = 0.37, BProb = 0.32;  // ff2
  //const double FProb = 0.37, BProb = 0.325; // ff22
  //const double FProb = 0.37, BProb = 0.33;  // ff3
  //const double FProb = 0.37, BProb = 0.35;  // ff4
  //const double FProb = 0.38, BProb = 0.35;  // ff5
  TVec<PGStatVec> GAtTmV;
  TFfGGen FF(false, 1, FProb, BProb, 1.0, 0, 0);
  for (int r = 0; r < NRuns; r++) {
    PGStatVec GV = TGStatVec::New(tmuNodes, TGStat::AllStat());
    FF.GenGraph(NNodes, GV, true);
    for (int i = 0; i < GV->Len(); i++) {
      if (i == GAtTmV.Len()) {
        GAtTmV.Add(TGStatVec::New(tmuNodes, TGStat::AllStat()));
      }
      GAtTmV[i]->Add(GV->At(i));
    }
    IAssert(GAtTmV.Len() == GV->Len());
  }
  PGStatVec AvgStat = TGStatVec::New(tmuNodes, TGStat::AllStat());
  for (int i = 0; i < GAtTmV.Len(); i++) {
    AvgStat->Add(GAtTmV[i]->GetAvgGStat(false));
  }
  AvgStat->PlotAllVsX(gsvNodes, FNm, TStr::Fmt("Forest Fire: F:%g  B:%g (%d runs)", FProb, BProb, NRuns));
  AvgStat->Last()->PlotAll(FNm, TStr::Fmt("Forest Fire: F:%g  B:%g (%d runs)", FProb, BProb, NRuns));
}

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

Definition at line 327 of file ff.cpp.

                                                                                 {
  Graph = PNGraph::New();
  return AddNodes(GraphNodes, FloodStop);
}

TFfGGen::TStopReason TFfGGen::GenGraph	(	const int &	GraphNodes,
		PGStatVec &	EvolStat,
		const bool &	FloodStop = `true`
	)

Definition at line 332 of file ff.cpp.

                                                                                                      {
  int GrowthStatNodes = 100;
  Graph = PNGraph::New();
  AddNodes(StartNodes);
  TStopReason SR = srUndef;
  while (Graph->GetNodes() < GraphNodes) {
    SR = AddNodes(GrowthStatNodes, FloodStop);
    if (SR != srOk) { return SR; }
    EvolStat->Add(Graph, TSecTm(Graph->GetNodes()));
    GrowthStatNodes = int(1.5*GrowthStatNodes);
  }
  return SR;
}

PNGraph TFfGGen::GetGraph ( ) const [inline]

Definition at line 64 of file ff.h.

{ return Graph; }

TStr TFfGGen::GetParamStr ( ) const

Definition at line 267 of file ff.cpp.

                                {
  return TStr::Fmt("%s  FWD:%g  BCK:%g, StartNds:%d, Take2:%g, Orphan:%g, ProbDecay:%g",
    BurnExpFire?"EXP":"GEO", FwdBurnProb(), BckBurnProb(), StartNodes(), Take2AmbProb(), OrphanProb(), ProbDecay());
}

void TFfGGen::PlotFireSize	(	const TStr &	FNmPref,
		const TStr &	DescStr
	)

Definition at line 346 of file ff.cpp.

                                                                   {
  TGnuPlot GnuPlot("fs."+FNmPref, TStr::Fmt("%s. Fire size. G(%d, %d)",
    DescStr.CStr(), Graph->GetNodes(), Graph->GetEdges()));
  GnuPlot.SetXYLabel("Vertex id (iterations)", "Fire size (node out-degree)");
  TFltPrV IdToOutDegV;
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    IdToOutDegV.Add(TFltPr(NI.GetId(), NI.GetOutDeg())); }
  IdToOutDegV.Sort();
  GnuPlot.AddPlot(IdToOutDegV, gpwImpulses, "Node out-degree");
  GnuPlot.SavePng();
}