GraphsAndLabyrinths.sagews

︠de5aa988-75f8-4960-a660-a453cdb53179s︠
G = Graph(3)
G

Graph on 3 vertices

plot(G)

︠203590be-d963-4fb1-afe7-ac9a31a88f83s︠
G.add_edge((0,1))
plot(G)

︠7de6b95b-c08a-415b-b923-fea225aadff8s︠
def labyrinthGraph(n,m):
    G = Graph()
    G.add_vertices([(i,j) for i in xrange(n) for j in xrange(m)])
    G.add_edges([((i,j),(i+1,j)) for i in xrange(n-1) for j in xrange(m)])
    G.add_edges([((i,j),(i,j+1)) for i in xrange(n) for j in xrange(m-1)])
    return G
def showLabyrinthGrid(G):
    return G.plot(pos={v:v for v in G.vertices()})

def showSpanningTree(ST):
    G = Graph()
    G.add_edges(ST)
    return showLabyrinthGrid(G)

L3_4 = labyrinthGraph(3,4)
showLabyrinthGrid(L3_4)

L3_4.edges()

[((0, 0), (0, 1), None), ((0, 0), (1, 0), None), ((0, 1), (0, 2), None), ((0, 1), (1, 1), None), ((0, 2), (0, 3), None), ((0, 2), (1, 2), None), ((0, 3), (1, 3), None), ((1, 0), (1, 1), None), ((1, 0), (2, 0), None), ((1, 1), (1, 2), None), ((1, 1), (2, 1), None), ((1, 2), (1, 3), None), ((1, 2), (2, 2), None), ((1, 3), (2, 3), None), ((2, 0), (2, 1), None), ((2, 1), (2, 2), None), ((2, 2), (2, 3), None)]

ST = L3_4.random_spanning_tree()
showSpanningTree(ST)