0:00

[MUSIC]

Â Okay so we've got the abstract class spelled out in terms of what methods our

Â graphs ought to be able to implement, and now let's think about how we would

Â actually go ahead and implement some of those methods.

Â So, in this video, you'll be able to see how to do at least one implementation

Â using something called an adjacency matrix.

Â So, let's think back to an example of a graph that we've been

Â going back to a little bit in this sequence of videos.

Â And so, this is a small example.

Â Most of the real world examples that you think about will have many,

Â many, many more nodes and many, many, many more edges.

Â Especially when you're thinking of the applications we care about.

Â For example, in the project where the nodes are representing cities or

Â 0:45

intersections of roads, and

Â then we have the edges indicate ways of getting from one place to the other.

Â So, think about the number of cities in the world or

Â the number of roads in the world and you start getting to really big graphs.

Â But when we're doing the definitions, it's good to have a toy example of just

Â a few vertices, a few edges, so we can see how the definitions play out.

Â And then, afterwards we'll scale up to the realistic problems.

Â So with this example, we just have six vertices with some edges between them.

Â And we could label the vertices one through six.

Â Could use these labels of vertices to index into some array structures, and so

Â if we think about representing the relationships between these vertices, so

Â we can think of a grid.

Â So this grid would be indexed by the labels of these vertices.

Â And what we'd like to do is store information in a particular grid location

Â based on whether these two vertices do or don't have an edge between them.

Â So for example, if we think about the vertex labeled 1 and the vertex labeled 2.

Â In this graph there's no edge between them, and so

Â we'd like to store that information and so in this grid representation we're going to

Â say there's no edge and represent that with a 0.

Â Now there are some edges in the graph that we're trying to represent, and so for

Â example if we look at the vertex of 0, it's adjacent to the vertex 1,

Â namely there's an edge that starts at 0 and goes to 1.

Â And so we'd like to record that, and we're going to record that with a 1.

Â Now notice that at this point, we've got 0 and

Â 1 as the entries that we've used in this grid.

Â It's possible to have bigger integers and

Â that might indicate multiple edges from one vertex to another.

Â 2:25

Now notice that in this graph there's an edge that goes from zero to one.

Â But there isn't an edge that goes from one to zero.

Â And so in the symmetric location in the grid with row one and

Â column zero we put a zero.

Â If we were thinking about representing an undirected graph as a matrix, using

Â these zeros and ones to indicate whether the pairs of vertices are related or not.

Â Then in those undirected graphs, this grid would by symmetric.

Â Namely, if we tried to imagine flipping it across the diagonal, then

Â we'd get the result of the flip would look exactly the same as the original matrix.

Â So with undirected graphs we get more structure in this adjacency matrix.

Â But for directed graphs we need to think about every single grid point

Â on its own independently.

Â So if we want to fill in the rest of this adjacency matrix, and

Â matrix here just means 2D array, then we notice that we are going to get a one for

Â every single edge in the graph.

Â And there's one, two, three, four, five edges,we see one, two, three, four,

Â five 1s in the array.

Â And the rest of the entries, well, they're just 0s, because the rest of those entires

Â indicate pairs of vertices that happen not to be adjacent in this graph.

Â And so we indicate that in the adjacency matrix by putting a 0 in each of

Â those locations.

Â 3:56

But really our computers, we know, don't really get as input this grid of 0s and

Â 1s, we still wanna translate how we're doing this representation to Java.

Â And so let's think back about the class structure that we have to write

Â in order to represent the graphs.

Â And from the previous video, we saw we've already set up an abstract class and

Â now we'd like to defined a sub class of it that's going to

Â implement those abstract methods.

Â So in our new class, graph adjacency matrix, so GraphAdjMatrix,

Â we're going to extend that abstract class we started with.

Â And the new piece, the new field, that we're going to define for

Â objects that are of type graph adjacency matrix are these adjacency matrix

Â that are going to be 2D arrays of integers.

Â And so what we'd like to do now is implement those add vertices,

Â and add edge, and get neighbors methods using this idea that

Â the relationships in the graph are encapsulated in this matrix.

Â So let's think about how to do at least one of these methods to start, and

Â let's think about implementing adding an edge.

Â 5:01

And so if we're adding an edge from a vertex v to a vertex w and

Â each of these vertices is encoded by an integer.

Â Then really what we're doing is setting that location in the matrix to say,

Â yes, there's an edge between my two vertices.

Â So in row v and column w, there ought to be a 1.

Â Now, notice here, we're saying this flag is set to one, which

Â means that we're not going to take into account multiple edges between vertices.

Â We're going to say that if we are adding an edge between two vertices,

Â we're going to assume that there wasn't an edge there before, or

Â if there was an edge, we're not going to double count that edge at all.

Â We're just going to say, if there's an edge, it's going to be set to one.

Â All right, that wasn't too bad.

Â So what about some of the other functionality that we

Â wanted in our graphs?

Â So in particular, how do we add a vertex to the graph?

Â 5:56

So think about how vertices are represented in this graph, and

Â we don't have a dedicated data structure that tells us about all the vertices.

Â The way that we have access to the vertices is as the row labels and

Â the column labels of the adjacency matrix.

Â So if we want to add another vertex what we need to do is add another row and

Â add another column to correspond to that new vertex.

Â But that means increasing the dimensions of this adjacency matrix, and so

Â that's a little bit tricky.

Â Now what we want to do is we want to say okay, so

Â if the vertex that we need to add has to really increase the size of

Â our adjacency matrix, then we're going to plan ahead.

Â And we're not going to change this adjacency matrix just by adding one

Â row and one column at a time, but we are going to say if we are adding one vertex,

Â then maybe we'll need to add more vertices later.

Â And so we are going to make our new adjacency matrix much bigger.

Â So in particular we're going to double the number of vertices,

Â double the number of columns and that way at least for a while, while we're

Â adding more vertices we won't have to increase the size of our array each time.

Â Because if you remember when we want to increase the size of our array we can't

Â just take our old array and fiddle around with it.

Â What we need to do is create a new array of the new size and

Â then copy over all the contents from the older rate to the newer rate.

Â That takes a bunch of time, and so we don't want to have to do that too often.

Â And, so our idea is going to be to add a vertex.

Â We're going to if we need to change the size of the array at all,

Â we're gonna change it by a lot.

Â Double the size, so double the number of rows, double the number of columns.

Â And then copy over all of the values from the old adjacency matrix to the new

Â adjacency matrix.

Â 7:53

So we saw that adding an edge was really very quick.

Â Adding a vertex had to be done with a little bit more care.

Â And we can think of a filling in the rest of this class definition.

Â We need to, of course,

Â define a constructor which is going to initialize our adjacency matrix.

Â And we're going to fill in some of the other methods as well.

Â Now in particular, when we're talking about graphs, a useful method

Â to keep in mind is to think about whether two vertices are in fact

Â neighbors of one another, it there's an edge that goes from one vertex to another.

Â So thinking about this implementation of the graph where we have

Â our edge relationship defined through this adjacency matrix.

Â How long will it take, to test whether there's an edge between one vertex and

Â another?

Â 8:39

Okay, so let's come back and think about how to finish off this adjacency matrix

Â representation of the graph.

Â And in particular,

Â let's reflect on what properties we've seen as we've built up this class.

Â So you'll write up some of these other methods as part of the project,

Â and also we'll guide you through some of them in the support videos.

Â But as you're writing these methods, you want to think about

Â the performance implications of the data structure that we've chosen.

Â So we've chosen a data structure that is very algebraic.

Â A 2D array,

Â which we can think of abstractly as a matrix that we can do linear algebra on.

Â And so it turns out that once we represent a graph as this algebraic

Â representation, then the linear algebra tools are very powerful.

Â And you'll see one example of that in a later video.

Â But as you go on and think about more graph algorithms and more applications of

Â graphs, you see linear algebra coming in again, and again, and again.

Â And so, thinking of the adjacency matrix as a crucial representation of the graph

Â is indeed very powerful.

Â But it does have a lot of drawbacks.

Â Because even though it was really fast for us to implement the test for

Â edges method as you saw in the video quiz.

Â And even though it's really fast to add and

Â remove edges because we're just dealing with a single entry in the 2D array.

Â If we want to change the big structure,

Â the underlying structure of the graph by adding vertices, that took a lot of time.

Â And the most important piece that is a drawback for the adjacency matrix is that

Â when we think about this storage that's required an adjacency matrix, we need to

Â store a 2D array, whose dimensions, are the number of the vertices.

Â So that means, that we're storing

Â n squared pieces of information if n is the number of vertices.

Â And that can get really, really big.

Â So think back to what these vertices represent.

Â These vertices are cities, or they're intersections, or in biological

Â representations, they might be genomes or they might be little pieces of genomes.

Â Or if you think back to the World Wide Web analysis,

Â then each of these vertices is a unique URL, unique website.

Â Or if you're thinking about social networks,

Â then each of these vertices is a person.

Â And in all of these, think in all of these applications, the set of vertices is huge.

Â Not only is the set of vertices huge, most vertices are not related to one another.

Â So most people are not friends with most other people in this world.

Â Our communities don't encompass the whole globe, don't encompass the whole world.

Â Similarly, most cities don't have

Â 11:24

nonstop flights to all other cities or to many, many other cities in the world.

Â Usually we have to think about going out gradually and doing

Â lots of shorter flights in order to get from one place in the world to another.

Â And so, even though when we have a lot of vertices there's a lot of potential edges,

Â there's a lot of potential relationships,

Â many of those edges just aren't in the graph.

Â Whereas storing the adjacency matrix of a graph

Â requires us to store information about every single pair of vertices.

Â And that can take up a huge amount of space.

Â And so if space is a concern, if we're trying to depict a big graph,

Â then often adjacency matrices are prohibitively big.

Â We can't store the whole adjacency matrix.

Â And so, we're going to think about another implementation

Â of the edge relation description of the graph

Â that will lend itself better in many practical applications.

Â