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

for i in range(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
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))

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 = {}

for i in range(n):
for j in range(n):

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>

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):