Lab 3: Internet as a Graph
Lab 3: Internet as a Graph
NetID:
Link to your published notebook:
In this lab, we will explore network graphs and internet topology .
Network Representation using Graphs
Network Representation using Graphs
A graph is a way of showing connections between things—say how computers are linked together to form a network.
A very simple graph with 2 connections:
In[]:=
Graph[{a->b,b->c}]
Out[]=
Let’s add labels to identify who is connected to whom:
In[]:=
Graph[{a->b,b->c},VertexLabels->Automatic]
Out[]=
Let’s add one more edge from c back to a:
In[]:=
Graph[{a->b,b->c,c->a},VertexLabels->Automatic]
Out[]=
The circles are called “vertices” and lines between these circles are called "edges".
The vertices (sometimes called “nodes”) represent the computers and the edges represent the connections between the computers.
The vertices (sometimes called “nodes”) represent the computers and the edges represent the connections between the computers.
Directed Graphs
Directed Graphs
If the "direction" of a connection matters, we have a “directed edge” between two nodes.
Maybe you can only go from a to b but not the other way around (like on a one-way road).
Maybe you can only go from a to b but not the other way around (like on a one-way road).
In[]:=
Graph[{a->b},VertexLabels->Automatic]
Out[]=
Undirected Graphs
Undirected Graphs
Sometimes the "direction" of a connection doesn’t matter. You can go both ways, as is the case with the connection between two computers. So we can drop the arrows.
In[]:=
UndirectedGraph[{a->b},VertexLabels->Automatic]
Out[]=
In[]:=
Graph[{ab},VertexLabels->Automatic]
Out[]=
In[]:=
Graph[{harryron},VertexLabels->Automatic]
Out[]=
In[]:=
ab
Out[]=
ab
You can get the by typing Esc ue Esc from your keyboard.
Unweighted Graphs
Unweighted Graphs
In the above graphs, there are no “edge weights” i.e. no cost for traversing down a connection.
Graphs without edge weights are called “unweighted graphs”.
Graphs without edge weights are called “unweighted graphs”.
In[]:=
Graph{sa,ab,bd},
Out[]=
Weighted Graphs
Weighted Graphs
Sometimes there is a cost associated with each connection and this cost can be represented by the “Edge weight”.
The numbers along the edges represents “weight” of the edge or the cost of the corresponding connection.
For this lab, we will assume that the Source node “s” (shown in green) wants to send a message to the destination node “d” (shown in red).
The numbers along the edges represents “weight” of the edge or the cost of the corresponding connection.
For this lab, we will assume that the Source node “s” (shown in green) wants to send a message to the destination node “d” (shown in red).
In[]:=
Graph{sa,ad},EdgeWeight{1,3},VertexLabelsAutomatic,EdgeLabels"EdgeWeight",
Out[]=
We will mostly use weighted graphs in this lab . The following is another example of a weighted graph :
In[]:=
Graph{sa,ab,bd},EdgeWeight{4,3,1},VertexLabelsAutomatic,EdgeLabels"EdgeWeight",
Out[]=
Problem 1
Problem 1
Edit the following code to create your own graph. Add in as many nodes and edges as you like (copy, paste and edit)
and also change the values for the edge weights. Create an interesting topology.
and also change the values for the edge weights. Create an interesting topology.
Answer
Answer
edges={xy,yw,yz}weights={1,1,1}Graph[edges,EdgeWeightweights,VertexLabelsAutomatic,EdgeLabels"EdgeWeight"]
Cost of a Path through the Graph
Cost of a Path through the Graph
Let' s look at a slightly more complicated example :
In[]:=
Graph{sa,sb,ab,bd},
Out[]=
Problem 2
Problem 2
In the graph above, what is the least-cost path from s to d?
What is that least cost?
(For example, you can say: the least cost path is s -> a -> b -> d, and the least cost is 13.)
What is that least cost?
(For example, you can say: the least cost path is s -> a -> b -> d, and the least cost is 13.)
Answer
Answer
Problem 3
Problem 3
What about the least-hop path from s to d?
What is the least number of hops?
What is the least number of hops?
Answer
Answer
Problem 4
Problem 4
Now, let’s look at an even more complex example:
In[]:=
g=Graph{sm,sn,mn,md,nd},EdgeWeight{5,2,1,2,5},VertexLabels->Automatic,EdgeLabels->"EdgeWeight",
Out[]=
What is the least-cost path from s to d in the graph above? What is that least cost?
Answer
Answer
More Nodes means More Paths
More Nodes means More Paths
Start simple
Start simple
Let' s look at the same graph as above, but with edge weights removed .
Problem 5
Problem 5
How many total paths are there from s to d in the graph above?Can you list all of the paths?
Answer
Answer
Add another node
Add another node
Now, let’s add one more node o to the graph above. This node is connected to all other nodes.
Problem 6
Problem 6
Can you list all of the paths from s to d in the graph now? Hint: there are 15 possible paths!
Answer
Answer
That seemed like a lot of work, right? Let’s have the computer do this for us:
Highlight those paths on the graph
Extra Credit
Extra Credit
Create a graph representing a collection of entities and the connections between them from your own life/experience.
Submitting your work
Submitting your work
1
. Publish your notebook
1
.1
.From the cloud notebook, click on “Publish” at the top right corner.
1
.2
.From the desktop notebook, use the menu option File -> Publish to Cloud
2
.Copy the published link
3
.Add it to the top of the notebook, below your netID
4
.Print to PDF
5
.Upload to Gradescope
6
.Just to be sure, maybe ping your TA Sattwik on Slack that you have submitted.