Coding challenges on graph-theoretic models — MIT problem set

Problem 1Coding a Graph in Python: Node, Edge, Digraph and Graph

Campus Map: A Weighted Edge

MIT 6.0002 Introduction to Computational Thinking and Data Science, Fall 2016 · Problem set 2, Problem 1: Creating the Data Structure Representation — WeightedEdge · Prof. Eric Grimson, Prof. John Guttag and Dr. Ana Bell · CC BY-NC-SA 4.0 · MIT publishes no solution for this set; the worked solution is ours

Complete the WeightedEdge class, a subclass of Edge that also stores the two costs of traversing the edge: its total distance and its distance spent outdoors.

In this problem set we are dealing with edges that have different weights. Each edge of the MIT campus map has a cost in terms of total distance traveled and a cost in terms of distance spent outdoors. The distance spent outdoors for a single edge is always less than or equal to the total distance it takes to traverse that edge. For example, the cost of going from a to b to e might be a total distance traveled of 22 meters, of which 14 meters are spent outdoors.

The Node and Edge classes are given; they do not store weights. WeightedEdge(src, dest, total_distance, outdoor_distance) must keep both weights, return them from get_total_distance() and get_outdoor_distance(), and implement __str__ as follows. Suppose a WeightedEdge object e contains:

Source node name: 'a'
Destination node name: 'b'
Total distance along the edge: 15
Outdoor distance along the edge: 10

Then str(e) should yield a->b (15, 10).

print(str(WeightedEdge(Node('a'), Node('b'), 15, 10)))  # a->b (15, 10)
print(WeightedEdge(Node('b'), Node('c'), 3, 1).get_outdoor_distance())  # 1

# --- given: Node and Edge from graph.py (do not edit) ---
class Node(object):
    """Represents a node in the graph"""
    def __init__(self, name):
        self.name = str(name)

    def get_name(self):
        return self.name

    def __str__(self):
        return self.name

    def __repr__(self):
        return self.name

    def __eq__(self, other):
        return self.name == other.name

    def __ne__(self, other):
        return not self.__eq__(other)

    def __hash__(self):
        # This function is necessary so that Nodes can be used as
        # keys in a dictionary, even though Nodes are mutable
        return self.name.__hash__()


class Edge(object):
    """Represents an edge in the dictionary. Includes a source and
    a destination."""
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def get_source(self):
        return self.src

    def get_destination(self):
        return self.dest

    def __str__(self):
        return '{}->{}'.format(self.src, self.dest)


class WeightedEdge(Edge):
    def __init__(self, src, dest, total_distance, outdoor_distance):
        pass

    def get_total_distance(self):
        pass

    def get_outdoor_distance(self):
        pass

    def __str__(self):
        pass

# --- given: Node and Edge from graph.py (do not edit) ---
class Node(object):
    """Represents a node in the graph"""
    def __init__(self, name):
        self.name = str(name)

    def get_name(self):
        return self.name

    def __str__(self):
        return self.name

    def __repr__(self):
        return self.name

    def __eq__(self, other):
        return self.name == other.name

    def __ne__(self, other):
        return not self.__eq__(other)

    def __hash__(self):
        # This function is necessary so that Nodes can be used as
        # keys in a dictionary, even though Nodes are mutable
        return self.name.__hash__()


class Edge(object):
    """Represents an edge in the dictionary. Includes a source and
    a destination."""
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def get_source(self):
        return self.src

    def get_destination(self):
        return self.dest

    def __str__(self):
        return '{}->{}'.format(self.src, self.dest)


class WeightedEdge(Edge):
    def __init__(self, src, dest, total_distance, outdoor_distance):
        pass

    def get_total_distance(self):
        pass

    def get_outdoor_distance(self):
        pass

    def __str__(self):
        pass

Scratchpad— run any Python to test ideas

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment

Visible tests · 2Examples — click to expand

str() of a weighted edge (MIT's tester)

the total distance (MIT's tester)

Hidden tests · 4Bodies hidden — pass/fail only

Hidden test 1

Hidden test 2

Hidden test 3

Hidden test 4

Campus Map: A Weighted Edge

Complete the WeightedEdge class, a subclass of Edge that also stores the two costs of traversing the edge: its total distance and its distance spent outdoors.

Source node name: 'a'
Destination node name: 'b'
Total distance along the edge: 15
Outdoor distance along the edge: 10

Then str(e) should yield a->b (15, 10).

print(str(WeightedEdge(Node('a'), Node('b'), 15, 10)))  # a->b (15, 10)
print(WeightedEdge(Node('b'), Node('c'), 3, 1).get_outdoor_distance())  # 1

# --- given: Node and Edge from graph.py (do not edit) ---
class Node(object):
    """Represents a node in the graph"""
    def __init__(self, name):
        self.name = str(name)

    def get_name(self):
        return self.name

    def __str__(self):
        return self.name

    def __repr__(self):
        return self.name

    def __eq__(self, other):
        return self.name == other.name

    def __ne__(self, other):
        return not self.__eq__(other)

    def __hash__(self):
        # This function is necessary so that Nodes can be used as
        # keys in a dictionary, even though Nodes are mutable
        return self.name.__hash__()


class Edge(object):
    """Represents an edge in the dictionary. Includes a source and
    a destination."""
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def get_source(self):
        return self.src

    def get_destination(self):
        return self.dest

    def __str__(self):
        return '{}->{}'.format(self.src, self.dest)


class WeightedEdge(Edge):
    def __init__(self, src, dest, total_distance, outdoor_distance):
        pass

    def get_total_distance(self):
        pass

    def get_outdoor_distance(self):
        pass

    def __str__(self):
        pass

# --- given: Node and Edge from graph.py (do not edit) ---
class Node(object):
    """Represents a node in the graph"""
    def __init__(self, name):
        self.name = str(name)

    def get_name(self):
        return self.name

    def __str__(self):
        return self.name

    def __repr__(self):
        return self.name

    def __eq__(self, other):
        return self.name == other.name

    def __ne__(self, other):
        return not self.__eq__(other)

    def __hash__(self):
        # This function is necessary so that Nodes can be used as
        # keys in a dictionary, even though Nodes are mutable
        return self.name.__hash__()


class Edge(object):
    """Represents an edge in the dictionary. Includes a source and
    a destination."""
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def get_source(self):
        return self.src

    def get_destination(self):
        return self.dest

    def __str__(self):
        return '{}->{}'.format(self.src, self.dest)


class WeightedEdge(Edge):
    def __init__(self, src, dest, total_distance, outdoor_distance):
        pass

    def get_total_distance(self):
        pass

    def get_outdoor_distance(self):
        pass

    def __str__(self):
        pass

Scratchpad— run any Python to test ideas

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment

Visible tests · 2Examples — click to expand

str() of a weighted edge (MIT's tester)

the total distance (MIT's tester)

Hidden tests · 4Bodies hidden — pass/fail only

Hidden test 1

Hidden test 2

Hidden test 3

Hidden test 4