0:07

In this lecture, we'll implement a graph.

And C sharp does not provide a graph class to you.

So, if you need a graph,

you need to implement one yourself.

We'll start by looking at the class for a graph node.

Lots of people call these vertices or the singular would be vertex,

a vertex in the graph,

but I'm going to pretty consistently use the terminology node in the graph.

It's a generic, so we can store any data type in the graph nodes,

and it has two fields.

It has a value and it has a list of

the other graph nodes that are neighbors of this graph node.

So, that means that this graph node is connected to its neighbors with edges.

The constructor simply sets the value of the node and creates an empty list of neighbors,

because a new graph node doesn't have any edges connecting it to anything else yet.

We can get the value of the node and we can get the list of neighbors,

but here's something new.

We don't actually just want to return the list of neighbors

to somebody because they could to then modify

the contents of that list by adding and removing elements from

the list and that would change the neighbors for this particular graph node.

If somebody wants to change the neighbors for this graph node,

we want them to use the methods for our data type here,

rather than manipulating the list.

So, we want to return a read-only list of the neighbors of the node.

Now, we can do that by just making a new copy of the list and returning it,

but we can also do it the way shown here.

So, we can return neighbors as

read-only and you'll notice that the return type here is not a list,

it's I list, it's an interface to a list.

And an I list actually does not contain the methods to modify the contents of the list.

You can still lock the list and do all kinds of things with the list but

you can't add and remove things from the list.

So, this is the way that we return

a read-only list of neighbors to whoever wants that list.

Before adding a neighbor,

we check to make sure we don't already have an edge to that neighbor.

Now, if in fact the edges had weights on them,

in other words, if there there were some cost associated with following the edge,

then we might want to allow multiple different edges between two specific nodes,

but this is an unweighted graph,

so each edge costs the same to traverse.

So, we don't allow duplicate nodes

and if we find a duplicate neighbor, we just return, "False."

We say, "No, we didn't add that as a neighbor."

Otherwise, we just add the provided node to our list of neighbors and return, "True."

We can remove a neighbor by removing that node from the list of neighbors,

and it turns out that this list method

actually will return false if the neighbor isn't contained in

the list so that takes care of us returning false if there's

no neighbor that they're trying to remove.

We provide a method to remove all neighbors and this is

helpful as we will see when we get to the graph class.

When we went to clear the graph,

we actually want to remove all the references between the nodes in the graph,

so the garbage collector can pick those nodes

up when the garbage collector decides to collect the garbage.

And finally, we have a method to convert the node to a string

providing the value and the list of neighbors for the node.

The graph class is also generic and the only field

that has is the list of nodes in the class.

The constructor doesn't do anything.

We have a count property to return the number of nodes in the graph,

and we have a way to access the list of nodes in the graph.

But again, we return that as an I list, a read-only list,

so that a consumer of the graph can't

actually change the nodes in the graph by manipulating that list.

They need to use AddNode and RemoveNode methods here in

this graph class to manipulate the nodes contained in the graph.

We have a Clear method that, first,

removes all the neighbors for every node so that we're

releasing all those references between the objects,

and then we remove all the nodes from the nodes list.

So once we're done with this,

all the nodes have been disconnected from each other and

all the nodes have been removed from the graph.

To add a node to the graph,

the first thing we check is to see if the graph already has that node.

This particular graph that I've implemented doesn't allow duplicate values.

So, if you think of this as sort of representing specific cities,

you wouldn't have the same cities included in the graph,

like the same values, the same location.

We just need one node for that particular location.

There are certainly scenarios where you might want to allow duplicate values,

but I don't allow them in this particular graph.

And we'll look at the Find method soon,

but basically, the Find method returns the node for the given value.

So if that's not null,

there is already a node for this value,

so we return false because it's a duplicate value.

Otherwise, we add a new graph node with that value to our nodes list and return true.

Another thing we might want to do is add an edge between nodes of particular values.

So, we first find both those nodes that we're trying to connect.

If either one of them is null,

we return false because we can't add an edge to a node that doesn't exist.

We also check to see if the node1 neighbors already contains node2.

In other words, there's already an edge from node1 to node2.

And if that's the case,

the edge already exists and we return false.

Finally, if everything's okay,

we add node2 as a neighbor to node1,

and we add node1 as a neighbor to node2.

So, this is an undirected graph.

There's no direction to the edges,

so we need to add each of the nodes as a neighbor to the other.

In a directed graph,

we'd be adding an edge from node1 to node2.

For example, so we'd only have this line of code,

not this line of code.

But in an undirected graph,

the common way to do this is connect both sides.

We can remove a node with a particular value from the graph.

The first thing we try to do is find the node with that value.

If we can't find it,

that node is not in the graph,

so we return false.

Otherwise, we do a few things.

We remove the node from the list of nodes for the graph,

and we also walk through each of the nodes in the graph and

we remove this node as a neighbor from those nodes,

because we don't want a linkage,

an edge to this node that we're taking out of the graph.

We can also remove edges between two nodes.

We first find those nodes.

If one or both of them don't exist,

we return false because there can't be an edge

between them because one or both of them doesn't exist in the graph.

If node1 doesn't have node2 as a neighbor,

there isn't an edge so there's nothing to remove,

so we return false.

And finally, if we get here, everything's okay.

So, we removed node2 as a neighbor for node1,

and we removed node1 as a neighbor for node2.

And again, we do both of these things because this is an undirected graph.

If this were a directed graph,

we would only do this one.

We look for a graph node with a given value by

simply iterating over the list of nodes in the graph and if,

in fact, the value equals the value that was provided,

we return that node.

If we get all the way here,

we couldn't find that node,

so we return null.

And the last thing we have is the ToString method to convert

a graph to the list of nodes that are in the graph.

To recap, in this lecture,

we learned how to implement a graph and graph nodes,

we saw how to provide read-only access to a collection,

and we saw how to support garbage collection when we clear a graph.