# Source code for openalea.mtg.layout

# -*- python -*-
#
#       OpenAlea.mtg
#
#
#
#       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
#
###############################################################################

import traversal, matrix
from random import random

[docs]def layout2d(g, vid=None, origin=(0,0), steps=(4,8), property_name='position'):
""" Compute 2d coordinates for each vertex.

This method compute a 2D layout of a tree or a MTG at a specific scale.
This will allow to plot tree in matplotlib for instance.

:Usage:

.. code-block:: python

>>> g.reindex()
>>> g1 = g.reindex(copy=True)
>>> mymap = dict(zip(list(traversal.iter_mtg2(g,g.root)), range(len(g))))
>>> g2 = g.reindex(mapping=mymap, copy=True)

:Optional Parameters:

- origin : a 2D point for the root of the tree.
- property (str) : Name of the property storing the 2D coordinates.

:Returns:

- a MTG
"""
if vid is None:
vid = g.root
if hasattr(g, 'max_scale'):
vid = g.component_roots_at_scale_iter(g.root, g.max_scale()).next()

# Algorithm
# 1. the y is defined by the Height of a node
# 2. The x is computed using non intersecting bounding box

x_step, y_step = steps

y= {}
vtxs = traversal.pre_order2(g,vid)
vtxs.next()
y[vid] = origin
for v in vtxs:
y[v] = y[g.parent(v)]+y_step

bbox = {}
for v in traversal.post_order2(g,vid):
children = g.children(v)
if not children:
bbox[v] = 2*x_step
else:
has_successor = [cid for cid in children if g.edge_type(cid)=='<']
# 2 is for symmetry
bbox[v] = sum(bbox[cid] for cid in children)
if not has_successor:
bbox[v]+=2*x_step

x ={}
vtxs = traversal.pre_order2(g,vid)
x[vid] = int(bbox[vid]/2.)

for v in vtxs:
_width = bbox[v]
kids = g.children(v)
successor = [cid for cid in kids if g.edge_type(cid)=='<']
ramifs = [cid for cid in kids if g.edge_type(cid)=='+']
_min = x[v]; _max = x[v]
for cid in successor:
_x = x[cid] = x[v]
width = bbox[cid]
_min = _x-max(1,width/2)-x_step
_max = _x+max(1,width/2)+x_step

weights = [bbox[rid] for rid in ramifs]

def mean_ind(weights):
left = bool(random()<0.5)
mid= sum(weights)/2.
total = 0
n = 0
for w in weights:
if total+w <= mid:
total+= w
else:
break
n+=1

if total-mid > 1 and left:
n+=1
if n == 0 and len(weights)>1:
n+=1
return n

n = mean_ind(weights)
for rid in reversed(ramifs[:n]):
width = bbox[rid]
x[rid] = _min - max(1,width/2)
_min -= width
for rid in ramifs[n:]:
width = bbox[rid]
x[rid] = _max + max(1,width/2)
_max += width

# TODO: The tree s not well proportionned because we impose a constraint that the
# < is aligned to its parent

position = dict((k, (x[k],y[k])) for k in y)
g.properties()[property_name] = position

return g

[docs]def simple_layout(g, vid=None, origin=(0,0), steps=(4,8), property_name='position', multiscale=True):
""" Compute 2d coordinates for each vertex.

This method compute a 2D layout of a tree or a MTG at a specific scale.
This will allow to plot tree in matplotlib for instance.

:Usage:

.. code-block:: python

>>> g = simple_layout(g)

:Optional Parameters:

- origin : a 2D point for the root of the tree.
- property (str) : Name of the property storing the 2D coordinates.

:Returns:

- a MTG
"""

def shuffle_post_order(tree, vtx_id):
'''
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')

def shuffle_children(vid):
''' Internal function to retrieve the children in a correct order:
- Branch before successor.
'''
kids = tree.children(vid)
plus = []
successor = []
for v in kids:
if edge_type.get(v) == '<':
successor.append(v)
else:
plus.append(v)
n = len(plus)
i = n/2
if n%2!=0:
left = int(random()<0.5)
i += left
child = plus[:i]+successor+plus[i:]

return child

visited = set([])

queue = [vtx_id]

# 1. select first '+' edges

while queue:

vtx_id = queue[-1]
for vid in shuffle_children(vtx_id):
if vid not in visited:
queue.append(vid)
break
else: # no child or all have been visited
yield vtx_id
queue.pop()

if vid is None:
vid = g.root
if hasattr(g, 'max_scale'):
vid = g.component_roots_at_scale_iter(g.root, g.max_scale()).next()

# Algorithm
# 1. the y is defined by the Height of a node
# 2. The x is computed using non intersecting bounding box

x_step, y_step = steps
y= {}
vtxs = traversal.pre_order2(g,vid)
vtxs.next()
y[vid] = origin
for v in vtxs:
y[v] = y[g.parent(v)]+y_step

def leaves(g, vid):
for v in shuffle_post_order(g,vid):
if g.is_leaf(v):
yield v
def successor(g, vid):
for cid in g.children(vid):
if g.edge_type(cid)=='<':
return cid
return

x = {}
x_pos = origin

for v in leaves(g,vid):
x[v] = x_pos
x_pos += x_step*10

for v in shuffle_post_order(g,vid):
if v in x:
continue
son_id = successor(g,v)
if son_id:
x[v] = x[son_id]
else:
children = g.children(v)
x[v] = int(float(sum(x[cid] for cid in children)) / (len(children)))

position = dict((k, (x[k],y[k])) for k in y)

if multiscale:
# get the position at the lower scales
max_scale = g.scale(vid)

for s in range(max_scale-1,0,-1):
v_root = g.complex_at_scale(vid, scale=s)
vtxs = traversal.pre_order2(g, v_root)
for v in vtxs:
comp_id = g.component_roots_at_scale_iter(v, scale=max_scale).next()
position[v] = position[comp_id]

g.properties()[property_name] = position

return g

[docs]def fruchterman_reingold_layout(g,dim=2,k=None,
pos=None,
fixed=None,
iterations=50,
weight='weight',
scale=1.0):
"""Position nodes using Fruchterman-Reingold force-directed algorithm.

Parameters
----------
G : NetworkX graph

dim : int
Dimension of layout

k : float (default=None)
Optimal distance between nodes.  If None the distance is set to
1/sqrt(n) where n is the number of nodes.  Increase this value
to move nodes farther apart.

pos : dict or None  optional (default=None)
Initial positions for nodes as a dictionary with node as keys
and values as a list or tuple.  If None, then nuse random initial
positions.

fixed : list or None  optional (default=None)
Nodes to keep fixed at initial position.

iterations : int  optional (default=50)
Number of iterations of spring-force relaxation

weight : string or None   optional (default='weight')
The edge attribute that holds the numerical value used for
the edge weight.  If None, then all edge weights are 1.

scale : float (default=1.0)
Scale factor for positions. The nodes are positioned
in a box of size [0,scale] x [0,scale].

Returns
-------
dict :
A dictionary of positions keyed by node

Examples
--------
>>> G=nx.path_graph(4)
>>> pos=nx.spring_layout(G)

# The same using longer function name
>>> pos=nx.fruchterman_reingold_layout(G)
"""
try:
import numpy as np
except ImportError:
raise ImportError("fruchterman_reingold_layout() requires numpy: http://scipy.org/ ")

max_scale = g.max_scale()
vertexlist = g.vertices(scale=max_scale)
if fixed is not None:
nfixed=dict(zip(vertexlist,range(len(vertexlist))))
fixed=np.asarray([nfixed[v] for v in fixed])

if pos is not None:
pos_arr=np.asarray(np.random.random((len(vertexlist),dim)))
for i,n in enumerate(vertexlist):
if n in pos:
pos_arr[i]=np.asarray(pos[n])
else:
pos_arr=None

if len(vertexlist)==0:
return {}
if len(vertexlist)==1:
return {vertexlist:(1,)*dim}

try:
# Sparse matrix
#if len(G) < 500:  # sparse solver for large graphs
#    raise ValueError
A=matrix.to_scipy_sparse_matrix(g,weight=weight,dtype='f')
pos=_sparse_fruchterman_reingold(A,dim,k,pos_arr,fixed,iterations)
except:
A=matrix.to_numpy_matrix(G,weight=weight)
pos=_fruchterman_reingold(A,dim,k,pos_arr,fixed,iterations)
if fixed is None:
pos=_rescale_layout(pos,scale=scale)
return dict(zip(vertexlist,pos))

spring_layout=fruchterman_reingold_layout

def _fruchterman_reingold(A, dim=2, k=None, pos=None, fixed=None,
iterations=50):
# Position nodes in adjacency matrix A using Fruchterman-Reingold
# Entry point for NetworkX graph is fruchterman_reingold_layout()
try:
import numpy as np
except ImportError:
raise ImportError("_fruchterman_reingold() requires numpy: http://scipy.org/ ")

try:
nnodes,_=A.shape
except AttributeError:
raise Exception(
"fruchterman_reingold() takes an adjacency matrix as input")

A=np.asarray(A) # make sure we have an array instead of a matrix

if pos==None:
# random initial positions
pos=np.asarray(np.random.random((nnodes,dim)),dtype=A.dtype)
else:
# make sure positions are of same type as matrix
pos=pos.astype(A.dtype)

# optimal distance between nodes
if k is None:
k=np.sqrt(1.0/nnodes)
# the initial "temperature"  is about .1 of domain area (=1x1)
# this is the largest step allowed in the dynamics.
t=0.1
# simple cooling scheme.
# linearly step down by dt on each iteration so last iteration is size dt.
dt=t/float(iterations+1)
delta = np.zeros((pos.shape,pos.shape,pos.shape),dtype=A.dtype)
# the inscrutable (but fast) version
# this is still O(V^2)
# could use multilevel methods to speed this up significantly
for iteration in range(iterations):
# matrix of difference between points
for i in range(pos.shape):
delta[:,:,i]= pos[:,i,None]-pos[:,i]
# distance between points
distance=np.sqrt((delta**2).sum(axis=-1))
# enforce minimum distance of 0.01
distance=np.where(distance<0.01,0.01,distance)
# displacement "force"
displacement=np.transpose(np.transpose(delta)*\
(k*k/distance**2-A*distance/k))\
.sum(axis=1)
# update positions
length=np.sqrt((displacement**2).sum(axis=1))
length=np.where(length<0.01,0.1,length)
delta_pos=np.transpose(np.transpose(displacement)*t/length)
if fixed is not None:
# don't change positions of fixed nodes
delta_pos[fixed]=0.0
pos+=delta_pos
# cool temperature
t-=dt
pos=_rescale_layout(pos)
return pos

def _sparse_fruchterman_reingold(A, dim=2, k=None, pos=None, fixed=None,
iterations=50):
# Position nodes in adjacency matrix A using Fruchterman-Reingold
# Entry point for NetworkX graph is fruchterman_reingold_layout()
# Sparse version
try:
import numpy as np
except ImportError:
raise ImportError("_sparse_fruchterman_reingold() requires numpy: http://scipy.org/ ")
try:
nnodes,_=A.shape
except AttributeError:
raise Exception(
"fruchterman_reingold() takes an adjacency matrix as input")
try:
from scipy.sparse import spdiags,coo_matrix
except ImportError:
raise ImportError("_sparse_fruchterman_reingold() scipy numpy: http://scipy.org/ ")
# make sure we have a LIst of Lists representation
try:
A=A.tolil()
except:
A=(coo_matrix(A)).tolil()

if pos==None:
# random initial positions
pos=np.asarray(np.random.random((nnodes,dim)),dtype=A.dtype)
else:
# make sure positions are of same type as matrix
pos=pos.astype(A.dtype)

# no fixed nodes
if fixed==None:
fixed=[]

# optimal distance between nodes
if k is None:
k=np.sqrt(1.0/nnodes)
# the initial "temperature"  is about .1 of domain area (=1x1)
# this is the largest step allowed in the dynamics.
t=0.1
# simple cooling scheme.
# linearly step down by dt on each iteration so last iteration is size dt.
dt=t/float(iterations+1)

displacement=np.zeros((dim,nnodes))
for iteration in range(iterations):
displacement*=0
# loop over rows
for i in range(A.shape):
if i in fixed:
continue
# difference between this row's node position and all others
delta=(pos[i]-pos).T
# distance between points
distance=np.sqrt((delta**2).sum(axis=0))
# enforce minimum distance of 0.01
distance=np.where(distance<0.01,0.01,distance)
Ai=np.asarray(A.getrowview(i).toarray())
# displacement "force"
displacement[:,i]+=\
(delta*(k*k/distance**2-Ai*distance/k)).sum(axis=1)
# update positions
length=np.sqrt((displacement**2).sum(axis=0))
length=np.where(length<0.01,0.1,length)
pos+=(displacement*t/length).T
# cool temperature
t-=dt
pos=_rescale_layout(pos)
return pos

def _rescale_layout(pos,scale=1):
# rescale to (0,pscale) in all axes

# shift origin to (0,0)
lim=0 # max coordinate for all axes
for i in range(pos.shape):
pos[:,i]-=pos[:,i].min()
lim=max(pos[:,i].max(),lim)
# rescale to (0,scale) in all directions, preserves aspect
for i in range(pos.shape):
pos[:,i]*=scale/lim
return pos