Changeset - dcda30d3618c
Parent rev.
Child rev.
[Not reviewed]
0 1 0
Tom Bannink - 8 years ago 2017-06-11 15:07:19
tombannink@gmail.com
Update spectrum computation
1 file changed with 47 insertions and 23 deletions:
cpp/switchchain_spectrum.cpp
47
23
0 comments (0 inline, 0 general)
cpp/switchchain_spectrum.cpp
➞
Show inline comments
 
@@ -13,38 +13,66 @@
 
#include <vector>
 

			




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

			




	
	
	
		
 
    // Generate a random degree sequence

			




	
	
	
		
 
    std::mt19937 rng(std::random_device{}());

			




	
	
	
		
 
    // Simulation parameters

			




	
	
	
		
 
    const int numVerticesMin = 100;

			




	
	
	
		
 
    const int numVerticesMax = 500;

			




	
	
	
		
 
    const int numVerticesStep = 100;

			




	
	
	
		
 

			




	
	
	
		
 
    // Goal:

			




	
	
	
		
 
    // Degrees follow a power-law distribution with some parameter tau

			




	
	
	
		
 
    // Expect:  #tri = const * n^{ something }

			




	
	
	
		
 
    // The goal is to find the 'something' by finding the number of triangles

			




	
	
	
		
 
    // for different values of n and tau

			




	
	
	
		
 
    float tauValues[] = {2.1f, 2.2f, 2.3f, 2.4f, 2.5f, 2.6f, 2.7f, 2.8f, 2.9f};

			




	
	
	
		
 

			




	
	
	
		
 
    Graph g;

			




	
	
	
		
 
    const int totalDegreeSamples = 5;

			




	
	
	
		
 

			




	
	
	
		
 
    std::ofstream outfile;

			




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

			




	
	
	
		
 
        return int(30.0f * (50.0f - 30.0f * (tau - 2.0f)) * n);

			




	
	
	
		
 
    };

			




	
	
	
		
 
    constexpr int measurements = 50;

			




	
	
	
		
 
    constexpr int measureSkip = 200; // Take a sample every ... steps

			




	
	
	
		
 

			




	
	
	
		
 
    // Output file

			




	
	
	
		
 
    std::ofstream outfile;

			




	
	
	
		
 
    if (argc >= 2)

			




	
	
	
		
 
        outfile.open(argv[1]);

			




	
	
	
		
 
    else

			




	
	
	
		
 
        outfile.open("graphdata_spectrum.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 << "degreeSamples: " << totalDegreeSamples << std::endl;

			




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

			




	
	
	
		
 
    outfile << "data:\n";

			




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

			




	
	
	
		
 
    outfile << "2: triangleSeq\n";

			




	
	
	
		
 
    outfile << "3: edges\n";

			




	
	
	
		
 
    outfile << "4: start adj spectrum\n";

			




	
	
	
		
 
    outfile << "5: start laplacian spectrum\n";

			




	
	
	
		
 
    outfile << "6: end adj spectrum\n";

			




	
	
	
		
 
    outfile << "7: end laplacian spectrum\n";

			




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

			




	
	
	
		
 

			




	
	
	
		
 
    // Mathematica does not accept things of the form 1.23e-5

			




	
	
	
		
 
    // (instead it would write that as 1.23*^-5)

			




	
	
	
		
 
    // so simply use normal notation up to 6 decimals

			




	
	
	
		
 
    outfile << std::fixed;

			




	
	
	
		
 

			




	
	
	
		
 
    outfile << '{';

			




	
	
	
		
 
    bool outputComma = false;

			




	
	
	
		
 

			




	
	
	
		
 
    for (int numVertices = 500; numVertices <= 500; numVertices += 1000) {

			




	
	
	
		
 
    std::mt19937 rng(std::random_device{}());

			




	
	
	
		
 
    Graph g;

			




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

			




	
	
	
		
 
         numVertices += numVerticesStep) {

			




	
	
	
		
 
        for (float tau : tauValues) {

			




	
	
	
		
 
            // For a single n,tau take samples over several instances of

			




	
	
	
		
 
            // the degree distribution.

			




	
	
	
		
 
            for (int degreeSample = 0; degreeSample < 5; ++degreeSample) {

			




	
	
	
		
 
            for (int degreeSample = 0; degreeSample < totalDegreeSamples;

			




	
	
	
		
 
                 ++degreeSample) {

			




	
	
	
		
 
                DegreeSequence ds;

			




	
	
	
		
 
                generatePowerlawGraph(numVertices, tau, g, ds, rng);

			




	
	
	
		
 

			




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

			




	
	
	
		
 
                std::cout << "Running n = " << numVertices << ", tau = " << tau

			




	
	
	
		
 
                          << ". \t" << std::flush;

			




	
	
	
		
 

			




	
	
	
		
 
                //int mixingTime = (32.0f - 26.0f*(tau - 2.0f)) * numVertices; //40000;

			




	
	
	
		
 
                //constexpr int measurements = 50;

			




	
	
	
		
 
                //constexpr int measureSkip =

			




	
	
	
		
 
                //    200; // Take a sample every ... steps

			




	
	
	
		
 
                int mixingTime = 0;

			




	
	
	
		
 
                constexpr int measurements = 50000;

			




	
	
	
		
 
                constexpr int measureSkip = 1;

			




	
	
	
		
 

			




	
	
	
		
 
                int mixingTime = getMixingTime(numVertices,tau);;

			




	
	
	
		
 

			




	
	
	
		
 
                int movesTotal = 0;

			




	
	
	
		
 
                int movesSuccess = 0;

			




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

			




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

			




	
	
	
		
 
                // std::cout << std::endl;

			




	
	
	
		
 

			




	
	
	
		
 
                GraphSpectrum gs(g);

			




	
	
	
		
 
                GraphSpectrum gs_start(g);

			




	
	
	
		
 
                GraphSpectrum gs_end(chain.g);

			




	
	
	
		
 

			




	
	
	
		
 
                if (outputComma)

			




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

			




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

			




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

			




	
	
	
		
 
                outfile << ',' << triangles;

			




	
	
	
		
 
                outfile << ',' << g.edgeCount();

			




	
	
	
		
 
                outfile << ',' << gs.computeAdjacencySpectrum();

			




	
	
	
		
 
                outfile << ',' << gs.computeLaplacianSpectrum();

			




	
	
	
		
 
                outfile << ',' << gs_start.computeAdjacencySpectrum();

			




	
	
	
		
 
                outfile << ',' << gs_start.computeLaplacianSpectrum();

			




	
	
	
		
 
                outfile << ',' << gs_end.computeAdjacencySpectrum();

			




	
	
	
		
 
                outfile << ',' << gs_end.computeLaplacianSpectrum();

			




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

			




	
	
	
		
 

			




	
	
	
		
 
                std::cout << std::endl;

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








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