COMP 182 Lab 1 Solutions

3.2 Union

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.
    """
    result = set()

    for element in set1:
        result.add(element)

    for element in set2:
        result.add(element)

    return result

3.3 - Intersection

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.
    """
    result = set()

    for element in set1:
        if element in set2:
            result.add(element)

    return result

4.1 Dictionary Creation

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.
    """
    result = { }

    for key in keys:
        result[key] = default_value
    
    return result

4.2 Value Assertion

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 performs no action and immediately 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.
    """
    if pairs.has_key(key):
        found_value = pairs[key]
        if found_value == expected_value:
            return pairs # key was found and mapped to exepcted value
        else:
            pairs[key] = expected_value
            return pairs # key was found and not mapped to exepcted value      
    else:
       pairs[key] = expected_value
       return pairs # given key was not found

5.1 Node Count

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.
    """
    return len(graph.keys())

5.2 Edge Count

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.
    """
    edge_double_count = 0
    for nodeKey in graph.keys():
        edge_double_count = edge_double_count + len(graph[nodeKey])

    return edge_double_count / 2

5.3 Complete Graph

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.
    """
    result = { }
        
    for node_key in range(num_nodes):
        result[node_key] = set()
        for node_value in range(num_nodes):
            if node_key != node_value: # no loops allowed in 182
                result[node_key].add(node_value)

    return result

6.1 Digraph

{0: set([1]), 1: set([2]), 2: set([3]), 3: set([4]), 4: set([5]), 5: set([0])}

6.2 In-Degree

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.
    """
    count = 0

    for key in digraph.keys():
        for to_node in digraph[key]:
            if to_node == node:
                count = count + 1

    return count