SNAP Library 3.0, User 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
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:479
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:483
TGStat::AllStat
static TFSet AllStat()
Definition: gstat.cpp:401
TPt< TNGraph >::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:547
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
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:438
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:168
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:542
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:1047
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:90
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
TUNGraph
Undirected graph.
Definition: graph.h:32
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
TFile::GetUniqueFNm
static TStr GetUniqueFNm(const TStr &FNm)
Definition: fl.cpp:1225
TUndirFFire::Graph
PUNGraph Graph
Definition: ff.h:135
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs 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:213
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:307
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:481
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:102
TForestFire::FwdBurnProb
TFlt FwdBurnProb
Definition: ff.h:10
TNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:362
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:1271
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
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:495
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, TSizeTy > GetV(const TInt &Val1)
Returns a vector on element Val1.
Definition: ds.h:817
TFfGGen::Take2AmbProb
TFlt Take2AmbProb
Definition: ff.h:59
TNGraph::TNodeI::GetInDeg
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:360
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:476
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
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:368
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:574
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:186
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
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:372
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
TUndirFFire::GetBurnedNId
int GetBurnedNId(const int &n) const
Definition: ff.h:144