# -*- 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"
from . 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 = next(g.component_roots_at_scale_iter(vid, scale=scale))
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 = next(g.component_roots_at_scale_iter(vid, scale=scale))
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 = next(g.component_roots_at_scale_iter(vtx_id, scale=scale))
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
next(subtree)
else:
v2 = next(subtree)
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