# Author: Marshall Ossi Shires
# Date  : 24 SEP 2017

##### This worksheet contains three cells:
### Cell 1: Using Kruskal's Algorithm:
## Using the previously-defined random_weighted_graph function from ws4,
#   cell 1 uses Kruskal's Algorithm to calculate the weight of a minimum spanning weight of a random weighted graph in 20 vertices.
### Cell 2: Defining a function for Prim's Algorithm:
## Using the previously-defined random_weighted_graph function from ws4,
#   cell 2 defines a new function prim, which derives a minimum spanning tree using Prim's Algorithm,
#   and uses the output from prim to calculate the minimum spanning weight of a random weighted graph in 20 vertices.
### Cell 3: Comparison of output of Kruskal's and Prim's Algorithms:
## Using the same functions as the above two cells,
#   cell 3 calculates the weight of a minimum spanning tree of a random weighted graph in 20 vertices,
#   using both the user-defined prim function and the imported kruskal function, displaying the
#   random weighted graph, its minimum spanning trees as calculated by Prim's and Kruskal's Algorithms,
#   and the edges and total weight included in each. This cell shows that the two functions produce
#   the same weight for a given graph's minimum spanning tree.
### Cell 4: Comparison and analysis of functions implementing Kruskal's and Prim's Algorithms:
## Using the same functions as the above two cells,
#   cell 4 records the time taken to run the prim and kruskal functions
#   for random weighted graphs with different probabilities of adding an edge.
#   These results are displayed in a table.



###Cell 1: Using Kruskal's Algorithm:
##Using the previously-defined random_weighted_graph function from ws4,
#  cell 1 calculates the weight of a minimum spanning weight of a random weighted graph in 20 vertices.

from sage.graphs.spanning_tree import kruskal
import random;
load("graphFunctions.sage");

G = random_weighted_graph(20,.6,1,20);           #Calls the function with 15 vertices, 60% probability, and weights 1 to 20.
G.plot();                                        #Plots the generated graph.

E = kruskal(G);
print("Minimum Spanning Tree of the graph by Kruskal's Algorithm:\n" + str(E));
MST = G.subgraph(edges=E);
MST.show(edge_labels=true);

weightSum = 0;
for c in xrange(0, len(E)):
    weightSum = weightSum + E[c][2];
#end for loop

print("Minimum Spanning Tree Weight: " + str(weightSum));

###Cell 2: Implementation of Prim's Algorithm:
##Using the previously-defined random_weighted_graph function from ws4,
#  cell 2 defines a new function prim, which derives a minimum spanning tree using Prim's Algorithm,
#  and uses the output from prim to calculate the minimum spanning weight of a random weighted graph in 20 vertices.

import random;
import math;
load("graphFunctions.sage");

G = random_weighted_graph(20,.6,1,20);                  #Calls the function with 15 vertices, 60% probability, and weights 1 to 20.
G.plot();                                               #Plots the generated graph.

def prim(H):
    ###This function takes a weighted, connected graph as input, and returns, as a list of edges, its minimum spanning tree as derived by Prim's Algorithm.
    ##Input:
    #H = A weighted, connected graph.
    ##Output:
    #treeEdges = A list of the edges included in the minimum spanning tree.
    ##Example: Let H = Graph([(0,1,5),(1,2,1),(2,0,1)]). prim(H) will return [(2,0,1),(1,2,1)].
    #Note that the number of edges returned will always be equal to H.vertices() - 1, since this is a spanning tree.

    E = H.edges();                                          #Get the edges in a numEdges by 3 list E.
    V = H.vertices();                                       #Get the vertices in list V.
    treeVerts = [0]*len(V);                                 #All vertices will eventuall be in the tree, but at this time the tree is empty.
    treeVerts[0] = 1;                                       #Start the minimum spanning tree at vertex 0.
    treeEdges = [(0,0,0)]*(len(V) - 1);                     #The minimum spanning tree with have len(V) - 1 edges.

    lowEdge = -1;                                           #Initialize edge to be added
    lowEdgeWeight = oo;                                     #Initialize weight at infinity such that any edge weight will be less than the initial lowEdgeWeight

    for e in xrange(0, len(treeEdges)):                     #For each edge in the minimum spanning tree, which will have len(V) - 1 edges,
        for v in xrange(0, len(V)):                         #Examine each vertex
            if(treeVerts[v] == 1):                          #If the vertex v is in the minimum spanning tree,
                for edge in xrange(0,G.size()):             #Examine each edge on the graph,
                    if((E[edge][0] == v or E[edge][1] == v) \
                       and (treeVerts[E[edge][0]] !=        \#and if the edge is incident on vertex v, and both vertices it is incident on
                            treeVerts[E[edge][1]])):        #  are not already in the tree, such as to avoid repeats or cycles, then
                        if(E[edge][2] < lowEdgeWeight):     #Check if its weight is less than lowEdgeWeight, and
                            lowEdge = edge;                 #If so, set this edge as the lowEdge,
                            lowEdgeWeight = E[edge][2];     #And set the lowEdgeWeight to the weight of this edge.
                        #end if(E[edge][2] < lowEdge)
                    #end if(E[edge][0] ... == v)
                #end for loop edge
            #end if(treeVerts[v] == 1)
        #end for loop v

        if(lowEdge != -1):                                  #Checks that an edge was found
            treeVerts[E[lowEdge][0]] = 1;                   #Includes both vertices incident on the lowEdge
            treeVerts[E[lowEdge][1]] = 1;                   # in the vertices of the minimum spanning tree
            treeEdges[e] = E[lowEdge];                      #Includes the edge lowEdge in the minimum spanning tree
        lowEdge = -1;                                       #Resets lowEdge and lowEdgeWeight to prepare for
        lowEdgeWeight = oo;                                 #  the next edge to be added to the minimum spanning tree.
    #end for loop e

    return treeEdges;
#end function definition

E = prim(G);
E
MST = G.subgraph(edges=E);
MST.show(edge_labels=true);

weightSum = 0;
for c in xrange(0, len(E)):
    weightSum = weightSum + E[c][2];
#end for loop
print("Minimum Spanning Tree Weight via Prim's Algorithm: " + str(weightSum));

###Cell 3: Comparison of output of Kruskal's and Prim's Algorithms:
##Using the same functions as the above two cells,
#  cell 3 calculates the weight of a minimum spanning tree of a random weighted graph in 20 vertices,
#  using both the user-defined prim function and the imported kruskal function, displaying the
#  random weighted graph, its minimum spanning trees as calculated by Prim's and Kruskal's Algorithms,
#  and the edges and total weight included in each. This cell shows that the two functions produce
#  the same weight for a given graph's minimum spanning tree.

import random;
import math;
from sage.graphs.spanning_tree import kruskal
load("graphFunctions.sage");

G = random_weighted_graph(50,.9,1,200);      #Calls the function with 15 vertices, 60% probability, and weights 1 to 20.
G.plot();                                    #Plots the generated graph.


Eprim = prim(G);
print("Minimum Spanning Tree via Prim's Algorithm:\n" + str(Eprim));
MSTp = G.subgraph(edges=Eprim);
MSTp.show(edge_labels=true);


weightSumPrim = 0;
for c in xrange(0, len(Eprim)):
    weightSumPrim = weightSumPrim + Eprim[c][2];
#end for loop
print("Minimum Spanning Tree Weight via Prim's Algorithm:\n" + str(weightSumPrim) + "\n\n\n\n\n\n\n");







Ekru = kruskal(G);
print("Minimum Spanning Tree via Kruskal's Algorithm:\n" + str(Ekru));
MSTk = G.subgraph(edges=Ekru);
MSTk.show(edge_labels=true);

weightSumKruskal = 0;
for c in xrange(0, len(Ekru)):
    weightSumKruskal = weightSumKruskal + Ekru[c][2];
#end for loop

print("Minimum Spanning Tree Weight via Kruskal's Algorithm:\n" + str(weightSumKruskal) + "\n\n");

###Cell 4: Comparison and analysis of Kruskal's and Prim's Algorithms:
##Using the same functions as the above two cells,
#  cell 4 records the time taken to run the prim and kruskal functions
#  for random weighted graphs with different probabilities of adding an edge.
#  These results are displayed in a table.

import random;
import math;
from sage.graphs.spanning_tree import kruskal
load("graphFunctions.sage");

num = 20;                                         #Will create num rows in output table, with probability of adding an edge from 1/10 to 1.
numRange = range(1,num+1);                        #Creates a range for use in the for loop from 1 to num+1.
vertexNum = 100;                                  #Each random weighted graph will have vertexNum number of vertices.
weightLim = [1,100]                               #Each edge in the random weighted graph will have a weight from weightLim[0] to weightLim[1].
probs = [None for x in range(num)];               #Initializes empty arrays of size num to store probabilities,
runtimesP = [None for x in range(num)];           #runtimes of Prim's Algorithm,
runtimesK = [None for x in range(num)];           #runtimes of Kruskal's Algorithm,
edgeNum = [None for x in range(num)];             #and the number of edges for the random weighted graph.

for c in numRange:                                #Iterates num times.
    #Creates a random weighted graph with vertexNum vertices, c/num probability of adding and edge, and edge weight distributed from weightLim[0] to weightLim[1].
    G = random_weighted_graph(vertexNum,c/num,weightLim[0],weightLim[1]);
    probs[c-1] = c/num;                           #Records the probability of adding an edge for this iteration through the for loop.
    edgeNum[c-1] = len(G.edges());                #Records the number of edges in the random weighted graph for this iteration through the for loop.

    t0 = cputime();                               #Notes time before Prim's Algorithm is run on graph G.
    O = prim(G);                                  #Runs Prim's Algorithm. O is not used, and exists merely to supress the output of prim(G).
    tf = cputime();                               #Notes time after Prim's Algorithm is run on graph G.
    runtimesP[c-1] = tf-t0;                       #Records the time taken to run Prim's Algorithm as the difference in time before and after it is run.

    t0 = cputime();                               #Notes time before Kruskal's Algorithm is run on graph G.
    O = kruskal(G);                               #Runs Kruskal's Algorithm. O is not used, and exists merely to supress the output of kruskal(G).
    tf = cputime();                               #Notes time after Kruskal's Algorithm is run on graph G.
    runtimesK[c-1] = tf-t0;                       #Records the time taken to run Kruskal's Algorithm as the difference in time before and after it is run.
#end for loop


#Creates a table with the resultant runtimes of random weighted graphs with the edgeNum number of edges as a result of probs probability of adding an edge.
Table1 = table(columns=[probs,edgeNum,runtimesP,runtimesK], header_row=["p", "Edges in Graph", "runtime, Prim's", "runtime, Kruskal's"], frame=True);
Table1

print("As evidenced by the table, as the number of edges in a graph increases, the runtime of my created function for Prim's Algorithm increases drastically, while the impact on the kruskal function is negligible.");