Is there a map or graph module?

[Elaine Jackson]

"""
Hopefully some of the following will help you. The idea is to implement weighted
digraphs as dictionaries: the keys are edges and the values are weights. If
direction is not important in a particular graph, you can 'bidirectionalize' it
(see below). If weights are not important, just ignore them. Since the only
important property of a vertex is its name, the sensible thing is to build
graphs whose vertices are self-referring strings: a function is provided that
declares any number of such vertices at the same time. Another function returns
all the edges of the cyclic digraph with specified vertices. The exercises at
the bottom are from Discrete Mathematics and its Applications by Kenneth Rosen.
"""

def declareVertices(strg):
    from string import split
    for name in split(strg,','):
        globals()[name]=name

cycleEdges = lambda *X: [(X[i],X[(i+1)%len(X)]) for i in range(len(X))]

def bidirectionalize(graph):
    converse = dict([((b,a),graph[a,b]) for (a,b) in graph.keys()])
    graph.update(converse)

def vertexSet(graph):
    A=[a for (a,b) in graph.keys()]
    B=[b for (a,b) in graph.keys()]
    X=A+B
    return [X[i] for i in range(len(X)) if X[i] not in X[0:i]]

def neighbors(a,graph):
    leftNeighbors=[b for b in vertexSet(graph) if (b,a) in graph.keys()]
    rightNeighbors=[b for b in vertexSet(graph) if (a,b) in graph.keys()]
    X=leftNeighbors+rightNeighbors
    return [X[i] for i in range(len(X)) if X[i] not in X[0:i]]

def dijkstra(origin,graph):
    infinity = sum(graph.values())+1
    reVal =  {origin:0}
    A = lambda y: [x for x in reVal.keys() if (x,y) in graph.keys()]
    B = lambda y: (A(y) and min([reVal[x]+graph[x,y] for x in A(y)])) \
                    or infinity
    while [y for y in vertexSet(graph) if y not in reVal.keys()]:
        C = [(y,B(y)) for y in vertexSet(graph) if y not in reVal.keys()]
        m = min([pair[1] for pair in C])
        reVal.update(dict([(y,z) for (y,z) in C if z==m]))
    return reVal

def kruskal(graph):
    forest=[[x] for x in vertexSet(graph)]
    freeEdges=graph.keys()
    takenEdges=[]
    while len(forest)>1:
        minWeight=min([graph[edge] for edge in freeEdges])
        A = lambda edge: graph[edge]==minWeight
        B = lambda edge: [x for x in forest if edge[0] in x or edge[1] in x]
        edge=filter((lambda edge: A(edge) and len(B(edge))==2),freeEdges)[0]
        freeEdges.remove(edge)
        takenEdges.append(edge)
        newTree=B(edge)[0]+B(edge)[1]
        forest=[x for x in forest if x not in B(edge)]
        forest.append(newTree)
    return takenEdges

####################################################
####################################################

"""
#################################
## Rosen; Section 7.6; Exercise 4
#################################

declareVertices('a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z')

graph = {                                          \
    (a,b):2, (a,c):4, (a,d):1, (b,c):3, (b,e):1,   \
    (c,e):2, (c,f):2, (d,f):5, (d,g):4, (e,h):3,   \
    (f,g):3, (f,h):3, (f,i):2, (f,j):4, (g,k):2,   \
    (h,l):1, (h,o):8, (i,j):3, (i,l):3, (i,m):2,   \
    (j,k):6, (j,m):6, (j,n):3, (k,n):4, (k,r):2,   \
    (l,m):3, (l,o):6, (m,n):5, (m,o):4, (m,p):2,   \
    (n,q):2, (n,r):1, (o,p):2, (o,s):6, (p,q):1,   \
    (p,s):2, (p,t):1, (q,r):8, (q,t):3, (r,t):8,   \
    (s,z):2, (t,z):8                               \
    }

distances = dijkstra(a,graph)
X = distances.keys()
X.sort()
for vertex in X: print vertex, ": ", distances[vertex]
"""

####################################################
####################################################

"""
#################################
## Rosen; Section 8.6; Exercise 3
#################################

declareVertices('a,b,c,d,e,f,g,h,i,j,k,l')

graph = {                                 \
    (a,b):2, (b,c):3, (c,d):1,            \
    (a,e):3, (b,f):1, (c,g):2, (d,h):5,   \
    (e,f):4, (f,g):3, (g,h):3,            \
    (e,i):4, (f,j):2, (g,k):4, (h,l):3,   \
    (i,j):3, (j,k):3, (k,l):1             \
    }

totalWeight = lambda tree,graph: sum([graph[edge] for edge in tree])
spanTree=kruskal(graph)
print totalWeight(spanTree,graph)
"""