So, before we can develop code for our implementations we need to settle on an

API for edge weighted graphs. Now this actually needs a bit of

discussion. It would seem to be simple to add weights.

But there's a few technicalities that it's easy to understand.

But it's going to take a little explanation.

So, the whole idea is that we need an edge abstraction.

Before for directed graphs, undirected graphs, we're talking about graphs in

terms of connections, and the edges were really implicit.

So, for a vertex, we would keep a bag of vertices that its connected to but we

wouldn't explicitly represent edges. For weighted edges, we're going to need to

do that. So we're going to start out with an the

just for processing edges. Now, it's simple. The constructor is just

going to create an edge. So, what is an edge?

A weighted edge is two vertices that they connect, that, it connects and then a

double value, which is the weight. So that's clearly one thing we have to do

is, is construct the edge. Now what do we want to do when we process

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

Edge-Weighted Graph API

Algorithms, Part II

Meet the Instructors