Changeset - 0290e63ba024
Parent rev.
Child rev.
[Not reviewed]
0 3 0
Tom Bannink - 8 years ago 2017-03-06 16:58:42
tombannink@gmail.com
Add start of faster cpp code
3 files changed with 50 insertions and 32 deletions:
cpp/graph.hpp
8
1
cpp/switchchain.cpp
37
20
showgraphs.m
5
11
0 comments (0 inline, 0 general)
cpp/graph.hpp
➞
Show inline comments
 
@@ -88,7 +88,14 @@ class Graph {
 
    }
 

			




	
	
	
		
 
    // Assumes valid vertex indices

			




	
	
	
		
 
    bool hasEdge(const Edge &e) const {

			




	
	
	
		
 
    bool hasEdge(const Edge& e_) const {

			




	
	
	
		
 
        Edge e;

			




	
	
	
		
 
        if (adj[e_.u].size() <= adj[e_.v].size()) {

			




	
	
	
		
 
            e = e_;

			




	
	
	
		
 
        } else {

			




	
	
	
		
 
            e.u = e_.v;

			




	
	
	
		
 
            e.v = e_.u;

			




	
	
	
		
 
        }

			




	
	
	
		
 
        for (unsigned int v : adj[e.u]) {

			




	
	
	
		
 
            if (v == e.v)

			




	
	
	
		
 
                return true;

			




        

    


    
    

    

        

                

                    cpp/switchchain.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -16,7 +16,10 @@ bool edgeConflicts(const Edge& e1, const Edge& e2) {

			




	
	
	
		
 

			




	
	
	
		
 
class SwitchChain {

			




	
	
	
		
 
  public:

			




	
	
	
		
 
    SwitchChain() : mt(std::random_device{}()), permutationDistribution(0, 2) {

			




	
	
	
		
 
    SwitchChain()

			




	
	
	
		
 
        : mt(std::random_device{}()), permutationDistribution(0.5)

			




	
	
	
		
 
    // permutationDistribution(0, 2)

			




	
	
	
		
 
    {

			




	
	
	
		
 
        // random_device uses hardware entropy if available

			




	
	
	
		
 
        // std::random_device rd;

			




	
	
	
		
 
        // mt.seed(rd());

			




	
	
		
 
@@ -33,38 +36,53 @@ class SwitchChain {

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
	
		
 
    bool doMove() {

			




	
	
	
		
 
        Edge e1 = g.getEdge(edgeDistribution(mt));

			




	
	
	
		
 
        Edge e2 = g.getEdge(edgeDistribution(mt));

			




	
	
	
		
 
        // Keep regenerating while conflicting edges

			




	
	
	
		
 
        Edge e1, e2;

			




	
	
	
		
 
        int e1index, e2index;

			




	
	
	
		
 
        int timeout = 0;

			




	
	
	
		
 
        while (edgeConflicts(e1, e2)) {

			




	
	
	
		
 
            e1 = g.getEdge(edgeDistribution(mt));

			




	
	
	
		
 
            e2 = g.getEdge(edgeDistribution(mt));

			




	
	
	
		
 
        // Keep regenerating while conflicting edges

			




	
	
	
		
 
        do {

			




	
	
	
		
 
            e1index = edgeDistribution(mt);

			




	
	
	
		
 
            e2index = edgeDistribution(mt);

			




	
	
	
		
 
            e1 = g.getEdge(e1index);

			




	
	
	
		
 
            e2 = g.getEdge(e2index);

			




	
	
	
		
 
            ++timeout;

			




	
	
	
		
 
            if (timeout % 100 == 0) {

			




	
	
	
		
 
                std::cerr << "Warning: sampled " << timeout

			




	
	
	
		
 
                          << " random edges but they keep conflicting.\n";

			




	
	
	
		
 
            }

			




	
	
	
		
 
        }

			




	
	
	
		
 
        } while (edgeConflicts(e1, e2));

			




	
	
	
		
 

			




	
	
	
		
 
        // Consider one of the three possible permutations

			




	
	
	
		
 
        // 1) e1.u - e1.v and e2.u - e2.v (original)

			




	
	
	
		
 
        // 2) e1.u - e2.u and e1.v - e2.v

			




	
	
	
		
 
        // 3) e1.u - e2.v and e1.v - e2.u

			




	
	
	
		
 

			




	
	
	
		
 
        // Note that it might be that these new edges already exist

			




	
	
	
		
 
        // in which case we also reject the move

			




	
	
	
		
 
        // This is checked in exchangeEdges

			




	
	
	
		
 
        // in which case we reject the move

			




	
	
	
		
 
        bool switchType = permutationDistribution(mt);

			




	
	
	
		
 
        if (switchType) {

			




	
	
	
		
 
            if (g.hasEdge({e1.u, e2.u}) || g.hasEdge({e1.v, e2.v}))

			




	
	
	
		
 
                return false; // conflicting edges

			




	
	
	
		
 
        } else {

			




	
	
	
		
 
            if (g.hasEdge({e1.u, e2.v}) || g.hasEdge({e1.v, e2.u}))

			




	
	
	
		
 
                return false; // conflicting edges

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        int perm = permutationDistribution(mt);

			




	
	
	
		
 
        if (perm == 0) // Original permutation

			




	
	
	
		
 
            return false;

			




	
	
	
		
 
        return g.exchangeEdges(e1, e2, perm == 1);

			




	
	
	
		
 
        // TODO

			




	
	
	
		
 
        // rest of the switching process

			




	
	
	
		
 

			




	
	
	
		
 
        // int perm = permutationDistribution(mt);

			




	
	
	
		
 
        // if (perm == 0) // Original permutation

			




	
	
	
		
 
        //    return false;

			




	
	
	
		
 
        // return g.exchangeEdges(e1, e2, perm == 1);

			




	
	
	
		
 
        return g.exchangeEdges(e1, e2, switchType);

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
	
		
 
    Graph g;

			




	
	
	
		
 
    std::mt19937 mt;

			




	
	
	
		
 
    std::uniform_int_distribution<> edgeDistribution;

			




	
	
	
		
 
    std::uniform_int_distribution<> permutationDistribution;

			




	
	
	
		
 
    //std::uniform_int_distribution<> permutationDistribution;

			




	
	
	
		
 
    std::bernoulli_distribution permutationDistribution;

			




	
	
	
		
 
};

			




	
	
	
		
 

			




	
	
	
		
 
int main() {

			




	
	
		
 
@@ -76,7 +94,7 @@ int main() {

			




	
	
	
		
 
    // 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.2f, 2.35f, 2.5f, 2.65f, 2.8f};

			




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

			




	
	
	
		
 

			




	
	
	
		
 
    Graph g;

			




	
	
	
		
 

			




	
	
		
 
@@ -114,11 +132,10 @@ int main() {

			




	
	
	
		
 
                    return 1;

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                std::cout << "Starting switch Markov chain with n = "

			




	
	
	
		
 
                          << numVertices << ", tau = " << tau << ". \t"

			




	
	
	
		
 
                          << std::flush;

			




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

			




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

			




	
	
	
		
 

			




	
	
	
		
 
                constexpr int mixingTime = 30000;

			




	
	
	
		
 
                constexpr int mixingTime = 40000;

			




	
	
	
		
 
                constexpr int measureTime = 20000;

			




	
	
	
		
 
                constexpr int measureSkip =

			




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

			




        

    


    
    

    

        

                

                    showgraphs.m
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -17,7 +17,7 @@ Needs["ErrorBarPlots`"]

			




	
	
	
		
 
(*   (a) Don't remove/add edges from the std::vector. Simply replace them*)

			




	
	
	
		
 
(*   (b) Better direct triangle counting? (I doubt it)*)

			




	
	
	
		
 
(*   (b') Better triangle counting by only keeping track of CHANGES in #triangles*)

			




	
	
	
		
 
(*   (c) Do not choose the three permutations with 1/3 probability: choose the "staying" one with a very low probability. Should still be a valid switch chain?*)

			




	
	
	
		
 
(*   (c) Do not choose the three permutations with 1/3 probability: choose the "staying" one with zero probability. Should still be a valid switch chain?*)

			




	
	
	
		
 
(**)

			




	
	
	
		
 
(*- Experimental mixing time as function of n. At (n,tau)=(1000,2.5) it seems to be between 10.000 and 20.000 steps.*)

			




	
	
	
		
 
(**)

			




	
	
		
 
@@ -62,7 +62,7 @@ Grid[Partition[gs,10],Frame->All]

			




	
	
	
		
 
(*Data import and data merge*)

			




	
	
	
		
 

			




	
	
	
		
 

			




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

			




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

			




	
	
	
		
 
gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
		
 
@@ -70,9 +70,9 @@ gdata=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}];

			




	
	
	
		
 
(* gdata[[ tau index, n index, run index , {ntau, #tris, ds} ]] *)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
newData=Import[NotebookDirectory[]<>"graphdata_tau_multi4.m"];

			




	
	
	
		
 
mergedData=Import[NotebookDirectory[]<>"graphdata_merged.m"];

			




	
	
	
		
 
Export[NotebookDirectory[]<>"graphdata_merged_new.m",Join[mergedData,newData]]

			




	
	
	
		
 
newData=Import[NotebookDirectory[]<>"data/graphdata_3.m"];

			




	
	
	
		
 
mergedData=Import[NotebookDirectory[]<>"data/graphdata_merged.m"];

			




	
	
	
		
 
Export[NotebookDirectory[]<>"data/graphdata_merged_new.m",Join[mergedData,newData]]

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
(* ::Subsection:: *)

			




	
	
		
 
@@ -151,12 +151,6 @@ ErrorListPlot[averagesErrorBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{

			




	
	
	
		
 
ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels]

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
averagesErrorBars=Map[

			




	
	
	
		
 
{{Log[#[[1,1,1]]],Log[Mean[#[[All,2]]]]},

			




	
	
	
		
 
ErrorBar[ (StandardDeviation[#[[All,2]]] )]

			




	
	
	
		
 
}&,averagesGrouped,{2}];

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
(* ::Subsection:: *)

			




	
	
	
		
 
(*Fitting the log-log-plot*)

			




	
	
	
		
 

			




        

    



    


    



    



      

      





    
    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