graph.py

class Graph:
    def __init__(self):
        self.childrenchildren = {}  # dictionnary giving the list of childrens for each node.
        self.qq = []  # configuration associated to each node.
        self.connexconnex = []  # ID of the connex component the node is belonging to.
        self.nconnexnconnex = 0  # number of connex components.
        self.existing_connexexisting_connex = []  # List of existing connex component ID.
 
    def add_node(self, q=None, new_connex=False):
        """
        Create the memory to store a new edge. Initialize all components to None.
        Create an empty list of children.
        """
        idx = len(self.childrenchildren)
        self.childrenchildren[idx] = []
        self.qq.append(q)
        self.connexconnex.append(None)
        if new_connex:
            self.new_connexnew_connex(idx)
        return idx
 
    def add_edge(self, first, second, orientation=0):
        """
        Add edge from first to second. Also add edge from second to first if orientation
        is null.
        """
        assert first in self.childrenchildren and second in self.childrenchildren
        if orientation >= 0:
            self.childrenchildren[first].append(second)
        if orientation <= 0:
            self.childrenchildren[second].append(first)
 
    def new_connex(self, idx):
        """
        Create a new connex component for node <idx>
        """
        self.connexconnex[idx] = self.nconnexnconnex
        self.existing_connexexisting_connex.append(self.nconnexnconnex)
        self.nconnexnconnex += 1
 
    def rename_connex(self, past, future):
        """
        Change the index of the all the nodes belonging to a connex component.
        Useful when merging two connex components.
        """
        try:
            self.existing_connexexisting_connex.remove(past)
            self.connexconnex = [c if c != past else future for c in self.connexconnex]
        except:  # noqa: E722
            pass
 
    def connexIndexes(self, connex):
        """
        Return the list of all node indexes belonging to connex component <connex>.
        """
        return [i for i, c in enumerate(self.connexconnex) if c == connex]