class3.txt~

Degrees and Paths in Graphs


Clique:

degree O(n) in relation to the number of nodes
path (longest path from one node to another node) O(1)

Ring:

degree O(1)
path O(n)

Balanced Tree:

degree O(1)
path O(logn)

Hypercube:

degree O(logn)
path O(logn)





CLUSTERING COEFFICIENT


CC(v):

V: a node
Kv: its degree
Nv: number of links between the neighbors of V


CC(v) = (2*Nv)/(Kv*(Kv-1))

This represents the fraction of possible interconnections

It has to be between 0 and 1. 0 if you have a star and 1 if you have a clique


CC(G) (clustering coefficient for a graph) = average of all CC(v)










DEPTH FIRST SEARCH


DFS RECURSIVE:
5.
##################################################################
# Traversal...
# Call this routine on nodes being visited for the first time
def mark_component(G, node, marked):
    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)
    return v2 in marked
    
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)
    assert check_connection(G, "a", "c") == True
    assert check_connection(G, 'a', 'b') == False
    
    
    
    
    
    
BREADTH FIRST SEARCH 
AND DFS NON RECURSIVE (with open list)




FINDING BRIDGE EDGES

1) Build tree out of graph
2) Post-order nodes
3) Compute Number of descendants for each node in the graph (green edges only)
4) Lowest: green/one red
5) Highest: green/one red
6) Bridge edge:
    has a green number (#5) that is smaller or equal to black number (post-order nodes, #2) AND the red number (#4) is bigger than blue number (#3) minus black number
    

    
    
    
    






HOMEWORK


6.

# Rewrite `mark_component` to not use recursion 
# and instead use the `open_list` data structure 
# discussed in lecture
#

RECURSIVE VERSION
def mark_component(G, node, marked):
    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
    


NON RECURSIVE:

# Rewrite `mark_component` to not use recursion 
# and instead use the `open_list` data structure 
# discussed in lecture
#

def mark_component(G, node, marked):
    open_list = [node]
    total_marked = 0
    
    while open_list:
        current_node = open_list.pop(0)
        marked[current_node] = True
        total_marked += 1
        
        for neighbor in G[current_node]:
            if neighbor in marked:
                continue
            
            if neighbor not in open_list:
                open_list.append(neighbor)
    
    return total_marked

#########
# Code for testing
#
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():
    test_edges = [(1, 2), (2, 3), (4, 5), (5, 6)]
    G = {}
    for n1, n2 in test_edges:
        make_link(G, n1, n2)
    marked = {}
    assert mark_component(G, 1, marked) == 3
    assert 1 in marked
    assert 2 in marked
    assert 3 in marked
    assert 4 not in marked
    assert 5 not in marked
    assert 6 not in marked



PROF's answer:

def mark_component(G, node, marked):
    open_list = [node]
    total_marked = 1
    marked[node] = True
    while len(open_list) > 0:
        node = open_list.pop()
        for neighbor in G[node]:
            if neighbor not in marked:
                open_list.append(neighbor)
                marked[neighbor] = True
                total_marked += 1
    return total_marked
    
    
    
    
    
    
    
    
    



















7.
CENTRALITY AVERAGE

def centrality(G,v):
    distance_from_start = {}
    open_list = [v]
    distance_from_start[v] = 0
    while  len(open_list) > 0:
        current = open_list[0]
        del open_list[0]
        for neighbor in G[current].keys():
            if neighbor not in distance_from_start:
                distance_from_start[neighbor] = distance_from_start[current] + 1
                open_list.append(neighbor)
    return (sum(distance_from_start.values())+0.0)/len(distance_from_start)
    
    
CENTRALITY MAX


#
# Write centrality_max to return the maximum distance
# from a node to all the other nodes it can reach
#

def centrality_max(G,v):
    distance_from_start = {}
    open_list = [v]
    distance_from_start[v] = 0
    while open_list:
        current = open_list.pop(0)
        for neighbor in G[current]:
            if neighbor not in distance_from_start:
                distance_from_start[neighbor] = distance_from_start[current] + 1
                open_list.append(neighbor)
    return max(distance_from_start.values())
        

#################
# Testing code
#
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

chain = ((1,2), (2,3), (3,4), (4,5), (5,6))
G = {}
for n1, n2 in chain:
    make_link(G, n1, n2)

print centrality_max(G, 1)        

def test():
    chain = ((1,2), (2,3), (3,4), (4,5), (5,6))
    G = {}
    for n1, n2 in chain:
        make_link(G, n1, n2)
    assert centrality_max(G, 1) == 5
    assert centrality_max(G, 3) == 3
    tree = ((1, 2), (1, 3),
            (2, 4), (2, 5),
            (3, 6), (3, 7),
            (4, 8), (4, 9),
            (6, 10), (6, 11))
    G = {}
    for n1, n2 in tree:
        make_link(G, n1, n2)
    assert centrality_max(G, 1) == 3
    assert centrality_max(G, 11) == 6