Shared2015-08-03-161507.sagewsOpen in CoCalc
Author: Szabolcs Tengely
Views : 55
def Arrangement1n(n): G=Graph() G.add_vertices([1..n]) Gedges=[] for i in [1..n]: for j in [i+1..n]: if (i+j).is_perfect_power(): Gedges.append([i,j]) G.add_edges(Gedges) G.show(layout='circular') print latex(G) if G.is_hamiltonian(): G.hamiltonian_cycle().show() return True else: G.add_vertex(0) for i in [1..n]: G.add_edges([[0,i]]) 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: clusters[label].add(node) 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])}