1:35

two edges, so that is, we want to compare the weights in, in a typical compare and

Â return a negative value of less than zero if equal and a positive value of one just

Â like any other compare. So we have one the method that takes an

Â edge as argument and compares that edge to this edge for sure.

Â We want to be able to extract the weight and have a string representation of the

Â edge. But then, what about getting the vertices

Â out of the edge? Well, the fact is that the, usually in

Â the, in the algorithm, we're holding on, to a vertex.

Â And generally, what we want to do is get the other vertex.

Â So, if we have a vertex v that we're holding on to, what we want is the other

Â vertex. So well that's the way that will get the

Â vertex to that a given edge. We're on a vertex and we have an edge we

Â want to get the edge that, that, the vertex that, that connects to,

Â We just call the other method. And if we have an idiom, we're just

Â getting started then, then we are happy to take either vertex.

Â So we have either and other for getting the vertices out of the edges and we

Â almost always do this kind of idiom where we pick out and we, we have an edge e that

Â we have to process. We pick out either edge, and we put that

Â in v, And we pick out the other edge, and put

Â that in w. So that's just a, a code for getting us

Â the v and w without adopting some convention on how to use those names that

Â might be required if you tried to access the instance variables directly or through

Â gutter methods. So, that's the edge API.

Â So it's easy to implement. So, now we're going to have instance

Â variables for v and w in the weight. The constructor just sets those instance

Â variables. Either just returns v arbitrarily ag, then

Â other, given a vertex that vertex is v, V or returns w, otherwise, it turns v, so

Â that's easy. And then, compared to is straightforward,

Â just using the weight instance variable of this, which is the keyword referring to

Â this object and that which is the argument edge that we're given.

Â So, that's a complete implementation of the weighted edge API and now our MST

Â algorithms can be clients of that. So well first, first we need a graph API

Â that has weighted edges. So we're going to use edge-weighted graph.

Â And it's going to have the same characteristics of the graph and

Â undirected graph API that we articulated before.

Â So we're going to create empty graph with a certain number of vertices and we do

Â that so we can use vertex index arrays as internal data structures.

Â We'll have a created a weighted graph from an input stream then the main operation to

Â build graphs is just to add edges. And then the key operation that all the

Â algorithms want to perform as usual is uniterable but give all the edges adjacent

Â to a given vertex. So now, we want the edges themselves cuz

Â they have the weights. Not just the vertex that it's connected

Â to. So, this, with the edge API, the edge

Â abstraction we get the edge, which gives us the weight and the other vertex at the

Â same time. Since we're using edges as distinct

Â entities it's easy to allow self loops in parallel edges in the graph API and it

Â doesn't have any impact on the MST algorithms.

Â So, we'll go ahead and do that. How do we represent edge-weighted graphs?

Â I, well, it's the straightforward extension of what we did for undirected

Â graphs. We're going to maintain a vertex index

Â array of edge lists. So for every vertex we have a list of the

Â edges connected to that vertex. For example in this graph weighted graph,

Â there is an edge the ones connected to vertex zero, or an edge that connects and

Â six and zero and has a weight 0.58 and an edge that connects two and zero and has

Â 0.26, zero and four has 0.38, zero and seven has 0.16. As with our undirected

Â graph representations each edge object is going to appear twice.

Â Once for each vertex that it connects. And it's actually not an object, it's a

Â reference to an object in Java. So, a graph is a vertex index array of

Â bags of edges. Since it's undirected each edge is going

Â to appear twice. So, when we build a graph just as with

Â undirected unweighted graphs we have to add,, If, if we have an edge that connects

Â v and w we have to add that edge to both v and w's adjacency list.

Â Otherwise it's quite similar to R code for graph.

Â We have a bag of edges instead of a bag of integers, which were vertex indices.

Â Constructor builds the bag. And builds the array and then fills the

Â bag associated, associated with each vertex as a new empty bag.

Â And then add, add edge, adds the edge to both v and w's bag.

Â And interval just returns the bag associated with the given vertex and

Â that's all the edges that are incident on that vertex.

Â And that's a bag which is interval. So, again, as for all the algorithms that

Â we've been looking at, the clients will just iterate.

Â Usually, you have a vertex, and it'll iterate through the edges adjacent to that

Â vertex. So that's the representation of the graph.

Â What about representing the MST? Well, usually the client of an MST

Â algorithm is going to want to have us compute the MST for a given edge-weighted

Â graph. So, we'll just do that in a class named

Â MST and make that the constructor. So then, as usual, in our graph processing

Â paradigm, the constructor will do all the work.

Â And then the client can ask queries about what happened.

Â And in this case, what's relevant is, what are the edges in the MST?

Â And the MST client is just going to want to iterate through those edges.

Â It might also want the total weight of the MST, so we can provide that, too.

Â So for example if we take a, an example with our tiny edge-weighted graph,

Â We're going to have the number of vertices, the number of edges and then, a

Â list of vertex pairs, which are the edge connections and the associated weights.

Â Ahm the what we'll want is the this is the test client is just going to print the

Â edges in the MST the middle-weight edges that connect them all instead the edges on

Â MST and the weight. And this is the code for that test client.

Â So we build an input stream which is given the argument, so that's the filename. and

Â then, we use the constructor from the stream to build an edge-weighted graph.

Â Then we do an MST calling the MST constructor with that graph is an argument

Â that creates an MST. And then, we use the iterator.

Â That mst.edges will give us some interval set of the edges that are in the MST that

Â it computed in the constructor. And it will print out the edges using

Â two-string for edge and then print out the weight.

Â So that's the code that gives the test client for this MST API.

Â So, for that graph, we get that output with that code.

Â So, that's a, the quick introduction to the API, APIs we use for MSTs.

Â