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
edges? Well, one thing we want to do is compare
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.