sa403_ws1.sagews

load("func_graphs.sage")
from sage.graphs.spanning_tree import kruskal

# small local function to print weight of tree
n = 400
for i in range(1, 10):

    # generate a random graph that is SPARSE
    # probability .6
    gg = random_weighted_graph(n, .5, 1, 100)
    num_edges = gg.size()
    # call kruskal's algorithm, and record the time
    t_init = cputime(subprocesses=True)
    E = kruskal(gg);
    w = print_tree_weight(E)
    t_final = cputime(subprocesses=True) - t_init
    print "1 Kruskal " + str(n) + " vertices, edges = " + str(num_edges) + ", weight = " + str(w) + ", time = " + str(t_final)


    # generate a random graph that is DENSE
    # probability .8
    gg = random_weighted_graph(n, .8, 1, 100)
    num_edges = gg.size()
    # call kruskal's algorithm, and record the time
    t_init = cputime(subprocesses=True)
    E = kruskal(gg);
    w = print_tree_weight(E)
    t_final = cputime(subprocesses=True) - t_init
    print "1 Kruskal " + str(n) + " vertices, edges = " + str(num_edges) + ", weight = " + str(w) + ", time = " + str(t_final)

1 Kruskal 400 vertices, edges = 39758, weight = 399, time = 0.064 1 Kruskal 400 vertices, edges = 63843, weight = 399, time = 0.104 1 Kruskal 400 vertices, edges = 39841, weight = 399, time = 0.064 1 Kruskal 400 vertices, edges = 63704, weight = 399, time = 0.112 1 Kruskal 400 vertices, edges = 39812, weight = 399, time = 0.064 1 Kruskal 400 vertices, edges = 63866, weight = 399, time = 0.108 1 Kruskal 400 vertices, edges = 40082, weight = 399, time = 0.064 1 Kruskal 400 vertices, edges = 63872, weight = 399, time = 0.104 1 Kruskal 400 vertices, edges = 39725, weight = 399, time = 0.068 1 Kruskal 400 vertices, edges = 63778, weight = 399, time = 0.104 1 Kruskal 400 vertices, edges = 39870, weight = 399, time = 0.068 1 Kruskal 400 vertices, edges = 63812, weight = 399, time = 0.116 1 Kruskal 400 vertices, edges = 39890, weight = 399, time = 0.068 1 Kruskal 400 vertices, edges = 63849, weight = 399, time = 0.112 1 Kruskal 400 vertices, edges = 39998, weight = 399, time = 0.064 1 Kruskal 400 vertices, edges = 64068, weight = 399, time = 0.108 1 Kruskal 400 vertices, edges = 39944, weight = 399, time = 0.064 1 Kruskal 400 vertices, edges = 63740, weight = 399, time = 0.124

#
# input: an integer n
# output: n!
# example: my_factorial(3) = 6
def my_factorial(n):
    my_fac = 1;
    for i in range(2,n+1):
        print "my_fac = " + str(my_fac)
        my_fac = my_fac*i
    return my_fac
#end def

my_factorial(6)

my_fac = 1 my_fac = 2 my_fac = 6 my_fac = 24 my_fac = 120 720

import random

g = Graph([(0,1),(0,2),(1,2)])
g.show()
uw_edges = g.edges()
uw_edges
#   00 01 02      10 11 12
# [(0, 1, None), (0, 2, None), (1, 2, None)]
uw_edges[2][1]
uw_edges[2][0]

# number of edges
m = g.size()
m

w = random.randint(1,10)
# [(0, 1, None), (0, 2, None), (1, 2, None)]
w_edges = [(uw_edges[i][0], uw_edges[i][1], random.randint(1,10)) for i in range(0,m)]
w_edges

gg = Graph(w_edges, weighted=true)
gg.show(edge_labels=true)

from sage.graphs.spanning_tree import kruskal
E = kruskal(gg);
E
H = gg.subgraph(edges=E)
H.show(edge_labels=true)

w = E[0][2] + E[1][2]
print "tree weight = " + str(w)

[(0, 1, None), (0, 2, None), (1, 2, None)] 2 1 3 [(0, 1, 3), (0, 2, 9), (1, 2, 3)]

[(0, 1, 3), (1, 2, 3)]

tree weight = 6

g = BipartiteGraph();
g.add_edges([(0,4),(0,5),(1,4),(1,7),(1,5),(1,6),(2,4),(3,4),(2,5),(3,5)]);
g.show()

A = Matrix([
        [1, 1, 1, 0, 0, 0, 0],# 0
        [0, 0, 0, 1, 0, 0, 0],# 1
        [0, 0, 0, 0, 1, 1, 1],# 2
        [1, 0, 0, 0, 1, 0, 0],# 3
        [0, 1, 0, 0, 0, 1, 0],# 4
        [0, 0, 1, 1, 0, 0, 1]# 5
        ]);
A

p = MixedIntegerLinearProgram(maximization=True, solver = "GLPK")
x = p.new_variable(integer=True, nonnegative=True)
p.add_constraint(x[0] + x[1] + x[2] <= 1) # row 0
p.add_constraint(x[3] <= 1) # row 1
p.add_constraint(x[4] + x[5] + x[6] <= 1) # row 2
p.add_constraint(x[0] + x[4] <= 1) # row 3
p.add_constraint(x[1] + x[5] <= 1) # row 4
p.add_constraint(x[2] + x[3] + x[6] <= 1) # row 5
p.set_objective(x[0] + x[1] + x[2] + x[3] + x[4] + x[5] + x[6])
p.show()
print('Objective Value: {}'.format(p.solve()))
for i, v in p.get_values(x).iteritems():
    print('x_%s = %s' % (i, int(round(v))))

# find the minimum cover
p = MixedIntegerLinearProgram(maximization=False, solver = "GLPK")
y = p.new_variable(integer=True, nonnegative=True)
p.add_constraint(y[0] + y[3] >= 1) # column 03
p.add_constraint(y[0] + y[4] >= 1) # column 04
p.add_constraint(y[0] + y[5] >= 1) # column 05
p.add_constraint(y[1] + y[5] >= 1) # column 15
p.add_constraint(y[2] + y[3] >= 1) # column 23
p.add_constraint(y[2] + y[4] >= 1) # column 24
p.add_constraint(y[2] + y[5] >= 1) # column 25
p.set_objective(y[0] + y[1] + y[2] + y[3] + y[4] + y[5])
p.show()
print('Objective Value: {}'.format(p.solve()))
for i, v in p.get_values(y).iteritems():
    print('x_%s = %s' % (i, int(round(v))))

[1 1 1 0 0 0 0] [0 0 0 1 0 0 0] [0 0 0 0 1 1 1] [1 0 0 0 1 0 0] [0 1 0 0 0 1 0] [0 0 1 1 0 0 1] Maximization: x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 Constraints: x_0 + x_1 + x_2 <= 1.0 x_3 <= 1.0 x_4 + x_5 + x_6 <= 1.0 x_0 + x_4 <= 1.0 x_1 + x_5 <= 1.0 x_2 + x_3 + x_6 <= 1.0 Variables: x_0 is an integer variable (min=0.0, max=+oo) x_1 is an integer variable (min=0.0, max=+oo) x_2 is an integer variable (min=0.0, max=+oo) x_3 is an integer variable (min=0.0, max=+oo) x_4 is an integer variable (min=0.0, max=+oo) x_5 is an integer variable (min=0.0, max=+oo) x_6 is an integer variable (min=0.0, max=+oo) Objective Value: 3.0 x_0 = 1 x_1 = 0 x_2 = 0 x_3 = 1 x_4 = 0 x_5 = 1 x_6 = 0 Minimization: x_0 + x_1 + x_2 + x_3 + x_4 + x_5 Constraints: - x_0 - x_1 <= -1.0 - x_0 - x_2 <= -1.0 - x_0 - x_3 <= -1.0 - x_3 - x_4 <= -1.0 - x_1 - x_5 <= -1.0 - x_2 - x_5 <= -1.0 - x_3 - x_5 <= -1.0 Variables: x_0 is an integer variable (min=0.0, max=+oo) x_1 is an integer variable (min=0.0, max=+oo) x_2 is an integer variable (min=0.0, max=+oo) x_3 is an integer variable (min=0.0, max=+oo) x_4 is an integer variable (min=0.0, max=+oo) x_5 is an integer variable (min=0.0, max=+oo) Objective Value: 3.0 x_0 = 1 x_1 = 0 x_2 = 1 x_3 = 0 x_4 = 0 x_5 = 1

g = Graph();
g.add_edges([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)]);
show(g)
#draw(g)
#P.show()

M = Matrix([(0,1,0,0,1,1,0,0,0,0),(1,0,1,0,0,0,1,0,0,0),
(0,1,0,1,0,0,0,1,0,0), (0,0,1,0,1,0,0,0,1,0),(1,0,0,1,0,0,0,0,0,1),
(1,0,0,0,0,0,0,1,1,0), (0,1,0,0,0,0,0,0,1,1),(0,0,1,0,0,1,0,0,0,1),
(0,0,0,1,0,1,1,0,0,0), (0,0,0,0,1,0,1,1,0,0)])
M
G = Graph(M);
G.plot()

# create the incidence matrix for a path
# edges (0,1),(0,2),(1,2),(0,3),(1,3)
# incidence matrix is 4 x 5
M = Matrix([
        (1,1,0,1,0), # vertex 0
        (1,0,1,0,1), # vertex 1
        (0,1,1,0,0), # vertex 2
        (0,0,0,1,1) # vertex 3
        ]);
M
g = Graph(M)
g.plot()

d3-based renderer not yet implemented

[0 1 0 0 1 1 0 0 0 0] [1 0 1 0 0 0 1 0 0 0] [0 1 0 1 0 0 0 1 0 0] [0 0 1 0 1 0 0 0 1 0] [1 0 0 1 0 0 0 0 0 1] [1 0 0 0 0 0 0 1 1 0] [0 1 0 0 0 0 0 0 1 1] [0 0 1 0 0 1 0 0 0 1] [0 0 0 1 0 1 1 0 0 0] [0 0 0 0 1 0 1 1 0 0]

[1 1 0 1 0] [1 0 1 0 1] [0 1 1 0 0] [0 0 0 1 1]

g = graphs.PetersenGraph()
g.show()

/ext/sage/sage-8.0/local/lib/python2.7/site-packages/matplotlib/font_manager.py:273: UserWarning: Matplotlib is building the font cache using fc-list. This may take a moment. warnings.warn('Matplotlib is building the font cache using fc-list. This may take a moment.')