RandomSharingIsRandomCaring.sagews

G=Graph("{t?GW???oH?G?G??_?gO??S??g??E??H???O??CG??A???O??@???A????A???@?????O???A?????g???@O???C????A?????AO????O_????GO????C_??????_?????O??????O?????A??????__????@@???????C??????AG??????c??????CG??????@G??????AC????????_???????O????????c???????@_????????o???????@H????????@O????????g_??G@????C??@?A????")

G.show()
G.is_hamiltonian()

True

G=graphs.CompleteBipartiteGraph(3,3)

for g in graph_objects:
    if g.vertex_connectivity()>3:
        if g.is_hamiltonian():
            g.show()

g=graphs.PaleyGraph(9)
g.show()

def build_random_with_induced_H(n,p,H):
    H=graphs.ClawGraph()
    p=1
    k=H.order()
    while true:
        g=graphs.RandomGNP(n-k,p)
        g=g.disjoint_union(H)
        g.relabel()
        for x in [0..n-k-1]:
            for y in [n-k..n-1]:
                if random()<p:
                    g.add_edge(x,y)
        if g.is_connected():
            return g

def build_random_with_H(n,p,H):
    while true:
        g=graphs.RandomGNP(n,p)
        g=g.union(H)
        if g.is_connected():
            return g
        

H=graphs.ClawGraph()
build_random_with_H(30,.6,graphs.CompleteGraph(11)).show()

small_obj = []
for g in graph_objects:
    if g.order()<40:
        small_obj.append(g)

load("gt.sage")

loaded utilities loaded invariants loaded properties loaded theorems

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1044, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 1, in <module> File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_salvus.py", line 3537, in load exec 'salvus.namespace["%s"] = sage.structure.sage_object.load(*__args, **__kwds)'%t in salvus.namespace, {'__args':other_args, '__kwds':kwds} File "<string>", line 1, in <module> File "sage/structure/sage_object.pyx", line 1057, in sage.structure.sage_object.load (build/cythonized/sage/structure/sage_object.c:12915) sage.repl.load.load(filename, globals()) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/repl/load.py", line 247, in load exec(preparse_file(open(fpath).read()) + "\n", globals) File "<string>", line 5584, in <module> NameError: name 'graphs_objects' is not defined

g=graphs.CycleGraph(5)
h=graphs.CompleteBipartiteGraph(1,6)
g=g.cartesian_product(h)
g.is_perfect()
g.is_hamiltonian()

False False

for i in [1..1000]:
    g=graphs.CycleGraph(5)
    n=randint(3,20)
    p=random()
    h=graphs.RandomGNP(n,p)
    while not h.is_connected():
        h=graphs.RandomGNP(10,.3)
    print '.',
    GH=g.cartesian_product(h)
    #GH.show()
    if not GH.is_hamiltonian():
        print g.graph6_string()
        print h.graph6_string()
        print GH.is_perfect(),GH.is_hamiltonian()

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Error in lines 1-13 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1044, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 10, in <module> File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 21525, in is_hamiltonian tsp = self.traveling_salesman_problem(use_edge_labels = False) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 7574, in traveling_salesman_problem p.solve(log = verbose) File "sage/numerical/mip.pyx", line 2304, in sage.numerical.mip.MixedIntegerLinearProgram.solve (build/cythonized/sage/numerical/mip.c:17116) self._backend.solve() File "sage/numerical/backends/glpk_backend.pyx", line 1053, in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.c:9067) sig_on() File "src/cysignals/signals.pyx", line 94, in cysignals.signals.sig_raise_exception KeyboardInterrupt

from cysignals.alarm import alarm, AlarmInterrupt
from time import sleep

n=10
for g in graph_objects:
#(((has_radius_equal_diameter)&(is_line_graph))&(~(is_quasi_regular)))->(is_hamiltonian)
    if g.order()>2:
        #print '.',
        if not is_quasi_regular(g):
               if not g.is_perfect():
                    if has_radius_equal_diameter(g):
                        print ',',
                        if (not g.is_hamiltonian()):
                            print g, g.graph6_string()
                            break
print 'done'

, , , , , , , , , , , , , , , , , , , , , , , , , , done

Graph('\hCGGC@?G?_@?@??_?G?@??C??G??G??C??@???G???_??@???@????_???G???@????C').show()

g=Graph('Q~~~\z~n\NznvVSr|t|vrKVvNNg')
g.is_hamiltonian()

True

g=Graph('~?@_?CGGCP?GGg??P??_AGO@?@CA?G?AG??C??@???G???_??@???P????a??AG?O?????@E????G???AG??@?C????PG??A?G??????????@?????@??????_?????G?????P??????C?????AI????????????@C??????@??????AG?????G?_??????P??????O@???????G_???????G???????@????????C????????G????????G???????@C????????@?????A??AG??????G???????????P_????????@?????????G_???????A?G?????????PG???????@?C?????????????????????G??????????C??????????@???????????G??????????G_??????????@???????????PO??????????????????????AG???????????@???????????@C??????????A?G???????????AG??????????@?C????????????P?????????????G?????????????_????????????@?????????????@??????????????_????????????AG?????????????@??????????@??@C???????????A????????????????AK??????????????C??????????????P?????????????A?G??????????????Gc?????????????O@')
flagg=1
for i in [1..1000]:
    print '.',
    while not (g.subgraph_search(graphs.ClawGraph(), induced=True) is None):
        #flagg=-1*flagg
        #if flagg==1:
        g.add_edge(choice(g.subgraph_search(graphs.ClawGraph(), induced=True).complement().edges()))
        #else:
            #g.delete_edge(choice(g.subgraph_search(graphs.ClawGraph(), induced=True).edges()))
    if g.is_connected():
        print ',',
        if is_van_den_heuvel(g) and not g.is_hamiltonian():
            print g.graph6_string()
            g.show()
            break

. ,

Error in lines 3-12 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1044, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 7, in <module> File "<string>", line 1924, in is_van_den_heuvel File "sage/matrix/matrix2.pyx", line 5981, in sage.matrix.matrix2.Matrix.eigenvalues (build/cythonized/sage/matrix/matrix2.c:48804) for r,ee in f.change_ring(A).roots(): File "sage/rings/polynomial/polynomial_element.pyx", line 7558, in sage.rings.polynomial.polynomial_element.Polynomial.roots (build/cythonized/sage/rings/polynomial/polynomial_element.c:69684) rts = complex_roots(self, retval='algebraic') File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/rings/polynomial/complex_roots.py", line 246, in complex_roots factors = p.squarefree_decomposition() File "sage/rings/polynomial/polynomial_element.pyx", line 1709, in sage.rings.polynomial.polynomial_element.Polynomial.squarefree_decomposition (build/cythonized/sage/rings/polynomial/polynomial_element.c:18386) return self.base_ring()._squarefree_decomposition_univariate_polynomial(self) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/categories/fields.py", line 487, in _squarefree_decomposition_univariate_polynomial cur = cur.gcd(cur.derivative()) File "sage/structure/element.pyx", line 4073, in sage.structure.element.coerce_binop.new_method (build/cythonized/sage/structure/element.c:27023) return method(self, other, *args, **kwargs) File "sage/rings/polynomial/polynomial_element.pyx", line 4546, in sage.rings.polynomial.polynomial_element.Polynomial.gcd (build/cythonized/sage/rings/polynomial/polynomial_element.c:43866) return self.base_ring()._gcd_univariate_polynomial(self, other) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/categories/fields.py", line 278, in _gcd_univariate_polynomial q, r = a.quo_rem(b) File "sage/structure/element.pyx", line 4073, in sage.structure.element.coerce_binop.new_method (build/cythonized/sage/structure/element.c:27023) return method(self, other, *args, **kwargs) File "sage/rings/polynomial/polynomial_element.pyx", line 10604, in sage.rings.polynomial.polynomial_element.Polynomial_generic_dense.quo_rem (build/cythonized/sage/rings/polynomial/polynomial_element.c:99800) x[j] -= q * y[j-k] File "sage/structure/element.pyx", line 1519, in sage.structure.element.Element.__mul__ (build/cythonized/sage/structure/element.c:12077) return (<Element>left)._mul_(right) File "sage/structure/element.pyx", line 1560, in sage.structure.element.Element._mul_ (build/cythonized/sage/structure/element.c:12407) return python_op(other) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/rings/qqbar.py", line 3010, in _mul_ return type(self)(_binop_algo[sk,ok](self, other, operator.mul)) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/rings/qqbar.py", line 7434, in an_binop_rational return ANRational(op(a._descr._value, b._descr._value)) 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

g=graphs.CycleGraph(10)
for g in graph_objects:
    if is_van_den_heuvel(g) and not g.is_hamiltonian():
        print g.graph6_string()
g.show()
is_van_den_heuvel(g)

QpDHGOBCG?G@?@??o@G?a?AC@AG [hCGGC@?G?_`O@??_?G?@??CG?G??G?AC?O@C??G???o??@_O?_GGC??@@?_C@?O ]hCGHC@?GGg@?@?Gp?K????C???_?G??C??G?_?G???_?@G?C?@??@?_??H??C?@??@GC??OH? uhCGGCP?GGo@?PG?_?KO@?????G?????C??@??AG??????P??@?????_???G???P??AA??OCC?C?CC???AAO???__???CC???????????@????????????_?????G?????P????????????AG?????G???????C??????@??????AG?????OOG?????__??G???__??????OQ??????CC???????__?????G??G?????O??W ~?@MhEGHC?AG?_PO@?Ga?GA???C??G??G??C??P???G@?G_??????P????_??AG??O@???@C??A?G?????????C????@?????G?????_????P?????@?????G????????????P??????C?????AG????A?G?????_???????H???????G???????_??????@???????@????????_??????AG???????@?????_?@C????????????????AG????????C????????P???????A?G????????G_?????C??G_???????????????????_?????????G?????C???@??????????_?????@????G?????A???????????????_??????????@????@?????AG??????????C????G?????G@?AG@????????????????@??o??????CW????????????C?W?????????????I???????????c?G ShCGHC@?GGg@?@?Gp?K??C?CA?G?_G?Cc JntIBcPEA~_ ~?@_?CGGCP?GGg??P??_AGO@?@CA?G?AG??C??@???G???_??@???P????a??AG?O?????@E????G???AG??@?C????PG??A?G??????????@?????@??????_?????G?????P??????C?????AI????????????@C??????@??????AG?????G?_??????P??????O@???????G_???????G???????@????????C????????G????????G???????@C????????@?????A??AG??????G???????????P_????????@?????????G_???????A?G?????????PG???????@?C?????????????????????G??????????C??????????@???????????G??????????G_??????????@???????????PO??????????????????????AG???????????@???????????@C??????????A?G???????????AG??????????@?C????????????P?????????????G?????????????_????????????@?????????????@??????????????_????????????AG?????????????@??????????@??@C???????????A????????????????AK??????????????C??????????????P?????????????A?G??????????????Gc?????????????O@

Error in lines 2-4 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1044, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 2, in <module> File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 21525, in is_hamiltonian tsp = self.traveling_salesman_problem(use_edge_labels = False) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 7574, in traveling_salesman_problem p.solve(log = verbose) File "sage/numerical/mip.pyx", line 2304, in sage.numerical.mip.MixedIntegerLinearProgram.solve (build/cythonized/sage/numerical/mip.c:17116) self._backend.solve() File "sage/numerical/backends/glpk_backend.pyx", line 1053, in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.c:9067) sig_on() File "src/cysignals/signals.pyx", line 94, in cysignals.signals.sig_raise_exception KeyboardInterrupt

g=MakeHFree(Graph('QpDHGOBCG?G@?@??o@G?a?AC@AG'),graphs.CompleteBipartiteGraph(1,3))
g.show()

k1=graphs.CompleteGraph(1)

def rand_connected(n,p):
    counter=0
    gnp = graphs.RandomGNP(n,p)
    while not gnp.is_connected():
        gnp = graphs.RandomGNP(n,p)
        counter=counter+1
        if counter==200:
            gnp=k1
    return gnp


def rand_hk_connected(n,m,p):
    #HolmeKim is BA with triangles finished at probability p
    return graphs.RandomHolmeKim(n,m,p)

def randomNonHam(n,p):
    #THIS IS MEGA SLOW
    G=rand_connected(n,p)
    C=graphs.CycleGraph(n)
    G=MakeHFree(G,C)
    return G

def randomHam(n,p):
    G=graphs.CycleGraph(n)
    H=graphs.RandomGNP(n,p)
    return G.union(H)

def rand_regular_connected(n,d):
    counter=0
    gnd = graphs.RandomRegular(d,n)
    while not gnd.is_connected():
        gnd = graphs.RandomRegular(d,n)
        counter=counter+1
        if counter==200:
            gnd=k3
    return gnd


def rand_ba_connected(n,m):
    #BA IS ALWAYS CONNECTED
    return graphs.RandomBarabasiAlbert(n,m)
    #while not G.is_connected():
    #    G=graphs.RandomBarabasiAlbert(n,m)
    #    counter=counter+1
    #    if counter==200:
    #        G=k1
    #return G


def rand_gnm_connected(n,m):
    G=graphs.RandomGNM(n,m)
    while not G.is_connected():
        G=graphs.RandomGNM(n,m)
        counter=counter+1
        if counter==200:
            G=k1
    return G

def MakeTriangleFree(G):
    trilist=list(G.subgraph_search_iterator(k3,))
    flagg=0
    if len(trilist)==0:
        flagg=1
    while flagg==0:
        random_index = randrange(0,len(trilist))
        p=trilist[random_index]
        trilist.pop(random_index)
        if G.subgraph(p).is_isomorphic(k3):
            r2=randrange(0,len(p))
            r3=randrange(0,len(p))
            while r3==r2:
                r3=randrange(0,len(p))
            G.delete_edge(p[r2],p[r3])
        if G.is_triangle_free():
            flagg = 1
    return G

def MakeHFree(G,H):
    #THIS IS THE SLOWEST THING
    Hlist=list(G.subgraph_search_iterator(H))
    while len(Hlist)>0:
        random_index=randrange(0,len(Hlist))
        p=Hlist[random_index]
        Hlist.pop(random_index)
        if G.subgraph(p).is_isomorphic(H):
            r2=randrange(0,len(p))
            r3=randrange(0,len(p))
            while r3==r2:
                r3=randrange(0,len(p))
            G.delete_edge(p[r2],p[r3])
        for i in [len(Hlist)-1..0]:
            if not G.subgraph(Hlist[i]).is_isomorphic(H):
                Hlist.pop(i)
    return G

randomNonHam(20,.5).show()

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1043, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 1, in <module> File "", line 4, in randomNonHam File "", line 2, in MakeHFree File "sage/graphs/generic_graph_pyx.pyx", line 834, in sage.graphs.generic_graph_pyx.SubgraphSearch.__next__ (build/cythonized/sage/graphs/generic_graph_pyx.c:15364) sig_on() File "src/cysignals/signals.pyx", line 94, in cysignals.signals.sig_raise_exception KeyboardInterrupt

rand_gnm_connected(100,600).size()

600

load("gt-nb.sage")

load("gt.sage")

loaded utilities loaded invariants loaded properties loaded theorems loaded graphs Remember to load DIMACS and Sloane graphs if you want them

def cruelWorld(runs,min_size,max_size):
    for i in [1..runs]:
        if mod(i,10)==0:
            print '.',
        orde=randint(min_size,max_size)
        d=randint(3,orde-1)
        while not is_even(orde*d):
            d = randint(3,orde-1)
        #p=0.5
        g = rand_regular_connected(orde,d)
        if is_heliotropic_plant(g):
            print ',',
            if not g.is_hamiltonian():
                print g.graph6.string()
                max_size=g.order()-1
                if max_size==3:
                    break
        #g = graphs.RandomBicubicPlanar(orde)
        #while not g.is_connected():
        #    g = graphs.RandomBicubicPlanar(orde)
        #if (is_van_den_heuvel(g) and (not g.is_hamiltonian())):
        #    print 'VDHNH ',g.graph6_string()
        #
        #while g.is_hamiltonian() and g.is_connected():
        #    g.delete_edge(choice(g.hamilton_cycle().edges()))
        #if g.order()>2 and g.is_connected():
        #    print ',',g.is_hamiltonian()
        #    #if not g.is_hamiltonian():
        #        #g=MakeHFree(g,graphs.CycleGraph(g.order()))
        #    if (is_van_den_heuvel(g) and is_claw_free(g)):
        #        print ',',
        #        #if (not g.is_hamiltonian()):
        #        print g.graph6_string()
        #        max_size=g.order()-1
                    

g=Graph('LU@CIW_O?O_CAB')
is_independence_irreducible(g)
is_factor_critical(g)

g=graphs.CompleteBipartiteGraph(1,4)
is_ore(g)
g.is_semi_symmetric()

True True False False

q=Graph('Ms??WX?CH@CQCQR??')
is_heliotropic_plant(q)
q.is_regular()
q.is_hamiltonian()

True True False

cruelWorld(1000,4,60)

. . , . , , . . , , . , , , , . , , . , . , . . . , , , . . , . , . , . . , . . . , , , . . , . , . , . . . , . . , , , . , . . , . , . . . , . . , , , . , . . , . , . . , , , , . , , , . , , . , . , , . , . . . , , , , . , . , , . , , . , , , . , , . , , , , . , . , , . , , , . , . . , , . . , , . , . , , . , , , . . , . . , , . . , , , . . , , . , . , . , , . , , . . . , , . , . , . , . . , . , . , , . , . . , , , . , . , . , . . . . . . , . , , . , . , , . , , ., , , , . , , , . , , . , . , , . , . . . , , , , . , . , , . , , . , , , . , , . , , , , . , . , , . , , , . , . . , , . . , , . , . , , . , , , . . , . . , , . . , , , . . , , . , . , . , , . , , . . . , , . , . , . , . . , . , . , , . , . . , , , . , . , . , . . . . . . , . , , . , . , , . , , .

g=Graph('FnzxW')
g.show()
g.is_hamiltonian()

True

g=Graph('F~~~o')
g.show()

cruelWorld(1000,3,40)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1044, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 1, in <module> File "", line 7, in cruelWorld File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 21525, in is_hamiltonian tsp = self.traveling_salesman_problem(use_edge_labels = False) File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 7663, in traveling_salesman_problem obj = p.solve(log = verbose) 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

Graph('PHAJ@MD^IGKK@waiE[q?DIuW').order()

17