[MUSIC] So we're on a new topic. Everybody should've completed the Dijkstra's Algorithm which was our second assignment and really our first major assignment. so you should have a fair familiarity without how to process graphs. The notion of turning a graph into a class structure, an abstract data type, to getting a lot of benefit from using graphs which are very, very useful throughout algorithms computer science study, and again, hopefully for most of you, all of this is review, so we're using material you should've already learned. and isn't novel, but if it isn't review or you've forgot a lot of it. There're excellent articles especially on the Wikipedia on all these algorithms on the basic graph theory including the algorithmic graph theory behind things like Dijkstra's algorithm. Today's algorithm, which we're going to talk about and will be the basis for the next homework assignment. So it builds on Dijkstra, so in some sense, it should be easier because now you've, you've you're past the jitters. You've gotten your, your programming legs in terms of this complicated aggregate, and you're just going to add a new algorithm. And the whole course is structured to build algorithm by algorithm. Towards the end of the course, we're hoping you're going to all be able to implement this very interesting game, hex, which can also be represented largely as a graph. So, today the main topic is minimum spanning trees, basis for homework three, and we're also going to study again, object orientation. How important object orientation is. When we use a language, like C++, what are the ideas, we bring to the table, to do good C++ programming? C++ is way more than an object-oriented language. It's got multiple tools in its, in its bag and it has the ability to do generic programming and it has the ability actually, to do functional programming in terms of C++ 11. So it's multi-paradigmatic, C++ is multi-paradigmatic. But, a really great strength. And the thing that has it replacing C was the shift from ordinary imperative programming that was C. To encapsulation-based on the object-oriented paradigm. And we'll see that with, a very simple but, very useful example called class point. So, homework three. You've already built the graph abstract data type. you hopefully got the Dijkstra algorithm to work. You got it to work on automatically generated, graph based on densities and size. You computed an average length in such a graph. Saw how all of that could work. And we're going to add this next major algorithm, again extremely useful. Minimum spanning tree comes up. In many, many areas in computer science and electrical engineering. In some sense it's maybe at the heart of the Internet, the way the Internet works, one wants to have a minimum spanning tree so that from particular foci you can get your messages, packets whatever out to arbitrary other foci. Minimum spanning tree, a definition. So again, we're going to have a graph in which an edge has some arbitrary positive cost, an edge. So we might have an edge from a to b. With, let's say, cost seven. And we have a whole graph built of edges with costs. First off, we have to know what a spanning tree is. A spanning tree is just a set of edges, that in effect is a tree. Remember we, in computer science frequently use things called, binary trees. Binary trees would be spanning trees of graphs if the graph had inside it, a binary tree. So a spanning tree is a set of edges within the graph that connects all the nodes of the graph, and where there is no cycles. So an immediate implication of that is if we have a graph of n-nodes, a spanning tree is a tree with n minus 1 edges. Now, I'm also going to, in this homework problem, assume that edges in the spanning tree can have different colors. It's going to make it a little more sophisticated and it'll add to some of the ideas in how you learn C++ programming. It'll enable you to use, an enum type, or a class enum type. that, class enum type is yet another novel idea in C++ 11. So if you have a C++11 compiler we may talk a little bit about a class enum type, as opposed to the earlier, pure enum type, which remains. and so we can assume that an edge can be red. There can be red edges. There can be blue edges. There can be green edges. And we might, when we specify our minimum spanning tree problem, decide on well do we want a minimum spanning tree in which all the edges are green? Green and MST? Or maybe we would have blue and red and MST. So for the same graph in which they were colors, we could have multiple answers to the minimum spanning trees. So as they say, it just makes the problem a little bit non-standard, not as easy to copy the code off the internet, adds a little flavor to it. And actually it'll be a flavor that will be useful in many later and more complicated venues. So first let's take a little quiz. If we have a enumerated type, here's a simple enumerated type, color. This is different than as I say C++ 11 will have a class enumerated type. Why were the colors capitalized? The enumerators have internal values, in this case what would be the value of green? And if we wanted, and this is a new type. So again, object orientation is all about adding types to the basic native types in a way that, is compatible with the basic native types, and fulfills the expectation of the C++ community. And the expectation in the C++ community is that the IO, the, what you might call pseudo-operators, the, the operators adopted to in this case, the bit shift operators. Adapted so that they do IO. can be overloaded. How would we overload to print red? So take a few minutes and see how you'd answer those questions. Well, first off, the reason that we use capital is just a community convention. So whenever we have things that we think of as constants. This even goes back to the old C style where when we didn't have a enumerators, we just did this using macros. So the minute we see in our C code some big cap, all caps identifier, we think that must be some kind of standard constant. In this case, the values go sequentially 0, 1, and 2, so green ends up two, and then if we were to implement the code for overloading the operator, recall that it has a certain idiomatic format. We're always going to call by reference,this complex construct, the ostream. We call the new type that we want to overload. And then we're going to return. What do we return here? Everybody should know that should be return of out. Why is that again? So that we could properly use C out, something. And that in effect, these are expressions that evaluate to the same ostream so that you can use that output repeatedly. Here's some new novel stuff fresh from the new standard. They are what we call strongly typed enumerators, enum classes. We're going to see why we need them. Let's say in the old style I could've had enum color. And enum traffic. And then I'd have two specific uses of red as enumerators. And they can actually get confused because they weren't strongly typed. In essence, some kind of integer and they would be comparable if I wanted to. However, when I turn them into this newly, strongly typed enum, and that happens by, instead of just calling an enum, I'm calling them enum class, so it looks somewhat the same. Except now I have class. Now, the two enumerators are distinct. They're not comparable. They're not. They have type distinction. Since they have type distinction. They're much safer in code. We can't get into trouble with conversion opportunities for example.
