SimpleGraph - deadlock

[escalopa]

Problem 🐞

There is a possible scenario when using the graph.SimpleGraph structure that might lead to a deadlock!

Let me explain

1. SimpleGraph.Adj takes a mutex.RLock().
2. Under the hood, SimpleGraph.Degree is called, which also takes mutex.RLock().
3. If mutex.Lock() is called between the 2 stages above (using SimpleGraph.AddEdge), then both functions get blocked forever.

A simple block of code demonstrates this issue (time.Sleep() is used to simulate the call order).

Solution ✅

• Create a sub function SimpleGraph.degree() that doesn't use RLock() (similar to SimpleGraph.addVertex().
• Move code of SimpleGraph.Degree() to the new function and leave only RLock() code.

code example with fix