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
.