Data Structure & Algorithm Takeaway: C3 Linearisation

WarningWhat is C3 linearisation?

C3 linearisation is an algorithm to linearise a special kind of DAG (Directed Acyclic Graph). In DAG, the parent-child relationship exists, and linearisation is to give an 1D order of the nodes following that correct relationship. For this algorithm, the parents of a node has an predefined order itself, and the linearisation must follow this order as well.

WarningWhat are the input and output of C3 linearisation?

Inputs: A DAG $G=(V,E,\sigma )$, where the direct parent nodes for each node $v$ has an order $\sigma (v)$ (called local precedence order).

Outputs: An order of all parent nodes for each node $v$: $l(v)$, which satisfies:

• Preservation of local precedence order: the order of each $\sigma (v)$ must be consistent with $l(v)$

• Monotonicity: if $a$ is a parent node of $b$, then $l(a)$ must be consistent with $l(b)$

• Preservation of extended local precedence order: if $a<b$ in a certain local precedence order $\sigma (v)$, then for any child node $a^{\prime }$ as to $a$, $b^{\prime }$ as to $b$, $l(v)$ must keep the order that $a^{\prime }<b^{\prime }$.

WarningIs this output unique?

Yes, it is unique as long as it exists.

There are conditions on $G$ that guarantee its existence and uniqueness, but serious discussion goes too much into the maths. Please refer to the original paper. But there are some obvious situations that lead to non-existence:

• The graph is cyclic, i.e. there is a cycle in the graph.
• There are conflicting local precedence orders among sibling nodes.

WarningWhat are the real applications of C3 linearisation?

C3 linearisation is originally designed for resolving the problem of multiple inheritance in object-oriented programming languages, such as Dylan and Python. It is used to determine the method resolution order (MRO) in these languages.

The relationship among classes with multiple inheritance can be represented as a DAG, where each class is a node and the inheritance relationship is a directed edge. C3 linearisation provides a way to determine the order in which methods should be resolved when there are multiple parent classes.

An example of C3 linearisation. (Source: GeeksForGeeks)

For example, in the above figure, if a method appears in multiple parent classes of class $Z$ but not in $Z$ itself, when $Z$ calls this method, it searches through its parent classes in the order of $l(Z)$, and use the first occurrence of the method.

Python uses C3 linearisation to determine the method resolution order (MRO) for classes with multiple inheritance. You can use built-in methods C.mro() or C.__mro__ to get the MRO of a class $C$. Moreover, the super() in Python also find the first parent following the MRO.

However, many other languages such as C++ don’t have this feature.