Tree Related Algorithms

class treelas.Tree(parent, root=-1, n=None)

Rooted tree, stored as a parent np.array

static from_prufer(prufer)

If choose root by the Prüfer sequence

n

Number of nodes

show(wait=True)

Show the tree using graphviz’ dot

treelas.random_spanning_tree(index: treelas.graphidx._graphidx.BiAdjacent, seed: int = 2018, parent: numpy.ndarray[int32] = array([], dtype=int32)) → numpy.ndarray[int32]

Compute a random spanning tree (similar to Prim’s algorithm)

treelas.post_order(parent: numpy.ndarray[int32], root: int = -1, include_root: bool = False, verbose: bool = False) → numpy.ndarray[int32]

Compute a post order (DFS finish time) starting at root on the tree given by parent

treelas.tree.find_root(parent: numpy.ndarray[int32]) → int

Find smallest i such that parent[i] == i

treelas.graphidx.graphviz()

Load edges/{head,tail} and show the graph structure using the dot (https://www.graphviz.org/) program

Dynamic Programming Solvers

treelas.tree_dp(*args, **kwargs)

Overloaded function.

1. tree_dp(y: numpy.ndarray[float64], parent: numpy.ndarray[int32], lam: float, root: int = 0, mu: float = 1.0, x: numpy.ndarray[float64] = None, verbose: bool = False, merge_sort: bool = False, lazy_sort: bool = False) -> numpy.ndarray[float64]

   Dynamic programming algorithm for trees (uniform weighting)

2. tree_dp(y: numpy.ndarray[float64], parent: numpy.ndarray[int32], lam: numpy.ndarray[float64], mu: numpy.ndarray[float64], root: int = 0, verbose: bool = False, lazy_sort: bool = False, x: numpy.ndarray[float64] = None) -> numpy.ndarray[float64]

   Dynamic programming algorithm for trees (node and edge weighting)

Duality

treelas.tree_dual(parent: numpy.ndarray[int32], z: numpy.ndarray[float64], root: int = 0, alpha: numpy.ndarray[float64] = None, post_ord: numpy.ndarray[int32] = array([], dtype=int32), tree_orientation: bool = True, verbose: bool = False) → numpy.ndarray[float64]

Compute dual solution along tree. Be aware that z is supposed to be mu*(x - y) and will be changed. After the computation, z[root] will contain z.sum() (from before the computation).

If tree_orientation, every tree edge is directed from i to parent[i]; otherwise it goes from min(i, parent[i]) to max(i, parent[i]).

treelas.tree_dual_gap(x: numpy.ndarray[float64], alpha: numpy.ndarray[float64], lam: numpy.ndarray[float64], parent: numpy.ndarray[int32], root_val: float = 0.0, gamma: numpy.ndarray[float64] = None) → numpy.ndarray[float64]

Compute the duality gap vector