Traversal methods on tree and MTG

Tree and MTG Traversals

class openalea.mtg.traversal.Visitor

Bases: object

Used during a tree traversal.

post_order(vtx_id)

pre_order(vtx_id)

openalea.mtg.traversal.iter_mtg(mtg, vtx_id)

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)

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.

See also

iter_mtg(), iter_mtg_with_filter(), iter_mtg2_with_filter()

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)

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

iter_mtg(), iter_mtg2(), iter_mtg2_with_filter()

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)

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

iter_mtg(), iter_mtg2(), iter_mtg2_with_filter()

Note

Do not use this function. Instead use iter_mtg2_with_filter()

openalea.mtg.traversal.iter_scale(g, vtx_id, visited)

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)

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)

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)

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)

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)

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)

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)

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)

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)

Topological sort of a directed acyclic graph.

This is not a fully recursive implementation.

openalea.mtg.traversal.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, computing or storing vertices in a specific order.

See boost.graph.

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