Changeset - 2ba81931a724
Parent rev.
Child rev.
[Not reviewed]
0 3 1
Tom Bannink - 8 years ago 2017-08-30 16:57:26
tom.bannink@cwi.nl
Add canonical timeevol file
4 files changed with 113 insertions and 17 deletions:
cpp/Makefile
1
cpp/switchchain_canonical_mixingtime.cpp
5
5
cpp/switchchain_canonical_timeevol.cpp
89
triangle_canonical_mixingtime.m
18
12
0 comments (0 inline, 0 general)
cpp/Makefile
➞
Show inline comments
 
@@ -14,6 +14,7 @@ TARGETS += switchchain
 
TARGETS += switchchain_canonical_creationfreqs
 
TARGETS += switchchain_canonical_mixingtime
 
TARGETS += switchchain_canonical_properties
 
TARGETS += switchchain_canonical_timeevol
 
TARGETS += switchchain_ccm_constructionrate
 
TARGETS += switchchain_ccm_cputime
 
TARGETS += switchchain_ccm_initialtris
cpp/switchchain_canonical_mixingtime.cpp
➞
Show inline comments
 
@@ -13,9 +13,9 @@
 

			




	
	
	
		
 
int main(int argc, char* argv[]) {

			




	
	
	
		
 
    // Simulation parameters

			




	
	
	
		
 
    const int numVerticesMin = 2000;

			




	
	
	
		
 
    const int numVerticesMax = 5000;

			




	
	
	
		
 
    const int numVerticesStep = 1000;

			




	
	
	
		
 
    const int numVerticesMin = 10000;

			




	
	
	
		
 
    const int numVerticesMax = 20000;

			




	
	
	
		
 
    const int numVerticesStep = 10000;

			




	
	
	
		
 

			




	
	
	
		
 
    float tauValues[] = {2.1f, 2.3f, 2.5f, 2.7f, 2.9f};

			




	
	
	
		
 

			




	
	
		
 
@@ -52,7 +52,7 @@ int main(int argc, char* argv[]) {

			




	
	
	
		
 
    outfile << "tauValues: " << tauValues << std::endl;

			




	
	
	
		
 
    outfile << "Canonical degree sequence.\n";

			




	
	
	
		
 
    outfile << "sample runs: " << sampleRuns << std::endl;

			




	
	
	
		
 
    outfile << "time stamps: {0.1 n, 0.2 n, ... , 20.0 n}\n";

			




	
	
	
		
 
    outfile << "time stamps: {0.2 n, 0.4 n, 0.6 n, ... , 40.0 n}\n";

			




	
	
	
		
 
    outfile << "For uniform samples:\n";

			




	
	
	
		
 
    outfile << "mixingTime: 50 * (50 - 5 (tau - 2)) n\n";

			




	
	
	
		
 
    outfile << "measurements: 100000\n";

			




	
	
		
 
@@ -103,7 +103,7 @@ int main(int argc, char* argv[]) {

			




	
	
	
		
 
            outfile << '}';

			




	
	
	
		
 
#else

			




	
	
	
		
 
            std::vector<std::pair<int, Histogram>> samples;

			




	
	
	
		
 
            for (int i = 1; i <= 200; i++) {

			




	
	
	
		
 
            for (int i = 2; i <= 400; i += 2) {

			




	
	
	
		
 
                samples.push_back({(i * numVertices / 10), Histogram()});

			




	
	
	
		
 
            }

			




	
	
	
		
 

			




        

    


    
    

    

        

                

                    cpp/switchchain_canonical_timeevol.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
new file 100644

			




	
	
	
		
 
#include "exports.hpp"

			




	
	
	
		
 
#include "graph.hpp"

			




	
	
	
		
 
#include "graph_powerlaw.hpp"

			




	
	
	
		
 
#include "graph_spectrum.hpp"

			




	
	
	
		
 
#include "histogram.hpp"

			




	
	
	
		
 
#include "switchchain.hpp"

			




	
	
	
		
 
#include <algorithm>

			




	
	
	
		
 
#include <fstream>

			




	
	
	
		
 
#include <iostream>

			




	
	
	
		
 
#include <numeric>

			




	
	
	
		
 
#include <random>

			




	
	
	
		
 
#include <vector>

			




	
	
	
		
 

			




	
	
	
		
 
int main(int argc, char* argv[]) {

			




	
	
	
		
 
    // Simulation parameters

			




	
	
	
		
 
    const int numVerticesMin = 1000;

			




	
	
	
		
 
    const int numVerticesMax = 1000;

			




	
	
	
		
 
    const int numVerticesStep = 1000;

			




	
	
	
		
 

			




	
	
	
		
 
    float tauValues[] = {2.1f, 2.3f, 2.5f, 2.7f, 2.9f};

			




	
	
	
		
 

			




	
	
	
		
 
    auto getMeasurements = [](int n, float tau) {

			




	
	
	
		
 
        (void)n;

			




	
	
	
		
 
        (void)tau;

			




	
	
	
		
 
        return 50000;

			




	
	
	
		
 
    };

			




	
	
	
		
 

			




	
	
	
		
 
    // Output file

			




	
	
	
		
 
    std::ofstream outfile;

			




	
	
	
		
 
    if (argc >= 2)

			




	
	
	
		
 
        outfile.open(argv[1]);

			




	
	
	
		
 
    else

			




	
	
	
		
 
        outfile.open("graphdata_canonical_timeevol.m");

			




	
	
	
		
 
    if (!outfile.is_open()) {

			




	
	
	
		
 
        std::cout << "ERROR: Could not open output file.\n";

			




	
	
	
		
 
        return 1;

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
	
		
 
    // Output Mathematica-style comment to indicate file contents

			




	
	
	
		
 
    outfile << "(*\n";

			




	
	
	
		
 
    outfile << "n from " << numVerticesMin << " to " << numVerticesMax

			




	
	
	
		
 
            << " step " << numVerticesStep << std::endl;

			




	
	
	
		
 
    outfile << "tauValues: " << tauValues << std::endl;

			




	
	
	
		
 
    outfile << "Canonical degree sequence.\n";

			




	
	
	
		
 
    outfile << "10 runs per starting point.\n";

			




	
	
	
		
 
    outfile << "Measurements: 50000\n";

			




	
	
	
		
 
    outfile << "data:\n";

			




	
	
	
		
 
    outfile << "1: {n,tau}\n";

			




	
	
	
		
 
    outfile << "2: {triangles}\n";

			




	
	
	
		
 
    outfile << "*)" << std::endl;

			




	
	
	
		
 

			




	
	
	
		
 
    // Mathematica does not accept normal scientific notation

			




	
	
	
		
 
    outfile << std::fixed;

			




	
	
	
		
 
    outfile << '{' << '\n';

			




	
	
	
		
 
    bool outputComma = false;

			




	
	
	
		
 

			




	
	
	
		
 
    SwitchChain chain;

			




	
	
	
		
 
    Graph g;

			




	
	
	
		
 
    for (int numVertices = numVerticesMin; numVertices <= numVerticesMax;

			




	
	
	
		
 
         numVertices += numVerticesStep) {

			




	
	
	
		
 
        for (float tau : tauValues) {

			




	
	
	
		
 
            DegreeSequence ds;

			




	
	
	
		
 
            generateCanonicalPowerlawGraph(numVertices, tau, g, ds);

			




	
	
	
		
 

			




	
	
	
		
 
            std::cout << "Running (n,tau) = (" << numVertices << ',' << tau

			




	
	
	
		
 
                      << "). " << std::flush;

			




	
	
	
		
 

			




	
	
	
		
 
            for (int j = 0; j < 10; ++j) {

			




	
	
	
		
 
                std::vector<int> triangles;

			




	
	
	
		
 
                chain.initialize(g, true);

			




	
	
	
		
 
                int measurements = getMeasurements(numVertices, tau);

			




	
	
	
		
 
                for (int i = 0; i < measurements; ++i) {

			




	
	
	
		
 
                    chain.doMove(true);

			




	
	
	
		
 
                    triangles.push_back(chain.g.getTrackedTriangles());

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                if (outputComma)

			




	
	
	
		
 
                    outfile << ',' << '\n';

			




	
	
	
		
 
                outputComma = true;

			




	
	
	
		
 
                outfile << '{' << '{' << numVertices << ',' << tau << '}';

			




	
	
	
		
 
                outfile << ',' << triangles;

			




	
	
	
		
 
                outfile << '}' << std::flush;

			




	
	
	
		
 
            }

			




	
	
	
		
 
            std::cout << std::endl;

			




	
	
	
		
 
        }

			




	
	
	
		
 
    }

			




	
	
	
		
 
    outfile << '\n' << '}';

			




	
	
	
		
 
    return 0;

			




	
	
	
		
 
}

			




        

    


    
    

    

        

                

                    triangle_canonical_mixingtime.m
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
	
		
 
(* ::Package:: *)

			




	
	
	
		
 

			




	
	
	
		
 
gsraw=Import[NotebookDirectory[]<>"data/graphdata_canonical_mixingtime_histogram.m"];

			




	
	
	
		
 
gsraw=Import[NotebookDirectory[]<>"data/graphdata_canonical_mixingtime_histogram_merged.m"];

			




	
	
	
		
 
gdata=GatherBy[gsraw,{#[[1,2]]&}];

			




	
	
	
		
 
(* Data format: *)

			




	
	
	
		
 
(* gdata[[ tau index, n index, datatype index ]] *)

			




	
	
		
 
@@ -48,9 +48,10 @@ FrameLabel->{"triangles","probability"}

			




	
	
	
		
 
],

			




	
	
	
		
 
ListPlot[normalize[run[[3]]],Joined->True,PlotRange->plotrange,PlotLegends->Placed[{"uniform"},Scaled[{0.7,0.7}]],PlotStyle->{Thick,Black}]]]

			




	
	
	
		
 

			




	
	
	
		
 
plot1=makeHistogram[gdata[[1,-1]],{{3500,7800},{0,0.005}},{10,50,100}]

			




	
	
	
		
 
plot2=makeHistogram2[gdata[[3,-1]],{{50,300},{0,0.04}},{10,20,30}]

			




	
	
	
		
 
plot3=makeHistogram2[gdata[[5,-1]],{{0,70},{0,0.18}},{5,10,20}]

			




	
	
	
		
 
plot1=makeHistogram[gdata[[1,5]],{{3500,7800},{0,0.005}},{10,50,100}]

			




	
	
	
		
 
plot2=makeHistogram2[gdata[[3,5]],{{50,300},{0,0.04}},{10,20,30}]

			




	
	
	
		
 
plot3=makeHistogram2[gdata[[5,5]],{{0,70},{0,0.18}},{5,10,20}]

			




	
	
	
		
 
plot4=makeHistogram[gdata[[1,-1]],Automatic,{50,100,150,200}]

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
Export[NotebookDirectory[]<>"plots/triangle_distributions_over_time.pdf",plot2]

			




	
	
		
 
@@ -79,8 +80,10 @@ m=Min[hist1[[1,1]],hist2[[1,1]]];

			




	
	
	
		
 
M=Max[hist1[[-1,1]],hist2[[-1,1]]];

			




	
	
	
		
 
probs=ConstantArray[0,M-m+1];

			




	
	
	
		
 
probs1=hist1[[All,2]];

			




	
	
	
		
 
(* probs1=GaussianFilter[probs1,10]; (* test *) *)

			




	
	
	
		
 
probs1=probs1/Total[probs1];

			




	
	
	
		
 
probs2=hist2[[All,2]];

			




	
	
	
		
 
(* probs2=GaussianFilter[probs2,10]; (* test *) *)

			




	
	
	
		
 
probs2=probs2/Total[probs2];

			




	
	
	
		
 
probs[[1+hist1[[1,1]]-m;;1+hist1[[-1,1]]-m]]+=probs1;

			




	
	
	
		
 
probs[[1+hist2[[1,1]]-m;;1+hist2[[-1,1]]-m]]-=probs2;

			




	
	
		
 
@@ -105,18 +108,20 @@ ratios=Map[getRatios,gdata,{2}];

			




	
	
	
		
 
(*Map[ListPlot[#[[All,2]],Joined->True,PlotMarkers->Automatic,PlotRange->(1+{-0.15,+0.15}),PlotLegends->#[[All,1]],ImageSize->300]&,ratios]*)

			




	
	
	
		
 
(*Map[ListPlot[#[[All,3]],Joined->True,PlotMarkers->Automatic,PlotRange->(0+{-1,+1}),PlotLegends->#[[All,1]],ImageSize->300]&,ratios]*)

			




	
	
	
		
 
*)

			




	
	
	
		
 
getTVDs[run_]:=Module[{scalefactor},

			




	
	
	
		
 
scalefactor=1/(run[[1,1]]*Log[2,run[[1,1]]]^(1*(4-run[[1,2]])));

			




	
	
	
		
 
{"\[Tau] = "<>ToString[run[[1,2]]],

			




	
	
	
		
 
Map[{#[[1]]*scalefactor,getTVDistance2[#[[2]],run[[3]]]}&,run[[2]]]}

			




	
	
	
		
 
getTVDs[run_]:=Module[{scaling},

			




	
	
	
		
 
scaling[step_,n_,tau_]:=step/(n*Log[n]^(4-tau));

			




	
	
	
		
 
{"n = "<>ToString[run[[1,1]]],"\[Tau] = "<>ToString[run[[1,2]]],

			




	
	
	
		
 
Map[{scaling[#[[1]],run[[1,1]],run[[1,2]]],getTVDistance2[#[[2]],run[[3]]]}&,run[[2]]]}

			




	
	
	
		
 
]

			




	
	
	
		
 
TVDs=Map[getTVDs,gdata,{2}];

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
Map[Show[ListPlot[#[[All,2]],

			




	
	
	
		
 
Map[Show[ListPlot[#[[All,3]],

			




	
	
	
		
 
Joined->True,(*PlotMarkers->Automatic,*)

			




	
	
	
		
 
PlotLegends->#[[All,1]],ImageSize->500,

			




	
	
	
		
 
PlotRange->{0,1},Frame->True,FrameLabel->{"steps / (n (\!\(\*SubscriptBox[\(log\), \(2\)]\)n\!\(\*SuperscriptBox[\()\), \(4 - \[Tau]\)]\))","TV distance"}],

			




	
	
	
		
 
PlotLegends->Placed[#[[All,1]],Center],ImageSize->500,

			




	
	
	
		
 
PlotRange->{0,1},Frame->True,FrameLabel->{"steps / (n (\!\(\*SubscriptBox[\(log\), \(2\)]\)n\!\(\*SuperscriptBox[\()\), \(4 - \[Tau]\)]\))","TV distance"},

			




	
	
	
		
 
PlotLabel->#[[1,2]]

			




	
	
	
		
 
],

			




	
	
	
		
 
Plot[{0.1,0.05},{x,0,20},PlotStyle->Directive[Black,Dashed]]

			




	
	
	
		
 
]&,TVDs]

			




	
	
	
		
 

			




	
	
		
 
@@ -139,8 +144,9 @@ While[i<=Length[run[[2]]],

			




	
	
	
		
 
mixingtimes=Map[getMixingTime,gdata,{2}];

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
scaling[n_,tau_]:=n*Log[n]^(4-tau);

			




	
	
	
		
 
scaling[n_,tau_]:=n*Log[2,n]^(4-tau);

			




	
	
	
		
 
scaling[n_,tau_]:=n;

			




	
	
	
		
 
scaling[n_,tau_]:=n*Log[2,n]^1.5;

			




	
	
	
		
 
plotData=Map[{#[[1]],#[[4]]/scaling[#[[1]],#[[2]]]}&,mixingtimes,{2}]~Join~Map[{#[[1]],#[[3]]/scaling[#[[1]],#[[2]]]}&,mixingtimes,{2}];

			




	
	
	
		
 
fillings={1->{6},2->{7},3->{8},4->{9},5->{10}};

			




	
	
	
		
 
taulabels=Map["\[Tau] = "<>ToString[#[[1,2]]]&,mixingtimes];

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: kalli-2997587
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support