# Traversal methods on tree and MTG¶

Tree and MTG Traversals

class openalea.mtg.traversal.Visitor[source]

Bases: object

Used during a tree traversal.

post_order(vtx_id)[source]
pre_order(vtx_id)[source]
openalea.mtg.traversal.iter_mtg(mtg, vtx_id)[source]

Iterate on an MTG by traversiong vtx_id and all its components.

This function traverse a complex before its components and a parent before its children.

for vid in iter_mtg(g,g.root):
print vid

Parameters: mtg: the multi-scale graph vtx_id: the root of the sub-mtg which is traversed. iter of vid. Traverse all the vertices contained in the sub_mtg defined by vtx_id.

Note

Do not use this function. Use iter_mtg2() instead. If several trees belong to vtx_id, only the first one will be traversed.

Note

This is a recursive implementation. It can be problematic for large MTG with lots of scales (e.g. >40).

openalea.mtg.traversal.iter_mtg2(mtg, vtx_id)[source]

Iterate on an MTG by traversiong vtx_id and all its components.

This function traverse a complex before its components and a parent before its children.

for vid in iter_mtg2(g,g.root):
print vid

Parameters: mtg: the multi-scale graph vtx_id: the root of the sub-mtg which is traversed. iter of vid. Traverse all the vertices contained in the sub_mtg defined by vtx_id.

Note

Use this function instead of iter_mtg()

openalea.mtg.traversal.iter_mtg2_with_filter(mtg, vtx_id, pre_order_filter=None, post_order_visitor=None)[source]

Iterate on an MTG by traversiong vtx_id and all its components.

If defined, apply the two visitor functions before and after having visited all the successor of a vertex.

This function traverse a complex before its components and a parent before its children.

def pre_order_visitor(vid):
print vid
return True
def post_order_visitor(vid):
print vid
for vid in iter_mtg_with_filter(g,g.root, pre_order_visitor, post_order_visitor):
pass

Parameters: Optional Parameters: mtg: the multi-scale graph vtx_id: the root of the sub-mtg which is traversed. pre_order_visitor: function called before traversing the children or components. This function returns a boolean. If False, the sub-mtg rooted on the vertex is skipped. post_order_visitor : function called after the traversal of all the children and components. iter of vid. Traverse all the vertices contained in the sub_mtg defined by vtx_id.

Note

Use this function instead of iter_mtg_with_filter()

openalea.mtg.traversal.iter_mtg_with_filter(mtg, vtx_id, pre_order_filter=None, post_order_visitor=None)[source]

Iterate on an MTG by traversiong vtx_id and all its components.

If defined, apply the two visitor functions before and after having visited all the successor of a vertex.

This function traverse a complex before its components and a parent before its children.

def pre_order_visitor(vid):
print vid
return True
def post_order_visitor(vid):
print vid
for vid in iter_mtg_with_filter(g,g.root, pre_order_visitor, post_order_visitor):
pass

Parameters: Optional Parameters: mtg: the multi-scale graph vtx_id: the root of the sub-mtg which is traversed. pre_order_visitor: function called before traversing the children or components. This function returns a boolean. If False, the sub-mtg rooted on the vertex is skipped. post_order_visitor : function called after the traversal of all the children and components. iter of vid. Traverse all the vertices contained in the sub_mtg defined by vtx_id.

Note

Do not use this function. Instead use iter_mtg2_with_filter()

openalea.mtg.traversal.iter_scale(g, vtx_id, visited)[source]

Internal method used by iter_mtg() and iter_mtg_with_visitor().

Warning

Do not use. This function may be removed in other version.

openalea.mtg.traversal.iter_scale2(g, vtx_id, complex_id, visited)[source]

Internal method used by iter_mtg() and iter_mtg_with_visitor().

Warning

Do not use. This function may be removed in other version.

openalea.mtg.traversal.post_order(tree, vtx_id, complex=None, visitor_filter=None)[source]

Traverse a tree in a postfix way. (from leaves to root) This is a recursive implementation

openalea.mtg.traversal.post_order2(tree, vtx_id, complex=None, pre_order_filter=None, post_order_visitor=None)[source]

Traverse a tree in a postfix way. (from leaves to root)

Same algorithm than post_order. The goal is to replace the post_order implementation.

openalea.mtg.traversal.pre_order(tree, vtx_id, complex=None, visitor_filter=None)[source]

Traverse a tree in a prefix way. (root then children)

This is a non recursive implementation.

openalea.mtg.traversal.pre_order2(tree, vtx_id, complex=None, visitor_filter=None)[source]

Traverse a tree in a prefix way. (root then children)

This is an iterative implementation.

openalea.mtg.traversal.pre_order2_with_filter(tree, vtx_id, complex=None, pre_order_filter=None, post_order_visitor=None)[source]

Same algorithm than pre_order2. The goal is to replace the pre_order2 implementation.

The problem is for the pre_order filter when it is also a visitor

openalea.mtg.traversal.pre_order_in_scale(tree, vtx_id, visitor_filter=None)[source]

Traverse a tree in a prefix way. (root then children)

This is a non recursive implementation.

openalea.mtg.traversal.pre_order_with_filter(tree, vtx_id, pre_order_filter=None, post_order_visitor=None)[source]

Traverse a tree in a prefix way. (root then children)

This is an iterative implementation.

TODO: make the naming and the arguments more consistent and user friendly. pre_order_filter is a functor which has to return a boolean. If the return value is False, the vertex is not visited. Otherelse, some computation can be done.

The post_order_visitor is used to execute, store, compute a function when the tree rooted on the vertex has been visited.

openalea.mtg.traversal.topological_sort(g, vtx_id, visited=None)[source]

Topological sort of a directed acyclic graph.

This is not a fully recursive implementation.

openalea.mtg.traversal.traverse_tree(tree, vtx_id, visitor)[source]

Traverse a tree in a prefix or postfix way.

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

See boost.graph.

Download the source file ../../src/mtg/traversal.py.