1. Starting the IDLE Python Interpreter

Simple Python Interactions When you don't have any code written yet, this is simple. We want to start IDLE, Python's environment and editor. Windows: Under the Start Menu, select Python 2.7 / IDLE. Alternatively, if you have Enthought installed, then select Enthought / IDLE. Mac OS X: Under Go / Applications, select Python 2.7 / IDLE. Alternatively, if you have Enthought installed, then select Enthought / IDLE. Linux: Optionally cd to the directory you'll want your code, then enter idle &. This assumes you've added idle to your PATH. Utilizing Support Files Later, once you already have code written, you need to be careful how you start Python. Your programs typically won't be all in one file, and you need to start it in a way that it can find the related files. You'll need to do this each time you use Python, not just the first time. Windows: Open the folder with your Python files. Right click on one of the Python files, and select “Edit with IDLE”. Mac OS X: Look under Go / Utilities, and select Terminal. cd to the folder with your code, then enter idle &. Linux: cd to the directory with your code, then enter idle &. This assumes you've added idle to your PATH. You should see something like the window shown on the right. Note the version number shown in the first line. This is Python's interactive window. It is good for experimenting with small examples and running and testing your code. While you can write entire programs here, it's not a good tool for that. Of course, if you familiar with Python already and know other techniques for starting Python, you can still use those. Also, if you are using your own computer, you can also look into how to update PYTHONPATH, the list of folders/directories that Python searches for files.

---

2. Python Documentation

As the course progresses, we will be using various features of Python. Most of the features you did not learn in COMP 140 will be discussed in lab. However, it is always useful to be able to look things up in the Python documentation. The Language Reference section includes documentation for any and all features of Python. The Library Reference includes documentation for the standard Python libraries. You will find useful information in the Library Reference about the built-in types and their operations.

We encourage you to consult the documentation when you are unsure of how something works in Python. Of course, you are also always welcome to discuss such issues with the staff, as well.

---

3. Sets

Quick Reference:

empty_set = set() # Create an empty set.
north_colleges = set(["Jones", "Brown", "Martel", "Duncan", "McMurtry"]) # Create a set with initial elements.
north_colleges.add("Nakhleh") # Add to a set.
north_colleges.remove("Nakhleh") # Remove from a set.
>>> "Baker" in north_colleges # Test for membership in a set.
False

Exercise 3.1

What would you expect the value of this expression to be?

>>> set([0,1,2]) == set([2,0,1,1])

What would you expect the result of this Python code to be?

>>> some_set = set([0,1,2])
>>> some_set.add(2)
>>> some_set

Exercise 3.2 - Union

Write a function

def union(set1, set2):
    """
    Returns the union of two sets.

    Arguments:
    set1 -- The first set of the union.
    set2 -- The second set of the union.

    Returns:
    A new set containing all the elements of set1 and set2.
    """
    ...

that takes two sets as arguments and returns their union. (A union of two sets A and B is a new set that contains all the elements of both A and B. For example, the union of {1,2,3} and {2,3,4} is {1,2,3,4}.)

Assert your function produces the following output:

>>> union(set([1,2,3]), set([4,5,6]))
set([1, 2, 3, 4, 5, 6])

>>> union(set([1,2,3]), set([2,3,4]))
set([1, 2, 3, 4])

>>> union(set(), set([3]))
set([3])

>>> union(set(), set())
set([])

This method already exists in the set class by the name of union (along with many others, type help(set) for details). In the future, feel free to use this method instead of implementing union on your own. But do implement it yourself for this exercise.

Exercise 3.3 - Intersection

Write a function

def intersection(set1, set2):
    """
    Returns the intersection of two sets.

    Arguments:
    set1 -- The first set of the intersection.
    set2 -- The second set of the intersection.

    Returns:
    A new set containing only the elements common to set1 and set2.
    """
    ...

that takes two sets as arguments and returns their intersection. (An intersection of two sets A and B is a new set that contains only the elements common to both A and B. For example, the intersection of {1,2,3} and {2,3,4} is {2,3}.)

Assert your function produces the following output:

>>> intersection(set([1,2,3]), set([2,3,4]))
set([2, 3])

>>> intersection(set([1,2]), set([3,4]))
set([])

>>> intersection(set(), set([3]))
set([])

More Information

Consult the Python documentation for more details about sets.

---

4. Dictionaries

Quick Reference:

empty_dict = { } # Create an empty dictionary.
bb_alumni_victory = {
        2009:"Will Rice",
        2008:"Brown",
        2006:"Will Rice",
        1992:"Hanszen",
        1982:"Wiess" } # Create an explicit dictionary.
bb_alumni_victory[1984] = "Hanszen" # Add or update a key.
>>> bb_alumni_victory[2008]
'Brown'

Exercise 4.1 - Dictionary Creation

Write a function

def make_dict(keys, default_value):
    """
    Creates a new dictionary with the specified keys and default value.

    Arguments:
    keys          -- A list of keys to be included in the returned dictionary.
    default_value -- The initial mapping value for each key.

    Returns:
    A dictionary where every key is mapped to the given default_value.
    """
    ...

that takes a list of keys and a default value and creates a dictionary containing these keys with each key mapping to the given default value.

Assert your function produces the following output:

>>> make_dict(["a","b","c"], "z")
{'a': 'z', 'c': 'z', 'b': 'z'}

>>> make_dict([], [])
{}

Exercise 4.2 - Value Assertion

Write a function

def ensure_key_value_pair(pairs, key, expected_value):
    """
    Checks to ensure that the mapping of key in pairs matches the given expected value.

    If the state of pairs is such that the given key is already mapped to the given expected value
    this function in no way modifies the dictionary and returns the given dictionary.

    If the state of pairs is such that the given key does not map to the given expected value
    (or no such key is contained in pairs) then update (or add) the mapping of key to
    the given expected value and return the given dictionary.

    Arguments:
    pairs          -- A dictionary to check for the expected mapping.
    key            -- The key of the expected mapping.
    expected_value -- The the value of the expected mapping.

    Returns:
    The given dictionary.
    """
    ...

that returns the given dictionary if the lookup value of the dictionary under the given key has the same value as expected_value. Otherwise, ensure that the value at key for the given dictionary is expected_value and return the updated dictionary.

Note: You may find the dict method has_key(key) which tests whether the given key is contained in the dictionary useful.

Assert your function produces the following output:

>>> pairs = { 1:"a", 2:"b" }
>>> ensure_key_value_pair(pairs, 1, "a")
{1: 'a', 2: 'b'}

>>> ensure_key_value_pair(pairs, 2, "z")
{1: 'a', 2: 'z'}

>>> ensure_key_value_pair(pairs, 3, "x")
{1: 'a', 2: 'z', 3: 'x'}

More Information

Consult the Python documentation for more details about dictionaries.

---

5. Graphs

We will represent graphs as a dictionary utilizing nodes as keys and adjacency sets (i.e. the node's neighbors) as values. Therefore each node in the graph is a key in the dictionary that maps to a set containing that node's neighbors. For example the graph $G = (V, E)$ where $V = \{0, 1, 2\}$ and $E = \{ \{0, 1\}, \{1, 2\} \}$ can be represented as:

graph = { 0 : set([1]),
          1 : set([0, 2]),
          2 : set([1]) }

Exercise 5.1 - Node Count

Write a function:

def node_count(graph):
    """
    Returns the number of nodes in a graph.

    Arguments:
    graph -- The given graph.

    Returns:
    The number of nodes in the given graph.
    """
    ...

that computes the number of nodes in a graph.

You can obtain a list of a given dictionary's keys by using the keys() method. For example:

graph = { ... }
nodes_in_graph = graph.keys() # A dict's keys define a graph's nodes!

Assert that your function produces the following output:

>>> graph1 = { 0: set(), 1: set()}
>>> node_count(graph1)
2

>>> graph2 = { }
>>> node_count(graph2)
0

Exercise 5.2 - Edge Count

Write a function:

def edge_count(graph):
    """
    Returns the number of edges in a graph.

    Arguments:
    graph -- The given graph.

    Returns:
    The number of edges in the given graph.
    """
    ...

that computes the number of edges in a graph.

Assert that your function produces the following output:

>>> graph1 = { "0" : set(["1","2"]),
               "1" : set(["0","2"]),
               "2" : set(["1","0"]) }
>>> edge_count(graph1)
3

>>> graph2 = { 0: set(), 1: set()}
>>> edge_count(graph2)
0

>>> graph3 = { }
>>> edge_count(graph3)
0

Exercise 5.3 - Complete Graphs

Before starting this exercise copy the following code into the file you are working with:

def convert(g):
    """
    Print an undirected graph in a form that can be used by the
    graph visualizer.

    Arguments:
    g -- the given graph

    Returns:
    Nothing
    """
    nodes = g.keys()
    edges = []
    for u in g:
        for v in g[u]:
            if not [v, u] in edges:
                edges.append([u, v])
    print [nodes, edges]

(Do not worry about what this function is doing.)

A complete graph is a graph where every unordered pair of distinct nodes is connected by an edge. Write a function

def make_complete_graph(num_nodes):
    """
    Returns a complete graph containing num_nodes nodes.

    The nodes of the returned graph will be 0...(num_nodes-1) if num_nodes-1 is positive.
    An empty graph will be returned in all other cases.

    Arguments:
    num_nodes -- The number of nodes in the returned graph.

    Returns:
    A complete graph in dictionary form.
    """
    ...

that creates a complete graph with the specified number of nodes. The nodes of the graph should be the numbers from 0 to num_nodes-1 (for num_nodes>0). Now visually verify that your function generates a complete graph by interpreting:

>>> graph = make_complete_graph(5)
>>> convert(graph)

Cut and paste the output of convert into the textbox here and click the “draw” button. Make sure that you copy the text exactly. The graph visualizer does not do any serious error checking and is not robust if your input is incorrect.

Also assert your function produces the following output:

>>> graph = make_complete_graph(5)
>>> 3 in graph[3]
False

---

6. Digraphs

Recall that for digraphs (a.k.a. directed graphs) each edge is oriented from a tail node to a head node. An edge from node 0 to node 1 in a digraph does not imply that an edge exists from 1 to 0. In fact it is possible for none, either or both such edges to exist in a given digraph! We can modify our dictionary representation of graphs to represent digraphs as follows:

To represent an edge from node 0 to node 1 we place 1 in 0's adjacency set but, unlike our graph representation, we do not automatically place 0 in 1's adjacency set. The adjacency set for a given node key then records only those nodes which are "pointed to" from the key. The statement

if 1 in digraph[0]:

thus represents the question "Is there an edge from node 0 to node 1?" Because the adjacency sets of 0 and 1 are no longer symmetric we can now populate them independently to represent only those nodes immediately reachable from a given node.

Exercise 6.1 - Your First Digraph

Write the Python code to represent a digraph containing the nodes V = {0, 1, 2, 3, 4, 5} where an edge exists from n to n+1 (for n = 0...4). Also include the edge (5,0). Show your code to a lab assistant for verification.

Exercise 6.2 - In-Degree

Write a function

def in_degree(digraph, node):
    """
    Computes the in-degree of the given node.

    Arguments:
    digraph -- a dictionary representation of a digraph.
    node    -- the given to node.

    Returns:
    The in-degree of node.
    """
    ...

to compute the in-degree for a node in a given digraph.

Assert your function produces the following output:

>>> digraph = {  1 : set([2]),
                 2 : set([3,4]),
                 3 : set([]),
                 4 : set([3,2]),
                 5 : set() }
>>> in_degree(digraph, 3)
2

>> in_degree(digraph, 4)
1

>> in_degree(digraph, 1)
0

---

7. Optional Challenge Exercise

These problems are not officially a part of lab. While you do not need to continue, as it's the first lab of the semester, there is obviously more to learn! Further, you may find this useful as you test your code.

Exercise 7.1 - Graph Validity

One interesting observation about our dictionary representation of graphs is that each edge in the graph is in essence recorded twice. For example in the case of a two node, one edge graph:

graph = { "0" : set(["1"]),
          "1" : set(["0"]) }

we could test to see if an edge connects nodes 0 and 1 by either examining node 0's adjacency set looking for 1 or by examining 1's adjacency set looking for 0. If an edge connects these two nodes together then it doesn't matter which of the two sets we choose to examine--either will give us the answer. Node 0's adjacency set containing 1 implies that 1's set contains 0 and vice versa. Restated, if the answer to the question "Is node 0 connected to node 1?" is "Yes" then the answer to the question "Is node 1 connected to node 0?" must also be "Yes." That is unless we have made a mistake when creating the data structure representation of our graph. For example, what if we forgot to add node 0 to node 1's adjacency set?

illogical_graph = { "0" : set(["1"]),
                    "1" : set([]) }

It would be useful to create a function to check our graph structures for such mistakes. As such, write a function

def is_undirected_graph_valid(graph):
    """
    Tests whether the given graph is logically valid.

    Asserts for every unordered pair of distinct nodes {n1, n2} that
    if n2 appears in n1's adjacency set then n1 also appears in 
    n2's adjacency set.  Also asserts that no node appears in 
    its own adjacency set and that every value that appears in
    an adjacency set is a node in the graph.

    Arguments:
    graph -- The graph in dictionary form to test.

    Returns:
    True if the graph is logically valid.  False otherwise.
    """
    ...

that tests whether a given graph is logically valid.

Assert your function produces the following output:

>>> graph1 = { "0" : set(["1","2"]),
               "1" : set(["0","2"]),
               "2" : set(["1","0"]) }
>>> is_undirected_graph_valid(graph1)
True

>>> graph2 = { "0" : set(["1","2"]),
               "1" : set(["0","2"]),
               "2" : set(["1"]) }
>>> is_undirected_graph_valid(graph2)
False

>>> graph3 = make_complete_graph(100)
>>> is_undirected_graph_valid(graph3)
True

>>> graph4 = { "0" : set(["1","2"]),
               "1" : set(["0","2"]),
               "2" : set(["1","3"]) }
>>> is_undirected_graph_valid(graph4)
False

>>> graph5 = { "0" : set(["0"]) }
>>> is_undirected_graph_valid(graph5)
False

It is good practice to routinely check the validity of your data structures as you test. You may find this function invaluable as you develop graph algorithms throughout the course.