Changeset - e65372736dde
[Not reviewed]
Merge
0 7 3
Tom Bannink - 8 years ago 2017-06-02 11:50:31
tom.bannink@cwi.nl
Merge branch 'master' of https://scm.cwi.nl/AC/switchchain
7 files changed with 105 insertions and 45 deletions:
0 comments (0 inline, 0 general)
cpp/Makefile
Show inline comments
 
#CXX=clang++
 

	
 
INCLUDES += -I.
 

	
 
CXXFLAGS += -std=c++14 -O3 -Wall -Wextra -Wfatal-errors -Wno-deprecated-declarations $(INCLUDES)
 
CXXFLAGS += -std=c++14 -O3 -Wall -Wextra -Wfatal-errors -Werror -pedantic -Wno-deprecated-declarations $(INCLUDES)
 

	
 

	
 
all: switchchain switchchain_exponent switchchain_initialtris
cpp/switchchain.cpp
Show inline comments
 
@@ -73,8 +73,8 @@ void getTriangleDegrees(const Graph& g) {
 
            for (unsigned int j = i + 1; j < v.size(); ++j) {
 
                if (g.hasEdge({v[i], v[j]})) {
 
                    ++triangles;
 
                    std::array<std::size_t, 3> ds = {v.size(), adj[v[i]].size(),
 
                                                     adj[v[j]].size()};
 
                    std::array<std::size_t, 3> ds = {{v.size(), adj[v[i]].size(),
 
                                                     adj[v[j]].size()}};
 
                    std::sort(ds.begin(), ds.end());
 
                    trids.push_back(ds);
 
                }
 
@@ -90,7 +90,8 @@ void getTriangleDegrees(const Graph& g) {
 
//
 
// method2 = true  -> take highest degree and finish its pairing completely
 
// method2 = false -> take new highest degree after every pairing
 
bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng, bool method2) {
 
template <typename RNG>
 
bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, RNG& rng, bool method2) {
 
    // Similar to Havel-Hakimi but instead of pairing up with the highest ones
 
    // that remain, simply pair up with random ones
 
    unsigned int n = ds.size();
 
@@ -194,7 +195,7 @@ bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng, bool meth
 
    return true;
 
}
 

	
 
int main() {
 
int main(int argc, char* argv[]) {
 
    // Generate a random degree sequence
 
    std::mt19937 rng(std::random_device{}());
 

	
 
@@ -209,11 +210,22 @@ int main() {
 
    Graph g1;
 
    Graph g2;
 

	
 
    std::ofstream outfile("graphdata.m");
 
    std::ofstream outfile;
 

	
 
    if (argc >= 2)
 
        outfile.open(argv[1]);
 
    else   
 
        outfile.open("graphdata.m");
 

	
 
    if (!outfile.is_open()) {
 
        std::cout << "ERROR: Could not open output file.\n";
 
        return 1;
 
    }
 

	
 
    outfile << '{';
 
    bool outputComma = false;
 

	
 
    for (int numVertices = 200; numVertices <= 2000; numVertices += 400) {
 
    for (int numVertices = 500; numVertices <= 500; numVertices += 1000) {
 
        for (float tau : tauValues) {
 

	
 
            DegreeSequence ds(numVertices);
 
@@ -223,7 +235,7 @@ int main() {
 
            // For a single n,tau take samples over several instances of
 
            // the degree distribution.
 
            // 500 samples seems to give reasonable results
 
            for (int degreeSample = 0; degreeSample < 1; ++degreeSample) {
 
            for (int degreeSample = 0; degreeSample < 5; ++degreeSample) {
 
                // Generate a graph
 
                // might require multiple tries
 
                for (int i = 1; ; ++i) {
 
@@ -247,6 +259,7 @@ int main() {
 
                    }
 
                }
 

	
 
#if 0
 
                //
 
                // Test the GCM1 and GCM2 success rate
 
                //
 
@@ -269,6 +282,9 @@ int main() {
 
                        g2 = gtemp;
 
                    }
 
                }
 
#endif
 

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

	
 
                SwitchChain chain;
 
                if (!chain.initialize(g)) {
 
@@ -276,17 +292,6 @@ int main() {
 
                    return 1;
 
                }
 

	
 
                SwitchChain chain1, chain2;
 
                bool do1 = true, do2 = true;
 
                if (!chain1.initialize(g1)) {
 
                    std::cerr << "Could not initialize Markov chain.\n";
 
                    do1 = false;
 
                }
 
                if (!chain2.initialize(g2)) {
 
                    std::cerr << "Could not initialize Markov chain.\n";
 
                    do2 = false;
 
                }
 

	
 
                std::cout << "Running n = " << numVertices << ", tau = " << tau
 
                          << ". \t" << std::flush;
 

	
 
@@ -299,28 +304,41 @@ int main() {
 
                constexpr int measureSkip = 1;
 

	
 

	
 

	
 
                int movesDone = 0;
 
                int movesTotal = 0;
 
                int movesSuccess = 0;
 

	
 
                int triangles[measurements];
 

	
 
                for (int i = 0; i < mixingTime; ++i) {
 
                    if (chain.doMove())
 
                        ++movesDone;
 
                    ++movesTotal;
 
                    if (chain.doMove()) {
 
                        ++movesSuccess;
 
                    }
 
                }
 

	
 
                std::vector<int> successRates;
 
                successRates.reserve(measurements * measureSkip);
 
                int successrate = 0;
 
                for (int i = 0; i < measurements; ++i) {
 
                    for (int j = 0; j < measureSkip; ++j)
 
                        if (chain.doMove())
 
                            ++movesDone;
 
                    for (int j = 0; j < measureSkip; ++j) {
 
                        ++movesTotal;
 
                        if (chain.doMove()) {
 
                            ++movesSuccess;
 
                            ++successrate;
 
                        }
 
                    }
 
                    triangles[i] = chain.g.countTriangles();
 

	
 
                    if ((i+1) % 100 == 0) {
 
                        successRates.push_back(successrate);
 
                        successrate = 0;
 
                    }
 
                }
 

	
 
                std::cout << movesDone << '/' << mixingTime + measurements * measureSkip
 
                          << " moves succeeded ("
 
                          << 100.0f * float(movesDone) /
 
                                 float(mixingTime + measurements * measureSkip)
 
                          << "%).";
 
                //std::cout << std::endl;
 
                std::cout << '('
 
                          << 100.0f * float(movesSuccess) / float(movesTotal)
 
                          << "% successrate). " << std::flush;
 
                // std::cout << std::endl;
 

	
 
                if (outputComma)
 
                    outfile << ',' << '\n';
 
@@ -330,10 +348,12 @@ int main() {
 
                outfile << '{' << '{' << numVertices << ',' << tau << '}';
 
                outfile << ',' << triangles;
 
                outfile << ',' << ds;
 
#if 0
 
                outfile << ',' << greedyTriangles1;
 
                outfile << ',' << greedyTriangles2;
 

	
 
                if (do1) {
 
                SwitchChain chain1, chain2;
 
                if (chain1.initialize(g1)) {
 
                    movesDone = 0;
 
                    SwitchChain& c = chain1;
 
                    for (int i = 0; i < mixingTime; ++i) {
 
@@ -355,7 +375,7 @@ int main() {
 

	
 
                    outfile << ',' << triangles;
 
                }
 
                if (do2) {
 
                if (chain2.initialize(g2)) {
 
                    movesDone = 0;
 
                    SwitchChain& c = chain2;
 
                    for (int i = 0; i < mixingTime; ++i) {
 
@@ -377,10 +397,14 @@ int main() {
 

	
 
                    outfile << ',' << triangles;
 
                }
 
#endif
 

	
 
                outfile << ',' << successRates;
 

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

	
 
                std::cout << std::endl;
 
                }
 
            }
 
        }
 
    }
cpp/switchchain_initialtris.cpp
Show inline comments
 
@@ -68,7 +68,8 @@ class SwitchChain {
 
//
 
// method2 = true  -> take highest degree and finish its pairing completely
 
// method2 = false -> take new highest degree after every pairing
 
bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng, bool method2) {
 
template <typename RNG>
 
bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, RNG& rng, bool method2) {
 
    // Similar to Havel-Hakimi but instead of pairing up with the highest ones
 
    // that remain, simply pair up with random ones
 
    unsigned int n = ds.size();
plots/avgtris_n.pdf
Show inline comments
 
new file 100644
 
binary diff not shown
plots/triangle_exponent.pdf
Show inline comments
 
new file 100644
 
binary diff not shown
triangle_analysis.m
Show inline comments
 
@@ -71,7 +71,7 @@ Needs["ErrorBarPlots`"]
 
(*Data import*)
 

	
 

	
 
gsraw=Import[NotebookDirectory[]<>"data/graphdata_partial.m"];
 
gsraw=Import[NotebookDirectory[]<>"data/graphdata_temp2.m"];
 
(* gsraw=SortBy[gsraw,{#[[1,1]]&,#[[1,2]]&}]; (* Sort by n and then by tau. The {} forces a *stable* sort because otherwise Mathematica sorts also on triangle count and other things. *) *)
 

	
 

	
 
@@ -146,19 +146,47 @@ Show[ListPlot[avgAndProp,AxesOrigin->{0,0},AxesLabel->{"degree-sequence-property
 
(*Plot triangle count over "time" in Markov chain instances*)
 

	
 

	
 
numPlots=20;
 
selectedData=gdata[[4,-1]][[-numPlots;;-1]];
 
numPlots=10;
 
selectedData=gdata[[1,-1]][[-numPlots;;-1]];
 
measureSkip=1;
 
minCount=Min[Map[Min[#[[2]]]&,selectedData]];
 
maxCount=Max[Map[Max[#[[2]]]&,selectedData]];
 
maxTime=Max[Map[Length[#[[2]]]&,selectedData]];
 
skipPts=Max[1,Round[maxTime/200]]; (* Plotting every point is slow. Plot only once per `skipPts` timesteps *)
 
coarseData=Map[#[[2,1;;-1;;skipPts]]&,selectedData];
 
maxTime=30000;
 
skipPts=Max[1,Round[maxTime/400]]; (* Plotting every point is slow. Plot only once per `skipPts` timesteps *)
 
coarseData=Map[#[[2,1;;maxTime;;skipPts]]&,selectedData];
 
labels=Map["{n,tau} = "<>ToString[#[[1]]]&,selectedData];
 
ListPlot[coarseData,Joined->True,PlotRange->{minCount,maxCount},DataRange->{0,measureSkip*maxTime},PlotLegends->labels]
 
ListPlot[coarseData,Joined->True,PlotRange->{0*minCount,maxCount},DataRange->{0,measureSkip*maxTime},PlotLegends->labels]
 
(* Map[ListPlot[#,Joined->True,PlotRange\[Rule]{minCount,maxCount},DataRange\[Rule]{0,maxTime}]&,coarseData] *)
 

	
 

	
 
(* ::Subsection:: *)
 
(*Plot success rate over "time"*)
 

	
 

	
 
numPlots=10;
 
selectedData=gdata[[1,-1]][[-numPlots;;-1]];
 
measureSkip=100;
 
maxTime=Max[Map[Length[#[[4]]]&,selectedData]];
 
maxTime=10000;
 
coarseData=Map[#[[4,1;;maxTime/measureSkip]]&,selectedData];
 
labels=Map["{n,tau} = "<>ToString[#[[1]]]&,selectedData];
 
ListPlot[coarseData,Joined->True,PlotRange->{0,100},DataRange->{0,maxTime},PlotLegends->labels]
 
(* Map[ListPlot[#,Joined->True,PlotRange\[Rule]{minCount,maxCount},DataRange\[Rule]{0,maxTime}]&,coarseData] *)
 

	
 

	
 
(* ::Subsection:: *)
 
(*Correlation of avgsuccess rate vs other things*)
 

	
 

	
 
compare1=Map[{Mean[#[[4]]],Mean[#[[2]]]}&,gdata,{3}];
 
(* { GCM1 rate, GCM2 rate, mixing time from ErdosGallai } *)
 

	
 

	
 
scatterPlots=Map[ListPlot[#,PlotRange->{{0,100},All},PlotStyle->PointSize[Large]]&,compare1,{2}];
 
TableForm[scatterPlots,TableHeadings->{taulabels,nlabels}]
 

	
 

	
 
(* ::Subsection:: *)
 
(*Compute 'mixing time'*)
 

	
triangle_exponent_plots.m
Show inline comments
 
@@ -16,7 +16,7 @@ Needs["ErrorBarPlots`"]
 

	
 

	
 
(* When importing from exponent-only-data file *)
 
gsraw=Import[NotebookDirectory[]<>"data/graphdata_exponent.m"];
 
gsraw=Import[NotebookDirectory[]<>"data/graphdata_exponent_mix32.m"];
 
gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *)
 
averagesGrouped=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}];
 

	
 
@@ -51,7 +51,10 @@ fitsExtra[[1]]["ParameterErrors"]
 
fitsExtra[[1]]["ParameterConfidenceIntervals"]
 

	
 

	
 
Show[ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels],Plot[fits,{logn,1,2000}]]
 
plot1=Show[ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->False,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels],Plot[fits,{logn,1,2000}]]
 

	
 

	
 
Export[NotebookDirectory[]<>"plots/avgtris_n.pdf",plot1]
 

	
 

	
 
(* ::Subsection:: *)
 
@@ -60,7 +63,7 @@ Show[ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Aut
 

	
 
tauValues=averagesGrouped[[All,1,1,1,2]];
 
exponents=Transpose[{tauValues,fits[[All,2,1]]}];
 
Show[ListPlot[exponents,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","T(\[Tau])"},PlotRange->{{2,3},{0,1.6}}],Plot[3/2(3-tau),{tau,2,3}]]
 
Show[ListPlot[exponents,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","exponent"},PlotRange->{{2,3},{0,1.6}}],Plot[3/2(3-tau),{tau,2,3}]]
 

	
 

	
 
(* ::Subsection:: *)
 
@@ -70,4 +73,7 @@ Show[ListPlot[exponents,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","T
 
tauValues=averagesGrouped[[All,1,1,1,2]];
 
exponentsErrorBars=Map[{{#[[1]],#[[2]]["BestFitParameters"][[2]]},ErrorBar[#[[2]]["ParameterConfidenceIntervals"][[2]]-#[[2]]["BestFitParameters"][[2]]]}&,
 
Transpose[{tauValues,fitsExtra}]];
 
Show[ErrorListPlot[exponentsErrorBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","T(\[Tau])"},PlotRange->{{2,3},{0,1.6}}],Plot[3/2(3-tau),{tau,2,3}]]
 
plot2=Show[ErrorListPlot[exponentsErrorBars,Joined->True,PlotMarkers->Automatic,Frame->True,FrameLabel->{"tau","triangle exponent"},PlotRange->{{2,3},{0,1.6}},ImageSize->300],Plot[3/2(3-tau),{tau,2,3},PlotStyle->{Dashed}]]
 

	
 

	
 
Export[NotebookDirectory[]<>"plots/triangle_exponent.pdf",plot2]
0 comments (0 inline, 0 general)