pylogeny.base module

Definitions for generalized containers and objects used by other structures in this framework.

pylogeny.base.longest_common_substring(s1, s2)

Simplified, traditional LCS algorithm implementation.

Returns:a string (longest common substring of s1, s2)

class pylogeny.base.patriciaTree

Bases: pylogeny.base.trie

Defines a PATRICIA tree (condensed trie) across a range of strings.

delete(seq)

Remove a sequence from the PATRICIA tree. Will not remove added characters to alphabet.

Parameters:seq – a sequence present in the trie

insert(seq)

Dynamically insert a sequence into the PATRICIA tree. Returns the unique index in the tree for that string.

search(seq)

Search for a sequence in the PATRICIA tree. Returns its position in addition sequence if it exists. Else, returns 0.

class pylogeny.base.treeBranch(parent=None, child=None, label='')

Bases: object

A branch in a tree.

__init__(parent=None, child=None, label='')

Instantiate this branch.

Parameters:

• parent (a treeNode object) – an optional parent node
• child (a treeNode object) – an optional child node
• label (a string) – an optional string label

getChild()

Return the child node of this branch.

Returns:a treeNode object

getLabel()

Return the label of this branch.

Returns:a string

getParent()

Return the parent node of this branch.

Returns:a treeNode object

setChild(c)

Set the child node of this branch.

Parameters:c (a treeNode object) – the child node of this object

setLabel(lbl)

Set the label of this branch.

Parameters:lbl (a string) – a string label

setParent(p)

Set the parent node of this branch.

Parameters:p (a treeNode object) – the parent node of this object

class pylogeny.base.treeNode(lbl=None, children=None, parent=None)

Bases: object

A node in a tree.

__init__(lbl=None, children=None, parent=None)

Initialize this tree node.

Parameters:

• lbl (a string) – an optional string to label this node
• children (a list of treeBranch objects) – an optional list of branches as children
• parent (a treeBranch object) – an optional branch to act as parent to this one

addChild(item)

Add a branch as a child.

Parameters:item (a treeBranch object) – a branch to add as a child

getChildByIndex(i)

Get a child branch by index in the list of children.

Parameters:i (an integer) – an index Returns:a treeBranch object

getChildren()

Return the list of children branch object.

Returns:a string

getLabel()

Return the label of this node.

Returns:a string

getParent()

Return the parent of this node.

Returns:a treeBranch object

isInternalNode()

Determine if this node is not a leaf (has children).

Returns:a boolean

isLeaf()

Determine if this node is a leaf (has no children).

Returns:a boolean

class pylogeny.base.treeStructure(root=None)

Bases: _abcoll.Container

Defines a base collection of treeNodes and treeBranches in a rooted, hierarchical tree structure.

__init__(root=None)

Initialize this tree structure.

Parameters:root (a treeNode object) – an optional node to root the tree with

getAllLeaves()

Acquire all leaf nodes for this structure.

Returns:a list of treeNode objects

getAllNodes()

Acquire all nodes for this structure.

Returns:a list of treeNode objects

getPostOrderTraversal()

getRoot()

Return the top-level, root, node of the tree.

Returns:a treeNode object

static leaves(root)

Static method to acquire all leaf nodes of a tree structure in order of how they are defined in children of nodes (DFS).

Parameters:root (a treeNode object) – a root node of a tree structure Returns:a list of treeNode objects

static nodes(root)

Static method to acquire all nodes of a tree structure in order of how they are defined in children of nodes (DFS).

Parameters:root (a treeNode object) – a root node of a tree structure Returns:a list of treeNode objects

static postOrderTraversal(root)

Static method to acquire all nodes of a tree structure as a post order traversal.

Parameters:root (a treeNode object) – a root node of a tree structure Returns:a list of treeNode objects

class pylogeny.base.trie

Bases: _abcoll.Sized, pylogeny.base.treeStructure

Defines a trie across a range of strings.

__init__()

Instantiate this trie as empty.

delete(seq)

Remove a sequence from the trie. Will not remove added characters to alphabet.

Parameters:seq – a sequence present in the trie

getAlphabet()

Acquire the unique alphabet of characters present across strings in this trie.

Returns:a list of characters

getRoot()

Get the root node of this trie.

Returns:a trieNode object

insert(seq)

Dynamically insert a sequence into the trie.

Returns:the label for this inserted sequence

search(seq)

Search for a sequence in the trie. Returns true if it exists.

Returns:a boolean

class pylogeny.base.trieNode(lbl=None, children=None, parent=None)

Bases: pylogeny.base.treeNode

A subclass of treeNode that allows for checking non-zero members amongst children branches and other conveniences.

getNonEmptyChildrenBranchLabels()

Acquire a list of labels for all non-empty children branches.

Returns:a list of strings

getNonEmptyChildrenBranches()

Acquire a list of all non-empty children branches.

Returns:a list of treeBranch objects

getNonEmptyChildrenNodes()

Acquire a list of all non-empty children nodes.

Returns:a list of treeNode objects

getParentNode()

Get the parent node of this node (assumes a parent branch).

Returns:the parent of the parent branch to this node

iterNonEmptyChildrenNodes()

Iterate over all children nodes that are not empty.

Returns:a generator yielding children treeNode objects

numEmptyChildrenNodes()

Acquire the number of children nodes that are marked 0 or nonexistent.

setChildNode(child, newchild)

Set a given child node (traversing branches along the way) of this node to a new object.

Parameters:

• child (a treeNode object) – a child node of this object
• newchild (a treeNode object) – the child node to replace