Python graph representation

Question

if I have a directed graph whose vertices are denoted by {1,2,3,...} and the connections between them are like this:(meaning there is a directed edge from b to a represented as a<-b)

List1: 1<-2<-3<-4<-5<-6
List2: 2<-4<-7<-6
List3: 1<-8<-7
List4: 1<-9<-2

The degree of vertex 4 is 2 (since it has a edge to 3 and 2), degree of 6 is 2 and so on. How can I compute this and store this in a dictionary in python as shown below:

dict = {}
dict{4:'2', 6:'2'}

like this. Thanks in advance.

My input looks like this : words[] = ['4777', '2516', '4637', '1221', '38803', '56203']. Where each element is connected by a directed edge to its previous element. — Nikhil
– Nikhil, Commented Apr 18, 2016 at 17:00
what's the degree of 7 in that input? Given 4777 and 4637, is it 4 or 2? — Tony Babarino
– Tony Babarino, Commented Apr 18, 2016 at 17:15

C Panda · Accepted Answer · 2016-04-18 17:16:55Z

1

Try the following,

l1 = [1, 2, 3, 4, 5, 6]
l2 = [2, 4, 7, 6]
l3 = [1,8,7]
l4 = [1, 9, 2]

from collections import defaultdict
d = defaultdict(list)

for l in [l1, l2, l3, l4]:
    for i,n in enumerate(l):
         if i:
             d[n].append(l[i-1])
In [144]: d
Out[144]:
defaultdict(list,
        {2: [1, 9],
         3: [2],
         4: [3, 2],
         5: [4],
         6: [5, 7],
         7: [4, 8],
         8: [1],
         9: [1]})

You can do all the operations on defaultdict that you can on dict. So if you want to count the degrees,

degree = {k: len(v) for k,v in d.items()}
In [146]: degree
Out[146]: {2: 2, 3: 1, 4: 2, 5: 1, 6: 2, 7: 2, 8: 1, 9: 1}

answered Apr 18, 2016 at 17:16

C Panda

3,4352 gold badges13 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Nikhil Over a year ago

hey what are 144 and 146 here? I am sorry I am new to this concept

C Panda Over a year ago

@Nikhil They are part of the terminal prompt.Not part of code.

C Panda Over a year ago

@Nikhil You will have >>> Type >>> d or >>> degrees

Collectives™ on Stack Overflow

Python graph representation

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related