Find articulation points/ cut vertices in graph

Question

I would like to get some feedback on my completed code that finds and displays the articulation vertices in an undirected graph.

I included a test case within the code, it should (and does) print c as the only articulation vertex.

Also I would like to clarify my understanding on some things,

1. This runs in \$\mathcal{O}(V+E)\$ time

2. In the final line of code I do, low_vis[vertex] = min(low_vis[neighbour], discovered[vertex])

   Does it make a difference if I use the fixed discovered position as shown above, or the lowest reachable visited vertex position (low_vis), my own tests showed no difference and the same answer was returned (c).

Thank you

class vertex:
 def __init__(self, key):
 self.neighbours = {}
 self.key = key
 
 def add(self, key, edge):
 self.neighbours[key] = edge
class graph:
 def __init__(self):
 self.root = {}
 self.nbnodes = 0
 self.curr = 0
 def add(self, key1, key2, edge=0):
 if key1 not in self.root:
 self.root[key1] = vertex(key1)
 self.nbnodes += 1
 if key2 not in self.root:
 self.root[key2] = vertex(key2)
 self.nbnodes += 1
 self.root[key1].add(key2, edge)
 self.root[key2].add(key1, edge)
 
 def cutver(self):
 
 visited = set()
 discovered = {}
 low_vis = {}
 parent = {}
 result = []
 for vertex in self.root:
 if vertex not in visited:
 parent[vertex] = -1
 self._cutver(vertex, parent, visited, discovered, low_vis, result)
 print(result)
 
 def _cutver(self, vertex, parent, visited, discovered, low_vis, result):
 visited.add(vertex)
 discovered[vertex] = self.curr
 low_vis[vertex] = self.curr
 children = 0
 self.curr += 1
 for neighbour in self.root[vertex].neighbours:
 if neighbour not in visited:
 parent[neighbour] = vertex
 children += 1
 self._cutver(neighbour, parent, visited, discovered, low_vis, result)
 low_vis[vertex] = min(low_vis[vertex], low_vis[neighbour])
 if children > 1 and parent[vertex] == -1:
 result.append(vertex) 
 
 if parent[vertex] != -1 and low_vis[neighbour] >= discovered[vertex]: 
 result.append(vertex)
 
 elif neighbour != parent[vertex]:
 low_vis[vertex] = min(low_vis[neighbour], discovered[vertex])
 
if __name__ == '__main__':
 a = graph()
 A = 'A'
 B = 'B'
 C = 'C'
 D = 'D'
 E = 'E'
 a.add(A,B)
 a.add(A,C)
 a.add(B,D)
 a.add(D,C)
 a.add(C,E)
 a.cutver()

Answer 1

PEP-8

class vertex:
class graph:

PEP-8 asks that you name these Vertex and Graph, with initial capital.

naming nodes

 self.key = key

Yes, you will be using this as a dict key. But name would have been the more natural identifier for a node name.

unused attribute

Please delete this line:

 self.nbnodes = 0

That quantity may be trivially obtained with len(self.root), and in any event you never reference it.

edge weight

At first blush this appears to be a default edge ID of zero:

def add(self, key1, key2, edge=0):

Later it looks more like an edge weight, an attribute of the edge. It would be helpful for a docstring to clarify this. Or just name it edge_weight.

API

Consider having cutver() print nothing, and instead return a result which the caller may print.

Also, _cutver() feels a lot like a Fortran subroutine, as it has side effects on the result parameter, rather than returning a result.

sentinel

You use this:

 parent[vertex] = -1

without every verifying that a node name is not -1, or constraining each node name to be a str. The usual convention would be to use None to represent this.

docstring

 self.curr = 0

This is absolutely not self-descriptive enough. Use a """docstring""" or # comment to tell us what quantity it is measuring.

reference

In general _cutver() is obscure, which increases the difficulty of answering your two questions. It cites no references and does not attempt to justify any of its algorithmic steps. Perhaps it correctly finds cut vertices, but the text does not give us any reason to see why that is obviously true. If the code tries to adhere to Hopcroft73 (with Tarjan, algorithm 447), then choosing to omit identifiers like lowpoint is not helping the reader to see how the current implementation corresponds to what Hopcroft describes.