2015-08-03-161507.sagews

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])}