cs215 ยป

Lecture 4: Ring Network

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

# Make an empty graph
a_ring = {}

n = 5

# Add in the edges
for i in range(n):
    make_link(a_ring, i, (i+1)%n)
# How many nodes? 
print len(a_ring)

# How many edges? 
print sum([len(a_ring[node]) for node in a_ring.keys()])/2

print a_ring

Lecture 5: Grid Network

import math
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

# Make an empty graph
G = {}    

n = 256
side = int(math.sqrt(n))

# Add in the edges
for i in range(side):
    for j in range(side):
        if i < side-1: make_link(G, (i,j), (i+1, j))
        if j < side-1: make_link(G, (i,j), (i, j+1))

# How many nodes? 
print len(G)

# How many edges? 
print sum([len(G[node]) for node in G.keys()])/2

Lecture 16: Complete Graph

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

#
# How many edges in a complete graph on n nodes?
#

def clique(n):
    # Return the number of edges
    # Try to use a mathematical formula...

    # Make an empty graph
    G = {}

    # Add in the edges
    for i in range(n):
        for j in range(n):
            if i<j: make_link(G, i, j)

    return sum([len(G[node]) for node in G.keys()])/2

for n in range(1,10):
    print n, clique(n), n*(n-1)/2

Lecture 21: Recursive Graphs (Pseudo-Code)

def makeG(n):

    if n == 1: return <a single node>

    G1 = makeG(n/2)
    G2 = makeG(n/2)

    i1 = <random node from G1 without replacement>
    i2 = <random node from G2 without replacement>

    make_link(G, i1, i2)

    return G

Lecture 25: Tangled Hypercube (Pseudo-Code)

def makeG(n):

    if n == 1: return <a single node>

    G1 = makeG(n/2)
    G2 = makeG(n/2)

    i1 = <list of nodes of G1 in random order>
    i2 = <list of nodes of G2 in random order>

    for i in range(n/2):
        make_link(G, i1[i], i2[i])

    return G