Shared2015-08-03-161507.sagewsOpen in CoCalc
Author: Szabolcs Tengely
Views : 55
def Arrangement1n(n):
G=Graph()
Gedges=[]
for i in [1..n]:
for j in [i+1..n]:
if (i+j).is_perfect_power():
Gedges.append([i,j])
G.show(layout='circular')
print latex(G)
if G.is_hamiltonian():
G.hamiltonian_cycle().show()
return True
else:
for i in [1..n]:
if G.is_hamiltonian():
G.hamiltonian_cycle().show()
return True
else:
return False
Arrangement1n(19)

\begin{tikzpicture} \definecolor{cv0}{rgb}{0.0,0.0,0.0} \definecolor{cfv0}{rgb}{1.0,1.0,1.0} \definecolor{clv0}{rgb}{0.0,0.0,0.0} \definecolor{cv1}{rgb}{0.0,0.0,0.0} \definecolor{cfv1}{rgb}{1.0,1.0,1.0} \definecolor{clv1}{rgb}{0.0,0.0,0.0} \definecolor{cv2}{rgb}{0.0,0.0,0.0} \definecolor{cfv2}{rgb}{1.0,1.0,1.0} \definecolor{clv2}{rgb}{0.0,0.0,0.0} \definecolor{cv3}{rgb}{0.0,0.0,0.0} \definecolor{cfv3}{rgb}{1.0,1.0,1.0} \definecolor{clv3}{rgb}{0.0,0.0,0.0} \definecolor{cv4}{rgb}{0.0,0.0,0.0} \definecolor{cfv4}{rgb}{1.0,1.0,1.0} \definecolor{clv4}{rgb}{0.0,0.0,0.0} \definecolor{cv5}{rgb}{0.0,0.0,0.0} \definecolor{cfv5}{rgb}{1.0,1.0,1.0} \definecolor{clv5}{rgb}{0.0,0.0,0.0} \definecolor{cv6}{rgb}{0.0,0.0,0.0} \definecolor{cfv6}{rgb}{1.0,1.0,1.0} \definecolor{clv6}{rgb}{0.0,0.0,0.0} \definecolor{cv7}{rgb}{0.0,0.0,0.0} \definecolor{cfv7}{rgb}{1.0,1.0,1.0} \definecolor{clv7}{rgb}{0.0,0.0,0.0} \definecolor{cv8}{rgb}{0.0,0.0,0.0} \definecolor{cfv8}{rgb}{1.0,1.0,1.0} \definecolor{clv8}{rgb}{0.0,0.0,0.0} \definecolor{cv9}{rgb}{0.0,0.0,0.0} \definecolor{cfv9}{rgb}{1.0,1.0,1.0} \definecolor{clv9}{rgb}{0.0,0.0,0.0} \definecolor{cv10}{rgb}{0.0,0.0,0.0} \definecolor{cfv10}{rgb}{1.0,1.0,1.0} \definecolor{clv10}{rgb}{0.0,0.0,0.0} \definecolor{cv11}{rgb}{0.0,0.0,0.0} \definecolor{cfv11}{rgb}{1.0,1.0,1.0} \definecolor{clv11}{rgb}{0.0,0.0,0.0} \definecolor{cv12}{rgb}{0.0,0.0,0.0} \definecolor{cfv12}{rgb}{1.0,1.0,1.0} \definecolor{clv12}{rgb}{0.0,0.0,0.0} \definecolor{cv13}{rgb}{0.0,0.0,0.0} \definecolor{cfv13}{rgb}{1.0,1.0,1.0} \definecolor{clv13}{rgb}{0.0,0.0,0.0} \definecolor{cv14}{rgb}{0.0,0.0,0.0} \definecolor{cfv14}{rgb}{1.0,1.0,1.0} \definecolor{clv14}{rgb}{0.0,0.0,0.0} \definecolor{cv15}{rgb}{0.0,0.0,0.0} \definecolor{cfv15}{rgb}{1.0,1.0,1.0} \definecolor{clv15}{rgb}{0.0,0.0,0.0} \definecolor{cv16}{rgb}{0.0,0.0,0.0} \definecolor{cfv16}{rgb}{1.0,1.0,1.0} \definecolor{clv16}{rgb}{0.0,0.0,0.0} \definecolor{cv17}{rgb}{0.0,0.0,0.0} \definecolor{cfv17}{rgb}{1.0,1.0,1.0} \definecolor{clv17}{rgb}{0.0,0.0,0.0} \definecolor{cv18}{rgb}{0.0,0.0,0.0} \definecolor{cfv18}{rgb}{1.0,1.0,1.0} \definecolor{clv18}{rgb}{0.0,0.0,0.0} \definecolor{cv9v16}{rgb}{0.0,0.0,0.0} \definecolor{cv5v9}{rgb}{0.0,0.0,0.0} \definecolor{cv9v14}{rgb}{0.0,0.0,0.0} \definecolor{cv0v2}{rgb}{0.0,0.0,0.0} \definecolor{cv0v6}{rgb}{0.0,0.0,0.0} \definecolor{cv0v7}{rgb}{0.0,0.0,0.0} \definecolor{cv0v14}{rgb}{0.0,0.0,0.0} \definecolor{cv1v5}{rgb}{0.0,0.0,0.0} \definecolor{cv1v6}{rgb}{0.0,0.0,0.0} \definecolor{cv1v13}{rgb}{0.0,0.0,0.0} \definecolor{cv2v4}{rgb}{0.0,0.0,0.0} \definecolor{cv2v5}{rgb}{0.0,0.0,0.0} \definecolor{cv2v12}{rgb}{0.0,0.0,0.0} \definecolor{cv3v4}{rgb}{0.0,0.0,0.0} \definecolor{cv3v11}{rgb}{0.0,0.0,0.0} \definecolor{cv4v10}{rgb}{0.0,0.0,0.0} \definecolor{cv5v18}{rgb}{0.0,0.0,0.0} \definecolor{cv6v17}{rgb}{0.0,0.0,0.0} \definecolor{cv6v8}{rgb}{0.0,0.0,0.0} \definecolor{cv7v16}{rgb}{0.0,0.0,0.0} \definecolor{cv7v18}{rgb}{0.0,0.0,0.0} \definecolor{cv8v15}{rgb}{0.0,0.0,0.0} \definecolor{cv8v17}{rgb}{0.0,0.0,0.0} \definecolor{cv10v15}{rgb}{0.0,0.0,0.0} \definecolor{cv10v13}{rgb}{0.0,0.0,0.0} \definecolor{cv11v12}{rgb}{0.0,0.0,0.0} \definecolor{cv11v14}{rgb}{0.0,0.0,0.0} \definecolor{cv12v18}{rgb}{0.0,0.0,0.0} \definecolor{cv12v13}{rgb}{0.0,0.0,0.0} \definecolor{cv13v17}{rgb}{0.0,0.0,0.0} \definecolor{cv14v16}{rgb}{0.0,0.0,0.0} \definecolor{cv16v18}{rgb}{0.0,0.0,0.0} % \Vertex[style={minimum size=1.0cm,draw=cv0,fill=cfv0,text=clv0,shape=circle},LabelOut=false,L=\hbox{$1$},x=4.3933cm,y=3.1742cm]{v0} \Vertex[style={minimum size=1.0cm,draw=cv1,fill=cfv1,text=clv1,shape=circle},LabelOut=false,L=\hbox{$2$},x=4.3473cm,y=2.4382cm]{v1} \Vertex[style={minimum size=1.0cm,draw=cv2,fill=cfv2,text=clv2,shape=circle},LabelOut=false,L=\hbox{$3$},x=2.7141cm,y=2.6372cm]{v2} \Vertex[style={minimum size=1.0cm,draw=cv3,fill=cfv3,text=clv3,shape=circle},LabelOut=false,L=\hbox{$4$},x=0.0cm,y=2.8939cm]{v3} \Vertex[style={minimum size=1.0cm,draw=cv4,fill=cfv4,text=clv4,shape=circle},LabelOut=false,L=\hbox{$5$},x=1.0586cm,y=1.9979cm]{v4} \Vertex[style={minimum size=1.0cm,draw=cv5,fill=cfv5,text=clv5,shape=circle},LabelOut=false,L=\hbox{$6$},x=3.8281cm,y=3.5334cm]{v5} \Vertex[style={minimum size=1.0cm,draw=cv6,fill=cfv6,text=clv6,shape=circle},LabelOut=false,L=\hbox{$7$},x=5.0cm,y=1.7711cm]{v6} \Vertex[style={minimum size=1.0cm,draw=cv7,fill=cfv7,text=clv7,shape=circle},LabelOut=false,L=\hbox{$8$},x=5.0cm,y=4.2583cm]{v7} \Vertex[style={minimum size=1.0cm,draw=cv8,fill=cfv8,text=clv8,shape=circle},LabelOut=false,L=\hbox{$9$},x=4.6513cm,y=0.488cm]{v8} \Vertex[style={minimum size=1.0cm,draw=cv9,fill=cfv9,text=clv9,shape=circle},LabelOut=false,L=\hbox{$10$},x=4.1959cm,y=4.6223cm]{v9} \Vertex[style={minimum size=1.0cm,draw=cv10,fill=cfv10,text=clv10,shape=circle},LabelOut=false,L=\hbox{$11$},x=1.9924cm,y=0.946cm]{v10} \Vertex[style={minimum size=1.0cm,draw=cv11,fill=cfv11,text=clv11,shape=circle},LabelOut=false,L=\hbox{$12$},x=1.2107cm,y=3.6788cm]{v11} \Vertex[style={minimum size=1.0cm,draw=cv12,fill=cfv12,text=clv12,shape=circle},LabelOut=false,L=\hbox{$13$},x=2.4701cm,y=3.1256cm]{v12} \Vertex[style={minimum size=1.0cm,draw=cv13,fill=cfv13,text=clv13,shape=circle},LabelOut=false,L=\hbox{$14$},x=3.1256cm,y=1.7896cm]{v13} \Vertex[style={minimum size=1.0cm,draw=cv14,fill=cfv14,text=clv14,shape=circle},LabelOut=false,L=\hbox{$15$},x=2.9151cm,y=4.1936cm]{v14} \Vertex[style={minimum size=1.0cm,draw=cv15,fill=cfv15,text=clv15,shape=circle},LabelOut=false,L=\hbox{$16$},x=3.0806cm,y=0.0cm]{v15} \Vertex[style={minimum size=1.0cm,draw=cv16,fill=cfv16,text=clv16,shape=circle},LabelOut=false,L=\hbox{$17$},x=4.0317cm,y=5.0cm]{v16} \Vertex[style={minimum size=1.0cm,draw=cv17,fill=cfv17,text=clv17,shape=circle},LabelOut=false,L=\hbox{$18$},x=4.5116cm,y=1.1085cm]{v17} \Vertex[style={minimum size=1.0cm,draw=cv18,fill=cfv18,text=clv18,shape=circle},LabelOut=false,L=\hbox{$19$},x=3.6613cm,y=4.1862cm]{v18} % \Edge[lw=0.1cm,style={color=cv0v2,},](v0)(v2) \Edge[lw=0.1cm,style={color=cv0v6,},](v0)(v6) \Edge[lw=0.1cm,style={color=cv0v7,},](v0)(v7) \Edge[lw=0.1cm,style={color=cv0v14,},](v0)(v14) \Edge[lw=0.1cm,style={color=cv1v5,},](v1)(v5) \Edge[lw=0.1cm,style={color=cv1v6,},](v1)(v6) \Edge[lw=0.1cm,style={color=cv1v13,},](v1)(v13) \Edge[lw=0.1cm,style={color=cv2v4,},](v2)(v4) \Edge[lw=0.1cm,style={color=cv2v5,},](v2)(v5) \Edge[lw=0.1cm,style={color=cv2v12,},](v2)(v12) \Edge[lw=0.1cm,style={color=cv3v4,},](v3)(v4) \Edge[lw=0.1cm,style={color=cv3v11,},](v3)(v11) \Edge[lw=0.1cm,style={color=cv4v10,},](v4)(v10) \Edge[lw=0.1cm,style={color=cv5v9,},](v5)(v9) \Edge[lw=0.1cm,style={color=cv5v18,},](v5)(v18) \Edge[lw=0.1cm,style={color=cv6v8,},](v6)(v8) \Edge[lw=0.1cm,style={color=cv6v17,},](v6)(v17) \Edge[lw=0.1cm,style={color=cv7v16,},](v7)(v16) \Edge[lw=0.1cm,style={color=cv7v18,},](v7)(v18) \Edge[lw=0.1cm,style={color=cv8v15,},](v8)(v15) \Edge[lw=0.1cm,style={color=cv8v17,},](v8)(v17) \Edge[lw=0.1cm,style={color=cv9v14,},](v9)(v14) \Edge[lw=0.1cm,style={color=cv9v16,},](v9)(v16) \Edge[lw=0.1cm,style={color=cv10v13,},](v10)(v13) \Edge[lw=0.1cm,style={color=cv10v15,},](v10)(v15) \Edge[lw=0.1cm,style={color=cv11v12,},](v11)(v12) \Edge[lw=0.1cm,style={color=cv11v14,},](v11)(v14) \Edge[lw=0.1cm,style={color=cv12v13,},](v12)(v13) \Edge[lw=0.1cm,style={color=cv12v18,},](v12)(v18) \Edge[lw=0.1cm,style={color=cv13v17,},](v13)(v17) \Edge[lw=0.1cm,style={color=cv14v16,},](v14)(v16) \Edge[lw=0.1cm,style={color=cv16v18,},](v16)(v18) % \end{tikzpicture}
True


graphs.BalancedTree(3,3).show()



Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute flags=compile_flags), namespace, locals) File "<string>", line 1 ?mycielsk ^ SyntaxError: invalid syntax
g = graphs.RandomBarabasiAlbert(8,5)
g.show()

g.pagerank()

{0: 0.10074809095806429, 1: 0.07327961278619403, 2: 0.10074809095806443, 3: 0.0734331428270892, 4: 0.07327961278619406, 5: 0.22412076774886017, 6: 0.1928113985715906, 7: 0.16157928336394337}
g.num_edges()

15
def RWG(n, p, lower_weight = 1, upper_weight = 100):
import random
g = graphs.RandomGNP(n,p)
m = g.num_edges()
weights = [random.randint(lower_weight, upper_weight) for r in xrange(m)]
uw_edges = g.edges()

# Create weighted graph edge list
w_edges = [(uw_edges[i][0], uw_edges[i][1], weights[i]) for i in xrange(m)]

return Graph(w_edges, weighted = True)

G=RWG(9,0.5)





G.show(edge_labels=True)

V=G.vertices()

V.sort()

V

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
S=Set([1..10])

S.random_element()

1
import random
from collections import Counter
#from math import log2
from operator import itemgetter

__version__ = '0.5'

def top_weighting(G, node, neighbor):
""" A weight is the edge weight. """
return G[node][neighbor].get('weight', 1.)

def nolog_weighting(G, node, neighbor):
""" A weight is the edge weight divided to the node degree. """
return G[node][neighbor].get('weight', 1.) / G.degree(neighbor)

def log_weighting(G, node, neighbor):
""" A weight is the edge weight divided to the log2 of node degree. """
return G[node][neighbor].get('weight', 1.) / log2(G.degree(neighbor) + 1)

WEIGHTING = {
'top': top_weighting,
'nolog': nolog_weighting,
'log': log_weighting
}

def chinese_whispers(G, weighting='top', iterations=20, seed=None):
""" Performs clustering of nodes in a NetworkX graph G
using the 'weighting' method. Three weighing schemas are available:
'top' relies on the original weights; 'nolog' normalizes an edge weight
by the degree of the related node; 'log' normalizes an edge weight by the
logarithm of the output degree. It is possible to specify the maximum number
of iterations as well as the random seed to use. """

weighting_func = WEIGHTING[weighting] if isinstance(weighting, str) else weighting

shuffle_func = random.shuffle if seed is None else random.Random(seed).shuffle

for i, node in enumerate(G):
G.node[node]['label'] = i + 1

nodes = list(G)

for i in range(iterations):
changes = False

shuffle_func(nodes)

for node in nodes:
previous = G.node[node]['label']

if G[node]:
scores = score(G, node, weighting_func)
G.node[node]['label'], _ = max(scores.items(), key=itemgetter(1))

changes = changes or previous != G.node[node]['label']

if not changes:
break

return G

def score(G, node, weighting_func):
""" Computes label scores in the given node neighborhood. """

scores = Counter()

if node not in G:
return scores

for neighbor in G[node]:
scores[G.node[neighbor]['label']] += weighting_func(G, node, neighbor)

return scores

def aggregate_clusters(G):
""" Takes as input the labeled graph and outputs a dictionary with the keys
being cluster IDs and the values being sets of cluster elements. """

clusters = {}

for node in G:
label = G.node[node]['label']

if label not in clusters:
clusters[label] = {node}
else:

return clusters

G2=chinese_whispers(G1)

G1=G.networkx_graph()

Graph(G2).show(edge_labels=True)



aggregate_clusters(G2)

{9: set([0, 1, 2, 3, 4, 5, 6, 7, 8])}
G.show(edge_labels=True)

G=RWG(9,0.5)
G1=G.networkx_graph()
G2=chinese_whispers(G1)
aggregate_clusters(G2)
G.show(edge_labels=True)

{3: set([1, 2, 6]), 5: set([0, 3, 4]), 6: set([8, 5, 7])}

G=RWG(13,0.2)
G1=G.networkx_graph()
G2=chinese_whispers(G1)
aggregate_clusters(G2)
G.show(edge_labels=True)

{8: set([8, 11]), 9: set([0, 10, 5]), 3: set([1, 2, 12, 6]), 7: set([4, 7])}