class_prims.sagews

G = graphs.RandomGNP(8,.6)
G.show()

load("func_graphs.sage")

# NAME: add_edges_to_queue
# DESC: this is a helper function to prims algorithm
#     it adds all the edges NOT incident on a vertex in the
#     to a vertex in the tree
# INPUT: 
#     q: the priority queue used in the code
#     g: the parent graph
#     u: the vertex we are using to collect the incident edges
#     vertex_in_tree: a binary list indicating whether or not the vertices are 
#          "in" the tree
# OUTPUT: none
# EXAMPLE: only called from within prims algorithm
def add_edges_to_queue(q, g, u, vertex_in_tree):
    # get the edges incident on vertex u
    E = g.edges_incident(u)
    #print "adding edges incident on vertex " + str(u) + " to queue"
    for i in range(0, len(     E)):
        # if either vertex is already in the tree, then these edges
        # have already been added to the tree. Only new edges should
        # be added!
        if vertex_in_tree[0, E[i][0]] != 1 and vertex_in_tree[0, E[i][1]] != 1:
            # add edge to queue, keying off edge weight
            # (key, edge)
            q.put((E[i][2], E[i]))
        # end if
    #end for
# end def add_edges_to_queue


g = random_weighted_graph(8, .6, 1, 100)
g.show(edge_labels=true)

try:
    import Queue as Q  # ver. < 3.0
except ImportError:
    import queue as Q

# create empty priority queue
q = Q.PriorityQueue()

# create a list indicating whether or not a given vertex
# is in the tree. Initially, all vertices are 0 (not in tree)
vertex_in_tree = Matrix(1,g.order());

# create a graph to hold the spanning tree
T = Graph(g.order())
#T.show()

# indicate that vertex 0 is in the tree
vertex_in_tree[0, 0] = 1;

# get all the edges incident on vertex 0
# add them to the priority queue
E = g.edges_incident(0)
for i in range(0, len(E)):
    # add edge to queue, keying off edge weight
    # (key, edge)
    q.put((E[i][2], E[i]))

while not q.empty():
    elm = q.get()
    # recall that elements in the queue are stored as (key, value)
    # therefore the key (edge weight) is elm[0] and the edge is elm[1]
    e = elm[1]
    T.add_edge(e)
    # but we can only include this edge if there are no cycles!
    if T.is_forest():
        # if this vertex is already incident on an edge in the spanning tree
        # its edges will have already been added to the queue
        # only proceed if the vertex is NOT already in the tree
        if vertex_in_tree[0,e[0]] == 0:
            # add all incident edges to the queue
            add_edges_to_queue(q, g, e[0], vertex_in_tree)
            # indicate that this vertex has been added to the spanning tree
            vertex_in_tree[0,e[0]] = 1;
        else:
            # add all incident edges to the queue
            add_edges_to_queue(q, g, e[1], vertex_in_tree)
            # indicate that this vertex has been added to the spanning tree
            vertex_in_tree[0,e[1]] = 1;
        #T.show(edge_labels=true)
    else:
        T.delete_edge(e)
    # our tree is finished when there are n - 1 edges in the tree
    if T.size() == (g.order() - 1):
        break
T.show(edge_labels=true)

def mod_distance(i, j, n):
    return min(abs(i - j), n - abs(i-j))
#end def mod_distance(i, j, n)

def haray_graph(k, n):
    A = Matrix(n,n)
    print A
    r = ceil(k/2)
    print "r = " + str(r)
    for i in range(0, (n - 2) + 1):
        print "i = " + str(i)
        for j in range(i + 1, (n - 1) + 1):
            if mod_distance(i, j, n) <= r:
                A(i,j) = 1; A(j, i) = 1;
    return A
# end def haray_graph
A = haray_graph(4,8)
g = Graph(A)
g.show()

[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 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 0 0] [0 0 0 0 0 0 0 0] r = 2 i = 0

Error in lines 14-14 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 996, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "", line 10, in haray_graph File "sage/symbolic/expression.pyx", line 5837, in sage.symbolic.expression.Expression.function (/ext/sage/sage-8.0/src/build/cythonized/sage/symbolic/expression.cpp:36195) raise TypeError("Must construct a function with a tuple (or list) of symbolic variables.") TypeError: Must construct a function with a tuple (or list) of symbolic variables.