nodeseq_t Class Reference

A sequence of nodes. More...

#include <nodeseq.h>

Inheritance diagram for nodeseq_t:

Collaboration diagram for nodeseq_t:

Public Member Functions
	~nodeseq_t (void)
	destructor
size_t	bytesize (void) const
	size of serialized binary form
void	sort (void)
	order nodes in order of increasing time
pocket_t *	colored (color_t col) const
	Get all balls of a color.
size_t	ntime (slate_t t) const
	Number of distinct timepoints.
size_t	length (void) const
	Number of nodes in the sequence.
node_t *	position (int n)
	traverse to nth node, retrieve pointer
void	move (ball_t *b, node_t *p, node_t *q)
	move ball b from p to q
void	swap (ball_t *a, ball_t *b)
	swap balls a and b, wherever they lie
void	attach (node_t *p, node_t *q)
void	detach (node_t *p)
void	add (node_t *p, ball_t *a)
void	drop (ball_t *a)
void	destroy_node (node_t *p)
	remove a dead root node
void	weed (void)
	drop all dead roots
void	comb (void)
std::unordered_map< name_t, std::vector< node_t * > >	children_map (void) const
	map nodes onto vector of children
std::vector< node_t * >	sorted_roots (const std::unordered_map< name_t, slate_t > &height) const
	collect root nodes and sort them in order of decreasing subtree height
std::vector< node_t * >	ladderize (std::unordered_map< name_t, std::vector< node_t * > > &children) const
void	trace_lineages (void)
string_t	yaml (string_t tab="") const
	human/machine-readable info
SEXP	structure (void) const
	R list description.
string_t	newick (slate_t t, slate_t te, bool showdeme, bool extended) const
	put genealogy at time t into Newick format.

Static Public Member Functions
static bool	compare (node_t *p, node_t *q)

Private Member Functions
void	clean (void)
	clean up: delete all nodes, reset globals
void	repair_owners (const std::unordered_map< name_t, ball_t * > &names)
std::unordered_map< name_t, node_t * >	node_map (void) const
	map node names onto pointers
void	trace_lineage (ball_t *b, name_t u)

Friends
raw_t *	operator>> (const nodeseq_t &G, raw_t *o)
	binary serialization
raw_t *	operator>> (raw_t *o, nodeseq_t &G)
	binary deserialization

Detailed Description

A sequence of nodes.

Definition at line 19 of file nodeseq.h.

Constructor & Destructor Documentation

~nodeseq_t()

nodeseq_t::~nodeseq_t ( void )

inline

destructor

Definition at line 32 of file nodeseq.h.

                    {
    clean();
  };

Here is the call graph for this function:

Member Function Documentation

add()

void nodeseq_t::add ( node_t * p, ball_t * a )

inline

add node p; take as parent the node holding ball a. the deme of p is changed to match that of a

Definition at line 181 of file nodeseq.h.

                                  {
    swap(a,p->green_ball());
    p->deme() = a->deme();
    push_back(p);
  };

Here is the call graph for this function:

Here is the caller graph for this function:

attach()

void nodeseq_t::attach ( node_t * p, node_t * q )

inline

attach node q as descendant of node p. note that this does not push q into the nodeseq.

Definition at line 171 of file nodeseq.h.

                                     {
    move(q->green_ball(),q,p);
  };

Here is the call graph for this function:

Here is the caller graph for this function:

bytesize()

size_t nodeseq_t::bytesize ( void ) const

inline

size of serialized binary form

Definition at line 40 of file nodeseq.h.

                               {
    size_t s = sizeof(size_t);
    for (node_t *p : *this)
      s += p->bytesize();
    return s;
  };

Here is the call graph for this function:

Here is the caller graph for this function:

children_map()

std::unordered_map< name_t, std::vector< node_t * > > nodeseq_t::children_map ( void ) const

inline

map nodes onto vector of children

Definition at line 249 of file nodeseq.h.

                            {
    std::unordered_map<name_t, std::vector<node_t*>> children;
    children.reserve(size());
    // initialise every node with an empty vector
    for (node_t* p : *this)
      children[p->uniq];
    for (node_t* p : *this) {
      if (!p->is_root())
        children[p->parent()->uniq].push_back(p);
    }
    return children;
  };

Here is the call graph for this function:

Here is the caller graph for this function:

clean()

void nodeseq_t::clean ( void )

inlineprivate

clean up: delete all nodes, reset globals

Definition at line 24 of file nodeseq.h.

                    {
    for (node_t *p : *this) delete p;
    clear();
  };

Here is the caller graph for this function:

colored()

pocket_t * nodeseq_t::colored ( color_t col ) const

inline

Get all balls of a color.

Definition at line 118 of file nodeseq.h.

                                        {
    pocket_t *p = new pocket_t;
    for (node_t *q : *this) {
      for (ball_t *b : *q ) {
        if (b->is(col)) p->insert(b);
      }
    }
    return p;
  };

Here is the caller graph for this function:

comb()

void nodeseq_t::comb ( void )

inline

drop all inline nodes i.e., those holding just one ball that is green.

Definition at line 223 of file nodeseq.h.

                   {
    for (node_t *p : *this) {
      if (p->size() == 1 && p->holds(green)) {
        swap(p->last_ball(),p->green_ball());
      }
    }
    weed();
  };

Here is the call graph for this function:

Here is the caller graph for this function:

compare()

static bool nodeseq_t::compare ( node_t * p, node_t * q )

inlinestatic

Order relation among nodes. An ancestor node should always come before its descendants. Nodes should be ordered by time, then arbitrarily.

Definition at line 103 of file nodeseq.h.

                                             {
    return (p->slate < q->slate) ||
      ((p->slate == q->slate) &&
       ((p == q->parent()) ||
        ((q != p->parent()) && (p->uniq < q->uniq))));
  };

Here is the call graph for this function:

Here is the caller graph for this function:

destroy_node()

void nodeseq_t::destroy_node ( node_t * p )

inline

remove a dead root node

Definition at line 205 of file nodeseq.h.

                                {
    assert(p->dead_root());
    remove(p);
    delete p;
  };

Here is the call graph for this function:

Here is the caller graph for this function:

detach()

void nodeseq_t::detach ( node_t * p )

inline

detach node p from its parent. note that this does not remove q from the nodeseq.

Definition at line 176 of file nodeseq.h.

                          {
    move(p->green_ball(),p->parent(),p);
  };

Here is the call graph for this function:

Here is the caller graph for this function:

drop()

void nodeseq_t::drop ( ball_t * a )

inline

drop the black ball 'a' and the node if either (1) the node becomes thereby a dead root, or (2) the node's pocket becomes thereby empty.

Definition at line 189 of file nodeseq.h.

                        {
    assert(a->is(black));
    node_t *p = a->holder();
    if (p->size() > 1) {
      p->erase(a);
      delete a;
      if (p->dead_root()) {     // remove isolated root
        destroy_node(p);
      }
    } else {
      swap(a,p->green_ball());
      destroy_node(p);
      drop(a);                  // recurse
    }
  };

Here is the call graph for this function:

Here is the caller graph for this function:

ladderize()

std::vector< node_t * > nodeseq_t::ladderize ( std::unordered_map< name_t, std::vector< node_t * > > & children ) const

inline

ladderize the tree by sorting each vector in 'children' according to decreasing subtree height. Return the root nodes, sorted in the same way.

Definition at line 282 of file nodeseq.h.

           {
    std::unordered_map<name_t, slate_t> height;
    height.reserve(size());
    for (auto it = rbegin(); it != rend(); ++it) {
      node_t* p = *it;
      auto& ch = children.at(p->uniq);
      if (ch.empty()) {
        height[p->uniq] = p->slate;
      } else {
        std::sort(ch.begin(), ch.end(),
                  [&height](node_t* a, node_t* b) {
                    return height.at(a->uniq) > height.at(b->uniq);
                  });
        height[p->uniq] = height.at(ch[0]->uniq);
      }
    }
    return sorted_roots(height);
  };

Here is the call graph for this function:

Here is the caller graph for this function:

length()

size_t nodeseq_t::length ( void ) const

inline

Number of nodes in the sequence.

Definition at line 139 of file nodeseq.h.

                             {
    return this->size();
  };

Here is the caller graph for this function:

move()

void nodeseq_t::move ( ball_t * b, node_t * p, node_t * q )

inline

move ball b from p to q

Definition at line 156 of file nodeseq.h.

                                              {
    assert(b->holder() == p);
    p->erase(b); q->insert(b);
  };

Here is the call graph for this function:

Here is the caller graph for this function:

newick()

string_t nodeseq_t::newick	(	slate_t	t,
		slate_t	te,
		bool	showdeme,
		bool	extended ) const

put genealogy at time t into Newick format.

Definition at line 92 of file newick.cc.

{
  string_t o = "";
  for (node_t *p : *this) {
    if (p->is_root()) {
      o += p->newick(t,te,showdeme,extended) + ";";
    }
  }
  return o;
}

Here is the call graph for this function:

Here is the caller graph for this function:

node_map()

std::unordered_map< name_t, node_t * > nodeseq_t::node_map ( void ) const

inlineprivate

map node names onto pointers

Definition at line 90 of file nodeseq.h.

                        {
    std::unordered_map<name_t, node_t*> m;
    m.reserve(size());
    for (node_t* p : *this)
      m[p->uniq] = p;
    return m;
  };

ntime()

size_t nodeseq_t::ntime ( slate_t t ) const

inline

Number of distinct timepoints.

Definition at line 128 of file nodeseq.h.

                                 {
    size_t count = 1;
    for (node_t *p : *this) {
      if (t < p->slate) {
        t = p->slate;
        count++;
      }
    }
    return count;
  };

Here is the caller graph for this function:

position()

node_t * nodeseq_t::position ( int n )

inline

traverse to nth node, retrieve pointer

Definition at line 143 of file nodeseq.h.

                           {
    int i = 0;
    node_it k = cbegin();
    while (i < n && k != cend()) {
      i++; k++;
    }
    assert(k != cend());
    return *k;
  };

repair_owners()

void nodeseq_t::repair_owners ( const std::unordered_map< name_t, ball_t * > & names )

inlineprivate

Repair the links green balls and their names. Needed in deserialization.

Definition at line 82 of file nodeseq.h.

                                                                     {
    for (node_t *p : *this) {
      p->green_ball() = names.at(p->uniq);
    }
  };

Here is the call graph for this function:

Here is the caller graph for this function:

sort()

void nodeseq_t::sort ( void )

inline

order nodes in order of increasing time

Definition at line 111 of file nodeseq.h.

                   {
    std::list<node_t*>::sort(compare);
  };

Here is the call graph for this function:

Here is the caller graph for this function:

sorted_roots()

std::vector< node_t * > nodeseq_t::sorted_roots ( const std::unordered_map< name_t, slate_t > & height ) const

inline

collect root nodes and sort them in order of decreasing subtree height

Definition at line 264 of file nodeseq.h.

           {
    std::vector<node_t*> roots;
    for (node_t* p : *this)
      if (p->is_root()) roots.push_back(p);
    std::sort(roots.begin(), roots.end(),
              [&height](node_t* a, node_t* b) {
                return height.at(a->uniq) > height.at(b->uniq);
              });
    return roots;
  };

Here is the call graph for this function:

Here is the caller graph for this function:

structure()

SEXP nodeseq_t::structure

(

void

)

const

R list description.

Definition at line 70 of file structure.cc.

{
  SEXP Nodes;
  PROTECT(Nodes = NEW_LIST(size()));
  int k = 0;
  for (node_t *p : *this) {
    SET_ELEMENT(Nodes,k++,p->structure());
  }
  UNPROTECT(1);
  return Nodes;
}

Here is the call graph for this function:

Here is the caller graph for this function:

swap()

void nodeseq_t::swap ( ball_t * a, ball_t * b )

inline

swap balls a and b, wherever they lie

Definition at line 161 of file nodeseq.h.

                                   {
    node_t *p = a->holder();
    node_t *q = b->holder();
    if (p != q) {
      p->erase(a); q->insert(a);
      q->erase(b); p->insert(b);
    }
  };

Here is the call graph for this function:

Here is the caller graph for this function:

trace_lineage()

void nodeseq_t::trace_lineage ( ball_t * b, name_t u )

inlineprivate

trace back a single lineage. this results in the deme slot for all green balls along the lineage of 'b' begin replaced by the lineage of 'b'.

Definition at line 237 of file nodeseq.h.

                                           {
    node_t *p = b->holder();
    while (p->lineage() == null_lineage) {
      p->lineage() = u;
      p = p->parent();
    }
  };

Here is the call graph for this function:

Here is the caller graph for this function:

trace_lineages()

void nodeseq_t::trace_lineages ( void )

inline

trace back all sample lineages. this results in the deme slots of all green balls being replaced by the unique names of the lineages they trace.

Definition at line 309 of file nodeseq.h.

                             {
    // we trace each lineage in turn.
    // because we move from early to late,
    // the order is guaranteed to be valid.
    name_t u = 0;
    for (node_t *p : *this ) {
      for (ball_t *b : *p) {
        if (b->color==blue) {
          trace_lineage(b,u);
          u++;
        }
      }
    }
  };

Here is the call graph for this function:

Here is the caller graph for this function:

weed()

void nodeseq_t::weed ( void )

inline

drop all dead roots

Definition at line 211 of file nodeseq.h.

                   {
    node_nit j = begin();
    while (j != end()) {
      if ((*j)->dead_root()) {
        destroy_node(*(j++));
      } else {
        j++;
      }
    }
  };

Here is the call graph for this function:

Here is the caller graph for this function:

yaml()

string_t nodeseq_t::yaml

(

string_t

tab = ""

)

const

human/machine-readable info

Definition at line 51 of file yaml.cc.

{
  string_t o = "";
  string_t t = tab + "  ";
  for (node_t *p : *this) {
    o += tab + "- " + p->yaml(t);
  }
  return o;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Symbol Documentation

operator>> [1/2]

raw_t * operator>> ( const nodeseq_t & G, raw_t * o )

friend

binary serialization

Definition at line 47 of file nodeseq.h.

                                                          {
    size_t nnode = G.size();
    memcpy(o,&nnode,sizeof(size_t)); o += sizeof(size_t);
    for (node_t *p : G) {
      o = (*p >> o);
    }
    return o;
  };

operator>> [2/2]

raw_t * operator>> ( raw_t * o, nodeseq_t & G )

friend

binary deserialization

Definition at line 56 of file nodeseq.h.

                                                    {
    G.clean();
    std::unordered_map<name_t,node_t*> node_names;
    std::unordered_map<name_t,ball_t*> ball_names;
    size_t nnode = 0;
    memcpy(&nnode,o,sizeof(size_t)); o += sizeof(size_t);
    node_names.reserve(nnode);
    ball_names.reserve(nnode);
    for (size_t i = 0; i < nnode; i++) {
      node_t *p = new node_t();
      o = (o >> *p);
      G.push_back(p);
      node_names[p->uniq] = p;
    }
    for (node_t *q : G) {
      q->repair_owners(node_names,&ball_names);
    }
    G.repair_owners(ball_names);
    G.trace_lineages();
    return o;
  };

---

The documentation for this class was generated from the following files:

• src/nodeseq.h
• src/newick.cc
• src/structure.cc
• src/yaml.cc