def makeG(N):
if n == 1:
return <a single node>
g1 = makeG(n / 2)
g2 = makeG(n / 2)
for i in range(log(n)):
i1 = <random node from g1 without replacement>
i2 = <random node from g2 without replacement>
make_link(G, i1, i2)
return G
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):
marked = {}
mark_component(G, v1, marked)
def make_line(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
