Struct rose_tree::RoseTree
[−]
[src]
pub struct RoseTree<N, Ix: IndexType = DefIndex> { // some fields omitted }
An indexable tree data structure with a variable and unbounded number of branches per node.
Also known as a multi-way tree.
See the wikipedia article on the "Rose tree" data structure.
Note: The following documentation is adapted from petgraph's Graph documentation.
RoseTree is parameterized over the node weight N and Ix which is the index type used.
A wrapper around petgraph's Graph data structure with a refined API specifically targeted towards use as a RoseTree.
NodeIndex is a type that acts as a reference to nodes, but these are only stable across certain operations. Removing nodes may shift other indices. Adding kids to the RoseTree keeps all indices stable, but removing a node will force the last node to shift its index to take its place.
The fact that the node indices in the RoseTree are numbered in a compact interval from 0 to n-1 simplifies some graph algorithms.
The Ix parameter is u32 by default. The goal is that you can ignore this parameter completely unless you need a very large RoseTree -- then you can use usize.
The RoseTree also offers methods for accessing the underlying Graph, which can be useful for taking advantage of petgraph's various graph-related algorithms.
Methods
impl<N, Ix = DefIndex> RoseTree<N, Ix> where Ix: IndexType
[src]
fn new(root: N) -> (Self, NodeIndex<Ix>)
Create a new RoseTree
along with some root Node.
Returns both the RoseTree
and an index into the root Node in a tuple.
fn with_capacity(nodes: usize, root: N) -> (Self, NodeIndex<Ix>)
Create a new RoseTree
with estimated capacity and some root Node.
Returns both the RoseTree
and an index into the root Node in a tuple.
fn node_count(&self) -> usize
The total number of nodes in the RoseTree.
fn remove_all_but_root(&mut self)
Remove all nodes in the RoseTree
except for the root.
fn graph_ref(&self) -> &PetGraph<N, Ix>
Borrow the RoseTree
's underlying PetGraph<N, Ix>
.
All existing NodeIndex
s may be used to index into this graph the same way they may be
used to index into the RoseTree
.
fn into_graph(self) -> PetGraph<N, Ix>
Take ownership of the RoseTree and return the internal PetGraphNodeIndex
s may be used to index into this graph the same way they may be
used to index into the RoseTree
.
fn add_child(&mut self, parent: NodeIndex<Ix>, kid: N) -> NodeIndex<Ix>
Add a child Node to the Node at the given NodeIndex. Returns an index into the child's position within the tree.
Computes in O(1) time.
Panics if the given parent node doesn't exist.
Panics if the Graph is at the maximum number of edges for its index.
fn node_weight(&self, node: NodeIndex<Ix>) -> Option<&N>
Borrow the weight from the node at the given index.
fn node_weight_mut(&mut self, node: NodeIndex<Ix>) -> Option<&mut N>
Mutably borrow the weight from the node at the given index.
fn index_twice_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> (&mut N, &mut N)
Index the RoseTree
by two node indices.
Panics if the indices are equal or if they are out of bounds.
Trait Implementations
impl<N: Debug, Ix: Debug + IndexType> Debug for RoseTree<N, Ix>
[src]
impl<N: Clone, Ix: Clone + IndexType> Clone for RoseTree<N, Ix>
[src]
fn clone(&self) -> RoseTree<N, Ix>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more