SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
ff.cpp
Go to the documentation of this file.
1 // Forest Fire
3 void TForestFire::InfectAll() {
4  InfectNIdV.Gen(Graph->GetNodes());
5  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
6  InfectNIdV.Add(NI.GetId()); }
7 }
8 
9 void TForestFire::InfectRnd(const int& NInfect) {
10  IAssert(NInfect < Graph->GetNodes());
11  TIntV NIdV(Graph->GetNodes(), 0);
12  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
13  NIdV.Add(NI.GetId()); }
14  NIdV.Shuffle(Rnd);
15  InfectNIdV.Gen(NInfect, 0);
16  for (int i = 0; i < NInfect; i++) {
17  InfectNIdV.Add(NIdV[i]); }
18 }
19 
20 // burn each link independently (forward with FwdBurnProb, backward with BckBurnProb)
21 void TForestFire::BurnExpFire() {
22  const double OldFwdBurnProb = FwdBurnProb;
23  const double OldBckBurnProb = BckBurnProb;
24  const int NInfect = InfectNIdV.Len();
25  const TNGraph& G = *Graph;
26  TIntH BurnedNIdH; // burned nodes
27  TIntV BurningNIdV = InfectNIdV; // currently burning nodes
28  TIntV NewBurnedNIdV; // nodes newly burned in current step
29  bool HasAliveNbrs; // has unburned neighbors
30  int NBurned = NInfect, NDiedFire=0;
31  for (int i = 0; i < InfectNIdV.Len(); i++) {
32  BurnedNIdH.AddDat(InfectNIdV[i]); }
33  NBurnedTmV.Clr(false); NBurningTmV.Clr(false); NewBurnedTmV.Clr(false);
34  for (int time = 0; ; time++) {
35  NewBurnedNIdV.Clr(false);
36  // for each burning node
37  for (int node = 0; node < BurningNIdV.Len(); node++) {
38  const int& BurningNId = BurningNIdV[node];
39  const TNGraph::TNodeI Node = G.GetNI(BurningNId);
40  HasAliveNbrs = false;
41  NDiedFire = 0;
42  // burn forward links (out-links)
43  for (int e = 0; e < Node.GetOutDeg(); e++) {
44  const int OutNId = Node.GetOutNId(e);
45  if (! BurnedNIdH.IsKey(OutNId)) { // not yet burned
46  HasAliveNbrs = true;
47  if (Rnd.GetUniDev() < FwdBurnProb) {
48  BurnedNIdH.AddDat(OutNId); NewBurnedNIdV.Add(OutNId); NBurned++; }
49  }
50  }
51  // burn backward links (in-links)
52  if (BckBurnProb > 0.0) {
53  for (int e = 0; e < Node.GetInDeg(); e++) {
54  const int InNId = Node.GetInNId(e);
55  if (! BurnedNIdH.IsKey(InNId)) { // not yet burned
56  HasAliveNbrs = true;
57  if (Rnd.GetUniDev() < BckBurnProb) {
58  BurnedNIdH.AddDat(InNId); NewBurnedNIdV.Add(InNId); NBurned++; }
59  }
60  }
61  }
62  if (! HasAliveNbrs) { NDiedFire++; }
63  }
64  NBurnedTmV.Add(NBurned);
65  NBurningTmV.Add(BurningNIdV.Len() - NDiedFire);
66  NewBurnedTmV.Add(NewBurnedNIdV.Len());
67  //BurningNIdV.AddV(NewBurnedNIdV); // node is burning eternally
68  BurningNIdV.Swap(NewBurnedNIdV); // node is burning just 1 time step
69  if (BurningNIdV.Empty()) break;
70  FwdBurnProb = FwdBurnProb * ProbDecay;
71  BckBurnProb = BckBurnProb * ProbDecay;
72  }
73  BurnedNIdV.Gen(BurnedNIdH.Len(), 0);
74  for (int i = 0; i < BurnedNIdH.Len(); i++) {
75  BurnedNIdV.Add(BurnedNIdH.GetKey(i)); }
76  FwdBurnProb = OldFwdBurnProb;
77  BckBurnProb = OldBckBurnProb;
78 }
79 
80 // Node selects N~geometric(1.0-FwdBurnProb)-1 out-links and burns them. Then same for in-links.
81 // geometirc(p) has mean 1/(p), so for given FwdBurnProb, we burn 1/(1-FwdBurnProb)
82 void TForestFire::BurnGeoFire() {
83  const double OldFwdBurnProb=FwdBurnProb;
84  const double OldBckBurnProb=BckBurnProb;
85  const int& NInfect = InfectNIdV.Len();
86  const TNGraph& G = *Graph;
87  TIntH BurnedNIdH; // burned nodes
88  TIntV BurningNIdV = InfectNIdV; // currently burning nodes
89  TIntV NewBurnedNIdV; // nodes newly burned in current step
90  bool HasAliveInNbrs, HasAliveOutNbrs; // has unburned neighbors
91  TIntV AliveNIdV; // NIds of alive neighbors
92  int NBurned = NInfect, time;
93  for (int i = 0; i < InfectNIdV.Len(); i++) {
94  BurnedNIdH.AddDat(InfectNIdV[i]); }
95  NBurnedTmV.Clr(false); NBurningTmV.Clr(false); NewBurnedTmV.Clr(false);
96  for (time = 0; ; time++) {
97  NewBurnedNIdV.Clr(false);
98  for (int node = 0; node < BurningNIdV.Len(); node++) {
99  const int& BurningNId = BurningNIdV[node];
100  const TNGraph::TNodeI Node = G.GetNI(BurningNId);
101  // find unburned links
102  HasAliveOutNbrs = false;
103  AliveNIdV.Clr(false); // unburned links
104  for (int e = 0; e < Node.GetOutDeg(); e++) {
105  const int OutNId = Node.GetOutNId(e);
106  if (! BurnedNIdH.IsKey(OutNId)) {
107  HasAliveOutNbrs = true; AliveNIdV.Add(OutNId); }
108  }
109  // number of links to burn (geometric coin). Can also burn 0 links
110  const int BurnNFwdLinks = Rnd.GetGeoDev(1.0-FwdBurnProb) - 1;
111  if (HasAliveOutNbrs && BurnNFwdLinks > 0) {
112  AliveNIdV.Shuffle(Rnd);
113  for (int i = 0; i < TMath::Mn(BurnNFwdLinks, AliveNIdV.Len()); i++) {
114  BurnedNIdH.AddDat(AliveNIdV[i]);
115  NewBurnedNIdV.Add(AliveNIdV[i]); NBurned++; }
116  }
117  // backward links
118  if (BckBurnProb > 0.0) {
119  // find unburned links
120  HasAliveInNbrs = false;
121  AliveNIdV.Clr(false);
122  for (int e = 0; e < Node.GetInDeg(); e++) {
123  const int InNId = Node.GetInNId(e);
124  if (! BurnedNIdH.IsKey(InNId)) {
125  HasAliveInNbrs = true; AliveNIdV.Add(InNId); }
126  }
127  // number of links to burn (geometric coin). Can also burn 0 links
128  const int BurnNBckLinks = Rnd.GetGeoDev(1.0-BckBurnProb) - 1;
129  if (HasAliveInNbrs && BurnNBckLinks > 0) {
130  AliveNIdV.Shuffle(Rnd);
131  for (int i = 0; i < TMath::Mn(BurnNBckLinks, AliveNIdV.Len()); i++) {
132  BurnedNIdH.AddDat(AliveNIdV[i]);
133  NewBurnedNIdV.Add(AliveNIdV[i]); NBurned++; }
134  }
135  }
136  }
137  NBurnedTmV.Add(NBurned); NBurningTmV.Add(BurningNIdV.Len()); NewBurnedTmV.Add(NewBurnedNIdV.Len());
138  // BurningNIdV.AddV(NewBurnedNIdV); // node is burning eternally
139  BurningNIdV.Swap(NewBurnedNIdV); // node is burning just 1 time step
140  if (BurningNIdV.Empty()) break;
141  FwdBurnProb = FwdBurnProb * ProbDecay;
142  BckBurnProb = BckBurnProb * ProbDecay;
143  }
144  BurnedNIdV.Gen(BurnedNIdH.Len(), 0);
145  for (int i = 0; i < BurnedNIdH.Len(); i++) {
146  BurnedNIdV.Add(BurnedNIdH.GetKey(i)); }
147  FwdBurnProb = OldFwdBurnProb;
148  BckBurnProb = OldBckBurnProb;
149 }
150 
151 /*// exact implementation of the algorithm described in KDD '05 paper
152 void TForestFire::BurnGeoFire() {
153  const double OldFwdBurnProb=FwdBurnProb;
154  const double OldBckBurnProb=BckBurnProb;
155  const double ProbRatio = BckBurnProb/FwdBurnProb;
156  const int NInfect = InfectNIdV.Len();
157  const TNGraph& G = *Graph;
158  TIntH BurnedNIdH; // burned nodes
159  TIntV BurningNIdV = InfectNIdV; // currently burning nodes
160  TIntV NewBurnedNIdV; // nodes newly burned in current step
161  bool HasAliveInNbrs, HasAliveOutNbrs; // has unburned neighbors
162  TIntV AliveNIdV; // NIds of alive neighbors
163  int NBurned = NInfect, time;
164  for (int i = 0; i < InfectNIdV.Len(); i++) {
165  BurnedNIdH.AddDat(InfectNIdV[i]); }
166  NBurnedTmV.Clr(false); NBurningTmV.Clr(false); NewBurnedTmV.Clr(false);
167  for (time = 0; ; time++) {
168  NewBurnedNIdV.Clr(false);
169  for (int node = 0; node < BurningNIdV.Len(); node++) {
170  const int& BurningNId = BurningNIdV[node];
171  const int BurnNLinks = Rnd.GetGeoDev(1.0-(FwdBurnProb)) - 1;
172  const TNGraph::TNode& Node = G.GetNode(BurningNId);
173  // find unburned links
174  if (BurnNLinks > 0) {
175  AliveNIdV.Clr(false);
176  for (int e = 0; e < Node.GetOutDeg(); e++) {
177  const int OutNId = Node.GetOutNId(e);
178  if (! BurnedNIdH.IsKey(OutNId)) { HasAliveOutNbrs=true; AliveNIdV.Add(OutNId); }
179  }
180  for (int e = 0; e < Node.GetInDeg(); e++) {
181  const int InNId = Node.GetInNId(e);
182  if (! BurnedNIdH.IsKey(InNId)) { HasAliveInNbrs=true; AliveNIdV.Add(-InNId); }
183  }
184  AliveNIdV.Shuffle(Rnd);
185  // add links
186  for (int e = i; i < AliveNIdV.Len(); i++) {
187  if (AliveNIdV[i] > 0) BurnedNIdH.AddDat(AliveNIdV[i]);
188  NewBurnedNIdV.Add(AliveNIdV[i]); NBurned++;
189  }
190  }
191  HasAliveOutNbrs = false;
192  AliveNIdV.Clr(false); // unburned links
193  for (int e = 0; e < Node.GetOutDeg(); e++) {
194  const int OutNId = Node.GetOutNId(e);
195  if (! BurnedNIdH.IsKey(OutNId)) {
196  HasAliveOutNbrs = true; AliveNIdV.Add(OutNId); }
197  }
198  // number of links to burn (geometric coin). Can also burn 0 links
199  const int BurnNFwdLinks = Rnd.GetGeoDev(1.0-FwdBurnProb) - 1;
200  if (HasAliveOutNbrs && BurnNFwdLinks > 0) {
201  AliveNIdV.Shuffle(Rnd);
202  for (int i = 0; i < TMath::Mn(BurnNFwdLinks, AliveNIdV.Len()); i++) {
203  BurnedNIdH.AddDat(AliveNIdV[i]);
204  NewBurnedNIdV.Add(AliveNIdV[i]); NBurned++; }
205  }
206  // backward links
207  if (BckBurnProb > 0.0) {
208  // find unburned links
209  HasAliveInNbrs = false;
210  AliveNIdV.Clr(false);
211  for (int e = 0; e < Node.GetInDeg(); e++) {
212  const int InNId = Node.GetInNId(e);
213  if (! BurnedNIdH.IsKey(InNId)) {
214  HasAliveInNbrs = true; AliveNIdV.Add(InNId); }
215  }
216  // number of links to burn (geometric coin). Can also burn 0 links
217  const int BurnNBckLinks = Rnd.GetGeoDev(1.0-BckBurnProb) - 1;
218  if (HasAliveInNbrs && BurnNBckLinks > 0) {
219  AliveNIdV.Shuffle(Rnd);
220  for (int i = 0; i < TMath::Mn(BurnNBckLinks, AliveNIdV.Len()); i++) {
221  BurnedNIdH.AddDat(AliveNIdV[i]);
222  NewBurnedNIdV.Add(AliveNIdV[i]); NBurned++; }
223  }
224  }
225  }
226  NBurnedTmV.Add(NBurned); NBurningTmV.Add(BurningNIdV.Len()); NewBurnedTmV.Add(NewBurnedNIdV.Len());
227  // BurningNIdV.AddV(NewBurnedNIdV); // node is burning eternally
228  BurningNIdV.Swap(NewBurnedNIdV); // node is burning just 1 time step
229  if (BurningNIdV.Empty()) break;
230  FwdBurnProb = FwdBurnProb * ProbDecay;
231  BckBurnProb = BckBurnProb * ProbDecay;
232  }
233  BurnedNIdV.Gen(BurnedNIdH.Len(), 0);
234  for (int i = 0; i < BurnedNIdH.Len(); i++) {
235  BurnedNIdV.Add(BurnedNIdH.GetKey(i)); }
236  FwdBurnProb = OldFwdBurnProb;
237  BckBurnProb = OldBckBurnProb;
238 }//*/
239 
240 void TForestFire::PlotFire(const TStr& FNmPref, const TStr& Desc, const bool& PlotAllBurned) {
241  TGnuPlot GnuPlot(FNmPref, TStr::Fmt("%s. ForestFire. G(%d, %d). Fwd:%g Bck:%g NInfect:%d",
242  Desc.CStr(), Graph->GetNodes(), Graph->GetEdges(), FwdBurnProb(), BckBurnProb(), InfectNIdV.Len()));
243  GnuPlot.SetXYLabel("TIME EPOCH", "Number of NODES");
244  if (PlotAllBurned) GnuPlot.AddPlot(NBurnedTmV, gpwLinesPoints, "All burned nodes till time");
245  GnuPlot.AddPlot(NBurningTmV, gpwLinesPoints, "Burning nodes at time");
246  GnuPlot.AddPlot(NewBurnedTmV, gpwLinesPoints, "Newly burned nodes at time");
247  GnuPlot.SavePng(TFile::GetUniqueFNm(TStr::Fmt("fireSz.%s_#.png", FNmPref.CStr())));
248 }
249 
250 PNGraph TForestFire::GenGraph(const int& Nodes, const double& FwdProb, const double& BckProb) {
251  TFfGGen Ff(false, 1, FwdProb, BckProb, 1.0, 0.0, 0.0);
252  Ff.GenGraph(Nodes);
253  return Ff.GetGraph();
254 }
255 
257 // Forest Fire Graph Generator
258 int TFfGGen::TimeLimitSec = 30*60; // 30 minutes
259 
260 TFfGGen::TFfGGen(const bool& BurnExpFireP, const int& StartNNodes, const double& ForwBurnProb,
261  const double& BackBurnProb, const double& DecayProb, const double& Take2AmbasPrb, const double& OrphanPrb) :
262  Graph(), BurnExpFire(BurnExpFireP), StartNodes(StartNNodes), FwdBurnProb(ForwBurnProb),
263  BckBurnProb(BackBurnProb), ProbDecay(DecayProb), Take2AmbProb(Take2AmbasPrb), OrphanProb(OrphanPrb) {
264  //IAssert(ProbDecay == 1.0); // do not need Decay any more
265 }
266 
267 TStr TFfGGen::GetParamStr() const {
268  return TStr::Fmt("%s FWD:%g BCK:%g, StartNds:%d, Take2:%g, Orphan:%g, ProbDecay:%g",
269  BurnExpFire?"EXP":"GEO", FwdBurnProb(), BckBurnProb(), StartNodes(), Take2AmbProb(), OrphanProb(), ProbDecay());
270 }
271 
272 TFfGGen::TStopReason TFfGGen::AddNodes(const int& GraphNodes, const bool& FloodStop) {
273  printf("\n***ForestFire: %s Nodes:%d StartNodes:%d Take2AmbProb:%g\n", BurnExpFire?"ExpFire":"GeoFire", GraphNodes, StartNodes(), Take2AmbProb());
274  printf(" FwdBurnP:%g BckBurnP:%g ProbDecay:%g Orphan:%g\n", FwdBurnProb(), BckBurnProb(), ProbDecay(), OrphanProb());
275  TExeTm ExeTm;
276  int Burned1=0, Burned2=0, Burned3=0; // last 3 fire sizes
277  // create initial set of nodes
278  if (Graph.Empty()) { Graph = PNGraph::New(); }
279  if (Graph->GetNodes() == 0) {
280  for (int n = 0; n < StartNodes; n++) { Graph->AddNode(); }
281  }
282  int NEdges = Graph->GetEdges();
283  // forest fire
284  TRnd Rnd(0);
285  TForestFire ForestFire(Graph, FwdBurnProb, BckBurnProb, ProbDecay, 0);
286  // add nodes
287  for (int NNodes = Graph->GetNodes()+1; NNodes <= GraphNodes; NNodes++) {
288  const int NewNId = Graph->AddNode(-1);
289  IAssert(NewNId == Graph->GetNodes()-1); // node ids have to be 0...N
290  // not an Orphan (burn fire)
291  if (OrphanProb == 0.0 || Rnd.GetUniDev() > OrphanProb) {
292  // infect ambassadors
293  if (Take2AmbProb == 0.0 || Rnd.GetUniDev() > Take2AmbProb || NewNId < 2) {
294  ForestFire.Infect(Rnd.GetUniDevInt(NewNId)); // take 1 ambassador
295  } else {
296  const int AmbassadorNId1 = Rnd.GetUniDevInt(NewNId);
297  int AmbassadorNId2 = Rnd.GetUniDevInt(NewNId);
298  while (AmbassadorNId1 == AmbassadorNId2) {
299  AmbassadorNId2 = Rnd.GetUniDevInt(NewNId); }
300  ForestFire.Infect(TIntV::GetV(AmbassadorNId1, AmbassadorNId2)); // take 2 ambassadors
301  }
302  // burn fire
303  if (BurnExpFire) { ForestFire.BurnExpFire(); }
304  else { ForestFire.BurnGeoFire(); }
305  // add edges to burned nodes
306  for (int e = 0; e < ForestFire.GetBurned(); e++) {
307  Graph->AddEdge(NewNId, ForestFire.GetBurnedNId(e));
308  NEdges++;
309  }
310  Burned1=Burned2; Burned2=Burned3; Burned3=ForestFire.GetBurned();
311  } else {
312  // Orphan (zero out-links)
313  Burned1=Burned2; Burned2=Burned3; Burned3=0;
314  }
315  if (NNodes % Kilo(1) == 0) {
316  printf("(%d, %d) burned: [%d,%d,%d] [%s]\n", NNodes, NEdges, Burned1, Burned2, Burned3, ExeTm.GetStr()); }
317  if (FloodStop && NEdges>GraphNodes && (NEdges/double(NNodes)>1000.0)) { // average node degree is more than 500
318  printf(". FLOOD. G(%6d, %6d)\n", NNodes, NEdges); return srFlood; }
319  if (NNodes % 1000 == 0 && TimeLimitSec > 0 && ExeTm.GetSecs() > TimeLimitSec) {
320  printf(". TIME LIMIT. G(%d, %d)\n", Graph->GetNodes(), Graph->GetEdges());
321  return srTimeLimit; }
322  }
323  IAssert(Graph->GetEdges() == NEdges);
324  return srOk;
325 }
326 
327 TFfGGen::TStopReason TFfGGen::GenGraph(const int& GraphNodes, const bool& FloodStop) {
328  Graph = PNGraph::New();
329  return AddNodes(GraphNodes, FloodStop);
330 }
331 
332 TFfGGen::TStopReason TFfGGen::GenGraph(const int& GraphNodes, PGStatVec& EvolStat, const bool& FloodStop) {
333  int GrowthStatNodes = 100;
334  Graph = PNGraph::New();
335  AddNodes(StartNodes);
336  TStopReason SR = srUndef;
337  while (Graph->GetNodes() < GraphNodes) {
338  SR = AddNodes(GrowthStatNodes, FloodStop);
339  if (SR != srOk) { return SR; }
340  EvolStat->Add(Graph, TSecTm(Graph->GetNodes()));
341  GrowthStatNodes = int(1.5*GrowthStatNodes);
342  }
343  return SR;
344 }
345 
346 void TFfGGen::PlotFireSize(const TStr& FNmPref, const TStr& DescStr) {
347  TGnuPlot GnuPlot("fs."+FNmPref, TStr::Fmt("%s. Fire size. G(%d, %d)",
348  DescStr.CStr(), Graph->GetNodes(), Graph->GetEdges()));
349  GnuPlot.SetXYLabel("Vertex id (iterations)", "Fire size (node out-degree)");
350  TFltPrV IdToOutDegV;
351  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
352  IdToOutDegV.Add(TFltPr(NI.GetId(), NI.GetOutDeg())); }
353  IdToOutDegV.Sort();
354  GnuPlot.AddPlot(IdToOutDegV, gpwImpulses, "Node out-degree");
355  GnuPlot.SavePng();
356 }
357 
358 void TFfGGen::GenFFGraphs(const double& FProb, const double& BProb, const TStr& FNm) {
359  const int NRuns = 10;
360  const int NNodes = 10000;
361  TGStat::NDiamRuns = 10;
362  //const double FProb = 0.35, BProb = 0.20; // ff1
363  //const double FProb = 0.37, BProb = 0.32; // ff2
364  //const double FProb = 0.37, BProb = 0.325; // ff22
365  //const double FProb = 0.37, BProb = 0.33; // ff3
366  //const double FProb = 0.37, BProb = 0.35; // ff4
367  //const double FProb = 0.38, BProb = 0.35; // ff5
368  TVec<PGStatVec> GAtTmV;
369  TFfGGen FF(false, 1, FProb, BProb, 1.0, 0, 0);
370  for (int r = 0; r < NRuns; r++) {
371  PGStatVec GV = TGStatVec::New(tmuNodes, TGStat::AllStat());
372  FF.GenGraph(NNodes, GV, true);
373  for (int i = 0; i < GV->Len(); i++) {
374  if (i == GAtTmV.Len()) {
375  GAtTmV.Add(TGStatVec::New(tmuNodes, TGStat::AllStat()));
376  }
377  GAtTmV[i]->Add(GV->At(i));
378  }
379  IAssert(GAtTmV.Len() == GV->Len());
380  }
381  PGStatVec AvgStat = TGStatVec::New(tmuNodes, TGStat::AllStat());
382  for (int i = 0; i < GAtTmV.Len(); i++) {
383  AvgStat->Add(GAtTmV[i]->GetAvgGStat(false));
384  }
385  AvgStat->PlotAllVsX(gsvNodes, FNm, TStr::Fmt("Forest Fire: F:%g B:%g (%d runs)", FProb, BProb, NRuns));
386  AvgStat->Last()->PlotAll(FNm, TStr::Fmt("Forest Fire: F:%g B:%g (%d runs)", FProb, BProb, NRuns));
387 }
388 
389 /*/////////////////////////////////////////////////
390 // Forest Fire Phase Transition
391 TFfPhaseTrans::TFfPhaseTrans(const int& NNds, const int& StartNds, const double& Take2AmbPr,
392  const double& ProbOrphan, const double& ProbIncrement, const int& NRunsPerFB) :
393  BurExpFire(false), NNodes(NNds), StartNodes(StartNds), NRuns(NRunsPerFB), Take2AmbProb(Take2AmbPr),
394  OrphanProb(ProbOrphan), ProbInc(ProbIncrement), FBPrGSetH(), FBPrGStatH() {
395  TakeStatSet = TFSet() | gsEffDiam;
396 }
397 
398 PFfPhaseTrans TFfPhaseTrans::New(const int& NNds, const int& StartNds, const double& Take2AmbPr,
399  const double& ProbOrphan, const double& ProbIncrement, const int& NRunsPerFB) {
400  return new TFfPhaseTrans(NNds, StartNds, Take2AmbPr, ProbOrphan, ProbIncrement, NRunsPerFB);
401 }
402 
403 TFfPhaseTrans::TFfPhaseTrans(TSIn& SIn) : BurExpFire(SIn), NNodes(SIn), StartNodes(SIn), NRuns(SIn),
404  Take2AmbProb(SIn), OrphanProb(SIn), ProbInc(SIn), FBPrGSetH(SIn), FBPrGStatH(SIn), TakeStatSet(SIn) {
405 }
406 PFfPhaseTrans TFfPhaseTrans::Load(TSIn& SIn) {
407  return new TFfPhaseTrans(SIn);
408 }
409 
410 void TFfPhaseTrans::Save(TFOut& SOut) const {
411  BurExpFire.Save(SOut); NNodes.Save(SOut);
412  StartNodes.Save(SOut); NRuns.Save(SOut);
413  Take2AmbProb.Save(SOut); OrphanProb.Save(SOut);
414  ProbInc.Save(SOut);
415  FBPrGSetH.Save(SOut); FBPrGStatH.Save(SOut);
416  TakeStatSet.Save(SOut);
417 }
418 
419 TStr TFfPhaseTrans::GetTitleStr(const int& ValN) const {
420  const PGrowthStat AvgStat = GetAvgGStat(ValN);
421  const double AvgDeg = 2.0*AvgStat->Last()->Edges / double(AvgStat->Last()->Nodes);
422  const double DiamCf = GetDecDiam(ValN).Val1;
423  const TFltPr GplCf = GetGplCf(ValN);
424  return TStr::Fmt("FWD: %.4f BCK: %.4f DIAM-INC: %.2f GPL: %.2f (%.2f) AvgDeg:%.1f",
425  GetFProb(ValN), GetBProb(ValN), DiamCf, GplCf.Val1(), GplCf.Val2(), AvgDeg);
426 }
427 
428 TStr TFfPhaseTrans::GetFNm(const TStr& FNmPref) const {
429  return TStr::Fmt("%s.n%dk.s%d", FNmPref.CStr(), int(NNodes/1000.0), StartNodes());
430 }
431 
432 TFltPr TFfPhaseTrans::GetGplCf(const int& ValN) const {
433  const TGrowthSet& GrowthSet = *GetGSet(ValN);
434  TMom GplMom;
435  for (int i = 0; i < GrowthSet.Len(); i++) {
436  GplMom.Add(GrowthSet[i]->GetGplCf());
437  }
438  GplMom.Def();
439  return TFltPr(GplMom.GetMean(), GplMom.GetSDev());
440 }
441 
442 TFltPr TFfPhaseTrans::GetDecDiam(const int& ValN) const {
443  const TGrowthSet& GrowthSet = *GetGSet(ValN);
444  TMom DiamMom;
445  for (int i = 0; i < GrowthSet.Len(); i++) {
446  DiamMom.Add(GrowthSet[i]->IsDecEffDiam());
447  }
448  DiamMom.Def();
449  return TFltPr(DiamMom.GetMean(), DiamMom.GetSDev());
450 }
451 
452 TFltPr TFfPhaseTrans::GetEffDiam(const int& ValN, const int& AtTick) const {
453  const TGrowthSet& GrowthSet = *GetGSet(ValN);
454  TMom DiamMom;
455  for (int i = 0; i < GrowthSet.Len(); i++) {
456  if (AtTick != -1) { DiamMom.Add(GrowthSet[i]->At(AtTick)->EffDiam); }
457  else { DiamMom.Add(GrowthSet[i]->Last()->EffDiam); }
458  }
459  DiamMom.Def();
460  return TFltPr(DiamMom.GetMean(), DiamMom.GetSDev());
461 }
462 
463 void TFfPhaseTrans::GetFProbV(TFltV& FProbV) const {
464  THash<TFlt, TInt> FProbH;
465  for (int i = 0; i < Len(); i++) {
466  FProbH.AddKey(GetFProb(i)); }
467  FProbH.GetKeyV(FProbV);
468  FProbV.Sort();
469 }
470 
471 TFltPr TFfPhaseTrans::RunForestFire(double FwdProb, double BckProb, const bool& Plot) {
472  FwdProb = TMath::Round(FwdProb, 4);
473  BckProb = TMath::Round(BckProb, 4);
474  printf("\n---FwdBurnProb--%g----Back--%g------------------[%s]\n", FwdProb, BckProb, TExeTm::GetCurTm());
475  if (FBPrGStatH.IsKey(TFltPr(FwdProb, BckProb))) {
476  printf("*** SKIP -- already have it\n");
477  const TGrowthStat& Stat = *FBPrGStatH.GetDat(TFltPr(FwdProb, BckProb));
478  return TFltPr(Stat.GetGplCf(), Stat.IsDecEffDiam());
479  }
480  if (BckProb > 1.0) return TFltPr(-1, -1);
481  PGrowthSet GrowthSet = TGrowthSet::New();
482  TExeTm ExeTm;
483  TFfGGen ForestFire(false, StartNodes, FwdProb, BckProb, 1.0, Take2AmbProb, OrphanProb);
484  ForestFire.TakeStat(TakeStatSet); // gsDiam
485  GrowthSet->Clr(false);
486  for (int run = 0; run < NRuns; run++) {
487  printf("\nRUN %d [last run %s]\n", run+1, ExeTm.GetTmStr()); ExeTm.Tick();
488  TFfGGen::TStopReason StopReason =*//* ForestFire.GenGraph(NNodes, true);
489  if (! ForestFire.GetGrowthStat()->Empty()) {
490  GrowthSet->Add(ForestFire.GetGrowthStat()); }
491  }
492  IAssert(! GrowthSet.Empty());
493  // add stat
494  FBPrGSetH.AddDat(TFltPr(FwdProb, BckProb), GrowthSet);
495  PGrowthStat AvgStat = TGrowthStat::New();
496  AvgStat->AvgGrowthStat(*GrowthSet);
497  FBPrGStatH.AddDat(TFltPr(FwdProb, BckProb), AvgStat);
498  const double DiamCf = LastDecDiam().Val1;
499  const double GplCf = LastGplCf().Val1;
500  // plot
501  if (Plot && ! AvgStat.Empty()) {
502  const TStr FNm = TStr::Fmt("F%04d.B%04d", int(FwdProb*10000), int(BckProb*10000));
503  const TStr Title = GetTitleStr(Len()-1);
504  AvgStat->PlotDiam(FNm, Title);
505  AvgStat->PlotGpl(FNm, Title, true, false, false, false, false);
506  }
507  return TFltPr(GplCf, DiamCf);
508 }
509 
510 void TFfPhaseTrans::FwdProbSteps(const double& MinFwdProb, const double& MaxFwdProb, const double& BckProb) {
511  const TStr BinFNm = TFile::GetUniqueFNm(TStr::Fmt("phaseFwd.n%dk.s%d_#.bin", int(NNodes/1000.0), StartNodes()));
512  TFfGGen::TimeLimitSec = 10*60;
513  for (double FwdProb = MinFwdProb; FwdProb <= MaxFwdProb; FwdProb += ProbInc) {
514  RunForestFire(FwdProb, BckProb, true);
515  { TFOut FOut(BinFNm);
516  Save(FOut); }
517  }
518 }
519 
520 void TFfPhaseTrans::FwdProbStepsFact(const double& MinFwdProb, const double& MaxFwdProb, const double& BckFact) {
521  const TStr BinFNm = TFile::GetUniqueFNm(TStr::Fmt("phaseFwd.n%dk.s%d_#.bin", int(NNodes/1000.0), StartNodes()));
522  TFfGGen::TimeLimitSec = 10*60;
523  for (double FwdProb = MinFwdProb; FwdProb <= MaxFwdProb; FwdProb += ProbInc) {
524  RunForestFire(FwdProb, BckFact*FwdProb, true);
525  { TFOut FOut(BinFNm);
526  Save(FOut); }
527  }
528 }
529 
530 void TFfPhaseTrans::FwdBckPhasePlot(const double& MinFwdProb, const double& MaxFwdProb, const double& MinBckFact,
531  const double& MaxBckFact, const int& TimeLimitSec) {
532  const TStr BinFNm = TFile::GetUniqueFNm(TStr::Fmt("phaseFF.n%dk.s%d_#.bin", int(NNodes/1000.0), StartNodes()));
533  TFfGGen::TimeLimitSec = TimeLimitSec;
534  for (double FwdProb = MinFwdProb; FwdProb <= MaxFwdProb; FwdProb += ProbInc) {
535  for (double BckFact = MinBckFact; BckFact < MaxBckFact+0.001; BckFact += ProbInc) {
536  const double BckProb = FwdProb * BckFact;
537  RunForestFire(FwdProb, BckProb, true);
538  { TFOut FOut(BinFNm);
539  Save(FOut); }
540  }
541  }
542 }
543 
544 void TFfPhaseTrans::FindGplPhaseTr(const double& StartFProb, const double& FollowGplCf, const TStr& FNmPref, const TStr& Desc) {
545  const TStr FNm = TStr::Fmt("phGPL.%s", GetFNm(FNmPref).CStr());
546  const double Tolerance = 0.01;
547  const double MinDelta = 0.001;
548  const bool Plot = false;
549  TFfGGen::TimeLimitSec = 10*60;
550  TGrowthStat::MinNodesEdges = 2*(StartNodes-1)+100;
551  const int OldNDiamRuns = TGraphStat::NDiamRuns;
552  TGraphStat::NDiamRuns = 1; //!!! diameter
553  TakeStat(TFSet() | gsEffDiam);
554  FILE *F = fopen((FNm+".txt").CStr(), "wt");
555  fprintf(F, "FollowGplCf: %g\n", FollowGplCf);
556  fprintf(F, "StartNodes: %d\n", StartNodes());
557  fprintf(F, "Take2AmbProb: %g\n", Take2AmbProb());
558  fprintf(F, "OrphanProb: %g\n", OrphanProb());
559  fprintf(F, "Tolerance: %g\n", Tolerance);
560  double FwdProb = StartFProb, LBckRat=0, RBckRat=1, BckRat, GplCf;
561  //TFltPr GplPr;
562  while (FwdProb < 1.0) {
563  while (true) {
564  BckRat = (RBckRat+LBckRat) / 2;
565  fprintf(F, "FWD: %g, (%f -- %f)", FwdProb, LBckRat, RBckRat);
566  GplCf = RunForestFire(FwdProb, FwdProb*BckRat, Plot).Val1;
567  IAssert(GplCf != -1);
568  fprintf(F, " %f gpl: %.4f (%.4f)", BckRat, GplCf, LastGplCf().Val2());
569  if (TMath::IsInEps(GplCf - FollowGplCf, Tolerance)) { fprintf(F, " ***\n"); break; }
570  if (RBckRat-LBckRat < MinDelta) { fprintf(F, " gap\n"); break; }
571  if (GplCf > FollowGplCf) { RBckRat = BckRat; } else { LBckRat = BckRat; }
572  fprintf(F, "\n"); fflush(F);
573  }
574  FwdProb += ProbInc;
575  RBckRat = BckRat+0.01;
576  if (RBckRat > 1.0) RBckRat = 1.0;
577  LBckRat = RBckRat - 0.2;
578  if (LBckRat < 0.0) LBckRat = 0.0;
579  { TFOut FOut(FNm+".bin");
580  Save(FOut); }
581  SaveGplPhaseTr(FollowGplCf, FNmPref, Desc);
582  fprintf(F, "\n");
583  }
584  fclose(F);
585  TGraphStat::NDiamRuns = OldNDiamRuns;
586 }
587 
588 void TFfPhaseTrans::SaveGplPhaseTr(const double& FollowGplCf, const TStr& FNmPref, const TStr& Desc) {
589  const double Tolerance = 0.02;
590  THash<TFlt, TIntFltPr> FProbH;
591  for (int i = 0; i < Len(); i ++) {
592  const double FProb = GetFProb(i);
593  const double GplCf = GetGplCf(i).Val1;
594  if (TMath::IsInEps(GplCf-FollowGplCf, Tolerance)) {
595  if (! FProbH.IsKey(FProb)) {
596  FProbH.AddDat(FProb, TIntFltPr(i, GplCf)); }
597  else {
598  const double bestCf = FProbH.GetDat(FProb).Val2;
599  if (fabs(bestCf - FollowGplCf) > fabs(GplCf - FollowGplCf)) {
600  FProbH.AddDat(FProb, TIntFltPr(i, GplCf)); }
601  }
602  }
603  }
604  TVec<TPair<TFlt, TIntFltPr> > FProbV;
605  FProbH.GetKeyDatPrV(FProbV); FProbV.Sort();
606  const bool HasDiam = TakeStatSet.In(gsEffDiam);
607  FILE *F = fopen(TStr::Fmt("phGPL.%s.tab", GetFNm(FNmPref).CStr()).CStr(), "wt");
608  if (! Desc.Empty()) fprintf(F, "%s\n", Desc.CStr());
609  fprintf(F, "FollowGplCf: %g\n", FollowGplCf);
610  fprintf(F, "StartNodes: %d\n", StartNodes());
611  fprintf(F, "Take2AmbProb: %g\n", Take2AmbProb());
612  fprintf(F, "OrphanProb: %g\n", OrphanProb());
613  fprintf(F, "Tolerance: %g\n", Tolerance);
614  fprintf(F, "id\tFProb\tBProb\tBRatio\tGlp\tGlpDev");
615  if (HasDiam) { fprintf(F, "\tDiamCf\tDiamDev\tEffDiam"); }
616  fprintf(F, "\n");
617  for (int i = 0; i < FProbH.Len(); i++) {
618  const int Id = FProbV[i].Val2.Val1;
619  const TFltPr Gpl = GetGplCf(Id);
620  fprintf(F, "%d\t%f\t%f\t%f\t", Id, GetFProb(Id), GetBProb(Id), GetBProb(Id)/GetFProb(Id));
621  fprintf(F, "%f\t%f", Gpl.Val1(), Gpl.Val2());
622  if (HasDiam) {
623  const TFltPr DiamCf = GetDecDiam(Id);
624  fprintf(F, "\t%f\t%f\t%f", DiamCf.Val1(), DiamCf.Val2(), GetEffDiam(Id, -1).Val1());
625  }
626  fprintf(F, "\n");
627  }
628  fclose(F);
629 }
630 
631 void TFfPhaseTrans::FindDiamPhaseTr(const double& StartFProb, const double& FollowDiamCf, const TStr& FNmPref, const TStr& Desc) {
632  const TStr FNm = TStr::Fmt("phDIAM.%s", GetFNm(FNmPref).CStr());
633  const double Tolerance = 0.01;
634  const double MinDelta = 0.001;
635  const bool Plot = false;
636  TFfGGen::TimeLimitSec = 10*60;
637  const int OldNDiamRuns = TGraphStat::NDiamRuns;
638  TGraphStat::NDiamRuns = 1;
639  TGrowthStat::MinNodesEdges = 2*(StartNodes-1)+100;
640  TakeStat(TFSet() | gsEffDiam);
641  FILE *F = fopen((FNm+".txt").CStr(), "wt");
642  fprintf(F, "FollowDiamCf: %g\n", FollowDiamCf);
643  fprintf(F, "StartNodes: %d\n", StartNodes());
644  fprintf(F, "Take2AmbProb: %g\n", Take2AmbProb());
645  fprintf(F, "OrphanProb: %g\n", OrphanProb());
646  fprintf(F, "Tolerance: %g\n", Tolerance);
647  double FwdProb = StartFProb, LBckRat=0, RBckRat=1, BckRat, DiamCf;
648  //TFltPr GplPr;
649  while (FwdProb < 1.0) {
650  while (true) {
651  BckRat = (RBckRat+LBckRat) / 2;
652  fprintf(F, "FWD: %g, (%f -- %f)", FwdProb, LBckRat, RBckRat);
653  DiamCf = RunForestFire(FwdProb, FwdProb*BckRat, Plot).Val2;
654  IAssert(DiamCf != -1);
655  fprintf(F, " %f diam: %.4f (%.4f)", BckRat, DiamCf, LastDecDiam().Val2());
656  if (TMath::IsInEps(DiamCf - FollowDiamCf, Tolerance)) { fprintf(F, " ***\n"); break; }
657  if (RBckRat-LBckRat < MinDelta) { fprintf(F, " gap\n"); break; }
658  if (DiamCf < FollowDiamCf) { RBckRat = BckRat; } else { LBckRat = BckRat; }
659  fprintf(F, "\n"); fflush(F);
660  }
661  FwdProb += ProbInc;
662  RBckRat = BckRat+0.05;
663  if (RBckRat > 1.0) RBckRat = 1.0;
664  LBckRat = RBckRat - 0.15;
665  if (LBckRat < 0.0) LBckRat = 0.0;
666  { TFOut FOut(FNm+".bin");
667  Save(FOut); }
668  SaveDiamPhaseTr(FollowDiamCf, FNmPref, Desc);
669  fprintf(F, "\n");
670  }
671  fclose(F);
672  TGraphStat::NDiamRuns = OldNDiamRuns;
673 }
674 
675 void TFfPhaseTrans::SaveDiamPhaseTr(const double& FollowDiamCf, const TStr& FNmPref, const TStr& Desc) {
676  const double Tolerance = 0.03;
677  THash<TFlt, TIntFltPr> FProbH;
678  for (int i = 0; i < Len(); i ++) {
679  const double FProb = GetFProb(i);
680  const double DiamCf = GetDecDiam(i).Val1;
681  if (TMath::IsInEps(DiamCf - FollowDiamCf, Tolerance)) {
682  if (! FProbH.IsKey(FProb)) {
683  FProbH.AddDat(FProb, TIntFltPr(i, DiamCf)); }
684  else {
685  const double bestCf = FProbH.GetDat(FProb).Val2;
686  if (fabs(bestCf - FollowDiamCf) > fabs(DiamCf - FollowDiamCf)) {
687  FProbH.AddDat(FProb, TIntFltPr(i, DiamCf)); }
688  }
689  }
690  }
691  TVec<TPair<TFlt, TIntFltPr> > FProbV;
692  FProbH.GetKeyDatPrV(FProbV); FProbV.Sort();
693  FILE *F = fopen(TStr::Fmt("phDIAM.%s.tab", GetFNm(FNmPref).CStr()).CStr(), "wt");
694  if (! Desc.Empty()) fprintf(F, "%s\n", Desc.CStr());
695  fprintf(F, "FollowDiamCf: %g\n", FollowDiamCf);
696  fprintf(F, "StartNodes: %d\n", StartNodes());
697  fprintf(F, "Take2AmbProb: %g\n", Take2AmbProb());
698  fprintf(F, "OrphanProb: %g\n", OrphanProb());
699  fprintf(F, "Tolerance: %g\n", Tolerance);
700  fprintf(F, "id\tFProb\tBProb\tBRatio\tDiamCf\tDiamDev\tGplCf\tGplDev\tEffDiam\n");
701  for (int i = 0; i < FProbV.Len(); i++) {
702  const int Id = FProbV[i].Val2.Val1;
703  const TFltPr DiamCf = GetDecDiam(Id);
704  const TFltPr GplCf = GetGplCf(Id);
705  const TFltPr EffDiam = GetEffDiam(Id, -1);
706  fprintf(F, "%d\t%f\t%f\t%f\t", Id, GetFProb(Id), GetBProb(Id), GetBProb(Id)/GetFProb(Id));
707  fprintf(F, "%f\t%f\t%f\t%f\t%f\n", DiamCf.Val1(), DiamCf.Val2(), GplCf.Val1(), GplCf.Val2(), EffDiam.Val1());
708  }
709  fclose(F);
710 }
711 
712 void TFfPhaseTrans::Merge(const PFfPhaseTrans& FfPhaseTrans) {
713  Merge(*FfPhaseTrans);
714 }
715 
716 void TFfPhaseTrans::Merge(const TFfPhaseTrans& FfPhaseTrans) {
717  printf("Merging:\n");
718  printf(" source %6d (Fwd,Bck) pairs\n", FfPhaseTrans.Len());
719  printf(" destination %6d (Fwd,Bck) pairs\n", Len());
720  IAssert(BurExpFire == FfPhaseTrans.BurExpFire);
721  IAssert(NNodes == FfPhaseTrans.NNodes);
722  IAssert(StartNodes == FfPhaseTrans.StartNodes);
723  IAssert(Take2AmbProb == FfPhaseTrans.Take2AmbProb);
724  IAssert(FBPrGSetH.Len() == FBPrGStatH.Len());
725  IAssert(FfPhaseTrans.FBPrGSetH.Len() == FfPhaseTrans.FBPrGStatH.Len());
726  for (int i1 = 0; i1 < FfPhaseTrans.FBPrGSetH.Len(); i1++) {
727  IAssert(FfPhaseTrans.FBPrGSetH.GetKey(i1) == FfPhaseTrans.FBPrGStatH.GetKey(i1));
728  const TFltPr& Key = FfPhaseTrans.FBPrGSetH.GetKey(i1);
729  if (! FBPrGStatH.IsKey(Key)) {
730  const PGrowthStat Stat = FfPhaseTrans.FBPrGStatH[i1];
731  const PGrowthSet Set = FfPhaseTrans.FBPrGSetH[i1];
732  FBPrGStatH.AddDat(Key, Stat);
733  FBPrGSetH.AddDat(Key, Set);
734  }
735  }
736  printf(" ** merged %6d (Fwd,Bck) pairs\n", Len());
737 }
738 //*/
739 
741 // Undirected Forest Fire (does not densify!)
742 
743 // Node selects N~geometric(1.0-BurnProb)-1 links and burns them.
744 // geometirc(p) has mean 1/(p), so for given BurnProb, we burn 1/(1-BurnProb) links in average
745 int TUndirFFire::BurnGeoFire(const int& StartNId) {
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) {
768  AliveNIdV.Shuffle(Rnd);
769  for (int i = 0; i < TMath::Mn(BurnNLinks, AliveNIdV.Len()); i++) {
770  BurnedSet.AddKey(AliveNIdV[i]);
771  NewBurnedNIdV.Add(AliveNIdV[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 }
783 
784 TFfGGen::TStopReason TUndirFFire::AddNodes(const int& GraphNodes, const bool& FloodStop) {
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 }
TForestFire::PlotFire
void PlotFire(const TStr &FNmPref, const TStr &Desc, const bool &PlotAllBurned=false)
Definition: ff.cpp:240
THashSet::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
TForestFire::BurnExpFire
void BurnExpFire()
Definition: ff.cpp:21
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TMath::Mn
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TFfGGen::Graph
PNGraph Graph
Definition: ff.h:54
TFfGGen::BurnExpFire
TBool BurnExpFire
Definition: ff.h:56
TForestFire::GetBurnedNId
int GetBurnedNId(const int &NIdN) const
Definition: ff.h:37
TForestFire::InfectNIdV
TIntV InfectNIdV
Definition: ff.h:11
TNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
TExeTm
Definition: tm.h:355
Kilo
#define Kilo(n)
Definition: gbase.h:3
TRnd
Definition: dt.h:11
TFfGGen::GenGraph
TStopReason GenGraph(const int &GraphNodes, const bool &FloodStop=true)
Definition: ff.cpp:327
TGnuPlot::SavePng
void SavePng(const int &SizeX=1000, const int &SizeY=800, const TStr &Comment=TStr())
Definition: gnuplot.h:120
TNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
TGStat::AllStat
static TFSet AllStat()
Definition: gstat.cpp:401
TPt::New
static TPt New()
Definition: bd.h:479
TFfGGen::BckBurnProb
TFlt BckBurnProb
Definition: ff.h:58
TPt::Empty
bool Empty() const
Definition: bd.h:501
TUndirFFire::BurnedSet
TIntSet BurnedSet
Definition: ff.h:137
TNGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TUNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TUNGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TForestFire::Infect
void Infect(const int &NodeId)
Definition: ff.h:27
TFfGGen::OrphanProb
TFlt OrphanProb
Definition: ff.h:59
TForestFire::NBurnedTmV
TIntV NBurnedTmV
Definition: ff.h:14
TUndirFFire::AddNodes
TFfGGen::TStopReason AddNodes(const int &GraphNodes, const bool &FloodStop=true)
Definition: ff.cpp:784
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503
TGnuPlot::SetXYLabel
void SetXYLabel(const TStr &XLabel, const TStr &YLabel)
Definition: gnuplot.h:73
TUndirFFire::BurnProb
double BurnProb
Definition: ff.h:136
TUndirFFire::BurnGeoFire
int BurnGeoFire(const int &StartNId)
Definition: ff.cpp:745
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TUndirFFire::NewBurnedNIdV
TIntV NewBurnedNIdV
Definition: ff.h:138
TFfGGen::PlotFireSize
void PlotFireSize(const TStr &FNmPref, const TStr &DescStr)
Definition: ff.cpp:346
TForestFire::NBurningTmV
TIntV NBurningTmV
Definition: ff.h:14
TFfGGen::ProbDecay
TFlt ProbDecay
Definition: ff.h:58
TForestFire
Definition: ff.h:6
TFfGGen::TimeLimitSec
static int TimeLimitSec
Definition: ff.h:52
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
TUNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
TFfGGen::TStopReason
TStopReason
Definition: ff.h:51
TForestFire::InfectAll
void InfectAll()
Definition: ff.cpp:3
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TFfGGen::GetParamStr
TStr GetParamStr() const
Definition: ff.cpp:267
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
TUNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:94
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TUNGraph
Undirected graph.
Definition: graph.h:32
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TFile::GetUniqueFNm
static TStr GetUniqueFNm(const TStr &FNm)
Definition: fl.cpp:1281
TUndirFFire::Graph
PUNGraph Graph
Definition: ff.h:135
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
TUNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
TUndirFFire::AliveNIdV
TIntV AliveNIdV
Definition: ff.h:138
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TUndirFFire::BurningNIdV
TIntV BurningNIdV
Definition: ff.h:138
TForestFire::Rnd
TRnd Rnd
Definition: ff.h:8
tmuNodes
Definition: tm.h:14
TFltPr
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TForestFire::InfectRnd
void InfectRnd(const int &NInfect)
Definition: ff.cpp:9
TFfGGen::AddNodes
TStopReason AddNodes(const int &GraphNodes, const bool &FloodStop=true)
Definition: ff.cpp:272
TGStat::NDiamRuns
static int NDiamRuns
Definition: gstat.h:38
TUNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
TFfGGen::TFfGGen
TFfGGen(const bool &BurnExpFireP, const int &StartNNodes, const double &ForwBurnProb, const double &BackBurnProb, const double &DecayProb, const double &Take2AmbasPrb, const double &OrphanPrb)
Definition: ff.cpp:260
TForestFire::BckBurnProb
TFlt BckBurnProb
Definition: ff.h:10
TForestFire::BurnGeoFire
void BurnGeoFire()
Definition: ff.cpp:82
TNGraph
Directed graph.
Definition: graph.h:346
THashSet::Len
int Len() const
Definition: shash.h:1121
TSecTm
Definition: tm.h:81
TForestFire::ProbDecay
TFlt ProbDecay
Definition: ff.h:10
TNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
TUndirFFire::Rnd
TRnd Rnd
Definition: ff.h:134
TUNGraph::TNodeI::GetOutNId
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:106
TForestFire::FwdBurnProb
TFlt FwdBurnProb
Definition: ff.h:10
TNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
TStr
Definition: dt.h:412
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TFfGGen::GetGraph
PNGraph GetGraph() const
Definition: ff.h:64
TVec::Shuffle
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TExeTm::GetSecs
double GetSecs() const
Definition: tm.h:366
TRnd::GetUniDev
double GetUniDev()
Definition: dt.h:30
TFfGGen::FwdBurnProb
TFlt FwdBurnProb
Definition: ff.h:58
TGnuPlot::AddPlot
int AddPlot(const TIntV &YValV, const TGpSeriesTy &SeriesTy=gpwLinesPoints, const TStr &Label=TStr(), const TStr &Style=TStr())
Definition: gnuplot.cpp:186
TForestFire::GetBurned
int GetBurned() const
Definition: ff.h:36
TFfGGen::GenFFGraphs
static void GenFFGraphs(const double &FProb, const double &BProb, const TStr &FNm)
Definition: ff.cpp:358
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
gsvNodes
Definition: gstat.h:16
TRnd::GetGeoDev
int GetGeoDev(const double &Prb)
Definition: dt.h:45
TVec< TInt >::GetV
static TVec< TInt, int > GetV(const TInt &Val1)
Returns a vector on element Val1.
Definition: ds.h:848
TFfGGen::Take2AmbProb
TFlt Take2AmbProb
Definition: ff.h:59
TNGraph::TNodeI::GetInDeg
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:404
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
TFfGGen::StartNodes
TInt StartNodes
Definition: ff.h:57
TStr::CStr
char * CStr()
Definition: dt.h:479
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TNGraph::TNodeI::GetInNId
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:412
TGStatVec::New
static PGStatVec New(const TTmUnit &_TmUnit=tmu1Sec)
Definition: gstat.cpp:426
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TForestFire::GenGraph
static PNGraph GenGraph(const int &Nodes, const double &FwdProb, const double &BckProb)
Definition: ff.cpp:250
TForestFire::BurnedNIdV
TIntV BurnedNIdV
Definition: ff.h:12
TForestFire::Graph
PNGraph Graph
Definition: ff.h:9
THash::Len
int Len() const
Definition: hash.h:228
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TForestFire::NewBurnedTmV
TIntV NewBurnedTmV
Definition: ff.h:14
TFfGGen
Definition: ff.h:49
TNGraph::TNodeI::GetOutNId
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
TUndirFFire::GetBurnedNId
int GetBurnedNId(const int &n) const
Definition: ff.h:144