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

How do Node, Edge and a dictionary of children become a working Digraph, and why is Graph just a subclass that adds the reverse edge?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Wire up a three-node digraph

The given code creates a Digraph and adds the nodes X, Y and Z. Add the three directed edges from the video, X→Y, Y→X and Y→Z, using addEdge, Edge and getNode. The checks read the graph g.

Given code — runs before yours

class Node(object):
    def __init__(self, name):
        """Assumes name is a string"""
        self.name = name
    def getName(self):
        return self.name
    def __str__(self):
        return self.name

class Edge(object):
    def __init__(self, src, dest):
        """Assumes src and dest are nodes"""
        self.src = src
        self.dest = dest
    def getSource(self):
        return self.src
    def getDestination(self):
        return self.dest
    def __str__(self):
        return self.src.getName() + '->' + self.dest.getName()

class Digraph(object):
    """edges is a dict mapping each node to a list of its children"""
    def __init__(self):
        self.edges = {}
    def addNode(self, node):
        if node in self.edges:
            raise ValueError('Duplicate node')
        else:
            self.edges[node] = []
    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.edges and dest in self.edges):
            raise ValueError('Node not in graph')
        self.edges[src].append(dest)
    def childrenOf(self, node):
        return self.edges[node]
    def hasNode(self, node):
        return node in self.edges
    def getNode(self, name):
        for n in self.edges:
            if n.getName() == name:
                return n
        raise NameError(name)
    def __str__(self):
        result = ''
        for src in self.edges:
            for dest in self.edges[src]:
                result = result + src.getName() + '->' + dest.getName() + '\n'
        return result[:-1]

class Graph(Digraph):
    def addEdge(self, edge):
        Digraph.addEdge(self, edge)
        rev = Edge(edge.getDestination(), edge.getSource())
        Digraph.addEdge(self, rev)

g = Digraph()
for name in ('X', 'Y', 'Z'):
    g.addNode(Node(name))
# Add the edges X->Y, Y->X and Y->Z.

g = Digraph()
for name in ('X', 'Y', 'Z'):
    g.addNode(Node(name))
# Add the edges X->Y, Y->X and Y->Z.

Python runs in your browser

⌘/Ctrl + Enter runs

is a Digraph with three nodes

Y has children X and Z, in that order

X points to Y and Z has no children

←Previous Graphs as Models: Nodes, Edges and Euler's Seven Bridges Next Depth-First Search for the Shortest Path in a Graph →

class Node(object): def __init__(self, name): """Assumes name is a string""" self.name = name def getName(self): return self.name def __str__(self): return self.name class Edge(object): def __init__(self, src, dest): """Assumes src and dest are nodes""" self.src = src self.dest = dest def getSource(self): return self.src def getDestination(self): return self.dest def __str__(self): return self.src.getName() + '->' + self.dest.getName() class Digraph(object): """edges is a dict mapping each node to a list of its children""" def __init__(self): self.edges = {} def addNode(self, node): if node in self.edges: raise ValueError('Duplicate node') else: self.edges[node] = [] def addEdge(self, edge): src = edge.getSource() dest = edge.getDestination() if not (src in self.edges and dest in self.edges): raise ValueError('Node not in graph') self.edges[src].append(dest) def childrenOf(self, node): return self.edges[node] def hasNode(self, node): return node in self.edges def getNode(self, name): for n in self.edges: if n.getName() == name: return n raise NameError(name) def __str__(self): result = '' for src in self.edges: for dest in self.edges[src]: result = result + src.getName() + '->' + dest.getName() + '\n' return result[:-1] class Graph(Digraph): def addEdge(self, edge): Digraph.addEdge(self, edge) rev = Edge(edge.getDestination(), edge.getSource()) Digraph.addEdge(self, rev)