
Title:
0206 Ring Network

Description:

Next, let's take a look at a ring network.

Now, a chain network you can think of as being the relationship between a set of individuals

with a direct chainbasically, for example, the relationship between me

and my chain of ancestors.

This might be my son, who is connected to me, and I'm connected to my dad.

My dad is connected to my grandfather, and so on.

I actually don't know who my greatgrandfather was. That's a chain network.

In a ring network, we actually now complete the loop,

which isn't a good representation of my family, I'm glad to say,

but lots of other things do have this sort of relationship.

As we can see in this particular example, we have a ring of 5 nodes and there are 5 edges

1, 2, 3, 4, 5.

One thing that might be useful to do at this point is to look at what a ring network

like this might look like as a piece of code.

For the purposes of this course, I'm going to represent graphs as dictionaries of dictionaries.

The way that that works islet's take a look here.

What we're going to do is make a graph. We're going to call it a_ring.

We set it equal to 5 and we initialize the ring to be an empty dictionaryjust { }.

Then what we're going to do is to this empty graph we're going to start adding in edges.

The particular edges we're going to add in we're going to loop for each number from 0 to n  1.

We're going to make a link in the ring from node i to node i+1 mod n.

That's going to get us the wrap around at the very end.

What make_link doesand I'm going to use the same definition throughout

is it takes a dictionary or graph and two nodes if we want to connect together,

checks whether the first node is already in the graph.

If it is not, then it creates an empty dictionary for that node. Same thing for node 2.

Then it goes to the dictionary for node 1 in the graph and says that there is a connection

to node 2, so this basically just establishes the connection between node 1 and node 2

so that later we can go and test for it if we want to.

Once we've created that dictionary, we can ask questions like, well, how many nodes

are in the graph and how many edges are in the graph?

I actually ran this already.

You can see that the number of nodes is indeed 5, which is good,

because that's what we wanted it to be.

The number of edgesthe way that we're calculating that is

by taking a look at all the nodes in the graphin this case, the a_ring.keys()

is giving us back a list of all of the names of the nodes in the graph.

We're going to assign the variable node to be each one of those in turn.

What we're going to do with that node is look up the dictionary for that node

in other words, look up all the connections that that node has in the graph,

and look up the length of that, put it together in a big list.

This list has one entry for each node in the graph,

and that entry is exactly how many edges that node has,

which you may recall from last time is called the degree of the node.

This expressionactually, from this bracket here to this bracket here

gives us a list of the degrees of all the nodes.

We sum all those up and now we've counted each edge twice,

so we divide by 2 to get the total number of edges in the graph.

In this case, I then printed out the actual graph itself just so you can see what it looks like.

Five is the number of nodes. Five also happens to be the number of edges.

Because this is a ring, there is one edge coming out of each node

and then wrapping back around to the front.

What it actually looks like internally is the list of the nodes.

This could be any name at all as long as each node has a unique name.

I used numbers here, because it was really easy to do.

There's node 0, node 1, node 2, node 3, and node 4.

What node 0 is is a dictionary of all the nodes that it is connected to directly.

Node 0 in a fivenode ring is connected to node 1, the node to its right,

and node 4, the node that would be one behind it with the wraparound.

Similarly, 1 is connected to 0 and 2, 2 is connected to 1 and 3, and so on.