MCL summer workshop in graph theory

Project 2: Weighted graphs and Google Maps

Due: Thursday, July 14

Definition. A weighted graph is a graph in which each edge $e$ has a nonnegative weight $w(e)$.

The definitions of path length and distance is slightly different for weighted graphs.

Definition. The length of a path $P = v_0v_1\ldots v_k$ in a weighted graph $G$ is the total weight of all the edges in the $P$, i.e. $w(v_0v_1) + w(v_1v_2) + \ldots + w(v_{k - 1}v_k)$.

Definition. The distance between two vertices $u$ and $v$ in a weighted graph $G$, denoted $d(u, v)$, is the length of the shortest path from $u$ to $v$ in $G$.

Thus, the distance between two vertices in a weighted graph is the minimum total weight of a path between those vertices.

Part 1: Google Maps

Discuss how shortest paths in weighted graphs relate to the problem of finding the fastest route from one city to another in Google Maps. What are the vertices? The edges? The weights? The connected components? What are some features of the real Google Maps that this approach doesn't deal with?

Write your answer here. (Double click on this box to edit it, and press Shift-Enter to display it.)

Part 2: Random weighted graphs

You will define a function to generate random weighted graphs for testing.

I added a WeightedGraph class to graphs.py. It is a subclass of Graph, so anything that works with a Graph should work with a WeightedGraph. Here is a demo of some of the added functionality:

In [ ]:
from graphs import *

# Construct an empty weighted graph with edges 0, 1, 2, 3
G = WeightedGraph(4)

# Add an edge; the 3rd parameter is the weight
G.addEdge(0, 3, 5)

# If weight is not specified it is set to 1
G.addEdge(1, 3)

print(G)

# Get the weight of edge 13
print(G.weight(1, 3)) # Should print 1

# If you call addEdge on an edge that's already there, the weight is updated
G.addEdge(1, 3, 2)
print(G.weight(1, 3)) # Should print 2

The numbers in parentheses represent the weights of the edges to those vertices. For example, the line

3: 0(5) 1(1)

means 30 is an edge with weight 5, and 31 is an edge with weight 1.

Now define a function RandomWeightedGraph( $n$, $p$, $w_\textrm{max}$ , wtype ) to generate a random weighted graph.

  • $n$ is the number of vertices.
  • For each pair of vertices, add an edge with probability $p$. Be careful to only consider each pair once!
  • wtype should be either "int" or "real".
  • Whenever you add an edge, give it a random weight between 0 and $w_\textrm{max}$. If wtype is "int", use random.randint(1, $w_\textrm{max}$ ), and if wtype is "real", use random.uniform(0, $w_\textrm{max}$ ).
In [ ]:
from graphs import *
import random

def RandomWeightedGraph(n, p, wmax, wtype):
    # Define an empty weighted graph with vertices 0, 1, ..., n - 1
    G = WeightedGraph(n)
    
    # TO DO: ADD EDGES
    
    return G

#### Testing #####
G = RandomWeightedGraph(10, .5, 10, "int")
print(G)

Part 3: Weighted shortest paths

Try to develop an algorithm analogous to breadth-first search for weighted graphs. I.e., find the distance from a single start vertex $s$ to each other vertex. Use RandomWeightedGraph for testing.

For now, assume that all weights are integers $\geq 1$.

Hint: you can convert your weighted graph to an unweighted graph and use BFS.

In [ ]:
def weightedSearch(G, s):
    # Your code here
    # Return distances from s to every other vertex

Can you think of any disadvantages to this method? What happens if some edges have very large weights?

Write your answer here.

Now consider the general case in which the weights can be any nonnegative real numbers. This time you will need to come up with a modified version of BFS. Use RandomWeightedGraph for testing.

In [ ]:
def realWeightedSearch(G, s):
    # Your code here

Write-up

Write a few paragraphs here describing how you solved these problems, any difficulties you encountered along the way, etc. Explain what your code does and why you think it works.

Double click on this box to edit it, and press Shift-Enter to display it.

When you're done, save this file and email it to scole3@uic.edu.

Enjoy the rest of your summer!