Random Graphs in Sage.sagews

from sage.plot.histogram import Histogram

g = graphs.RandomGNP(15, .2)  # 15 vertices and 20 edges
show(g)
g.incidence_matrix()

d3-based renderer not yet implemented

[1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0] [0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1] [0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0] [0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1]

g = graphs.RandomGNM(15, 7)
show(g)
g.connected_components()

d3-based renderer not yet implemented

[[1, 5, 7, 12, 13], [2, 6, 14], [0, 10], [3], [4], [8], [9], [11]]

g = graphs.RandomGNM(15, 7)
show(g)
L = g.connected_components()
len(L[0])

d3-based renderer not yet implemented

7

x = 1000
M=[]
while x != 0:
    g = graphs.RandomGNM(15, 9)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
M
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

[9, 8, 9, 6, 10, 10, 7, 10, 7, 7, 9, 6, 7, 6, 7, 5, 6, 9, 8, 8, 6, 8, 6, 4, 6, 6, 7, 9, 9, 6, 8, 5, 6, 7, 9, 5, 7, 6, 7, 7, 10, 10, 10, 6, 9, 6, 7, 7, 7, 5, 8, 9, 9, 6, 10, 6, 10, 10, 7, 6, 7, 7, 9, 8, 6, 5, 7, 9, 5, 9, 10, 7, 9, 7, 10, 8, 10, 8, 9, 5, 8, 6, 7, 6, 5, 7, 7, 7, 6, 9, 8, 5, 7, 8, 6, 8, 9, 6, 7, 10, 8, 5, 7, 4, 5, 7, 8, 7, 8, 6, 9, 6, 7, 8, 7, 6, 4, 9, 8, 10, 4, 6, 8, 9, 8, 8, 9, 10, 6, 6, 5, 9, 10, 9, 8, 5, 7, 4, 4, 9, 7, 5, 6, 9, 10, 7, 10, 8, 9, 8, 7, 7, 7, 9, 5, 9, 6, 7, 5, 6, 5, 8, 8, 10, 8, 9, 7, 5, 9, 8, 7, 5, 7, 5, 7, 6, 6, 8, 6, 7, 8, 8, 7, 5, 10, 9, 7, 7, 9, 10, 4, 5, 8, 8, 8, 5, 6, 7, 7, 10, 10, 8, 9, 10, 7, 9, 5, 9, 8, 5, 9, 6, 8, 8, 8, 6, 10, 8, 6, 8, 8, 8, 6, 7, 10, 10, 6, 9, 7, 8, 10, 9, 7, 6, 10, 6, 9, 7, 6, 6, 4, 6, 5, 9, 6, 5, 8, 6, 6, 8, 9, 5, 7, 7, 10, 5, 8, 9, 9, 10, 6, 10, 6, 6, 8, 7, 9, 9, 6, 7, 7, 7, 8, 6, 6, 9, 6, 6, 4, 7, 9, 6, 9, 7, 6, 8, 6, 10, 6, 7, 5, 7, 9, 6, 10, 7, 6, 10, 7, 6, 7, 8, 7, 8, 7, 9, 7, 9, 6, 7, 3, 4, 6, 5, 7, 5, 8, 8, 6, 9, 3, 8, 9, 5, 7, 9, 7, 10, 7, 6, 7, 9, 9, 9, 8, 7, 5, 5, 7, 6, 4, 4, 7, 7, 6, 9, 9, 9, 8, 5, 5, 5, 8, 6, 3, 6, 9, 8, 7, 6, 7, 7, 7, 10, 9, 3, 8, 4, 8, 5, 9, 10, 8, 9, 8, 8, 7, 8, 7, 8, 9, 6, 9, 7, 9, 4, 8, 7, 9, 5, 5, 5, 8, 9, 9, 9, 6, 6, 7, 4, 7, 4, 8, 7, 9, 4, 6, 8, 6, 7, 5, 10, 6, 10, 8, 6, 6, 8, 10, 6, 7, 7, 8, 9, 10, 7, 8, 5, 7, 6, 7, 8, 6, 6, 7, 5, 10, 8, 8, 10, 5, 9, 10, 5, 8, 7, 9, 6, 7, 8, 7, 9, 9, 10, 7, 6, 4, 10, 7, 9, 5, 10, 8, 4, 4, 10, 9, 5, 5, 6, 9, 9, 4, 6, 8, 9, 8, 7, 6, 7, 9, 4, 8, 10, 5, 7, 10, 7, 8, 10, 7, 7, 9, 7, 6, 9, 9, 5, 7, 8, 9, 8, 8, 6, 10, 5, 10, 7, 10, 8, 5, 5, 5, 8, 6, 7, 10, 6, 9, 9, 9, 8, 7, 7, 7, 5, 6, 10, 4, 6, 8, 5, 8, 5, 10, 7, 6, 9, 6, 4, 5, 7, 9, 9, 8, 10, 5, 7, 10, 5, 9, 7, 10, 8, 7, 5, 8, 10, 6, 4, 5, 10, 8, 9, 6, 7, 5, 10, 6, 8, 4, 9, 7, 9, 10, 5, 6, 7, 8, 8, 6, 8, 6, 8, 7, 7, 6, 9, 9, 6, 6, 6, 10, 8, 5, 10, 5, 8, 7, 5, 7, 7, 10, 8, 8, 4, 9, 10, 8, 4, 7, 8, 8, 8, 9, 8, 7, 4, 9, 5, 5, 6, 5, 7, 7, 9, 9, 4, 7, 5, 9, 9, 10, 5, 9, 7, 6, 9, 6, 5, 7, 8, 8, 8, 5, 9, 6, 5, 8, 9, 9, 7, 9, 8, 6, 9, 8, 8, 7, 10, 8, 4, 5, 7, 9, 8, 8, 7, 6, 8, 6, 6, 10, 9, 5, 10, 5, 7, 8, 6, 9, 5, 7, 6, 5, 8, 9, 10, 6, 10, 7, 6, 7, 6, 4, 5, 10, 8, 4, 4, 7, 10, 8, 6, 6, 9, 5, 6, 6, 7, 8, 10, 5, 5, 9, 6, 9, 6, 7, 4, 4, 8, 7, 7, 9, 9, 7, 6, 9, 10, 5, 9, 9, 9, 9, 8, 5, 7, 10, 6, 10, 8, 7, 9, 9, 7, 5, 9, 4, 6, 7, 4, 9, 8, 10, 5, 6, 5, 9, 7, 10, 10, 8, 9, 9, 8, 9, 7, 8, 8, 6, 8, 9, 5, 9, 8, 4, 7, 10, 9, 8, 6, 9, 6, 7, 8, 9, 10, 8, 9, 7, 8, 6, 9, 10, 8, 10, 4, 8, 6, 7, 6, 9, 5, 10, 5, 5, 10, 7, 4, 7, 4, 7, 8, 5, 7, 7, 8, 6, 7, 6, 8, 7, 5, 5, 10, 8, 7, 9, 6, 9, 7, 6, 8, 8, 6, 9, 10, 4, 7, 7, 7, 8, 7, 6, 6, 10, 9, 8, 9, 6, 6, 6, 6, 7, 8, 9, 9, 9, 6, 10, 10, 6, 8, 7, 5, 5, 4, 6, 10, 8, 6, 10, 8, 10, 8, 7, 6, 8, 6, 8, 9, 6, 9, 4, 6, 5, 8, 5, 7, 5, 6, 9, 5, 7, 4, 6, 8, 8, 8, 9, 6, 9, 5, 6, 7, 7, 7, 6, 8, 6, 10, 9, 10, 6, 9, 8, 7, 6, 9, 4, 8, 10, 5, 9, 8, 6, 8, 10, 6, 7, 6, 6, 6, 6, 7, 7, 7, 7, 7, 10, 8, 9, 8, 5, 6, 8, 7, 8, 10, 7, 5, 6, 8, 9, 5, 9, 9, 6, 5, 8, 6, 7, 9, 7, 5, 9, 6, 9, 10, 6, 4, 8, 9, 7, 6, 8, 5, 6, 7, 8, 4, 3, 8, 8, 7, 10, 7, 10, 8, 8, 10, 6, 7, 6, 5, 10, 8, 8, 8]

x = 50000
M=[]
while x != 0:
    g = graphs.RandomGNP(15, .1)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 50000
M=[]
while x != 0:
    g = graphs.RandomGNP(15, .05)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 50000
M=[]
while x != 0:
    g = graphs.RandomGNP(20, .1)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 50000
M=[]
while x != 0:
    g = graphs.RandomGNP(15, 16/105)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 50000
M=[]
while x != 0:
    g = graphs.RandomGNP(15, 15/105)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 50000
M=[]
while x != 0:
    g = graphs.RandomGNP(15, 0.18053668007)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 50000
M=[]
while x != 0:
    g = graphs.RandomGNP(15, 0.17)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 50000
M=[]
while x != 0:
    g = graphs.RandomGNP(15, 0.19)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 10000
M=[]
while x != 0:
    g = graphs.RandomGNP(1000, ln(1000)/1000)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

for a in range(10):
    M = []
    n = 10
    p = .1
    # Make graph
    g = graphs.RandomGNP(n, p)
    # add the largest connected component to a M
    L = g.connected_components()
    M.append(len(L[0]))
    M

[3] [4] [2] [4] [3] [2] [5] [2] [7] [6]

def Test(n):
    # create list
    M = []
    L = []
    # create tripwrie
    trip = False
    # set probability to .1
    p = .1
    # begin loop to run 10 times
    for a in range(10):
        # Make graph
        g = graphs.RandomGNP(n, p)
        # add the largest connected component to a M
        L = g.connected_components()
        M.append(len(L[0]))

        # if gr is not connected then...
        if g.is_connected == False:
            # flip the trip wire
            trip = True
            # print M
            M
            # indicate tripped
            print "tripped"
            #stop
            break
    M
Test(5)

# Finding threshold for GNP
#testing for graphs of size 0 to 10
for n in range(10):
    #variable that lets us know if we've met the threshold
    reached = 0
    #beginning with probability 0
    p = 0
    #test while we have not found threshold
    while reached == 0:
        #set the counter for number of trials to 1
        count = 1
        #while we have not completed the trials
        while count <= 10:
            #make G(n,p)
            g = graphs.RandomGNP(n, p)
            #if the graph is not connected
            if g.is_connected == False:
                #increase p and restart trials
                p = p + .001
                break
            #if trials complete with all graphs being connected
            #print that p is the threshold and restart trials with n + 1
            if count == 10:
                print 'for %s, %s is the threshold'%(n,p)
            reached = 1

Error in lines 1-13 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 7, in <module> File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generators/random.py", line 109, in RandomGNP seed = current_randstate().long_seed() File "src/cysignals/signals.pyx", line 251, in cysignals.signals.python_check_interrupt File "src/cysignals/signals.pyx", line 94, in cysignals.signals.sig_raise_exception KeyboardInterrupt

x = 10000
M=[]
while x != 0:
    g = graphs.RandomGNP(1000, 0.006)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

Error in lines 3-7 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 2, in <module> File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generators/random.py", line 124, in RandomGNP return sageGNP(n, p) File "sage/graphs/graph_generators_pyx.pyx", line 87, in sage.graphs.graph_generators_pyx.RandomGNP (build/cythonized/sage/graphs/graph_generators_pyx.c:1676) G.add_edge(i,j) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 10424, in add_edge self._backend.add_edge(u, v, label, self._directed) File "src/cysignals/signals.pyx", line 251, in cysignals.signals.python_check_interrupt File "src/cysignals/signals.pyx", line 94, in cysignals.signals.sig_raise_exception KeyboardInterrupt

x = 10000
M=[]
while x != 0:
    g = graphs.RandomGNP(1000, .0068)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 10000
M=[]
while x != 0:
    g = graphs.RandomGNP(1000, .007)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

g = graphs.RandomGNM(15, 1000)
show(g)
print g.is_connected()

d3-based renderer not yet implemented

True

def test(N):
    P = .0001
    trip = False
    while trip == False:
        for a in range(10):
#            print "loop", a
            # Make graph
            g = graphs.RandomGNP(N, P)
            # add the largest connected component to a M
            if g.is_connected() == False:
#                print "P is too small"
                break
            if a == 5:
                trip = True
                break
        if trip == True:
            print P
            break
        P = P + .00001
    return P

test(1000)

0.00937999999999979 0.00937999999999979

test(1000)

0.0136000000000000 0.0136000000000000

test(30)

0.255399999999988 0.255399999999988

test(30)

0.176699999999997 0.176699999999997

test(30)

0.139200000000001 0.139200000000001

test(30)

0.138400000000001 0.138400000000001

test(30)

0.117500000000002 0.117500000000002

test(30)

0.0972000000000018 0.0972000000000018 0.0972000000000018 0.0972000000000018

test(30)

0.101519999999993 0.101519999999993

test(30)

0.105879999999992 0.105879999999992

test(30)

0.105529999999992 0.105529999999992

g = graphs.RandomGNM(15, 15)  # 15 vertices and 20 edges
show(g)

d3-based renderer not yet implemented

[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 1 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 1 1 1 1 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 0 0] [0 1 1 0 0 0 0 1 1 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 1 1 0 0 0 0] [0 0 0 0 0 0 0 0 0 1 0 1 1 0 0] [1 0 0 0 0 0 0 1 0 0 0 1 0 1 1] [0 0 0 0 0 0 0 0 0 0 0 0 1 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 1 0 0 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 0 1 0] [0 0 0 0 1 0 1 0 1 0 0 0 0 0 0] [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]

x = 10000
M=[]
while x != 0:
    g = graphs.RandomGNP(5000, .0008)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 10000
M=[]
while x != 0:
    g = graphs.RandomGNP(5000, .001)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))

x = 10000
M=[]
while x != 0:
    g = graphs.RandomGNP(5000, .00171)
    L = g.connected_components()
    M.append(len(L[0]))
    x = x - 1
stats.TimeSeries(M).plot_histogram(normalize=False,bins=(max(M)-min(M)))