CODEWITHSUNDEEP
pythongraph
rmcknst2
rmcknst2

Reputation: 307

How does this python code represent a weighted directed graph

I am trying to do some hw with Dijkstra algorithm but I am having trouble visualizing what this input would like as a graph. The code is python. How is that a graph?

example = [[(1, 1), (2, 2), (4, 3)], [(1, 3), (3, 4)], [(2, 3), (3, 5)], [(1, 4), (2, 5)], [], []]

Upvotes: 0

Views: 750

Answers (1)

Hugo Delahaye
Hugo Delahaye

Reputation: 141

I'm guessing that the ith element of the list example represents all the edges with weigth i. You can change the data structure of the graph to something else, like a dict where each key is a node and its value is the list of nodes it's connected to, with the corresponding weigths.

example = [[(1, 1), (2, 2), (4, 3)], [(1, 3), (3, 4)], [(2, 3), (3, 5)], [(1, 4), (2, 5)], [], []]

nodes = list(set([i for k in example for j in k for i in j ]))
arcs = [(i,example.index(j)) for j in example for i in j]

example_graph = {str(i):[] for i in nodes}
for i in arcs:
    example_graph[str(i[0][0])] += [(i[1],str(i[0][1]))]

print example_graph

This gives

example_graph = {'1': [(0, '1'), (1, '3'), (3, '4')],
                 '2': [(0, '2'), (2, '3'), (3, '5')],
                 '3': [(1, '4'), (2, '5')],
                 '4': [(0, '3')], 
                 '5': []}

Now you can implement the Dijkstra algorithm, here is an example I found :

from heapq import heappop,heappush    

def dijkstra(s, t, neighbors):
    M = set()
    d = {s: 0}
    p = {}
    new = [(0, s)] 
    while new != []:
        dx, x = heappop(new)
        if x in M:
            continue
        M.add(x)
        for w, y in neighbors(x):
            if y in M:
                continue
            dy = dx + w
            if y not in d or d[y] > dy:
                d[y] = dy
                heappush(new, (dy, y))
                p[y] = x
    path = [t]
    x = t
    while x != s:
        x = p[x]
        path.insert(0, x)
    return d[t], path

def neighbors(s,graph=example_graph):
    return graph[s]

For instance dijkstra('1', '4', neighbors) return (2, ['1', '3', '4'])

Upvotes: 1

Related Questions