def DFS_Visit(G, node, color):
    color[node] = 'gray'
    total_marked = 1
    for neighbor in G[node]:
        if color[neighbor] == 'white':
            total_marked += DFS_Visit(G, neighbor, color)
    color[node] = 'black'
    return total_marked

# Graph construction

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

edges1 = [('v', 'r'), ('r', 's'), ('s', 'w'), ('w', 't'), 
         ('w', 'x'), ('t', 'x'), ('t', 'u'), ('x', 'y'),
         ('u', 'y')]

G1 = {}
for v1, v2 in edges1:
    make_link(G1, v1, v2)

# Initialization of 'color' array
color = {}
for v in G1:
    color[v] = 'white'

# Run DFS starting from node 's'
num_nodes = DFS_Visit(G1, 't', color)

print "Number of visited nodes:", num_nodes

print color



def connected(G, v1, v2):
    color = {}
    for v in G1:
        color[v] = 'white'
    DFS_Visit(G, v1, color)
    return color[v2] == 'black'
        

edges2 = [('v', 'r'), ('r', 's'), ('w', 't'), 
         ('w', 'x'), ('t', 'x'), ('t', 'u'), ('x', 'y'),
         ('u', 'y')]

G2 = {}
for v1, v2 in edges2:
    make_link(G2, v1, v2)
    
print connected(G2, 'v', 's')
print connected(G2, 'v', 'y')

def DFS_Visit_p(G, node, color, parent):
    color[node] = 'gray'
    total_marked = 1
    for neighbor in G[node]:
        if color[neighbor] == 'white':
            parent[neighbor] = node
            total_marked += DFS_Visit_p(G, neighbor, color, parent)
    color[node] = 'black'
    return total_marked

def path(G, v1, v2):
    color = {}
    parent = {}
    for v in G:
        color[v] = 'white'
        parent[v] = None
    DFS_Visit_p(G, v1, color, parent)
    pathlist = []
    node = v2
    while node <> None:
        pathlist.append(node)
        node = parent[node]
    if color[v2] == 'black':
        return pathlist[::-1] # los vértices en pathlist están en orden inverso, [::-1] los invierte
    else:
        return []

print path(G1, 't', 'r')

def connected_components(G):
    color = {}
    parent = {}
    for v in G:
        color[v] = 'white'
        parent[v] = None
    count = 0
    for v in G:
        if color[v] == 'white':
            count += 1
            DFS_Visit_p(G, v, color, parent)
    return count

edges3 = [('v', 'r'), ('r', 's'), ('w', 't'), 
         ('w', 'x'), ('t', 'x'),
         ('u', 'y')]
G3 = {}
for v1, v2 in edges3:
    make_link(G3, v1, v2)
    

print connected_components(G1)
print connected_components(G2)
print connected_components(G3)

def DFS_iterative(G, node):
    color = {}
    parent = {}
    for v in G:
        color[v] = 'white'
    color[node] = 'gray'
    parent[node] = None
    nodelist = [node]
    total_marked = 1
    while nodelist <> []:
        u = nodelist.pop()
        for neighbor in G[u].keys()[::-1]:
            if color[neighbor] == 'white':
                color[neighbor] = 'gray'
                parent[neighbor] = u
                nodelist.append(neighbor)
                total_marked += 1
        color[u] = 'black'
    return total_marked, parent

print DFS_iterative(G1, 's')

def BFS_iterative(G, node):
    color = {}
    depth = {}
    parent = {}
    for v in G:
        color[v] = 'white'
    color[node] = 'gray'
    depth[node] = 0
    parent[node] = None
    nodelist = [node]
    total_marked = 1
    while nodelist <> []:
        u = nodelist[0]
        nodelist.remove(nodelist[0])
        for neighbor in G[u]:
            if color[neighbor] == 'white':
                color[neighbor] = 'gray'
                depth[neighbor] = depth[u] + 1
                parent[neighbor] = u
                nodelist.append(neighbor)
                total_marked += 1
        color[u] = 'black'
    return total_marked, parent, depth

print BFS_iterative(G1, 'w')
print '================================='
print DFS_iterative(G1, 'w')