Trait reingold_tilford::NodeInfo

pub trait NodeInfo<N> where
    Self::Key: Eq + Hash,
    N: Copy, {
    type Key;
    fn key(&self, node: N) -> Self::Key;
    fn children(&self, node: N) -> SmallVec<N>;

    fn dimensions(&self, _node: N) -> Dimensions { ... }
    fn border(&self, _node: N) -> Dimensions { ... }
}

Methods that are needed to apply this algorithm to any type of tree.

This trait is designed to work with both "traditional" point-to-children style trees (PTC trees) and index trees (such as you would have if you wanted to use petgraph::Graph as a tree). To accomodate this however the usage of the trait is not necessarily obvious when working with "traditional" trees (there more examples in the examples folder at this crate's repo).

The TL;DR is that because a PTC tree contains all of it's information inside the nodes you don't need a seperate tree type. However to accomodate index trees you need a "tree" type that you implement the trait on plus a "node" type that gets returned from children. We can handle this in PTC trees by defining a unit struct that we implement the trait on, but just ignore it in the functions.

Examples

PTC trees:

extern crate reingold_tilford;

struct Tree;

struct Node {
    id: usize,
    children: Vec<Node>,
}

impl<'n> reingold_tilford::NodeInfo<&'n Node> for Tree {
    type Key = usize;

    fn key(&self, node: &'n Node) -> Self::Key {
        node.id
    }

    fn children(&self, node: &'n Node) -> reingold_tilford::SmallVec<&'n Node> {
        node.children.iter().collect()
    }
}

fn main() {
    let root = Node {
        id: 0,
        children: vec![
            Node { id: 1, children: vec![] },
            Node { id: 2, children: vec![] },
        ],
    };

    let layout = reingold_tilford::layout(&Tree, &root);

    assert!(layout.get(&0).is_some());
    let zero = layout.get(&0).unwrap();
    assert!(1.0 - 1e-12 < zero.x && zero.x < 1.0 + 1e-12);
    assert!(0.5 - 1e-12 < zero.y && zero.y < 0.5 + 1e-12);
}

Index trees:

extern crate petgraph;
extern crate reingold_tilford;

use petgraph::graph;

struct Graph(graph::Graph<usize, ()>);

impl reingold_tilford::NodeInfo<graph::NodeIndex> for Graph {
    type Key = graph::NodeIndex;

    fn key(&self, node: graph::NodeIndex) -> Self::Key {
        node
    }

    fn children(&self, node: graph::NodeIndex) -> reingold_tilford::SmallVec<graph::NodeIndex> {
        self.0.neighbors(node).collect()
    }
}

Associated Types

type Key

Loading content...

Required methods

fn key(&self, node: N) -> Self::Key

Returns a key that will be used to uniquely identify a given node.

fn children(&self, node: N) -> SmallVec<N>

Returns the children that a given node has.

Loading content...

Provided methods

fn dimensions(&self, _node: N) -> Dimensions

Returns the dimensions of a given node.

This is the padding that you want around the centre point of the node so that you can line things up as you want to (e.g. nodes aligned by their top border vs being aligned by their centres).

This value is generic over units (but all nodes must use the same unit) and the layout that this crate calculates will be given in terms of this unit. For example if you give this value in pixels then the layout will be given in terms of number of pixels from the left of the tree. Alternatively you might want to give this value in terms of the proportion of the width of your window (though note that this does not guarantee that the tree will fit in your window).

Default

By default the algorithm assumes that each node is point-like (i.e. has no width or height).

fn border(&self, _node: N) -> Dimensions

Returns the desired border around a given node.

See the dimensions method for a description of what units this has.

Default

By default the algorithm assumes that each node has a border of 0.5 on every side.

Loading content...

Implementors

Loading content...