Cographs

Detection

LinearCographDetector

Linear cograph detection and cotree construction.

References

1. D. G. Corneil, Y. Perl, and L. K. Stewart. A Linear Recognition Algorithm for Cographs. In: SIAM J. Comput., 14(4), 926-934 (1985). DOI: 10.1137/0214065

Source code in tralda/cograph/detection.py

class LinearCographDetector:
    """Linear cograph detection and cotree construction.

    References:
        1. D. G. Corneil, Y. Perl, and L. K. Stewart. A Linear Recognition Algorithm for Cographs.
           In: SIAM J. Comput., 14(4), 926-934 (1985). DOI: 10.1137/0214065
    """

    def __init__(self, graph: Any) -> None:
        """Constructor of LinearCographDetector class.

        Args:
            graph: A graph. Must implement ``nodes()``, ``has_edge()``, and ``neighbors()``
                (as in :class:`networkx.Graph`).
        """
        if not (
            hasattr(graph, "nodes") and hasattr(graph, "has_edge") and hasattr(graph, "neighbors")
        ):
            raise TypeError("graph must implement nodes(), has_edge(), and neighbors()")

        self.graph = graph
        self.V: list[Any] = [v for v in self.graph.nodes()]

        self.tree = Tree(None)
        self.already_in_tree: set[Any] = set()
        self.leaf_map: dict[Any, TreeNode] = {}
        self.node_counter = 0

        self.marked: set[TreeNode] = set()
        self.m_u_children: dict[
            TreeNode, list[TreeNode]
        ] = {}  # lists of marked and unmarked children
        self.mark_counter = 0
        self.unmark_counter = 0

        # md is set to zero for all new nodes including leaves as they are added to the tree
        self.md: dict[TreeNode, int] = defaultdict(int)

        self.error_message = ""

    def recognition(self) -> Tree | None:
        """Run cotree construction.

        Function COGRAPH-RECOGNITION from Corneil et al. 1985.

        Returns:
            The cotree representation of the graph, or None if it is not a cograph.
        """
        if len(self.V) == 0:
            return None
        elif len(self.V) == 1:
            self.tree.root = TreeNode(label=self.V[0])

            return self.tree

        v1, v2 = self.V[0], self.V[1]
        self.already_in_tree.update([v1, v2])

        R = TreeNode(label="series")
        self.tree.root = R

        if self.graph.has_edge(v1, v2):
            v1_node = TreeNode(label=v1)
            v2_node = TreeNode(label=v2)
            R.add_child(v1_node)
            R.add_child(v2_node)
            self.node_counter = 3
        else:
            N = TreeNode(label="parallel")
            R.add_child(N)
            v1_node = TreeNode(label=v1)
            v2_node = TreeNode(label=v2)
            N.add_child(v1_node)
            N.add_child(v2_node)
            self.node_counter = 4

        self.leaf_map[v1] = v1_node
        self.leaf_map[v2] = v2_node

        if len(self.V) == 2:
            self._remove_single_child_root()
            return self.tree

        for x in self.V[2:]:
            # initialization (necessary?)
            self.marked.clear()
            self.m_u_children.clear()
            self.mark_counter = 0
            self.unmark_counter = 0
            self.already_in_tree.add(x)  # add x for subsequent iterations

            self._mark(x)

            # all nodes in T were marked and unmarked
            if self.node_counter == self.unmark_counter:
                R = self.tree.root
                x_node = TreeNode(label=x)
                R.add_child(x_node)
                self.node_counter += 1
                self.leaf_map[x] = x_node
                continue
            # no nodes in T were marked and unmarked
            elif self.mark_counter == 0:
                # d(R)=1
                if len(self.tree.root.children) == 1:
                    N = self.tree.root.children[0]
                    x_node = TreeNode(label=x)
                    N.add_child(x_node)
                    self.node_counter += 1
                else:
                    R_old = self.tree.root
                    R_new = TreeNode(label="series")
                    N = TreeNode(label="parallel")
                    R_new.add_child(N)
                    N.add_child(R_old)
                    self.tree.root = R_new

                    x_node = TreeNode(label=x)
                    N.add_child(x_node)
                    self.node_counter += 3
                self.leaf_map[x] = x_node
                continue

            u = self._find_lowest()
            if not u:
                return

            # label(u)=0 and |A|=1
            if u.label == "parallel" and len(self.m_u_children[u]) == 1:
                w = self.m_u_children[u][0]
                if w.is_leaf():
                    new_node = TreeNode(label="series")
                    u.remove_child(w)
                    u.add_child(new_node)
                    new_node.add_child(w)

                    x_node = TreeNode(label=x)
                    new_node.add_child(x_node)
                    self.node_counter += 2
                else:
                    x_node = TreeNode(label=x)
                    w.add_child(x_node)
                    self.node_counter += 1

            # label(u)=1 and |B|=1
            elif u.label == "series" and len(u.children) - len(self.m_u_children[u]) == 1:
                set_A = set(self.m_u_children[u])  # auxiliary set bounded by O(deg(x))
                w = None
                for child in u.children:
                    if child not in set_A:
                        w = child
                        break
                if w.is_leaf():
                    new_node = TreeNode(label="parallel")
                    u.remove_child(w)
                    u.add_child(new_node)
                    new_node.add_child(w)

                    x_node = TreeNode(label=x)
                    new_node.add_child(x_node)
                    self.node_counter += 2
                else:
                    x_node = TreeNode(label=x)
                    w.add_child(x_node)
                    self.node_counter += 1

            else:
                y = TreeNode(label=u.label)
                for a in self.m_u_children[u]:
                    u.remove_child(a)
                    y.add_child(a)

                if u.label == "parallel":
                    new_node = TreeNode(label="series")
                    u.add_child(new_node)

                    new_node.add_child(y)
                    x_node = TreeNode(label=x)
                    new_node.add_child(x_node)
                else:
                    par = u.parent
                    if par is not None:  # u was the root of T
                        par.remove_child(u)
                        par.add_child(y)
                    else:
                        self.tree.root = y  # y becomes the new root

                    new_node = TreeNode(label="parallel")
                    y.add_child(new_node)
                    new_node.add_child(u)
                    x_node = TreeNode(label=x)
                    new_node.add_child(x_node)
                self.node_counter += 3

            self.leaf_map[x] = x_node

        self._remove_single_child_root()

        return self.tree

    def _mark(self, x: Any) -> None:
        """Function MARK from Corneil et al. 1985.

        Args:
            x: A node in the input graph.
        """
        for v in self.graph.neighbors(x):
            if v in self.already_in_tree:
                self.marked.add(self.leaf_map[v])
                self.mark_counter += 1

        queue = deque(self.marked)

        while queue:  # contains only d(u)=md(u) nodes
            u = queue.popleft()
            self.marked.remove(u)  # unmark u
            self.unmark_counter += 1
            self.md[u] = 0  # md(u) <- 0
            if u is not self.tree.root:
                w = u.parent  # w <- parent(u)
                if w not in self.marked:
                    self.marked.add(w)  # mark w
                    self.mark_counter += 1
                self.md[w] += 1
                if self.md[w] == len(w.children):
                    queue.append(w)

                # append u to list of marked and unmarked children of w
                if w in self.m_u_children:
                    self.m_u_children[w].appendleft(u)
                else:
                    self.m_u_children[w] = deque([u])

        if (
            self.marked  # any vertex remained marked
            and len(self.tree.root.children) == 1
            and self.tree.root not in self.marked
        ):
            self.marked.add(self.tree.root)
            self.mark_counter += 1

    def _find_lowest(self):
        """Function FIND-LOWEST from Corneil et al. 1985.

        This function checks whether G+x is a cograph and, if so, returns u, the lowest marked
        vertex of T.

        Returns:
            The lowest marked vertex in the current tree.
        """
        R = self.tree.root
        y = "Lambda"

        if R not in self.marked:  # R is not marked
            self.error_message = "(iii): R={}".format(R)
            return  # G+x is not a cograph (iii)
        else:
            if self.md[R] != len(R.children) - 1:
                y = R
            self.marked.remove(R)
            self.md[R] = 0
            u = w = R

        # while there are marked vertices choose a arbitrary marked vertex u
        while self.marked:
            u = self.marked.pop()

            if y != "Lambda":
                self.error_message = "(i) or (ii): y={}".format(y)
                return  # G+x is not a cograph (i) or (ii)

            if u.label == "series":
                if self.md[u] != len(u.children) - 1:
                    y = u
                if u.parent in self.marked:
                    self.error_message = "(i) and (vi): u={}".format(u)
                    return  # G+x is not a cograph (i) and (vi)
                else:
                    t = u.parent.parent
            else:
                y = u
                t = u.parent
            self.md[u] = 0  # u was already unmarked above

            # check if the u-w path is part of the legitimate alternating path
            while t is not w:
                if t is R:
                    self.error_message = "(iv): t={}".format(t)
                    return  # G+x is not a cograph (iv)

                if t not in self.marked:
                    self.error_message = "(iii), (v) or (vi): t={}".format(t)
                    return  # G+x is not a cograph (iii), (v) or (vi)

                if self.md[t] != len(t.children) - 1:
                    self.error_message = "(ii): t={}".format(t)
                    return  # G+x is not a cograph (ii)

                if t.parent in self.marked:
                    self.error_message = "(i): t={}".format(t)
                    return  # G+x is not a cograph (i)

                self.marked.remove(t)  # unmark t
                self.md[t] = 0  # reset md(t)
                t = t.parent.parent

            w = u  # rest w for next choice of marked vertex

        return u

    def _remove_single_child_root(self):
        """If necessary, remove the root that has only one child v and make v the new root."""
        if len(self.tree.root.children) == 1:
            new_root = self.tree.root.children[0]
            new_root.detach()
            self.tree.root = new_root

__init__(graph: Any) -> None

Constructor of LinearCographDetector class.

Parameters:

Name	Type	Description	Default
graph	Any	A graph. Must implement nodes(), has_edge(), and neighbors() (as in :class:networkx.Graph).	required

Source code in tralda/cograph/detection.py

def __init__(self, graph: Any) -> None:
    """Constructor of LinearCographDetector class.

    Args:
        graph: A graph. Must implement ``nodes()``, ``has_edge()``, and ``neighbors()``
            (as in :class:`networkx.Graph`).
    """
    if not (
        hasattr(graph, "nodes") and hasattr(graph, "has_edge") and hasattr(graph, "neighbors")
    ):
        raise TypeError("graph must implement nodes(), has_edge(), and neighbors()")

    self.graph = graph
    self.V: list[Any] = [v for v in self.graph.nodes()]

    self.tree = Tree(None)
    self.already_in_tree: set[Any] = set()
    self.leaf_map: dict[Any, TreeNode] = {}
    self.node_counter = 0

    self.marked: set[TreeNode] = set()
    self.m_u_children: dict[
        TreeNode, list[TreeNode]
    ] = {}  # lists of marked and unmarked children
    self.mark_counter = 0
    self.unmark_counter = 0

    # md is set to zero for all new nodes including leaves as they are added to the tree
    self.md: dict[TreeNode, int] = defaultdict(int)

    self.error_message = ""

recognition() -> Tree | None

Run cotree construction.

Function COGRAPH-RECOGNITION from Corneil et al. 1985.

Returns:

Type	Description
Tree | None	The cotree representation of the graph, or None if it is not a cograph.

Source code in tralda/cograph/detection.py

def recognition(self) -> Tree | None:
    """Run cotree construction.

    Function COGRAPH-RECOGNITION from Corneil et al. 1985.

    Returns:
        The cotree representation of the graph, or None if it is not a cograph.
    """
    if len(self.V) == 0:
        return None
    elif len(self.V) == 1:
        self.tree.root = TreeNode(label=self.V[0])

        return self.tree

    v1, v2 = self.V[0], self.V[1]
    self.already_in_tree.update([v1, v2])

    R = TreeNode(label="series")
    self.tree.root = R

    if self.graph.has_edge(v1, v2):
        v1_node = TreeNode(label=v1)
        v2_node = TreeNode(label=v2)
        R.add_child(v1_node)
        R.add_child(v2_node)
        self.node_counter = 3
    else:
        N = TreeNode(label="parallel")
        R.add_child(N)
        v1_node = TreeNode(label=v1)
        v2_node = TreeNode(label=v2)
        N.add_child(v1_node)
        N.add_child(v2_node)
        self.node_counter = 4

    self.leaf_map[v1] = v1_node
    self.leaf_map[v2] = v2_node

    if len(self.V) == 2:
        self._remove_single_child_root()
        return self.tree

    for x in self.V[2:]:
        # initialization (necessary?)
        self.marked.clear()
        self.m_u_children.clear()
        self.mark_counter = 0
        self.unmark_counter = 0
        self.already_in_tree.add(x)  # add x for subsequent iterations

        self._mark(x)

        # all nodes in T were marked and unmarked
        if self.node_counter == self.unmark_counter:
            R = self.tree.root
            x_node = TreeNode(label=x)
            R.add_child(x_node)
            self.node_counter += 1
            self.leaf_map[x] = x_node
            continue
        # no nodes in T were marked and unmarked
        elif self.mark_counter == 0:
            # d(R)=1
            if len(self.tree.root.children) == 1:
                N = self.tree.root.children[0]
                x_node = TreeNode(label=x)
                N.add_child(x_node)
                self.node_counter += 1
            else:
                R_old = self.tree.root
                R_new = TreeNode(label="series")
                N = TreeNode(label="parallel")
                R_new.add_child(N)
                N.add_child(R_old)
                self.tree.root = R_new

                x_node = TreeNode(label=x)
                N.add_child(x_node)
                self.node_counter += 3
            self.leaf_map[x] = x_node
            continue

        u = self._find_lowest()
        if not u:
            return

        # label(u)=0 and |A|=1
        if u.label == "parallel" and len(self.m_u_children[u]) == 1:
            w = self.m_u_children[u][0]
            if w.is_leaf():
                new_node = TreeNode(label="series")
                u.remove_child(w)
                u.add_child(new_node)
                new_node.add_child(w)

                x_node = TreeNode(label=x)
                new_node.add_child(x_node)
                self.node_counter += 2
            else:
                x_node = TreeNode(label=x)
                w.add_child(x_node)
                self.node_counter += 1

        # label(u)=1 and |B|=1
        elif u.label == "series" and len(u.children) - len(self.m_u_children[u]) == 1:
            set_A = set(self.m_u_children[u])  # auxiliary set bounded by O(deg(x))
            w = None
            for child in u.children:
                if child not in set_A:
                    w = child
                    break
            if w.is_leaf():
                new_node = TreeNode(label="parallel")
                u.remove_child(w)
                u.add_child(new_node)
                new_node.add_child(w)

                x_node = TreeNode(label=x)
                new_node.add_child(x_node)
                self.node_counter += 2
            else:
                x_node = TreeNode(label=x)
                w.add_child(x_node)
                self.node_counter += 1

        else:
            y = TreeNode(label=u.label)
            for a in self.m_u_children[u]:
                u.remove_child(a)
                y.add_child(a)

            if u.label == "parallel":
                new_node = TreeNode(label="series")
                u.add_child(new_node)

                new_node.add_child(y)
                x_node = TreeNode(label=x)
                new_node.add_child(x_node)
            else:
                par = u.parent
                if par is not None:  # u was the root of T
                    par.remove_child(u)
                    par.add_child(y)
                else:
                    self.tree.root = y  # y becomes the new root

                new_node = TreeNode(label="parallel")
                y.add_child(new_node)
                new_node.add_child(u)
                x_node = TreeNode(label=x)
                new_node.add_child(x_node)
            self.node_counter += 3

        self.leaf_map[x] = x_node

    self._remove_single_child_root()

    return self.tree

---

Editing

edit_to_cograph(graph: Any, run_number: int = 10) -> nx.Graph

Heuristic algorithm for optimal cograph editing.

Time complexity O(|V|^2).

Parameters:

Name	Type	Description	Default
graph	Any	A graph. Must implement nodes(), has_edge(), and neighbors() (as in :class:networkx.Graph).	required
run_number	int	Number of editing runs from which the best editing result is returned.	10

Returns:

Type	Description
Graph	The cograph that corresponds to the best editing result.

References

1. Christophe Crespelle (2021). Linear-Time Minimal Cograph Editing. In: Bampis, E., Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in Computer Science, vol 12867. Springer, Cham. DOI: 10.1007/978-3-030-86593-1_12

Source code in tralda/cograph/editing.py

def edit_to_cograph(graph: Any, run_number: int = 10) -> nx.Graph:
    """Heuristic algorithm for optimal cograph editing.

    Time complexity O(|V|^2).

    Args:
        graph: A graph. Must implement ``nodes()``, ``has_edge()``, and ``neighbors()`` (as in
            :class:`networkx.Graph`).
        run_number: Number of editing runs from which the best editing result is returned.

    Returns:
        The cograph that corresponds to the best editing result.

    References:
        1. Christophe Crespelle (2021). Linear-Time Minimal Cograph Editing. In: Bampis, E.,
           Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in
           Computer Science, vol 12867. Springer, Cham. DOI: 10.1007/978-3-030-86593-1_12
    """
    ce = CographEditor(graph)
    best_cotree = ce.cograph_edit(run_number=run_number)

    return to_cograph(best_cotree)

CographEditor

Heuristic for cograph editing running in O(|V|^2).

References

1. Christophe Crespelle (2021). Linear-Time Minimal Cograph Editing. In: Bampis, E., Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in Computer Science, vol 12867. Springer, Cham. DOI: 10.1007/978-3-030-86593-1_12

Source code in tralda/cograph/editing.py

class CographEditor:
    """Heuristic for cograph editing running in O(|V|^2).

    References:
        1. Christophe Crespelle (2021). Linear-Time Minimal Cograph Editing. In: Bampis, E.,
           Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in
           Computer Science, vol 12867. Springer, Cham. DOI: 10.1007/978-3-030-86593-1_12
    """

    def __init__(self, graph: Any) -> None:
        """Constructor of the CographEditor class.

        Args:
            graph: A graph. Must implement ``nodes()``, ``has_edge()``, and ``neighbors()``
                (as in :class:`networkx.Graph`).

        Raises:
            ValueError: If the provided graph is empty.
        """
        if not (
            hasattr(graph, "nodes") and hasattr(graph, "has_edge") and hasattr(graph, "neighbors")
        ):
            raise TypeError("graph must implement nodes(), has_edge(), and neighbors()")

        self.graph = graph
        self.V = [v for v in self.graph.nodes()]

        if len(self.V) == 0:
            raise ValueError("empty graph in cograph editing")

        self.cotrees = []
        self.costs = []

        self.best_tree = None
        self.best_cost = float("inf")

    def cograph_edit(self, run_number: int = 10) -> Tree:
        """Run the cograph editing.

        Args:
            run_number: Number of editing runs from which the best editing result is returned.

        Returns:
            The cotree, i.e., a Tree instance with inner vertex labels `"series"` and `"parallel"`,
                that corresponds to the best editing result.
        """
        for i in range(run_number):
            self.aux_counter = {}
            already_in_tree = set()
            leaf_map = {}
            total_cost = 0

            # shuffle the vertex list (beginning from second run)
            if i > 0:
                random.shuffle(self.V)

            # build starting tree for the first two vertices
            T = self._start_tree(already_in_tree, leaf_map)

            # incrementally insert vertices while updating total cost
            for x in self.V[2:]:
                cost, x_node = self._insert(x, T, already_in_tree, leaf_map)

                # update the number of leaves on the path to the root
                current = x_node.parent
                while current:
                    self.aux_counter[current] += 1
                    current = current.parent

                leaf_map[x] = x_node
                already_in_tree.add(x)
                total_cost += cost

            self.cotrees.append(T)
            self.costs.append(total_cost)

            # update the best cost
            if total_cost < self.best_cost:
                self.best_tree = T
                self.best_cost = total_cost

            # stop if original graph was a cograph, i.e., cost is 0
            if self.best_cost <= 0:
                break

        return self.best_tree

    def _start_tree(
        self,
        already_in_tree: set[Any],
        leaf_map: dict[Any, TreeNode],
    ) -> Tree:
        """Initialize tree with (at most) two leaves.

        Args:
            already_in_tree: Set of nodes in the graph that are already added to the tree.
            leaf_map: Dictionary mapping nodes in the graph to the corresponding leaf nodes in the
                tree.

        Returns:
            The initialized tree.
        """
        if len(self.V) == 1:
            return Tree(TreeNode(label=self.V[0]))

        tree = Tree(None)
        v1, v2 = self.V[0], self.V[1]
        already_in_tree.update([v1, v2])

        R = TreeNode(label="series")
        self.aux_counter[R] = 2
        tree.root = R

        if self.graph.has_edge(v1, v2):
            v1_node = TreeNode(label=v1)
            self.aux_counter[v1_node] = 1
            v2_node = TreeNode(label=v2)
            self.aux_counter[v2_node] = 1
            R.add_child(v1_node)
            R.add_child(v2_node)
        else:
            N = TreeNode(label="parallel")
            self.aux_counter[N] = 2
            R.add_child(N)
            v1_node = TreeNode(label=v1)
            self.aux_counter[v1_node] = 1
            v2_node = TreeNode(label=v2)
            self.aux_counter[v2_node] = 1
            N.add_child(v1_node)
            N.add_child(v2_node)

        leaf_map[v1] = v1_node
        leaf_map[v2] = v2_node

        return tree

    def _insert(
        self,
        x: Any,
        T: Tree,
        already_in_tree: set[Any],
        leaf_map: dict[Any, TreeNode],
    ) -> tuple[int, TreeNode]:
        """Insert the next node x into the tree.

        Args:
            x: The node from the input graph to be inserted.
            T: The current tree.
            already_in_tree: Set of nodes in the graph that are already added to the tree.
            leaf_map: Dictionary mapping nodes in the graph to the corresponding leaf nodes in the
                tree.

        Returns:
            The cost of the node insertion and the newly inserted leaf node.
        """
        # information for non-hollow nodes
        C_nh = {}  # node --> list of non-hollow children
        C_nh_number = {}  # node --> number of non-hollow children

        Nx_number = {}  # node --> number of neighbors of x in V(u)
        completion_forced = {}  # node --> completion-forced or not
        full = {}  # node --> full or not (i.e. mixed)
        deletion_forced = {}  # node --> deletion-forced or not

        Nx_counter = 0

        # ---- FIRST STEP ----

        # first traversal (C_nh)
        for v in self.graph.neighbors(x):
            if v not in already_in_tree:
                continue

            Nx_counter += 1

            v = leaf_map[v]
            C_nh[v] = []
            C_nh_number[v] = 0
            Nx_number[v] = 1
            completion_forced[v] = True
            full[v] = True
            deletion_forced[v] = False

            current = v
            while current.parent:
                if current.parent in C_nh:
                    C_nh[current.parent].append(current)
                    break  # rest of the path is already done
                else:
                    C_nh[current.parent] = [current]
                current = current.parent  # continue path to root

        # all nodes in T are adjacent to x
        if self.aux_counter[T.root] == Nx_counter:
            R = T.root
            x_node = TreeNode(label=x)
            self.aux_counter[x_node] = 1
            R.add_child(x_node)
            leaf_map[x] = x_node
            return 0, x_node  # cost is 0
        # no nodes in T are adjacent to x
        elif Nx_counter == 0:
            # d(R)=1
            if len(T.root.children) == 1:
                N = T.root.children[0]
                x_node = TreeNode(label=x)
                self.aux_counter[x_node] = 1
                N.add_child(x_node)
            else:
                R_old = T.root
                R_new = TreeNode(label="series")
                self.aux_counter[R_new] = self.aux_counter[R_old]
                N = TreeNode(label="parallel")
                self.aux_counter[N] = self.aux_counter[R_old]
                R_new.add_child(N)
                N.add_child(R_old)
                T.root = R_new

                x_node = TreeNode(label=x)
                self.aux_counter[x_node] = 1
                N.add_child(x_node)

            return 0, x_node  # cost is 0

        # second traversal, postorder
        # (C_nh_number, Nx_number, completion_forced, mixed, deletion_forced)
        stack = [T.root]
        while stack:
            u = stack.pop()
            if not u.children:
                continue
            elif u not in C_nh_number:
                stack.append(u)
                C_nh_number[u] = len(C_nh[u])
                for nh_child in C_nh[u]:
                    stack.append(nh_child)
            else:
                completion_forced_counter = 0
                deletion_forced_counter = 0
                full_counter = 0
                Nx_number[u] = 0
                for nh_child in C_nh[u]:
                    Nx_number[u] += Nx_number[nh_child]
                    if completion_forced[nh_child]:
                        completion_forced_counter += 1
                    if deletion_forced[nh_child]:
                        deletion_forced_counter += 1
                    if full[nh_child]:
                        full_counter += 1
                full[u] = True if Nx_number[u] == self.aux_counter[u] else False

                # u completion-forced?
                if (
                    full[u]
                    or (u.label == "parallel" and len(u.children) == C_nh_number[u])
                    or (u.label == "series" and len(u.children) == completion_forced_counter)
                ):
                    completion_forced[u] = True
                else:
                    completion_forced[u] = False

                # u deletion-forced?
                if (u.label == "series" and full_counter == 0) or (
                    u.label == "parallel" and C_nh_number[u] == deletion_forced_counter
                ):
                    deletion_forced[u] = True
                else:
                    deletion_forced[u] = False

        # ---- SECOND STEP ----
        cost_above = {}  # node u: cost above u
        C_mixed = {}  # node u: mixed children of u
        C_full = {}  # node u: full children of u

        stack = [T.root]
        while stack:
            u = stack.pop()
            C_mixed[u] = []
            C_full[u] = []
            for nh_child in C_nh[u]:
                if not full[nh_child]:  # only mixed nodes are considered
                    stack.append(nh_child)
                    C_mixed[u].append(nh_child)
                else:
                    C_full[u].append(nh_child)
            v = u.parent
            if not v:  # root has no parent
                cost_above[u] = 0
            elif u.parent.label == "parallel":
                cost_above[u] = cost_above[v] + Nx_number[v] - Nx_number[u]
            else:
                cost_above[u] = cost_above[v] + (
                    (self.aux_counter[v] - Nx_number[v]) - (self.aux_counter[u] - Nx_number[u])
                )

        mincost = {}

        for u in cost_above.keys():  # contains exactly the mixed nodes
            # apply Lemma 7 directly if u has exactly 2 children
            if len(u.children) == 2 and u.label == "parallel":
                for i in range(2):
                    v, v2 = u.children[i], u.children[-1 - i]
                    if v in completion_forced and completion_forced[v]:
                        Nx_v2 = Nx_number[v2] if (v2 in Nx_number) else 0
                        cost = cost_above[u] + (self.aux_counter[v] - Nx_number[v]) + Nx_v2
                        if (u not in mincost) or (cost < mincost[u][0]):
                            mincost[u] = (cost, [v])
            elif len(u.children) == 2 and u.label == "series":
                for i in range(2):
                    v, v2 = u.children[i], u.children[-1 - i]
                    if v not in deletion_forced or deletion_forced[v]:
                        Nx_v = Nx_number[v] if (v in Nx_number) else 0
                        Nx_v2 = Nx_number[v2] if (v2 in Nx_number) else 0
                        cost = cost_above[u] + Nx_v + (self.aux_counter[v2] - Nx_v2)
                        if (u not in mincost) or (cost < mincost[u][0]):
                            mincost[u] = (cost, [v2])

            # u has at least 3 children
            elif len(u.children) >= 3:
                red = set()
                blue = set()

                if u.label == "parallel":  # u is a parallel node
                    # (step 0)
                    if C_nh_number[u] == 1:  # clean child (single non-hollow)
                        v = C_nh[u][0]  # v is the single nh child of u
                        if completion_forced[v]:
                            cost = cost_above[u] + (self.aux_counter[v] - Nx_number[v])
                            mincost[u] = (cost, [v])
                        continue  # otherwise u is not a minimal insertion node (Lemma 8)

                    # first step
                    for v in C_mixed[u]:
                        if Nx_number[v] >= self.aux_counter[v] - Nx_number[v]:
                            red.add(v)
                        else:
                            blue.add(v)

                    # second step
                    if C_nh_number[u] == len(u.children) and not blue:
                        current_min, current_min_node = float("inf"), None
                        for v in red:
                            # the following equals:
                            # Nx_number[v] - (self.aux_counter[v] - Nx_number[v])
                            diff = 2 * Nx_number[v] - self.aux_counter[v]
                            if diff < current_min:
                                current_min, current_min_node = diff, v
                        red.remove(current_min_node)
                        blue.add(current_min_node)

                    # third step
                    nb_filled = len(C_full[u]) + len(red)
                    if nb_filled < 2:
                        for i in range(2 - nb_filled):
                            current_min, current_min_node = float("inf"), None
                            for v in blue:
                                # the following equals:
                                # (self.aux_counter[v] - Nx_number[v]) - Nx_number[v]
                                diff = self.aux_counter[v] - 2 * Nx_number[v]
                                if diff < current_min:
                                    current_min, current_min_node = diff, v
                            blue.remove(current_min_node)
                            red.add(current_min_node)
                else:  # u is a series node
                    # (step 0)
                    if len(u.children) - len(C_full[u]) == 1:  # clean child (single non-full)
                        v = None
                        for child in u.children:
                            if (child not in full) or (not full[child]):
                                v = child  # v is the single non-full child of u
                                break
                        if (v not in deletion_forced) or (deletion_forced[v]):
                            Nx_v = Nx_number[v] if v in Nx_number else 0
                            cost = cost_above[u] + Nx_v
                            mincost[u] = (cost, C_full[u])
                        continue  # otherwise u is not a minimal insertion node (Lemma 8)

                    # first step
                    for v in C_mixed[u]:
                        if self.aux_counter[v] - Nx_number[v] >= Nx_number[v]:
                            blue.add(v)
                        else:
                            red.add(v)

                    # second step
                    if not C_full[u] and not red:
                        current_min, current_min_node = float("inf"), None
                        for v in blue:
                            # the following equals:
                            # (self.aux_counter[v] - Nx_number[v]) - Nx_number[v]
                            diff = self.aux_counter[v] - 2 * Nx_number[v]
                            if diff < current_min:
                                current_min, current_min_node = diff, v
                        blue.remove(current_min_node)
                        red.add(current_min_node)

                    # third step
                    nb_hollowed = (
                        len(u.children) - C_nh_number[u] + len(blue)
                    )  # number of hollow or blue children
                    if nb_hollowed < 2:
                        for i in range(2 - nb_hollowed):
                            current_min, current_min_node = float("inf"), None
                            for v in red:
                                # the following equals:
                                # Nx_number[v] - (self.aux_counter[v] - Nx_number[v])
                                diff = 2 * Nx_number[v] - self.aux_counter[v]
                                if diff < current_min:
                                    current_min, current_min_node = diff, v
                            red.remove(current_min_node)
                            blue.add(current_min_node)

                cost = cost_above[u]
                for v in red:
                    cost += self.aux_counter[v] - Nx_number[v]
                for v in blue:
                    cost += Nx_number[v]

                mincost[u] = (cost, C_full[u] + list(red))

        # determine a minimum cost settling
        insertion_mincost, settling_node = float("inf"), None
        for u in mincost.keys():
            if mincost[u][0] < insertion_mincost:
                insertion_mincost, settling_node = mincost[u][0], u

        # insert x into tree
        u = settling_node  # node under which x is inserted
        filled = mincost[u][1]  # children of u to be filled (marked nodes in LinearCographDetector)

        # parallel node where one child is to be filled
        if u.label == "parallel" and len(filled) == 1:
            w = filled[0]
            if w.is_leaf():
                new_node = TreeNode(label="series")  # leaves w and x (x added later)
                self.aux_counter[new_node] = 1
                u.remove_child(w)
                u.add_child(new_node)
                new_node.add_child(w)

                x_node = TreeNode(label=x)
                self.aux_counter[x_node] = 1
                new_node.add_child(x_node)
            else:
                x_node = TreeNode(label=x)
                self.aux_counter[x_node] = 1
                w.add_child(x_node)

        # series node and only one child is not to be filled
        elif u.label == "series" and len(u.children) - len(filled) == 1:
            set_A = set(filled)  # auxiliary set
            w = None
            for child in u.children:
                if child not in set_A:
                    w = child
                    break
            if w.is_leaf():
                new_node = TreeNode(label="parallel")  # leaves w and x (x added later)
                self.aux_counter[new_node] = 1
                u.remove_child(w)
                u.add_child(new_node)
                new_node.add_child(w)

                x_node = TreeNode(label=x)
                self.aux_counter[x_node] = 1
                new_node.add_child(x_node)
            else:
                x_node = TreeNode(label=x)
                self.aux_counter[x_node] = 1
                w.add_child(x_node)

        else:
            filled_aux_counter = 0
            y = TreeNode(label=u.label)
            for a in filled:
                u.remove_child(a)
                y.add_child(a)
                filled_aux_counter += self.aux_counter[a]
            self.aux_counter[y] = filled_aux_counter

            if u.label == "parallel":
                new_node = TreeNode(label="series")
                self.aux_counter[new_node] = filled_aux_counter
                u.add_child(new_node)

                new_node.add_child(y)
                x_node = TreeNode(label=x)
                self.aux_counter[x_node] = 1
                new_node.add_child(x_node)
            else:
                par = u.parent
                if par is not None:  # u was the root of T
                    par.remove_child(u)
                    par.add_child(y)
                else:
                    T.root = y  # y becomes the new root

                new_node = TreeNode(label="parallel")
                self.aux_counter[new_node] = 0
                y.add_child(new_node)
                new_node.add_child(u)
                x_node = TreeNode(label=x)
                self.aux_counter[x_node] = 1
                new_node.add_child(x_node)

                # update the leaf numbers
                self.aux_counter[y] = self.aux_counter[u]
                self.aux_counter[u] -= filled_aux_counter
                self.aux_counter[new_node] = self.aux_counter[u]

        return insertion_mincost, x_node

__init__(graph: Any) -> None

Constructor of the CographEditor class.

Parameters:

Name	Type	Description	Default
graph	Any	A graph. Must implement nodes(), has_edge(), and neighbors() (as in :class:networkx.Graph).	required

Raises:

Type	Description
ValueError	If the provided graph is empty.

Source code in tralda/cograph/editing.py

def __init__(self, graph: Any) -> None:
    """Constructor of the CographEditor class.

    Args:
        graph: A graph. Must implement ``nodes()``, ``has_edge()``, and ``neighbors()``
            (as in :class:`networkx.Graph`).

    Raises:
        ValueError: If the provided graph is empty.
    """
    if not (
        hasattr(graph, "nodes") and hasattr(graph, "has_edge") and hasattr(graph, "neighbors")
    ):
        raise TypeError("graph must implement nodes(), has_edge(), and neighbors()")

    self.graph = graph
    self.V = [v for v in self.graph.nodes()]

    if len(self.V) == 0:
        raise ValueError("empty graph in cograph editing")

    self.cotrees = []
    self.costs = []

    self.best_tree = None
    self.best_cost = float("inf")

cograph_edit(run_number: int = 10) -> Tree

Run the cograph editing.

Parameters:

Name	Type	Description	Default
run_number	int	Number of editing runs from which the best editing result is returned.	10

Returns:

Type	Description
Tree	The cotree, i.e., a Tree instance with inner vertex labels "series" and "parallel", that corresponds to the best editing result.

Source code in tralda/cograph/editing.py

def cograph_edit(self, run_number: int = 10) -> Tree:
    """Run the cograph editing.

    Args:
        run_number: Number of editing runs from which the best editing result is returned.

    Returns:
        The cotree, i.e., a Tree instance with inner vertex labels `"series"` and `"parallel"`,
            that corresponds to the best editing result.
    """
    for i in range(run_number):
        self.aux_counter = {}
        already_in_tree = set()
        leaf_map = {}
        total_cost = 0

        # shuffle the vertex list (beginning from second run)
        if i > 0:
            random.shuffle(self.V)

        # build starting tree for the first two vertices
        T = self._start_tree(already_in_tree, leaf_map)

        # incrementally insert vertices while updating total cost
        for x in self.V[2:]:
            cost, x_node = self._insert(x, T, already_in_tree, leaf_map)

            # update the number of leaves on the path to the root
            current = x_node.parent
            while current:
                self.aux_counter[current] += 1
                current = current.parent

            leaf_map[x] = x_node
            already_in_tree.add(x)
            total_cost += cost

        self.cotrees.append(T)
        self.costs.append(total_cost)

        # update the best cost
        if total_cost < self.best_cost:
            self.best_tree = T
            self.best_cost = total_cost

        # stop if original graph was a cograph, i.e., cost is 0
        if self.best_cost <= 0:
            break

    return self.best_tree

---

Functions

to_cograph(cotree: Tree) -> nx.Graph

Returns the cograph corresponding to the cotree.

Parameters:

Name	Type	Description	Default
cotree	Tree	A cotree, i.e., a Tree instance with inner vertex labels 'series' and 'parallel'.	required

Returns:

Type	Description
Graph	The corresponding cograph with the leaf labels as vertices.

Source code in tralda/cograph/functions.py

def to_cograph(cotree: Tree) -> nx.Graph:
    """Returns the cograph corresponding to the cotree.

    Args:
        cotree: A cotree, i.e., a Tree instance with inner vertex labels 'series' and 'parallel'.

    Returns:
        The corresponding cograph with the leaf labels as vertices.
    """
    leaves = cotree.leaf_dict()
    graph = nx.Graph()

    for v in leaves[cotree.root]:
        graph.add_node(v.label)

    for u in cotree.preorder():
        if u.label != "series":
            continue

        for v1, v2 in itertools.combinations(u.children, 2):
            for l1, l2 in itertools.product(leaves[v1], leaves[v2]):
                graph.add_edge(l1.label, l2.label)

    return graph

to_cotree(graph: nx.Graph) -> Tree | None

Checks if a graph is a cograph and returns its cotree.

Linear O(|V| + |E|) implementation.

Parameters:

Name	Type	Description	Default
graph	Graph	A graph.	required

Returns:

Type	Description
Tree | None	The cotree representation of the graph, or None if it is not a cograph.

References

1. D. G. Corneil, Y. Perl, and L. K. Stewart. A Linear Recognition Algorithm for Cographs. In: SIAM J. Comput., 14(4), 926-934 (1985). DOI: 10.1137/0214065

Source code in tralda/cograph/functions.py

def to_cotree(graph: nx.Graph) -> Tree | None:
    """Checks if a graph is a cograph and returns its cotree.

    Linear O(|V| + |E|) implementation.

    Args:
        graph: A graph.

    Returns:
            The cotree representation of the graph, or None if it is not a cograph.

    References:
        1. D. G. Corneil, Y. Perl, and L. K. Stewart. A Linear Recognition Algorithm for Cographs.
           In: SIAM J. Comput., 14(4), 926-934 (1985). DOI: 10.1137/0214065
    """
    return LinearCographDetector(graph).recognition()

complement_cograph(cotree: Tree, inplace: bool = False) -> Tree

Returns the cotree of the complement cograph.

Parameters:

Name	Type	Description	Default
cotree	Tree	A cotree, i.e., a Tree instance with inner vertex labels 'series' and 'parallel'.	required

Returns:

Type	Description
Tree	The cotree of the complement cograph.

Raises:

Type	Description
ValueError	If the label is not 'series' and 'parallel' for any inner node.

Source code in tralda/cograph/functions.py

def complement_cograph(cotree: Tree, inplace: bool = False) -> Tree:
    """Returns the cotree of the complement cograph.

    Args:
        cotree: A cotree, i.e., a Tree instance with inner vertex labels 'series' and 'parallel'.

    Returns:
        The cotree of the complement cograph.

    Raises:
        ValueError: If the label is not 'series' and 'parallel' for any inner node.
    """
    tree = cotree if inplace else cotree.copy()

    for v in tree.inner_nodes():
        if v.label == "series":
            v.label = "parallel"
        elif v.label == "parallel":
            v.label = "series"
        else:
            raise ValueError(f"inner node has label '{v.label}', must be 'series' or 'parallel'")

    return tree

random_cotree(number_of_leaves: int, force_series_root: bool = False) -> Tree

Creates a random cotree.

Parameters:

Name	Type	Description	Default
number_of_leaves	int	The number of leaves in the resulting tree.	required
force_series_root	bool	If True, the cograph of the resulting cotree will be connected, otherwise it may be disconnected.	False

Returns:

Type	Description
Tree	A cotree, i.e., a Tree instance with inner vertex labels 'series' and 'parallel'.

Source code in tralda/cograph/functions.py

def random_cotree(number_of_leaves: int, force_series_root: bool = False) -> Tree:
    """Creates a random cotree.

    Args:
        number_of_leaves: The number of leaves in the resulting tree.
        force_series_root: If True, the cograph of the resulting cotree will be connected, otherwise
            it may be disconnected.

    Returns:
        A cotree, i.e., a Tree instance with inner vertex labels 'series' and 'parallel'.
    """
    cotree = Tree.random_tree(number_of_leaves)

    # assign labels ('series', 'parallel')
    for v in cotree.preorder():
        if v.is_leaf():
            continue
        elif v.parent is None:
            if force_series_root:
                v.label = "series"
            else:
                v.label = "series" if random.random() < 0.5 else "parallel"
        else:
            v.label = "series" if v.parent.label == "parallel" else "parallel"

    return cotree

cluster_deletion(cograph: nx.Graph | Tree) -> list[list[Any]]

Cluster deletion for cographs.

Returns a partition of a cograph into disjoint cliques with a minimal number of edges between the cliques.

Parameters:

Name	Type	Description	Default
cograph	Graph | Tree	The cograph (as a graph or cotree) for which cluster deletion shall be performed.	required

Returns:

Type	Description
list[list[Any]]	A partition where each sublist corresponds to a clique in a solution of the cluster deletion problem.

Raises:

Type	Description
ValueError	If the input is not a valid cograph or cotree.

References

1. Gao Y, Hare DR, Nastos J (2013) The cluster deletion problem for cographs. Discrete Math 313(23):2763-2771, DOI: 10.1016/j.disc.2013.08.017.
2. Schaller D, Lafond M, Stadler PF, Wieseke N, Hellmuth M (2020) Indirect Identification of Horizontal Gene Transfer. Journal of Mathematical Biology 83(10), DOI: 10.1007/s00285-021-01631-0

Source code in tralda/cograph/functions.py

def cluster_deletion(cograph: nx.Graph | Tree) -> list[list[Any]]:
    """Cluster deletion for cographs.

    Returns a partition of a cograph into disjoint cliques with a minimal number of edges between
    the cliques.

    Args:
        cograph: The cograph (as a graph or cotree) for which cluster deletion shall be performed.

    Returns:
        A partition where each sublist corresponds to a clique in a solution of the cluster deletion
            problem.

    Raises:
        ValueError: If the input is not a valid cograph or cotree.

    References:
        1. Gao Y, Hare DR, Nastos J (2013) The cluster deletion problem for cographs. Discrete Math
           313(23):2763-2771, DOI: 10.1016/j.disc.2013.08.017.
        2. Schaller D, Lafond M, Stadler PF, Wieseke N, Hellmuth M (2020) Indirect Identification
           of Horizontal Gene Transfer. Journal of Mathematical Biology 83(10),
           DOI: 10.1007/s00285-021-01631-0
    """
    cotree = cograph if isinstance(cograph, Tree) else to_cotree(cograph)

    if not cotree:
        raise ValueError("not a valid cograph/cotree")

    partition = {}

    for u in cotree.postorder():
        partition[u] = []
        if not u.children:
            partition[u].append([u.label])

        elif u.label == "parallel":
            for v in u.children:
                partition[u].extend(partition[v])

            # naive sorting can be replaced by k-way merge-sort
            partition[u].sort(key=len, reverse=True)

        elif u.label == "series":
            for v in u.children:
                for i, Q_i in enumerate(partition[v]):
                    if i >= len(partition[u]):
                        partition[u].append([])
                    partition[u][i].extend(Q_i)

        else:
            raise ValueError("invalid cotree")

    return partition[cotree.root]

complete_multipartite_completion(cograph: nx.Graph | Tree, supply_graph: bool = False) -> list[list[Any]] | tuple[list[list[Any]], nx.Graph]

Complete multipartite graph completion for cographs.

Returns a partition of the vertex set corresponding to the (maximal) independent sets in an optimal edge completion of the cograph to a complete multipartite graph.

Parameters:

Name	Type	Description	Default
cograph	Graph | Tree	The cograph (as a graph or cotree) for which complete multipartite graph completion shall be performed.	required
supply_graph	bool	If True, the solution is additionally returned as a NetworkX Graph.	False

Returns:

Type	Description
list[list[Any]] | tuple[list[list[Any]], Graph]	A partition where each sublist corresponds to a (maximal) independent set in a solution of the complete multipartite graph completion problem. And, optionally, the solution as a graph.

Raises:

Type	Description
ValueError	If the input is not a valid cograph or cotree.

Source code in tralda/cograph/functions.py

def complete_multipartite_completion(
    cograph: nx.Graph | Tree,
    supply_graph: bool = False,
) -> list[list[Any]] | tuple[list[list[Any]], nx.Graph]:
    """Complete multipartite graph completion for cographs.

    Returns a partition of the vertex set corresponding to the (maximal) independent sets in an
    optimal edge completion of the cograph to a complete multipartite graph.

    Args:
        cograph: The cograph (as a graph or cotree) for which complete multipartite graph completion
            shall be performed.
        supply_graph: If True, the solution is additionally returned as a NetworkX Graph.

    Returns:
        A partition where each sublist corresponds to a (maximal) independent set in a solution of
            the complete multipartite graph completion problem. And, optionally, the solution as a
            graph.

    Raises:
        ValueError: If the input is not a valid cograph or cotree.
    """
    cotree = cograph if isinstance(cograph, Tree) else to_cotree(cograph)

    if not cotree:
        raise ValueError("not a valid cograph/cotree")

    # complete multipartite graph completion is equivalent to cluster deletion in the complement
    # cograph
    compl_cotree = complement_cograph(cotree, inplace=False)

    # clusters are then equivalent to the maximal independent sets
    independent_sets = cluster_deletion(compl_cotree)

    if not supply_graph:
        return independent_sets
    else:
        return (independent_sets, complete_multipartite_graph_from_sets(independent_sets))