CODEWITHSUNDEEP
python
Rachel
Rachel

Reputation: 383

Finding the degree of an undirected graph

I am trying to find the degree distribution of an undirected graph. And I tried the following code:

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : []
        }

def generate_edges(graph):
    edges = []
    for node in graph:
        for neighbour in graph[node]:
            edges.append((node, neighbour))

    return edges

print(generate_edges(graph))

And my output is something like this : 

[('c', 'a'), ('c', 'b'), ('c', 'd'), ('c', 'e'), ('b', 'c'), ('b', 'e'), ('a', 'c'), ('e', 'c'), ('e', 'b'), ('d', 'c')]

I am trying to find the degree but I am not getting it. I need my output to be [1,2,2,0,1] which is a list, where the index value range from 0 to maximum degree in the graph(i.e in the above graph 4 is the maximum degree for "c") and the index values are number of nodes with degree equal to that index. ( in the above above graph, there is 1 node with 0 degrees,2 with 1 degree and again 2 with 2 degrees,none with 3 degree and finally 1 with 4 degree). Hence [1,2,2,0,4]. Can anyone help me with this without using NetworkX ?

Upvotes: 2

Views: 5886

Answers (3)

Kiwi
Kiwi

Reputation: 2816

Another solution using Counter :

from collections import Counter
a = Counter(map(len, graph.values())) # map with degree as key and number of nodes as value
out = [a[i] for i in range(max(a)+1)] # transform the map to a list

Upvotes: 1

vaultah
vaultah

Reputation: 46533

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : [] }

def max_length(x):
    return len(graph[x])

# Determine what index has the longest value
index = max(graph, key=max_length)
m = len(graph[index])

# Fill the list with `m` zeroes
out = [0 for x in range(m+1)]

for k in graph:
    l = len(graph[k])
    out[l]+=1

print(out)

Outputs [1, 2, 2, 0, 1]

Upvotes: 1

Sudeep Juvekar
Sudeep Juvekar

Reputation: 5068

You can find the degrees of individual nodes by simply finding lengths of each element's list.

all_degrees = map(len, graph.values())

This, in your case produces the individual degrees, not necessarily in same order as the elements.

[1, 4, 2, 2, 1, 0]

Next thing is simply frequency count in the list.

from collections import defaultdict
freq = defaultdict(int)
for i in all_degrees:
    freq[i] += 1
print freq
Out: defaultdict(<type 'int'>, {0: 1, 1: 2, 2: 2, 4: 1})

As expected, freq now gives count of each values which you can then print, append to list etc. You can simply print values of the dictionary freq as

print freq.values()

Returns the desired list [1, 2, 2, 0, 1]. Or you can create an empty list and append values to it as

out = list()
for i in range(max(all_degrees)+1):
   out.append(freq[i])

Again returns out = [1,2,2,0,1] - the required output.

Upvotes: 0

Related Questions