Directed graphs

Humberto Ortiz-Zuazaga

A directed graph $G = (V, E)$, also called a digraph, is a set $V$ of vertices and a set $E$ of directed edges, or edges that proceed from a source vertex to a sink vertex. Here's a crude diagram of a directed graph:

(1) ---> (2) ---> (3) <--
 \______________________/

Where node 1 has an edge to node 2 and node 3, and node 2 has an edge to node 3.

Directed graphs in python

We can represent these graphs in python by keeping track of forward and reverse edges, so we can find neighbors for any vertex in either direction. Here we'll build an empty graph, using dicts to keep track of the forward and reverse relationships.



In [1]:

    
graph = {"forward" : {}, "reverse" : {}}

Adding the edge from 1 to 2 requires two steps, adding the forward relationship, and adding the reverse.



In [2]:

    
graph["forward"][1] = [2]
graph["reverse"][2] = [1]
graph









    Out[2]:





{'forward': {1: [2]}, 'reverse': {2: [1]}}

To add the edge between 1 and 3, we have to be careful, we need to append 3 to the neighbor list of 1.



In [3]:

    
graph["forward"][1].append(3)
graph["reverse"][3] = [1]
graph









    Out[3]:





{'forward': {1: [2, 3]}, 'reverse': {2: [1], 3: [1]}}

When can we assign to the neighbor list and when do we have to append? Let's see what happend when we add the edge from 2 to 3.



In [4]:

    
graph["forward"][2] = [3]
graph["reverse"][3].append(2)
graph









    Out[4]:





{'forward': {1: [2, 3], 2: [3]}, 'reverse': {2: [1], 3: [1, 2]}}

Exercises

Write definitions for these two functions.



In [5]:

    
def make_digraph():
    "Make an empty directed graph"
    pass



In [6]:

    
def add_edge(digraph, source, sink):
    "Add a directed edge from the source vertex to the sink vertex to the digraph."
    pass

Tests

After completing the exercise, these commands should produce a graph like the example.



In [7]:

    
graph2 = make_digraph()
add_edge(graph2, 1, 2)
add_edge(graph2, 1, 3)
add_edge(graph2, 2, 3)
graph2

Even and odd vertices

In class we saw that in order to construct Eulerian paths in directed graphs, we need to change the concept of an even or odd vertex. In particular, in a directed graph, a node is even if it has the same number of forward edges leaving it as edges inbound to it. A vertex is odd otherwise. We can write a function to return the number of inbound edges minus the number of outbound edges.



In [8]:

    
def check_vertex(digraph, vertex):
    "Check if a vertex in a digraph is even or odd."
    pass

To have an Eulerian path, all verticies except for two (zero for an Eulerian cycle) must be even, The odd verticies (if any) must have one more outbound edge than inbound (for the start vertex) and one more inbound than outbound (for the end vertex)

Eulerian path in directed graph

The algorithm we described for Eulerian paths prevously will work for directed graphs with a few small modifications.



In [9]:

    
def find_path(digraph):
    "Find an Eulerian path through digraph."
    path = []
    # Check if G has an Eulerian path or exit
    # make a copy of G (from now on work on the copy)
    # Choose a starting vertex
    # Push starting vertex onto stack
    # while items remain on the stack:
        # set current vertex to top of stack
        # if current vertex has forward (outbound) edges
            # put neighbor on stack
            # remove edge from current vertex to neighbor
        # else
            # append current vertex to path
            # pop current vertex from stack
    return path

You will also need to implement remove_edge, and functions to check if a path exists, and choose a starting node.



In [10]:

    
def remove_edge(digraph, source, sink):
    pass



In [11]:

    
def has_path(digraph):
    "Test if this digraph has an Eulerian path"
    pass



In [12]:

    
def pick_start(digraph):
    "Find a suitable starting vertex in digraph"
    pass









    



  File "<ipython-input-12-96a8791f2b21>", line 1
    dev pick_start(digraph):
                 ^
SyntaxError: invalid syntax

Assignment: reimplement `find_path`

Modify your find_path function so it works with directed graphs. When completed, you should be able to evaluate the following test and get back a path like [1, 2, 3, 4].



In [ ]:

    
graph3 = make_digraph()
add_edge(graph3, 1, 2)
add_edge(graph3, 2, 3)
add_edge(graph3, 3, 1)
add_edge(graph3, 1, 4)
find_path(graph3)