Tree Concept.

class core.graph.interface.treeconcept.EditableTreeConcept

Bases: core.graph.interface.treeconcept.MutableTreeConcept

add_child_tree(parent, tree)

Add a tree after the children of the parent vertex. Complexity have to be O(1) if tree == sub_tree()

Parameters:

• parent -- vertex identifier
• tree -- a rooted tree

insert_sibling_tree(vid, tree)

Insert a tree before the vid. vid and the root of the tree are siblings. Complexity have to be O(1) if tree comes from the actual tree ( tree= sef.sub_tree() )

Parameters:

• vid -- vertex identifier
• tree -- a rooted tree

sub_tree(vtx_id)

Return a reference of the tree rooted on vtx_id in O(1).

Returns:Editable Tree

class core.graph.interface.treeconcept.MutableTreeConcept

Bases: core.graph.interface.treeconcept.RootedTreeConcept, core.graph.interface.graphconcept.MutableVertexGraphConcept

A mutable rooted tree. The substitute method is defined outside the interface. substitute(self,vid,tree)

add_child(parent, child)

Add a child at the end of children

Parameters:

• parent -- The parent identifier.
• child -- The child identifier.

insert_parent(vtx_id, parent_id)

Insert parent_id between vtx_id and its actual parent.

Parameters:

• vtx_id -- a vertex identifier
• parent_id -- a vertex identifier

insert_sibling(vid1, vid2)

Insert vid2 before vid1.

Parameters:

• vid1 -- a vertex identifier
• vid2 -- the vertex to insert

class core.graph.interface.treeconcept.OrderedTreeConcept

Bases: core.graph.interface.treeconcept.RootedTreeConcept

An ordered tree is a rooted tree where an order relation is defined between chidren.

first_child(vid)

Return the first child of vid

Parameters:vid -- The vertex identifier. Returns:vid

last_child(vid)

Return the last child of vid

Parameters:vid -- The vertex identifier. Returns:vid

next_sibling(vid)

Return next sibling

Parameters:vid -- The vertex identifier. Returns:vid

previous_sibling(vid)

Return previous sibling

Parameters:vid -- The vertex identifier. Returns:vid

class core.graph.interface.treeconcept.RootedTreeConcept

Bases: core.graph.interface.graphconcept.VertexListGraphConcept

Rooted Tree interface.

depth(vid), depth() and sub_tree(vid) can be extenal algorithms.

children(vtx_id)

Return a vertex iterator

Parameters:vtx_id -- The vertex identifier. Returns:iter of vertex identifier

get_root()

Return the tree root.

Returns:vertex identifier

is_leaf(vtx_id)

Test if vtx_id is a leaf.

Returns:bool

nb_children(vtx_id)

Return the number of children

Parameters:vtx_id -- The vertex identifier. Return type:int

nb_siblings(vtx_id)

Return the number of siblings

Returns:int

parent(vtx_id)

Return the parent of vtx_id.

Parameters:vtx_id -- The vertex identifier. Returns:vertex identifier

set_root(vtx_id)

Set the tree root.

Parameters:vtx_id -- The vertex identifier.

siblings(vtx_id)

Return an iterator of vtx_id siblings. vtx_id is not include in siblings.

Parameters:vtx_id -- The vertex identifier. Returns:iter of vertex identifier

root

Return the tree root.

Returns:vertex identifier

class core.graph.interface.treeconcept.Visitor

Bases: object

Used during a tree traversal.

post_order(vtx_id)

todo

pre_order(vtx_id)

todo

core.graph.interface.treeconcept.traverse_tree(tree, vtx_id, visitor)

Traverse a tree in a prefix or postfix way.

We call a visitor for each vertex. This is usefull for printing, cmputing or storing vertices in a specific order.

See boost.graph.