Traversal methods on tree and MTG¶
Tree and MTG Traversals
- 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.
- Usage:
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.
- Returns:
iter of vid.
Traverse all the vertices contained in the sub_mtg defined by vtx_id.
See also
iter_mtg2()
,iter_mtg_with_filter()
,iter_mtg2_with_filter()
.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.
- Usage:
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.
- Returns:
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.
- Usage:
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:
mtg: the multi-scale graph
vtx_id: the root of the sub-mtg which is traversed.
- Optional Parameters:
- 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.
- Returns:
iter of vid.
Traverse all the vertices contained in the sub_mtg defined by vtx_id.
See also
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.
- Usage:
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:
mtg: the multi-scale graph
vtx_id: the root of the sub-mtg which is traversed.
- Optional Parameters:
- 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.
- Returns:
iter of vid.
Traverse all the vertices contained in the sub_mtg defined by vtx_id.
See also
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()
anditer_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()
anditer_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
.