# -*- coding: utf-8 -*-
# -*- python -*-
#
# OpenAlea.mtg
#
# Copyright 2008-2009 INRIA - CIRAD - INRA
#
# File author(s): Christophe Pradal <christophe.pradal.at.cirad.fr>
#
# Distributed under the Cecill-C License.
# See accompanying file LICENSE.txt or copy at
# http://www.cecill.info/licences/Licence_CeCILL-C_V1-en.html
#
# OpenAlea WebSite : http://openalea.gforge.inria.fr
#
################################################################################
"""Tree and MTG Traversals"""
from collections import deque
[docs]
def 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.
'''
if complex is not None and tree.complex(vtx_id) != complex:
return
if visitor_filter and not visitor_filter.pre_order(vtx_id):
return
edge_type = tree.property('edge_type')
# 1. select first '+' edges
successor = []
yield vtx_id
for vid in tree.children_iter(vtx_id):
if edge_type.get(vid) == '<':
successor.append(vid)
continue
for node in pre_order(tree, vid, complex, visitor_filter):
yield node
# 2. select then '<' edges
for vid in successor:
for node in pre_order(tree, vid, complex, visitor_filter):
yield node
if visitor_filter:
visitor_filter.post_order(vtx_id)
[docs]
def 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
'''
edge_type = tree.property('edge_type')
def order_children(vid):
''' Internal function to retrieve the children in a correct order:
- Branch before successor.
'''
plus = []
successor = []
for v in tree.children_iter(vid):
if complex is not None and tree.complex(v) != complex:
continue
if pre_order_filter and not pre_order_filter(v):
continue
if edge_type.get(v) == '<':
successor.append(v)
else:
plus.append(v)
plus.extend(successor)
child = plus
return list(reversed(child))
queue = deque()
queue.append( (vtx_id, order_children(vtx_id)) )
yield vtx_id
# 1. select first '+' edges
while queue:
vtx_id, children = queue[-1]
if children:
vid = children.pop()
yield vid
queue.append((vid,order_children(vid)))
else:
vtx_id, children = queue.pop()
if post_order_visitor:
post_order_visitor(vtx_id)
[docs]
def 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.
'''
if complex is not None and tree.complex(vtx_id) != complex:
return
edge_type = tree.property('edge_type')
queue = deque()
queue.append(vtx_id)
# 1. select first '+' edges
while queue:
plus = []
successor = []
vtx_id = queue.pop()
yield vtx_id
for vid in tree.children_iter(vtx_id):
if complex is not None and tree.complex(vid) != complex:
continue
if visitor_filter and not visitor_filter.pre_order(tree, vid):
continue
if edge_type.get(vid) == '<':
successor.append(vid)
else:
plus.append(vid)
plus.extend(successor)
child = plus
queue.extend(reversed(child))
[docs]
def 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.
'''
queue = deque()
queue.append(vtx_id)
while queue:
vtx_id = queue.pop()
yield vtx_id
for vid in tree.components_iter(vtx_id):
if visitor_filter and not visitor_filter.pre_order(vid):
continue
queue.append(vid)
[docs]
def 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
'''
if complex is not None and tree.complex(vtx_id) != complex:
return
if visitor_filter and not visitor_filter.pre_order(vtx_id):
return
for vid in tree.children_iter(vtx_id):
for node in post_order(tree, vid, complex, visitor_filter):
yield node
if visitor_filter:
visitor_filter.post_order(vtx_id)
yield vtx_id
[docs]
def 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.
'''
edge_type = tree.property('edge_type')
if pre_order_filter is None:
pre_order_filter = lambda v: True
if post_order_visitor is None:
post_order_visitor = lambda x: None
def order_children(vid):
''' Internal function to retrieve the children in a correct order:
- Branch before successor.
'''
plus = []
successor = []
for v in tree.children(vid):
if complex is not None and tree.complex(v) != complex:
continue
if not pre_order_filter(v):
continue
if edge_type.get(v) == '<':
successor.append(v)
else:
plus.append(v)
plus.extend(successor)
child = plus
return reversed(child)
visited = set([])
queue = [vtx_id]
# 1. select first '+' edges
while queue:
vtx_id = queue[-1]
for vid in order_children(vtx_id):
if vid not in visited:
queue.append(vid)
break
else: # no child or all have been visited
post_order_visitor(vtx_id)
yield vtx_id
visited.add(vtx_id)
queue.pop()
[docs]
def 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.
'''
yield visitor.pre_order(vtx_id)
for v in tree.children_iter(vtx_id):
for res in traverse_tree(tree, v, visitor):
yield res
yield visitor.post_order(vtx_id)
[docs]
class Visitor(object):
''' Used during a tree traversal. '''
[docs]
def pre_order(self, vtx_id):
pass
[docs]
def post_order(self, vtx_id):
pass
# old implementation
# Problem is the traversal traverse complex before components.
# def iter_mtg(mtg, vtx_id):
# yield vtx_id
# for vid in mtg.components(vtx_id):
# for node in iter_mtg(mtg, vid):
# yield node
[docs]
def iter_scale(g, vtx_id, visited):
""" Internal method used by :func:`iter_mtg` and :func:`iter_mtg_with_visitor`.
.. warning:: Do not use. This function may be removed in other version.
"""
if vtx_id is not None and vtx_id not in visited:
for v in iter_scale(g, g._complex.get(vtx_id), visited):
yield v
visited[vtx_id] = True
yield vtx_id
[docs]
def 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`.
.. seealso:: :func:`iter_mtg2`, :func:`iter_mtg_with_filter`, :func:`iter_mtg2_with_filter`.
.. note::
Do not use this function. Use :func:`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).
"""
visited = {vtx_id:True}
loc = vtx_id
yield vtx_id
while mtg._components.get(loc):
loc = mtg._components[loc][0]
vtx_id = loc
for vid in pre_order2(mtg, vtx_id):
for node in iter_scale(mtg, vid, visited):
yield node
[docs]
def 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`.
.. seealso:: :func:`iter_mtg`, :func:`iter_mtg_with_filter`, :func:`iter_mtg2_with_filter`
.. note:: Use this function instead of :func:`iter_mtg`
"""
visited = {vtx_id:True}
complex_id = vtx_id
max_scale = mtg.max_scale()
yield vtx_id
for vtx_id in mtg.component_roots_at_scale_iter(complex_id, max_scale):
for vid in pre_order2(mtg, vtx_id):
for node in iter_scale2(mtg, vid, complex_id, visited):
yield node
[docs]
def iter_scale2(g, vtx_id, complex_id, visited):
""" Internal method used by :func:`iter_mtg` and :func:`iter_mtg_with_visitor`.
.. warning:: Do not use. This function may be removed in other version.
"""
if vtx_id is not None and \
vtx_id not in visited and \
g.complex_at_scale(vtx_id, g.scale(complex_id)) == complex_id:
for v in iter_scale2(g, g._complex.get(vtx_id), complex_id, visited):
yield v
visited[vtx_id] = True
yield vtx_id
[docs]
def topological_sort(g, vtx_id, visited = None):
'''
Topological sort of a directed acyclic graph.
This is not a fully recursive implementation.
'''
if visited is None:
visited = {}
yield vtx_id
visited[vtx_id] = True
for vid in g.out_neighbors(vtx_id):
if vid in visited:
continue
for node in topological_sort(g, vid, visited):
yield node
[docs]
def 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.
'''
if pre_order_filter and not pre_order_filter(vtx_id):
return
edge_type = tree.property('edge_type')
# 1. select first '+' edges
successor = []
yield vtx_id
for vid in tree.children_iter(vtx_id):
if edge_type.get(vid) == '<':
successor.append(vid)
continue
for node in pre_order_with_filter(tree, vid, pre_order_filter, post_order_visitor):
yield node
# 2. select then '<' edges
for vid in successor:
for node in pre_order_with_filter(tree, vid, pre_order_filter, post_order_visitor):
yield node
if post_order_visitor:
post_order_visitor(vtx_id)
[docs]
def 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:
.. code-block:: python
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`.
.. seealso:: :func:`iter_mtg`, :func:`iter_mtg2`, :func:`iter_mtg2_with_filter`
.. note:: Do not use this function. Instead use :func:`iter_mtg2_with_filter`
"""
visited = {}
cid = mtg.complex(vtx_id)
if cid is not None:
visited[cid] = True
loc = vtx_id
while mtg._components.get(loc):
loc = mtg._components[loc][0]
#if pre_order_filter and not pre_order_filter(loc):
# return
vtx_id = loc
for vid in pre_order_with_filter(mtg, vtx_id, pre_order_filter, post_order_visitor):
for node in iter_scale(mtg, vid, visited):
yield node
[docs]
def 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:
.. code-block:: python
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`.
.. seealso:: :func:`iter_mtg`, :func:`iter_mtg2`, :func:`iter_mtg2_with_filter`
.. note:: Use this function instead of :func:`iter_mtg_with_filter`
"""
if pre_order_filter is None:
pre_order_filter = lambda v: True
if post_order_visitor is None:
post_order_visitor = lambda x: None
visited = {vtx_id:True}
complex_id = vtx_id
max_scale = mtg.max_scale()
queue = [] #cpl
pre_order_filter(vtx_id)#cpl
yield vtx_id
queue.append(vtx_id) #cpl
for vtx_id in mtg.component_roots_at_scale_iter(complex_id, max_scale):
for vid in pre_order2_with_filter(mtg, vtx_id,
pre_order_filter=None,
post_order_visitor=post_order_visitor,
complex=None):
for node in iter_scale2(mtg, vid, complex_id, visited):
scale = mtg.scale(node)
if scale != max_scale:
# we need to manage the right order for the post order visitor
prev_node = queue[-1]
prev_scale = mtg.scale(prev_node)
if prev_scale < scale:
# Nothing to do
queue.append(node)
elif prev_scale == scale:
# Test if the two vertices are connected
if mtg.parent(node) != prev_node:
post_order_visitor(prev_node)
queue[-1] = node
else:
queue.append(node)
else: # prev_scale > scale
prev_node = queue.pop()
while mtg.scale(prev_node) > scale:
post_order_visitor(prev_node)
prev_node = queue.pop()
if mtg.parent(node) != prev_node:
post_order_visitor(prev_node)
queue.append(node)
else:
queue.append(node)
pre_order_filter(node)
yield node
while len(queue) > 1:
node = queue.pop()
post_order_visitor(node)