Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 02-06 Ring Network

Get Embed Code
2 Languages

Showing Revision 1 created 07/07/2012 by Amara Bot.

  1. Next, let's take a look at a ring network.
  2. Now, a chain network you can think of as being the relationship between a set of individuals
  3. with a direct chain--basically, for example, the relationship between me
  4. and my chain of ancestors.
  5. This might be my son, who is connected to me, and I'm connected to my dad.
  6. My dad is connected to my grandfather, and so on.
  7. I actually don't know who my great-grandfather was. That's a chain network.
  8. In a ring network, we actually now complete the loop,
  9. which isn't a good representation of my family, I'm glad to say,
  10. but lots of other things do have this sort of relationship.
  11. As we can see in this particular example, we have a ring of 5 nodes and there are 5 edges--
  12. 1, 2, 3, 4, 5.
  13. One thing that might be useful to do at this point is to look at what a ring network
  14. like this might look like as a piece of code.
  15. For the purposes of this course, I'm going to represent graphs as dictionaries of dictionaries.
  16. The way that that works is--let's take a look here.
  17. What we're going to do is make a graph. We're going to call it a_ring.
  18. We set it equal to 5 and we initialize the ring to be an empty dictionary--just { }.
  19. Then what we're going to do is to this empty graph we're going to start adding in edges.
  20. The particular edges we're going to add in we're going to loop for each number from 0 to n - 1.
  21. We're going to make a link in the ring from node i to node i+1 mod n.
  22. That's going to get us the wrap around at the very end.
  23. What make_link does--and I'm going to use the same definition throughout--
  24. is it takes a dictionary or graph and two nodes if we want to connect together,
  25. checks whether the first node is already in the graph.
  26. If it is not, then it creates an empty dictionary for that node. Same thing for node 2.
  27. Then it goes to the dictionary for node 1 in the graph and says that there is a connection
  28. to node 2, so this basically just establishes the connection between node 1 and node 2
  29. so that later we can go and test for it if we want to.
  30. Once we've created that dictionary, we can ask questions like, well, how many nodes
  31. are in the graph and how many edges are in the graph?
  32. I actually ran this already.
  33. You can see that the number of nodes is indeed 5, which is good,
  34. because that's what we wanted it to be.
  35. The number of edges--the way that we're calculating that is
  36. by taking a look at all the nodes in the graph--in this case, the a_ring.keys()
  37. is giving us back a list of all of the names of the nodes in the graph.
  38. We're going to assign the variable node to be each one of those in turn.
  39. What we're going to do with that node is look up the dictionary for that node--
  40. in other words, look up all the connections that that node has in the graph,
  41. and look up the length of that, put it together in a big list.
  42. This list has one entry for each node in the graph,
  43. and that entry is exactly how many edges that node has,
  44. which you may recall from last time is called the degree of the node.
  45. This expression--actually, from this bracket here to this bracket here
  46. gives us a list of the degrees of all the nodes.
  47. We sum all those up and now we've counted each edge twice,
  48. so we divide by 2 to get the total number of edges in the graph.
  49. In this case, I then printed out the actual graph itself just so you can see what it looks like.
  50. Five is the number of nodes. Five also happens to be the number of edges.
  51. Because this is a ring, there is one edge coming out of each node
  52. and then wrapping back around to the front.
  53. What it actually looks like internally is the list of the nodes.
  54. This could be any name at all as long as each node has a unique name.
  55. I used numbers here, because it was really easy to do.
  56. There's node 0, node 1, node 2, node 3, and node 4.
  57. What node 0 is is a dictionary of all the nodes that it is connected to directly.
  58. Node 0 in a five-node ring is connected to node 1, the node to its right,
  59. and node 4, the node that would be one behind it with the wraparound.
  60. Similarly, 1 is connected to 0 and 2, 2 is connected to 1 and 3, and so on.