Question

Use a dictionary to represent a directed graph in which each key is a pair (tuple) of two nodes, with the corresponding value set to the edge weight.

For example, W[u,v] =42.

Where in u → v.

Write a function to calculate the in and out degree of a given node.

What would be the advantages and disadvantages of this representation?

in python

Answer 1

CODE

graph = {}

def addEdge(u, v, weight):

graph[(u, v)] = weight

def getDegree(u):

indegree = 0

outdegree = 0

for key in graph:

(a, b) = key

if a == u:

outdegree += 1

if b == u:

indegree += 1

return (indegree, outdegree)

addEdge('a','c', 1)

addEdge('b','c', 3)

addEdge('b','e', 4)

addEdge('c','d', 1)

addEdge('c','e', 1)

addEdge('c','a', 2)

addEdge('c','b', 3)

addEdge('e','b', 2)

addEdge('d','c', 4)

addEdge('e','c', 6)

(indegree, outdegree) = getDegree('a')

print(indegree)

print(outdegree)