Counting single degree vertex removal rounds (from a graph)

Question

Problem:

In this problem I had to remove all vertices with degree one from a given graph in rounds and count how many rounds are required to remove all possible vertices with degree 1.
e.g. 1-2-3-4 Remove 1 and 4 in round 1. Remove 2 and 3 in round 2.
e.g. we can't Remove any vertex here. Total 0 rounds.

1---2
 \ /
  3

So here is how I solve:

---

Logic:

• Create an adjaceny list adj.
• Create a degree sets dl with dl[i] containing all vertices with degree i.
• Remove all vertices of degree one and remove their adjacency list. I do not update the degree or adjacency list of it's neighbors upon removal but only after the round has completed. For this I use a map/dictionary dec such that dec[x][0] are the neighbors of the single degree vertex x whose adjacency list and degree needs to be updated while dec[x][1] is the amount of degree reduction.
• If we have non-zero single degree vertices then I first pop() them and update values of their dec value.
• Finally for each vertex who needs to be updated, I move it from one degree set to another and update it's adjacency list.
• Finally I increase round count and then I print it.

Note: Sometimes the single degree vertices may appear in pair like 1-2 then while pop(ping) it has already been removed so no need to update in last.

---

Code:

Please see Codeforces 192B for input description which is basically n(number of nodes), m(number of edges) and next m lines the edges.

from collections import defaultdict


n, m = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(m)]
adj = defaultdict(set)
for e in E:
    adj[e[0]].add(e[1])
    adj[e[1]].add(e[0])
dl = defaultdict(set)
for v in adj:
    dl[len(adj[v])].add(v)
if len(dl[1]) == 0:
    print('0')
else:
    cnt = 0
    while len(dl[1]) > 0:
        dec = defaultdict(lambda: [list(), 0])
        while len(dl[1]) > 0:
            v = dl[1].pop()
            for v2 in adj[v]:     
                dec[v2][0].append(v)
                dec[v2][1] += 1                                      
            del adj[v]
        for v2 in dec:
            if v2 in dl[len(adj[v2])]:
                dl[len(adj[v2])].remove(v2)
                dl[len(adj[v2]) - dec[v2][1]].add(v2)     
                for x in dec[v2][0]:  
                    adj[v2].remove(x)    
        cnt += 1
    print(cnt)

---

Questions:

• I have switched from a different language so my methods may not be very 'Pythonic' or exploiting advantages of 'Python' over others. Can you help?
• Other improvements, if any?

Answer 1

Naming

Explicit names can go a long way in conveying what a piece of code does. Combine that with unpacking and explicit assignments to name parts of sequences, you can get:

from collections import defaultdict


n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
adjacents = defaultdict(set)
for node1, node2 in edges:
    adjacent[node1].add(node2)
    adjacent[node2].add(node1)

degrees = defaultdict(set)
for node, neighbours in adjacents.items():
    degrees[len(neighbours].add(node)

if len(degrees[1]) == 0:
    print('0')
else:
    count = 0
    while len(degrees[1]) > 0:
        dec = defaultdict(lambda: [list(), 0])  # Can't figure out a good name for that
        singles = degrees[1]
        while len(singles) > 0:
            single = singles.pop()
            for node in adjacent[single]:
                dec[node][0].append(single)
                dec[node][1] += 1
            del adjacent[single]
        for node, (neighbours, count_neighbours) in dec.items():
            node_degree = len(adjacent[node])
            if node in degrees[node_degree]:
                degrees[node_degree].remove(node)
                degrees[node_degree - count_neighbours].add(node)
                for neighbour in neighbours:
                    adjacent[node].remove(neighbour)
        count += 1
    print(count)

Quick simplifications

We can see from there that some parts are unnecessary complicated: for node in adjacent(single) does not need to be a loop as there must be only one node adjacent to a node with degree 1. You can use unpacking to exctract this value; it will also let you ensure that there was actually only one value there:

while len(singles) > 0:
    single = singles.pop()
    neighbour, = adjacent[single]  # Do not forget the comma here
    del adjacent[single]
    dec[neighbour][0].append(single)
    dec[neighbour][1] += 1

You also have if len(degrees[1]) == 0: ... else: while len(degrees[1]) > 0 which are pretty much the same thing. You can remove the if, if there is no node of degree 1, then the while won't execute and count will still be 0.

Pythonic constructs

Every containers (lists, dicts, strings, sets, …) are considered False in a boolean context if they are empty and True otherwise. Which mean you should write while degrees[1]: or if not degrees[1].

You may also have noticed the use of dict.items() to iterate over both the keys and the values of a dictionnary at the same time. It is more efficient than using the key to retrieve the values latter.

You also don't really need to build a list of edges before building the dictionnary of adjacent nodes:

from collections import defaultdict


_, m = map(int, input().split())

adjacents = defaultdict(set)
for _ in range(m):
    node1, node2 = map(int, input().split())
    adjacent[node1].add(node2)
    adjacent[node2].add(node1)

degrees = defaultdict(set)
for node, neighbours in adjacents.items():
    degrees[len(neighbours].add(node)

count = 0
while degrees[1]:
    dec = defaultdict(lambda: [list(), 0])  # Can't figure out a good name for that
    singles = degrees[1]
    while singles:
        single = singles.pop()
        for node in adjacent[single]:
            dec[node][0].append(single)
            dec[node][1] += 1
        del adjacent[single]
    for node, (neighbours, count_neighbours) in dec.items():
        node_degree = len(adjacent[node])
        if node in degrees[node_degree]:
            degrees[node_degree].remove(node)
            degrees[node_degree - count_neighbours].add(node)
            for neighbour in neighbours:
                adjacent[node].remove(neighbour)
    count += 1

print(count)

Adding and removing nodes

You spend quite a lot of time moving nodes around in various lists and dictionaries. You could simplify the whole thing by using a more straightforward approach:

• you only need to keep track of the nodes with degree 1
• for each of these nodes:
  • remove it from its neighbour list of neighbours
  • if this neighbour now has degree 1, keep track of if in a temporary set
• when done, iterate with the new set of nodes with degree 1.

from collections import defaultdict


_, m = map(int, input().split())

adjacents = defaultdict(set)
for _ in range(m):
    node1, node2 = map(int, input().split())
    adjacent[node1].add(node2)
    adjacent[node2].add(node1)

singles = {node for node, neighbours in adjacents.items() if len(neighbours) == 1}
count = 0
while singles:
    new_singles = set()
    for single in singles:
        neighbour, = adjacents[single]
        adjacents[neighbour].remove(single)
        if len(adjacents[neighbour]) == 1:
            new_singles.add(neighbour)
        # del adjacents[single] if you whish but it has no added value here
    singles = new_singles
    count += 1

print(count)

Functions

Using can help make things faster as Python resolves local symbols faster than global ones. But mainly recommended to organise the flow of things better and reuse parts of code.

You should also wrap the top-level code that you don't want to put in a function under an if __name__ == '__main__' clause:

from collections import defaultdict


def remove_singles(adjacents):
    singles = {node for node, neighbours in adjacents.items()
               if len(neighbours) == 1}

    passes = 0
    while singles:
        new_singles = set()
        for single in singles:
            neighbour, = adjacents[single]
            adjacents[neighbour].remove(single)
            if len(adjacents[neighbour]) == 1:
                new_singles.add(neighbour)

        singles = new_singles
        passes += 1

    return passes


if __name__ == '__main__':
    _, m = map(int, input().split())

    graph = defaultdict(set)
    for _ in range(m):
        node1, node2 = map(int, input().split())
        graph[node1].add(node2)
        graph[node2].add(node1)

    print(remove_singles(graph))