So, part of what the course is going to give you expertise in is algorithmic graph theory, because it's a very, very good subject, because graphs themselves are widgets, complicated widgets. That have very different representations in many ways to try and implement and get efficient for particular different instances. And so, we can see a lot of the old ideas and a lot of the uses of C++ effectively. When we try to implement these algorithms in C++. But also it gives you some background in doing further and more complicated programs as this course (...) progresses. And one of the classical algorithms in computational, graph theory was invented by the very famous Dutch mathematician and computer scientist Edsger Dijkstra. So we're going to see how to use Dijkstra's algorithm and your homework is going to be to implement Dijkstra's algorithm and use it on a randomly generated graph, which you'll also have to implement. We'll also show you how to do a very similar but simpler problem based on an algorithm that I invented many, many years ago. Originally I implemented it in a much earlier programming language call PL-1. And it's the problem of finding out whether a graph is a simple connected component graph. And we're also going to add some drawing lessons. We're going to be drawing graphs as we go through and simulate these algorithms. So this is the set of ideas we're going to need, to do the remaining homework. in this class. So here's an unconnected graph and that unconnected graph is a graph of seven nodes. We might label these nodes 0, 1, 2, 3, 4, 5, 6. That would be traditional C labelling, namely we start from zero. We might label these nodes, A, B, C, D. You'll see all these labellings in the graph literature or might see them as nodes on graph, maybe this is San Francisco. And this is Los Angeles. All of these are possible. So I'm unconnected because we can't go from any node to any other node. There's, we don't see any path. Between, in this unconnected graph, between San Fransisco and Los Angeles. We just see nodes. Now, here's what we're going to show as a connected graph. So I have left the same labelling and now I'm going to add what are called edges. So these blue lines are what we call as edges. The little circles are nodes. The little blue lines are edges. When you think of edges, think of roads. So here's a road from San Francisco, going to Los Angeles. For us who are Californians, that might be 101. here's another road, from San Francisco to D. Maybe D is San Jose. Maybe this is San Diego. So again, you have familiarity in the, in the ordinary world with graphs. They're basically just road maps. And they're road maps in which the cities are nodes and the highways are edges. Now, I'll draw a few more edges. If you looked at this connected graph. The reason it's connected, is, I can find a path between any 2 of the cities. And 2 of these nodes. Or, another term for nodes is vertices. So if I want a path from San Francisco to San Diego, I'll use this little wiggly line and show you here. Oh, there's a path. So that whole graph is connected and indeed a single component. Now, how can I get a computer to draw a graph? Drawing a graph by computer is actually fairly efficient and the critical thing will be to generate using a representation for the graph, an internal representation a number of vertices, so we'll have to decide on the size of the graph. And then we'll have to decide what edges will be placed in the graph. And this particular algorithm I'm going to show you, that'll generate a randomly generated graph. We'll use the heap and create a two-dimensional representation of the graph. So let's see what that means. The overall graph is going to be a pointer That ultimately stores boolean values. What are boolean values? They're the values true or false. If I have a graph that has edges, let's say they were like What we just saw, zero to 6. And I have true in one of the matrix entries. So let's say, in element 3, 4, I've stored true. This is going to mean that the edge from vertex three to four exists. That's what's being created by this little routine. The way it's created is, I seed the random number generator, I hope this is all review, otherwise you'll have to review how a pseudo-random number generator works. I create a graph, in this case, of the appropriate size. It's a graph that is, has seven nodes. And then, for each node, I have to have a row, a Boolean row. So these are the rows. That's what's being created here. And then these are all capable of storing a Boolean value. So the heap has allocated off the heap, through this for loop I've created a two-dimensional array. Whose base pointer is graph. And now, I put edges in. And I'm going to put edges in according to a density. What do I mean by a density? The density is the probability an edge exists. So that could be 0, or it could be up to 1. That's what dense, the range of densities are. 0 would mean, that I'm never going to put (an edge in). If, if this had been 0, no probability would be greater than 0, less than 0. And so I'd never put in an edge. This is the act of putting an edge in. 0 would lead to no edges. One would lead to every edge, the term here is complete. A graph that has all its' edges, all its possible edges, is called complete. So, we have a for loop . The for loop marches through the 2 dimensional graph, if i equals j that means if its on the diagonal we automatically put in false. Otherwise and this is symmetric this turns out to be the undirected graph. If the probability, in our case, we're looking at a density of point one nine. So, roughly, one in five times I'm going to stick an edge in. And, probability is just some function I'm computing using the random number generator you may have to review that, or you may have to look at the code that's online for the probability function. That will generate a randomly generated graph of the given density. So, here's a few questions. Density is zero. The graph has no, what? Density is 1, the graph is what? The C word. The density is fixed, say, to some size and the graph gets larger. What can we say about it? Likely it, how likely it is to be connected. Take a second to look at that. Okay. As we just said already, zero means the calculation says, no chance. You're never going to stick in an edge. One means you're always going to stick an edge in. So it's going to be a complete graph. And now, if the density is 0.1 and we have a, a size that grows. So let's say we have five nodes, density is one. 0.1 I should say. 0.1. That means one tenth of the time in a five node graph, we're going to stick an edge. Well, that's not going to happen often. Five nodes, that means roughly speaking we're going to throw in an edge 50% of the time for that particular node. Well, that's not going to be connected, so it's very unlikely. Let's say we go to a 50,000 node graph whose density is 0.1. So if you're following me, the 50,000 node graph and we have lots of 50,000 node graphs in the real world. Just think of the map of all the cities in the United States. And if you're thinking about the map of all the cities in the United States. How many roads are there out of an individual city? Maybe there's 20 rows out of an individual city, that might even be a big city. So a density of 0.1 on a big map is not all that, this would mean, 0.1 would mean that on average, we're going to get 5,000 edges per node. Here it was an average one half edge per node. When half edge per node for a small graph, it's going to leave us unconnected. 5,000 edges out of a 50,000 node graph is going to leave us with a humongous number of paths in that graph and it's very likely that, almost certainly, with probability approaching 1, going to be connected. So if you have a good intuition, about what we've been talking about with these randomly generated graphs and this is going to come up in the homework I'm assigning you, as the graphs get larger, namely the number of vertices, the number of nodes in the graphs get larger. Having a particular density makes it more and more likely that there are paths between all the nodes.
