#NAME: Andrew Eisenhauer
#EMAIL: [email protected]

from sage.graphs.spanning_tree import kruskal;
import random;
##I sometimes get an error here. It says there is an error in line 6, "e = next(sortedE_iter) StopIteration" when this doesn't happen, the code compiles/runs just fine. It happens maybe 30% of the time I compile this code.
load("RandomWeightedGraph.sage");

g=random_weighted_graph(20, 0.1, 1, 20);
g.plot();

K = kruskal(g);

print("Kruskal's MST: " +str(K));

H = g.subgraph(edges=K);
H.show(edge_labels=true);


Sum = 0;
for i in xrange(0, len(K)):
    Sum = Sum + K[i][2];
#end for loop
print("MST Weight: \n" +str(Sum))

##Part 2

from sage.graphs.spanning_tree import kruskal;
import random;
load("RandomWeightedGraph.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()
    #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)
E = T.edges()

print"Now, we will compute the MST weight for Prim's algorithm"
Sum = 0;
for i in range(0, len(E)):
      Sum=Sum+E[i][2]
#end for loop
print("MST Weight: \n" +str(Sum))

##PART 3--PRIMS VS KRUSKALS--DENSE
g = random_weighted_graph(200, .6, 1, 100)
edges=g.size()
#g.show(edge_labels=true)
    
t_startP=cputime(subprocesses=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());

T = Graph(g.order())
vertex_in_tree[0, 0] = 1;
E = g.edges_incident(0)
for i in range(0, len(E)):
    q.put((E[i][2], E[i]))

while not q.empty():
    elm = q.get()
    e = elm[1]
    T.add_edge(e)
    if T.is_forest():
        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)
            vertex_in_tree[0,e[0]] = 1;
        else:
            add_edges_to_queue(q, g, e[1], vertex_in_tree)
            vertex_in_tree[0,e[1]] = 1;
    else:
        T.delete_edge(e)
    if T.size() == (g.order() - 1):
        break
t_endP=cputime(subprocesses=true)-t_startP

print("Number of vertices=200, Number of edges= " +str(edges), "runtime Prims="+str(t_endP))
t_startk=cputime(subprocesses=true)
K=kruskal(g)
t_endk=cputime(subprocesses=true) -t_startk
print("Number of vertices=200, Number of edges= " +str(edges), "runtime ="+str(t_endk))

#RUNTIME 1 Prims: 200 vertices, 11948 edges, .224 seconds
#RUNTIME 1 Kruskals: 200 vertices, 11948 edges, .016 seconds

#RUNTIME 2 Prims: 200 vertices, 11975 edges, .22 seconds
#RUNTIME 2 Kruskals: 200 vertices, 11975 edges, .02 seconds

#RUNTIME 3 Prims: 200 vertices, 11889 edges, .364 seconds
#RUNTIME 3 Kruskals: 200 vertices,11889 edges, .028 seconds

#RUNTIME 4 Prims: 200 vertices, 11852 edges, .284 seconds
#RUNTIME 4 Kruskals: 200 vertices, 11852 edges, .016 seconds

#RUNTIME 5 Prims: 200 vertices, 11891 edges, .24 seconds
#RUNTIME 5 Kruskals: 200 vertices,11891 edges .02 seconds

#RUNTIME 6 Prims: 200 vertices, 11857 edges, .504 seconds
#RUNTIME 6 Kruskals: 200 vertices, 11857 edges, 036 seconds

#RUNTIME 7 Prims: 200 vertices, 11904 edges, .268 seconds
#RUNTIME 7 Kruskals: 200 vertices, 11904 edges, .02 seconds

#RUNTIME 8 Prims: 200 vertices, 11851 edges, .232 seconds
#RUNTIME 8 Kruskals: 200 vertices, 11851 edges.002 seconds

#RUNTIME 9 Prims: 200 vertices, 12009 edges, .244 seconds
#RUNTIME 9 Kruskals: 200 vertices, .02 seconds

#RUNTIME 10 Prims: 200 vertices, 11917 edges, .268 seconds
#RUNTIME 10 Kruskals: 200 vertices, 11917 edges.024 seconds

##PART 3--PRIMS VS KRUSKALS--SPARSE
g = random_weighted_graph(200, .1, 1, 100)
edges=g.size()
#g.show(edge_labels=true)
    
t_startP=cputime(subprocesses=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());

T = Graph(g.order())
vertex_in_tree[0, 0] = 1;
E = g.edges_incident(0)
for i in range(0, len(E)):
    q.put((E[i][2], E[i]))

while not q.empty():
    elm = q.get()
    e = elm[1]
    T.add_edge(e)
    if T.is_forest():
        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)
            vertex_in_tree[0,e[0]] = 1;
        else:
            add_edges_to_queue(q, g, e[1], vertex_in_tree)
            vertex_in_tree[0,e[1]] = 1;
    else:
        T.delete_edge(e)
    if T.size() == (g.order() - 1):
        break
t_endP=cputime(subprocesses=true)-t_startP

print("Number of vertices=200, Number of edges= " +str(edges), "runtime Prims="+str(t_endP))
t_startk=cputime(subprocesses=true)
K=kruskal(g)
t_endk=cputime(subprocesses=true) -t_startk
print("Number of vertices=200, Number of edges= " +str(edges), "runtime ="+str(t_endk))

##200 vertices, .1 P, 1-100 edge weight

#1 Prims: .196s
#1 Kruskal: .008

#2 Prims: .164s
#2 Kruskal: .004s

#3 Prims: .168s
#3 Kruskal: .004

#4 Prims:.148s
#4 kruskal: .004

#5 Prims: .18
#5 Kruskal: .004

#6 Prims: .16
#6 Kruskal: .004

#7 Prims:.136
#7 Kruskal:.004

#8 Prims:.184
#8 Kruskal: .004

#9 Prims:.176
#9 Kruskal:.004

#10 Prims:.172
#10 kruskal: .004

##PART 4

#It appears that regardless of how dense or how sparse the graphs were, Kruskal's algorithm was consistently faster. I would attriubte this to a couple factors. First, Kruskal's algorithm, when done in class/on paper, is more efficient than Prim's. Additionally, the Sage incorporated code is probably more effeiciently written than our personally written code that we made for Prim's Algorithm.