graphs

package
v1.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 22, 2026 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

Package containing all structs and functions related to graph-like data structures used in CAMUS such as quartets, networks, and trees

Index

Constants

View Source 
const (
	Ui = iota // index of u and w in reticulation array
	Wi
)
View Source 
const (
	NilQuartet = 0
	NTaxa      = 4

	Qtopo1 = uint8(0b1100) // three quartet topologies
	Qtopo2 = uint8(0b1010)
	Qtopo3 = uint8(0b0110)

	// Possible results for quartet comparison
	Qneq  = iota // quartets equal
	Qeq          // quartets not equal
	Qdiff        // quartets on different taxa set
)

Variables

View Source 
var (
	ErrTipNameMismatch = errors.New("tip name mismatch! maybe the gene tree and constraint tree labels don't match?")
	ErrInvalidQuartet  = errors.New("invalid newick for quartet")
)

Functions

func GetChildren 

func GetChildren(node *tree.Node) []*tree.Node

Get children of node

func MapIDsFromConstTree 

func MapIDsFromConstTree(gtre, tre *tree.Tree) ([]int16, error)

func QSetToString 

func QSetToString(qSet map[Quartet]uint32, tre *tree.Tree) string

func QuartetsFromTree 

func QuartetsFromTree(tre, constTree *tree.Tree) (map[Quartet]uint32, error)

Returns hashmap containing quartets from tree

Types

type Branch 

type Branch struct {
	IDs [2]int // {0: u, 1: w}
}

func (Branch) Collide 

func (br Branch) Collide(br2 Branch) bool

func (Branch) Empty 

func (br Branch) Empty() bool

type Network 

type Network struct {
	NetTree       *tree.Tree        // tree from extended newick
	Reticulations map[string]Branch // reticulation branches
}

func MakeNetwork 

func MakeNetwork(td *TreeData, branches []Branch) *Network

Makes extended newick network out of newick tree and branch data computed by the CAMUS algorithm

func (*Network) Level1 

func (ntw *Network) Level1(td *TreeData) bool

func (*Network) Newick 

func (ntw *Network) Newick() string

type Quartet 

type Quartet uint64

func NewQuartet 

func NewQuartet(qTree, tre *tree.Tree) (Quartet, error)

Generates quartet from four leaf newick tree (only used for testing)

func QuartetFromTreeQ 

func QuartetFromTreeQ(tq *tree.Quartet, constMap []int16) Quartet

Create quartet from gotree *tree.Quartet

func (Quartet) AllQuartets added in v0.5.0 

func (q Quartet) AllQuartets() []Quartet

func (*Quartet) Compare 

func (q1 *Quartet) Compare(q2 Quartet) int

Compares two quartets (currently unused). There are three possible results:

  • Qdiff (they contain different taxa)
  • Qneq (they have a different topology)
  • Qeq (they have the same topology)

func (*Quartet) String 

func (q *Quartet) String(tre *tree.Tree) string

Not efficient, do no use except for testing !!!

func (Quartet) Taxa 

func (q Quartet) Taxa() iter.Seq2[int, uint16]

func (Quartet) Taxon added in v0.5.0 

func (q Quartet) Taxon(i int) uint16

func (Quartet) Topology 

func (q Quartet) Topology() uint8

type TreeData 

type TreeData struct {
	tree.Tree
	Children  [][]*tree.Node // Children for each node
	IdToNodes []*tree.Node   // Mapping between id and node pointer

	Depths         []int    // Distance from all nodes to the root
	NumLeavesBelow []uint64 // Number of leaves below node
	NLeaves        int      // Number of leaves
	// contains filtered or unexported fields
}

Expanded tree struct containing necessary preprocessed data

func MakeTreeData 

func MakeTreeData(tre *tree.Tree, qCounts map[Quartet]uint32) *TreeData

Preprocess tree data and makes TreeData struct. Pass nil for qCounts if you don't need quartets.

func (*TreeData) Clone 

func (td *TreeData) Clone() *TreeData

func (*TreeData) InLeafset 

func (td *TreeData) InLeafset(n1ID, n2ID uint16) bool

n2 (id) is in the leafset of n1 (id)

func (*TreeData) LCA 

func (td *TreeData) LCA(n1ID, n2ID int) int

Takes in the node ids of two nodes and returns the id of the LCA

func (*TreeData) LeafsetAsString 

func (td *TreeData) LeafsetAsString(n *tree.Node) string

Returns leafset as string for printing/testing

func (*TreeData) NumQuartet 

func (td *TreeData) NumQuartet(q Quartet) uint32

Get count of quartets with a particular topology

func (*TreeData) Quartets 

func (td *TreeData) Quartets(nid int) []Quartet

Get quartets corresponding to a given node (by id)

func (*TreeData) Sibling 

func (td *TreeData) Sibling(node *tree.Node) *tree.Node

Finds node's sibling -- assumes binary tree

func (*TreeData) TipToNodeID added in v0.6.0 

func (td *TreeData) TipToNodeID(idx uint16) int

func (*TreeData) TotalNumQuartets 

func (td *TreeData) TotalNumQuartets() uint32

returns total number of quartets (all topologies)

func (*TreeData) TotalNumUniqueQuartets added in v0.7.2 

func (td *TreeData) TotalNumUniqueQuartets() uint32

func (*TreeData) Under 

func (td *TreeData) Under(n1ID, n2ID int) bool

n2 is under n1

func (*TreeData) Verify 

func (td *TreeData) Verify()

Verify that tree still has the same root, and thus the data is still applicable

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.