Skip to content

BaseTree

Dataclass for the tree toplogy of a B cell lineage tree.

Attributes:

Name Type Description
T Digraph

a rooted tree

root str

the unique identifier of the root
id (int, optional)

the identifier of the tree
name (str, optional)

the name of the tree
Source code in tribal/base_tree.py 
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
@dataclass
class BaseTree:
    """Dataclass for the tree toplogy of a B cell lineage tree.

    Attributes
    ----------
    T : nx.Digraph
        a rooted tree 
    root : str
        the unique identifier of the root
    id : int, optional
        the identifier of the tree
    name : str, optional
        the name of the tree
    """

    T: nx.DiGraph
    root: str
    id: int = 0
    name: str = None


    def postorder_traversal(self) -> list:
        """
        Perform a postorder traversal of the tree.

        Postorder traversal means visiting the children nodes first, and then the parent node.

        Returns
        -------
        list
            List of nodes in postorder.
        """
        return list(nx.dfs_postorder_nodes(self.T, source=self.root))

    def preorder_traversal(self) -> list:
        """
        Perform a preorder traversal of the tree.

        Preorder traversal means visiting the parent node first, and then the children nodes.

        Returns
        -------
        list
            List of nodes in preorder.
        """
        return list(nx.dfs_preorder_nodes(self.T, source=self.root))

    def nodes(self):
        """Return the list of nodes of the tree."""
        return list(self.T.nodes)

    def edges(self):
        """Return the list of edges of the tree."""
        return list(self.T.edges)

    def parent(self, n):
        """Get the parent node of the given node.

        Parameters
        ----------
        n : node
            The node for which to find the parent.

        Returns
        -------
        str | None
            The parent node if it exists, otherwise None.
        """
        preds = list(self.T.predecessors(n))
        if len(preds) == 0:
            return None

        return preds[0]

    def relabel(self, labels):
        """Relabels a tree in place.

        Parameters
        ----------
        labels : dict
            a dictionary with current nodes as keys and new labels as values. May include only 
            a subset of nodes.
        """
        self.T = nx.relabel_nodes(self.T, labels)
        if self.root in labels:
            self.root = labels[self.root]

    def children(self,n):
        """Return the set of children of a specified node `n`."""
        return list(self.T.neighbors(n))

    def is_leaf(self, node):
        """Check if node is a leaf of the tree.

        Parameters
        ----------
        node : str | int
            a node in the lineage tree

        Returns
        -------
        bool
            leaf status of the specified node 
        """
        return self.T.out_degree(node) ==0

    def get_leafs(self):
        """Return the leafset of the lineage tree."""
        return [n for n in self.T if self.is_leaf(n)]

    def is_root(self, node):
        """Check if node is the root.

        Parameters
        ----------
        node : str | int
            a node in the lineage tree

        Returns
        -------
        bool
            indicator if the node is the root

        """
        if type(node) == int:
            node =str(node)
        return node == self.root

    def get_parents(self):
        """Obtain the parent of each node.

        Returns
        -------
        dict
            node as key and parent node as child. "" indicates no parent, i.e., the root.
        """
        parents = {}
        for n in self.T:
            parent = self.parent(n)
            if parent is not None:
                parents[n] = parent
        return parents

    def set_id(self,id):
        """Update the id of the tree.

        Parameters
        -------
        id : str,int
            the new id of the tree
        """
        self.id =id

    def set_name(self, name):
        """Update the name of the tree.

        Parameters
        -------
        name : str
            the new id of the tree
        """
        self.name= name

    @staticmethod
    def find_leaf_descendants(node, graph):
        """Obtain all descendants of a node in a graph that is a leaf.

        Parameters
        ----------
        node : str, int
        graph : nx.DiGraph

        Returns
        -------
            the set of leaf descendants

        """
        leaf_descendants = set()

        # Helper function to traverse the graph
        def dfs(current_node):
            nonlocal leaf_descendants
            # If the current node is a leaf, add it to the set
            if graph.out_degree(current_node) == 0:
                leaf_descendants.add(current_node)
            else:
                # Traverse all child nodes recursively
                for child_node in graph.successors(current_node):
                    dfs(child_node)

        # Start the depth-first search from the specified node
        dfs(node)
        return leaf_descendants

    def get_clade_set(self, tree):
        """Get the clades of the tree."""
        clade_set = []
        for node in tree:
            clade_set.append(self.find_leaf_descendants(node, tree))

        return(set(map(frozenset, clade_set)))


    def save_edges(self, fname):
        """Write the edge list to a file.

        Parameters
        ----------
        fname : str
            the file where the edge list should be saved.
        """
        with open(fname, "w+") as file:
            for u,v in self.T.edges:
                file.write(f"{u},{v}\n")

    def get_edge_df(self):
        """Get the edge list as a pandas.DataFrame."""
        u_list =[u for u,v in self.T.edges]
        v_list = [v for u,v in self.T.edges]
        return DataFrame({'parent': u_list, 'child': v_list})

children(n)

Return the set of children of a specified node n.

Source code in tribal/base_tree.py 
96
97
98
def children(self,n):
    """Return the set of children of a specified node `n`."""
    return list(self.T.neighbors(n))

edges()

Return the list of edges of the tree.

Source code in tribal/base_tree.py 
60
61
62
def edges(self):
    """Return the list of edges of the tree."""
    return list(self.T.edges)

find_leaf_descendants(node, graph) staticmethod

Obtain all descendants of a node in a graph that is a leaf.

Parameters:

Name Type Description Default
node (str, int)
required
graph DiGraph
required

Returns:

Type Description
the set of leaf descendants
Source code in tribal/base_tree.py 
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
@staticmethod
def find_leaf_descendants(node, graph):
    """Obtain all descendants of a node in a graph that is a leaf.

    Parameters
    ----------
    node : str, int
    graph : nx.DiGraph

    Returns
    -------
        the set of leaf descendants

    """
    leaf_descendants = set()

    # Helper function to traverse the graph
    def dfs(current_node):
        nonlocal leaf_descendants
        # If the current node is a leaf, add it to the set
        if graph.out_degree(current_node) == 0:
            leaf_descendants.add(current_node)
        else:
            # Traverse all child nodes recursively
            for child_node in graph.successors(current_node):
                dfs(child_node)

    # Start the depth-first search from the specified node
    dfs(node)
    return leaf_descendants

get_clade_set(tree)

Get the clades of the tree.

Source code in tribal/base_tree.py 
203
204
205
206
207
208
209
def get_clade_set(self, tree):
    """Get the clades of the tree."""
    clade_set = []
    for node in tree:
        clade_set.append(self.find_leaf_descendants(node, tree))

    return(set(map(frozenset, clade_set)))

get_edge_df()

Get the edge list as a pandas.DataFrame.

Source code in tribal/base_tree.py 
224
225
226
227
228
def get_edge_df(self):
    """Get the edge list as a pandas.DataFrame."""
    u_list =[u for u,v in self.T.edges]
    v_list = [v for u,v in self.T.edges]
    return DataFrame({'parent': u_list, 'child': v_list})

get_leafs()

Return the leafset of the lineage tree.

Source code in tribal/base_tree.py 
115
116
117
def get_leafs(self):
    """Return the leafset of the lineage tree."""
    return [n for n in self.T if self.is_leaf(n)]

get_parents()

Obtain the parent of each node.

Returns:

Type Description
dict

node as key and parent node as child. "" indicates no parent, i.e., the root.
Source code in tribal/base_tree.py 
137
138
139
140
141
142
143
144
145
146
147
148
149
150
def get_parents(self):
    """Obtain the parent of each node.

    Returns
    -------
    dict
        node as key and parent node as child. "" indicates no parent, i.e., the root.
    """
    parents = {}
    for n in self.T:
        parent = self.parent(n)
        if parent is not None:
            parents[n] = parent
    return parents

is_leaf(node)

Check if node is a leaf of the tree.

Parameters:

Name Type Description Default
node str | int

a node in the lineage tree

 required

Returns:

Type Description
bool

leaf status of the specified node
Source code in tribal/base_tree.py 
100
101
102
103
104
105
106
107
108
109
110
111
112
113
def is_leaf(self, node):
    """Check if node is a leaf of the tree.

    Parameters
    ----------
    node : str | int
        a node in the lineage tree

    Returns
    -------
    bool
        leaf status of the specified node 
    """
    return self.T.out_degree(node) ==0

is_root(node)

Check if node is the root.

Parameters:

Name Type Description Default
node str | int

a node in the lineage tree

 required

Returns:

Type Description
bool

indicator if the node is the root
Source code in tribal/base_tree.py 
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
def is_root(self, node):
    """Check if node is the root.

    Parameters
    ----------
    node : str | int
        a node in the lineage tree

    Returns
    -------
    bool
        indicator if the node is the root

    """
    if type(node) == int:
        node =str(node)
    return node == self.root

nodes()

Return the list of nodes of the tree.

Source code in tribal/base_tree.py 
56
57
58
def nodes(self):
    """Return the list of nodes of the tree."""
    return list(self.T.nodes)

parent(n)

Get the parent node of the given node.

Parameters:

Name Type Description Default
n node

The node for which to find the parent.

 required

Returns:

Type Description
str | None

The parent node if it exists, otherwise None.
Source code in tribal/base_tree.py 
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
def parent(self, n):
    """Get the parent node of the given node.

    Parameters
    ----------
    n : node
        The node for which to find the parent.

    Returns
    -------
    str | None
        The parent node if it exists, otherwise None.
    """
    preds = list(self.T.predecessors(n))
    if len(preds) == 0:
        return None

    return preds[0]

postorder_traversal()

Perform a postorder traversal of the tree.

Postorder traversal means visiting the children nodes first, and then the parent node.

Returns:

Type Description
list

List of nodes in postorder.
Source code in tribal/base_tree.py 
30
31
32
33
34
35
36
37
38
39
40
41
def postorder_traversal(self) -> list:
    """
    Perform a postorder traversal of the tree.

    Postorder traversal means visiting the children nodes first, and then the parent node.

    Returns
    -------
    list
        List of nodes in postorder.
    """
    return list(nx.dfs_postorder_nodes(self.T, source=self.root))

preorder_traversal()

Perform a preorder traversal of the tree.

Preorder traversal means visiting the parent node first, and then the children nodes.

Returns:

Type Description
list

List of nodes in preorder.
Source code in tribal/base_tree.py 
43
44
45
46
47
48
49
50
51
52
53
54
def preorder_traversal(self) -> list:
    """
    Perform a preorder traversal of the tree.

    Preorder traversal means visiting the parent node first, and then the children nodes.

    Returns
    -------
    list
        List of nodes in preorder.
    """
    return list(nx.dfs_preorder_nodes(self.T, source=self.root))

relabel(labels)

Relabels a tree in place.

Parameters:

Name Type Description Default
labels dict

a dictionary with current nodes as keys and new labels as values. May include only a subset of nodes.

 required
Source code in tribal/base_tree.py 
83
84
85
86
87
88
89
90
91
92
93
94
def relabel(self, labels):
    """Relabels a tree in place.

    Parameters
    ----------
    labels : dict
        a dictionary with current nodes as keys and new labels as values. May include only 
        a subset of nodes.
    """
    self.T = nx.relabel_nodes(self.T, labels)
    if self.root in labels:
        self.root = labels[self.root]

save_edges(fname)

Write the edge list to a file.

Parameters:

Name Type Description Default
fname str

the file where the edge list should be saved.

 required
Source code in tribal/base_tree.py 
212
213
214
215
216
217
218
219
220
221
222
def save_edges(self, fname):
    """Write the edge list to a file.

    Parameters
    ----------
    fname : str
        the file where the edge list should be saved.
    """
    with open(fname, "w+") as file:
        for u,v in self.T.edges:
            file.write(f"{u},{v}\n")

set_id(id)

Update the id of the tree.

Parameters:

Name Type Description Default
id (str, int)

the new id of the tree

 required
Source code in tribal/base_tree.py 
152
153
154
155
156
157
158
159
160
def set_id(self,id):
    """Update the id of the tree.

    Parameters
    -------
    id : str,int
        the new id of the tree
    """
    self.id =id

set_name(name)

Update the name of the tree.

Parameters:

Name Type Description Default
name str

the new id of the tree

 required
Source code in tribal/base_tree.py 
162
163
164
165
166
167
168
169
170
def set_name(self, name):
    """Update the name of the tree.

    Parameters
    -------
    name : str
        the new id of the tree
    """
    self.name= name