Okay, so, while I'm assigning you a homework problem that's Dijkstra's shortest path algorithm. I'm going to show you the process of handling the is-connected problem, they're related. To some extent you could, in fact, uses Dijkstra's shortest path algorithm. And it's in one form to find whether a graph is-connected or not. But the simpler one should give you ideas about how to do the Dijkstra's algorithm. And this goes back to my own work. Back in 1968 when I was a research graduate student research assistant at the Stanford Linear Accelerator Center. And I was being asked to use this very new programming language called PL1, which is more or less out of favor now but still available. And the interesting thing about PL1 was, it was an attempt to get a universal programming language. PL1 was supposed to IBM's ability to having to do away with special purpose languages. And IBM was finding that it was, it wanted to be a hardware company, not a software company. It wanted to sell big machines, which generally filled up lots of space, and cost lots of money. And software was an, an irritating expense. So, the fact that they had to provide machine language comp compilers, macro preprocessors, COBOL compilers, FORTRAN compilers, sometimes Algol compilers. That was just a lot of different software they were supporting and they just felt, well, why can't we get a universal language, and that will simplify our tasks. And they tried. And the way they tried was unfortunately what I call, the kitchen sink approach. They took everything they had, in all these different languages, threw them all together There was a lot of redundancy in, in this language. You could do things in a COBOL manner or Fortran manner. There wasn't an obvious PL 1 manner to do things. And that's in a way why PL 1 didn't survive the object oriented revolution. Object orientation allows you to have a much simpler idea of what a kernel language is, in our case C. And, then expanded by letting the programmer add classes, whenever they needed, yet, a new domain. A new set of widgets to work with. Now, the algorithm I'm going to describe goes back to work that I did and was documented in some reports at SLAC. But later it was generalized in a very important way by Tarjan and Hopcroft, and it's a foundational algorithm called breadth-first search. And you can certainly read about that. So this is also a vital algorithm that you should be familiar with, Breadth First Search and you can find it in the Wikipedia. And what we're going to do in trying to find out whether a graph, is connected is we're going to start arbitrarily with some node. And since everything in C starts at zero, and we'll probably use the labeling system that says we'll have node zero up to node n minus onee or up to node size minus one. We will assume that node zero Think of our map before, San Francisco. If I'm sitting in San Francisco, I've reached San Francisco. So San Francisco is automatically connected to San Francisco. So we're going to have this initial set, and in that intital set we'll put the node zero. Then we will look from San Fransiciso and see where are the next, where are the adjacent cities we can reach. And this will be what I will call a closed set. And then waht I'm going to call an open set, I'm going to put nodes reachable from San Francisco. So if I could reach node three and node seven, those will be nodes in the open set. Now, what if there was no way out of San Francisco? maybe there's been a huge earthquake and all roads have been busted. What does that mean? It means the graph is disconnected. I can't get from San Francisco to San Diego. I could stop. So, if I have a closed set automatically with a starting node, and if there's no edges out, well, then the algorhythm will stop and report that the graph is not connected. However, if there are ways to get out of San Francisco, namely I can go to Los Angeles or San Jose, as was in that early map I showed you. Those nodes with their names would go into the open set. And then each time I would go to the open set and pick off a next node. Maybe in my algorithm, I pick the node with the lowest number. Take that node and drag it over. Place it in the closed set, and look again for what places I can go from node three. And maybe I can go to node four and node two. And they would become new entries in the open set. So, the open set would contain those that can be reached from what was put in the closed set with the provisio that I don't need to go back to something in the closed set. If there's another way to get back to San Francisco, that's not of interest. So the open set will only have, nodes that are not in the closed set. The calculation will stop, when one of two things happen. Either, (futer - was further -sic) and this is important Either I can't reach all the nodes, in which case, the open set is exhausted, and the closed set has yet to contain size n nodes, all the nodes in the map. So I'm not connected. Or all the nodes, the set of nodes, that are now in the closed set, are, in fact, there are size of them. And then we can stop and the graph is connected. So that's our algorithm. That's what we're going to implement. We go back and we have our matrix representation of the graph, we have it as a Boolean matrix's representation. We have the size of a graph and we are going to keep track of closed and open. And here is where open of zero is true. That's like saying San Francisco is originally in the open set and it"ll be the first, since it will be the only thing in the open set. It'll get automatically selected, placed in the closed set. So, at this point, the open set has node zero on it. It could work if any other node is placed in it, but there's nothing special about zero. To determine whether the graph is connected or not. Nothing is yet in the closed set, and each iteration will add one node to the closed set and possibly many nodes to the open set, or maybe not. The open set doesn't get added to. We're still going to the open set each time as long as there are entries in the open set, and we've yet not worked out whether the graph is connected. So add (to) the closed while the, I'm keeping track of C_size. This is size of the closed set. The old size is the C_size. We then place something in the closed set, meaning. One element is placed in the closed set, so we ought to increment it. The closed set has that element being true. And then, we go and look for things in the open set. And we got to put into the open set anything that's already in the open set that stays in the open set or anything that's newly reachable. Recall this is just our note this is true if an edge (i,j) in the graph and this just logical or. So, this is the logical or operation. So, open is true, if open is already true, or. There is now a new edge that previously couldn't reach j, but now reaches j. We are done if we have all the nodes in the closed set, or if no nodes are available in the open set. If all the here connected, we're connected. Here we're unconnected, and these are our termination cases. And keep in mind, how many iterations are we going to do? We're going to do no more iterations than size. because, in size, we either get a new node, or we fail. And if we fail, before then, we fail before size. And if we keep getting a new node, we get everything up to San Diego and we're finished so we only have to do this the size of the graph. So the fairly straight forward algorithm. Okay. So, I'm going to explain a lot more about Dijkstra's algorithm, how to implement it, how to do your homework and that'll be in our next lecture.
