2018-02-24-155152.ipynb

Kernel: SageMath (stable)

# Import libraries
import itertools
from random import randint
# Variables
BLUE = 1
RED = 0
COLOR_NAMES = ["RED", "BLUE"]
TRI = 3
QUAD = 4
PENT = 5
HEX = 6
HEPT = 7
OCT = 8
NON = 9
SHAPE_NAMES = ["", "", "", "TRI", "QUAD", "PENT", "HEX", "HEPT",
"OCT", "NON"]

# Generate pseudo-random coloring of Kn
def gen_random_coloring(n):
    coloring = dict()
    for i in range(n):
        for j in range(i+1,n):
            coloring[(i,j)] = randint(0,1)
    return coloring

# Given a random coloring of Kn, shape, and color,
# return the number of occurrences of that shape in Kn
def count_freq_of_shape_of_color(nsize, num_vertices, color,
coloring):
    shape_count = 0
    for a_polygon in itertools.combinations(xrange(nsize),
num_vertices):
        coloring_index = sum([coloring[an_edge] for an_edge in
itertools.combinations(a_polygon, 2)])
RED:
if coloring_index == binomial(num_vertices, 2) and color ==
    shape_count = shape_count + 1
    
    elif coloring_index == 0 and color == BLUE:
        shape_count = shape_count + 1
return shape_count

# Create frequency distribution to list
def frequency_dist_to_list(freq_dist):
    maxval = max(freq_dist.keys())
    exhaustive_list = []
    for j in range(0,maxval+1):
        if j in freq_dist:
            exhaustive_list.append(freq_dist[j])
        else:
            exhaustive_list.append(0)
    return exhaustive_list

# Calculate mode, mean, and variance
def get_mode_mean_and_var(some_results):
    expanded_list = []
    for num, freq in some_results.items():
        for i in range(freq):
            expanded_list.append(num)
    return (max(expanded_list), mean(expanded_list),
variance(expanded_list))

from sage.plot.bar_chart import bar_chart
## RUN TRIAL AND CREATE PLOTS
def run_experiment(num_trials, num_vertices, shape_to_look_for,
color_to_look_for):
    print "### BEGIN TRIAL ###"
    results_dist = {}
    print "Generating and checking", num_trials, "cliques of size",
num_vertices
    print "\nThere are", num_trials*binomial(num_vertices,
shape_to_look_for),"possible", COLOR_NAMES[color_to_look_for],
SHAPE_NAMES[shape_to_look_for], "to check\n"
    for j in range(num_trials):
        if j%(num_trials/10) == 0:
            print j,'/',num_trials, "cliques scanned"
        count = count_freq_of_shape_of_color(num_vertices,
shape_to_look_for, color_to_look_for,
gen_random_coloring(num_vertices))
        if count in results_dist:
            results_dist[count] += 1
else:
    results_dist[count] = 1
    L = 2.0^(-
binomial(shape_to_look_for,2))*binomial(num_vertices,shape_to_look_for)
    if color_to_look_for == BLUE:
        graph_color = (0, 0, 1)
    else:
        graph_color = (1, 0, 0)
    graph = bar_chart(frequency_dist_to_list(results_dist),
rgbcolor=graph_color)+plot(num_trials*L^x/factorial(x)*exp(-L),
(0,len(frequency_dist_to_list(results_dist))),color='black')
    (the_mode, the_mean, the_var) =
get_mode_mean_and_var(results_dist)
    print "\n*** RESULTS ***"
    print "Mode:", the_mode
    print "L:", L
    print "Mean:", float(the_mean)
    print "Var:", float(the_var)
    print "SD:", sqrt(float(the_var))
    print "***************\n"
    print "\n### END EXPERIMENT ###\n"
    return (L, results_dist, graph, mean, var)

(L_tri, results_for_red_tri, red_tri_graph, red_tri_mean, red_tri_var) = run_experiment(100, 9, TRI, RED)

### BEGIN EXPERIMENT ###
Generating and checking 100 cliques of size 9

There are 8400 possible RED TRI to check

0 / 100 cliques scanned
10 / 100 cliques scanned
20 / 100 cliques scanned
30 / 100 cliques scanned
40 / 100 cliques scanned
50 / 100 cliques scanned
60 / 100 cliques scanned
70 / 100 cliques scanned
80 / 100 cliques scanned
90 / 100 cliques scanned

*** RESULTS ***
L: 10.5000000000000
Mean: 10.55
Var: 40.4116161616
SD: 6.35701314782
***************


### END EXPERIMENT ###

red_tri_graph

(L_pent, results_for_blue_pent, blue_pent_graph, blue_pent_mean, blue_pent_var) = run_experiment(10000, 14, PENT, BLUE)

### BEGIN EXPERIMENT ###
Generating and checking 10000 cliques of size 14

There are 20020000 possible BLUE PENT to check

0 / 10000 cliques scanned
1000 / 10000 cliques scanned
2000 / 10000 cliques scanned
3000 / 10000 cliques scanned
4000 / 10000 cliques scanned
5000 / 10000 cliques scanned
6000 / 10000 cliques scanned
7000 / 10000 cliques scanned
8000 / 10000 cliques scanned
9000 / 10000 cliques scanned

*** RESULTS ***
L: 1.95507812500000
Mean: 1.9438
Var: 13.7184134013
SD: 3.70383765861
***************


### END EXPERIMENT ###

experiments = [[1000, 14, PENT, BLUE], [1000, 14, RED, TRI], [1000, 9, RED, TRI]]
[run_experiment(*args) for args in experiments]

### BEGIN EXPERIMENT ###
Generating and checking 10000 cliques of size 14

There are 20020000 possible BLUE PENT to check

0 / 10000 cliques scanned

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-14-4ca99ac95f62> in <module>()
      1 experiments = [[Integer(10000), Integer(14), PENT, BLUE]]
----> 2 [run_experiment(*args) for args in experiments]

<ipython-input-8-82ada7006739> in run_experiment(num_trials, num_vertices, shape_to_look_for, color_to_look_for)
     10         if j%(num_trials/Integer(10)) == Integer(0):
     11             print j,'/',num_trials, "cliques scanned"
---> 12         count = count_freq_of_shape_of_color(num_vertices, shape_to_look_for, color_to_look_for, gen_random_coloring(num_vertices))
     13         if count in results_dist:
     14             results_dist[count] += Integer(1)
<ipython-input-5-478b4677255c> in count_freq_of_shape_of_color(nsize, num_vertices, color, coloring)
      5     for a_polygon in itertools.combinations(xrange(nsize), num_vertices):
      6         coloring_index = sum([coloring[an_edge] for an_edge in itertools.combinations(a_polygon, Integer(2))])
----> 7         if coloring_index == binomial(num_vertices, Integer(2)) and color == RED:
      8             shape_count = shape_count + Integer(1)
      9         elif coloring_index == Integer(0) and color == BLUE:
/ext/sage/sage-8.1/src/sage/symbolic/function.pyx in sage.symbolic.function.BuiltinFunction.__call__ (build/cythonized/sage/symbolic/function.cpp:11602)()
    992             res = self._evalf_try_(*args)
    993             if res is None:
--> 994                 res = super(BuiltinFunction, self).__call__(
    995                         *args, coerce=coerce, hold=hold)
    996 
/ext/sage/sage-8.1/src/sage/symbolic/function.pyx in sage.symbolic.function.Function.__call__ (build/cythonized/sage/symbolic/function.cpp:6696)()
    489                     (<Expression>args[0])._gobj, hold)
    490         elif self._nargs == 2:
--> 491             res = g_function_eval2(self._serial, (<Expression>args[0])._gobj,
    492                     (<Expression>args[1])._gobj, hold)
    493         elif self._nargs == 3:
/ext/sage/sage-8.1/src/sage/symbolic/function.pyx in sage.symbolic.function.BuiltinFunction._evalf_or_eval_ (build/cythonized/sage/symbolic/function.cpp:12951)()
   1081         res = self._evalf_try_(*args)
   1082         if res is None:
-> 1083             return self._eval0_(*args)
   1084         else:
   1085             return res
/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/functions/other.pyc in _eval_(self, n, k)
   1688         return prod(n - i for i in range(k)) / factorial(k)
   1689 
-> 1690     def _eval_(self, n, k):
   1691         """
   1692         EXAMPLES::
src/cysignals/signals.pyx in cysignals.signals.python_check_interrupt()
src/cysignals/signals.pyx in cysignals.signals.sig_raise_exception()
KeyboardInterrupt: