Directed graph nodes: Keep track of successors and predecessors

Question

I am trying to implement a class Node representing a node in a directed graph, which in particular has a set of successors and predecessors. I would like Node.predecessors and Node.predecessors to behave like sets, in particular I want to iterate over their elements, add and remove elements, check containment, and set them from an iterable. However, after node_1.sucessors.add(node_2) it should be True that node_1 in node_2.pedecessors.

It seems possible to write a new subclass of set that implements this magic, but as far as I see an implementation of such a class would be quite cumbersome, because it would have to know about the Node object it belongs to and if it is a predecessor or successor and would need some special methods for addition and so on, so that node_1.sucessors.add(node_2) will not call node_2.predecessors.add(node_1) and thus lead to an infinite loop.

Generating one of the two attributes on the fly (node for node in all_nodes if self in node.sucessors) should be possible, but then I need to keep track of all Nodes belonging to a graph, which is easy (adding it to a weakref.WeakSet class attribute in __init__) if I have only one graph, but using one big set for all nodes leads to large computational effort if I have multiple disjoint graphs, and I do not see how to modify the set of predecessors.

Does anybody have a good solution for this?

Answer 1

What if you wrap the add method in your class and then inside that wrapper method you just use the two attributes predecessors and sucessors. Something like this

That's the first solution that would come to my mind:

class Node:

    def __init__(self):
        self.pred = set()
        self.suce = set()

    def addSucessor(self, node):
        self.suce.add(node)
        node.pred.add(self)