Source code for openalea.mtg.algo

# -*- python -*-
# -*- coding: utf-8 -*-
#
#       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
#
################################################################################
"""Implementation of a set of algorithms for the MTG datastructure"""



__docformat__ = "restructuredtext"

import traversal

try:
    from tree import InvalidVertex
except ImportError:
    from openalea.container.tree import InvalidVertex


[docs]def ancestors(g, vid, **kwds): """ Return the vertices from vid to the root. :Parameters: - `g`: a tree or an MTG - `vid`: a vertex id which belongs to `g` :Returns: an iterator from `vid` to the root of the tree. .. seealso: :func:`aml.Ancestors` """ et = kwds.get('EdgeType','*') rt = kwds.get('RestrictedTo', 'NoRestriction') ci = kwds.get('ContainedIn') if ci is not None: c_scale = g.scale(ci) v = vid while v is not None: if rt == 'SameComplex': if g.complex(v) != g.complex(vid): break if ci and g.complex_at_scale(v, scale=c_scale) != ci: break yield v v = g.parent(v)
[docs]def path(g, vid1, vid2=None): """ Compute the vertices between v1 and v2. If v2 is None, return the path between v1 and the root. Otherelse, return the path between v1 and v2. If the graph is oriented from v1 to v2, sign is positive. Else, sign is negative. """ sign = 1 v1, v2 = vid1, vid2 if v2 is None: return ancestors(g,v1), sign l= list(ancestors(g,v2)) try: index = l.index(v1) except ValueError: l = list(ancestors(g,v1)) try: index = l.index(v2) sign = -1 except ValueError: return iter([]), 0 return reversed(l[:index+1]), sign
[docs]def edge_type(g,v): return g.property('edge_type').get(v)
[docs]def topological_path(g,v1, v2=None, edge=None): p, sign = path(g,v1,v2) if sign == 0: return None if edge is None: return sum(1 for v in p), sign else: return sum(1 for v in p if g.edge_type(v)==edge), sign
[docs]def order(g, v1, v2=None): return topological_path(g, v1, v2, '+')[0]
[docs]def alg_rank(g, v1, v2=None): p, sign = path(g,v1,v2) count = 0 for v in p: if edge_type(g,v) == '<': count+=1 else: break return count*sign
[docs]def rank(g, v1, v2=None): return abs(alg_rank(g,v1,v2))
[docs]def height(g, v1, v2=None): return topological_path(g, v1, v2 )[0]-1
[docs]def alg_order(g, v1, v2=None): p, s = topological_path(g, v1, v2, '+') if p is not None: return p*s
[docs]def alg_height(g, v1, v2=None): p, s = topological_path(g, v1, v2) if p is not None: return p*s
[docs]def father(g, vid, scale=-1, **kwds): """ See aml.Father function. """ edge_type = g.property('edge_type') et = kwds.get('EdgeType','*') rt = kwds.get('RestrictedTo', 'NoRestriction') ci = kwds.get('ContainedIn') current_scale = g.scale(vid) if scale <= 0 or scale == current_scale: p = g.parent(vid) elif scale < current_scale: vid = g.complex_at_scale(vid) p = g.parent(vid) else: vid = g.component_roots_at_scale_iter(vid, scale=scale).next() p = g.parent(vid) if et != '*': if edge_type.get(vid) != et: return None if rt != 'NoRestriction': if rt == 'SameComplex': if g.complex(p) != g.complex(vid): return None elif rt == 'SameAxis': if edge_type[vid] == '+': return None if ci is not None: c_scale = g.scale(ci) if g.complex_at_scale(vid, scale=c_scale) != g.complex_at_scale(p, scale=c_scale) != ci: return None return p
[docs]def successor(g, vid, **kwds): """ TODO: see aml.Successor doc string. """ edge_type = g.property('edge_type') rt = kwds.get('RestrictedTo', 'NoRestriction') ci = kwds.get('ContainedIn') son = None for v in g.children_iter(vid): if edge_type.get(v) == '<': son = v break else: return None if rt == 'SameComplex': if g.complex(son) != g.complex(vid): return None if ci is not None: c_scale = g.scale(ci) if g.complex_at_scale(vid, scale=c_scale) != g.complex_at_scale(son, scale=c_scale) != ci: return None return son
[docs]def predecessor(g, vid, **kwds): return father(g, vid, **kwds)
[docs]def root(g, vid, RestrictedTo='NoRestriction', ContainedIn=None): """ TODO: see aml.Root doc string. """ rt = RestrictedTo ci = ContainedIn v_current = vid for v in ancestors(g, vid): if rt == 'SameComplex': if g.complex(v) != g.complex(vid): break v_current = v return v_current
[docs]def location(g, vid, **kwds): """TODO: see doc aml.Location. """ scale = kwds.get('Scale') ci = kwds.get('ContainedIn') if not scale or scale < 0: scale = g.max_scale() current_scale = g.scale(vid) return father(g, vid, scale=scale, ContainedIn=ci)
[docs]def sons(g, vid, **kwds): """TODO: see doc aml.sons. """ et = kwds.get('EdgeType','*') rt = kwds.get('RestrictedTo', 'NoRestriction') ci = kwds.get('ContainedIn') scale = kwds.get('Scale') edge_type = g.property('edge_type') current_scale = g.scale(vid) if not scale or scale < 0: scale = current_scale if scale < current_scale: vid = g.complex_at_scale(vid, scale = scale) elif scale > current_scale: vid = g.component_roots_at_scale_iter(vid, scale=scale).next() children = g.children_iter(vid) if et != '*': children = (v for v in children if edge_type[v] == et) if ci is not None: c_scale = g.scale(ci) children = (v for v in children if g.complex_at_scale(v) == ci) return list(children)
[docs]def full_ancestors(g, v1, **kwds): " Return the vertices from v1 to the root. " edge_type = g.property('edge_type') et = kwds.get('EdgeType','*') rt = kwds.get('RestrictedTo', 'NoRestriction') ci = kwds.get('ContainedIn') v = v1 if ci is not None: c_scale = g.scale(ci) while v is not None: if et != '*' and edge_type.get(v) != et: break if rt == 'SameComplex': if g.complex(v) != g.complex(v1): break elif rt == 'SameAxis': if edge_type.get(v) == '+': break if ci and g.complex_at_scale(v, scale=c_scale) != ci: break yield v v = g.parent(v)
[docs]def axis(g, vtx_id, scale=-1, **kwds): """TODO: see aml doc """ edge_type = g.property('edge_type') rt = kwds.get('RestrictedTo', 'NoRestriction') ci = kwds.get('ContainedIn') kwds['EdgeType'] = '<' if ci is not None: c_scale = g.scale(ci) for v in ancestors(g, vtx_id, **kwds): if rt == 'SameComplex': if g.complex(v) != g.complex(vtx_id): break if ci and g.complex_at_scale(v, scale=c_scale) != ci: break if edge_type.get(v) == '+': break return local_axis(g, v, scale=scale, **kwds)
[docs]def descendants(g, vtx_id, scale=-1, **kwds): """TODO: see aml doc """ edge_type = g.property('edge_type') et = kwds.get('EdgeType','*') rt = kwds.get('RestrictedTo', 'NoRestriction') ci = kwds.get('ContainedIn') if ci is not None: c_scale = g.scale(ci) vtx_id = vertex_at_scale(g, vtx_id, scale) v = vtx_id if rt == 'SameComplex': complex = g.complex(vtx_id) def visitor(v): if et in ['<', '+'] and et != edge_type.get(v, et): return False if rt == 'SameComplex': if g.complex(v) != complex: return False elif rt == 'SameAxis' and edge_type.get(v) == '+': return False if ci and g.complex_at_scale(v, scale=c_scale) != ci: return False return True return traversal.pre_order2_with_filter(g, vtx_id, pre_order_filter=visitor)
[docs]def extremities(g, vid, **kwds): """ TODO see aml doc Implement the method more efficiently... """ vertices = set(descendants(g,vid, **kwds)) for v in vertices: if g.is_leaf(v): yield v else: for vtx in g.children_iter(v): if vtx in vertices: break else: yield v
[docs]def local_axis(g, vtx_id, scale=-1, **kwds): """ Return a sequence of vertices connected by '<' edges. The first element of the sequence is vtx_id. """ edge_type = g.property('edge_type') et = kwds.get('EdgeType','*') rt = kwds.get('RestrictedTo', 'NoRestriction') ci = kwds.get('ContainedIn') vtx_id = vertex_at_scale(g, vtx_id, scale) if ci is not None: c_scale = g.scale(ci) v = vtx_id while v is not None: yield v vtx = v; v = None for vid in g.children_iter(vtx): if edge_type.get(vid) == '<': v = vid if rt == 'SameComplex': if g.complex(v) != g.complex(vtx_id): v = None if ci and g.complex_at_scale(v, scale=c_scale) != ci: v = None
[docs]def vertex_at_scale(g, vtx_id, scale): if scale <= 0: return vtx_id current_scale = g.scale(vtx_id) if scale < current_scale: vtx_id = g.complex_at_scale(vtx_id, scale=scale) elif scale > current_scale: vtx_id = g.component_roots_at_scale_iter(vtx_id, scale=scale).next() return vtx_id
[docs]def trunk(g, vtx_id, scale=-1, **kwds): rt = kwds.get('RestrictedTo', 'NoRestriction') ci = kwds.get('ContainedIn') kwds['EdgeType'] = '<' vtx_id = vertex_at_scale(g, vtx_id, scale) v = root(g, vtx_id, RestrictedTo=rt, ContainedIn=ci) return local_axis(g, v, scale, **kwds)
[docs]def union(g1, g2, vid1=None, vid2=None, edge_type='<'): """ Return the union of the MTGs g1 and g2. :Parameters: - g1, g2 (MTG) : An MTG graph - vid1 : the anchor vertex identid=fier that belong to `g1` - vid2 : the root of the sub_mtg that belong to `g2` which will be added to g1. - edge_type (str) : the type of the edge which will connect vid1 to vid2 """ v1 = vid1 if vid1 is not None else g1.root if v1 not in g1: raise InvalidVertex(v1) v2 = vid2 if vid2 is not None else g2.root if v2 not in g2: raise InvalidVertex(v2) g = g1.sub_mtg(g1.root) #n2 = g._id+1 treeid_id = {} subtree = traversal.iter_mtg2(g2, v2) if v1 is g1.root and v2 is g2.root: treeid_id[v2] = v1 subtree.next() else: v2 = subtree.next() v = g.add_child(v1) treeid_id[v2] = v g._add_vertex_properties(v,g2.get_vertex_property(v2)) g.node(v).edge_type = edge_type for vid in subtree: complex_id = treeid_id[g2.complex(vid)] v = g.add_component(complex_id) treeid_id[vid] = v pid = g2.parent(vid) if pid is not None: parent = treeid_id[pid] v = g.add_child(parent, child=v) # Copy the properties g._add_vertex_properties(v, g2.get_vertex_property(vid)) return g
[docs]def split(g, scale=1): """ Split at scale. """ return [g.sub_mtg(vid) for vid in g.component_roots_at_scale(g.root,scale=scale)]
[docs]def orders(g, scale=-1): """ Compute the order of all vertices at scale `scale`. If scale == -1, the compute the order for vertices at the finer scale. """ orders = {} if scale <= 0: for vid in traversal.iter_mtg2(g, g.root): pid = g.parent(vid) p_order = 0 if pid is None else orders[pid] orders[vid] = p_order+1 if g.edge_type(vid) == '+' else p_order else: for rid in g.roots_iter(scale=scale): for vid in traversal.pre_order2(g, rid): pid = g.parent(vid) p_order = 0 if pid is None else orders[pid] orders[vid] = p_order+1 if g.edge_type(vid) == '+' else p_order return orders
[docs]def heights(g, scale=-1): """ Compute the order of all vertices at scale `scale`. If scale == -1, the compute the order for vertices at the finer scale. """ heights = {} if scale <= 0: for vid in traversal.iter_mtg2(g, g.root): pid = g.parent(vid) p_height = -1 if pid is None else heights[pid] heights[vid] = p_height+1 else: for rid in g.roots_iter(scale=scale): for vid in traversal.pre_order2(g, rid): pid = g.parent(vid) p_height = -1 if pid is None else heights[pid] heights[vid] = p_height+1 return heights
[docs]def lookForCommonAncestor(g, commonAncestors, currentNode): while not(currentNode is None): for i in range(len(commonAncestors)): node = commonAncestors[i] if node == currentNode: for j in range(i): commonAncestors.popleft() return i += 1 currentNode = g.parent(currentNode)
[docs]def lowestCommonAncestor(g, nodes): """LCA algorithm""" from collections import deque lca = None if (len(nodes) > 1): firstNode = nodes[0]; firstAncestors = deque(g.Ancestors(firstNode)) i = 1 while i < len(nodes) and len(firstAncestors) > 0: currentNode = nodes[i] lookForCommonAncestor(g, firstAncestors, currentNode) i += 1 if len(firstAncestors) > 0: lca = firstAncestors[0] return lca