Recursive version: Depth First Search in a Graph

checking_pairwise_connectivity_dict.py

##################################################################
# Udacity, CS215, unit3, 9.Checking Pairwise Connectivity.
# Traversal...
# Call this routine on nodes being visited for the first time
def mark_component(G, node, marked):
    '''Using a dict to store the nodes that connected.'''
    # Original vertion.
    marked[node] = True
    total_marked = 1
    for neighbor in G[node]:
        if neighbor not in marked:
            total_marked += mark_component(G, neighbor, marked)
    return total_marked

def check_connection(G, v1, v2):
    # Return True if v1 is connected to v2 in G
    # or False if otherwise
    marked = {}
    mark_component(G, v1, marked)
    print marked
    return True if v2 in marked else False
    
def make_link(G, node1, node2):
    if node1 not in G:
        G[node1] = {}
    (G[node1])[node2] = 1
    if node2 not in G:
        G[node2] = {}
    (G[node2])[node1] = 1
    return G

def test():
    edges = [('a', 'g'), ('a', 'd'), ('g', 'c'), ('g', 'd'), 
             ('b', 'f'), ('f', 'e'), ('e', 'h')]
    G = {}
    for v1, v2 in edges:
        make_link(G, v1, v2)
    print G
    assert check_connection(G, "a", "c") == True
    assert check_connection(G, 'a', 'b') == False
    
test()

checking_pairwise_connectivity_list.py

##################################################################
# Udacity, CS215, unit3, 9.Checking Pairwise Connectivity.
# Traversal...
# Call this routine on nodes being visited for the first time
def mark_component(G, node, marked):
    '''Use a list to store the nodes that connetcted'''
    # modified version
    marked.append(node)
    total_marked = 1
    for neighbor in G[node]:
        if neighbor not in marked:
            marked.append(neighbor)
            total_marked += mark_component(G, neighbor, marked)
    return total_marked

def check_connection(G, v1, v2):
    # Return True if v1 is connected to v2 in G
    # or False if otherwise
    marked = []
    mark_component(G, v1, marked)
    marked = set(marked) #remove the duplicate nodes in the list
    print marked
    return True if v2 in marked else False
    
def make_link(G, node1, node2):
    if node1 not in G:
        G[node1] = {}
    (G[node1])[node2] = 1
    if node2 not in G:
        G[node2] = {}
    (G[node2])[node1] = 1
    return G

def test():
    edges = [('a', 'g'), ('a', 'd'), ('g', 'c'), ('g', 'd'), 
             ('b', 'f'), ('f', 'e'), ('e', 'h')]
    G = {}
    for v1, v2 in edges:
        make_link(G, v1, v2)
    print G
    assert check_connection(G, "a", "c") == True
    assert check_connection(G, 'a', 'b') == False
    
test()

Print_results.py

Graph:
{'a': {'d': 1, 'g': 1}, 'c': {'g': 1}, 'b': {'f': 1}, 'e': {'h': 1, 'f': 1}, 'd': {'a': 1, 'g': 1}, 'g': {'a': 1, 'c': 1, 'd': 1}, 'f': {'b': 1, 'e': 1}, 'h': {'e': 1}}

List example:
set(['a', 'c', 'd', 'g'])
set(['a', 'c', 'd', 'g'])

Dict example:
{'a': True, 'c': True, 'd': True, 'g': True}
{'a': True, 'c': True, 'd': True, 'g': True}