# -*- coding: utf-8 -*-
# !/usr/bin/env python3
import re
import random
import logging
import numpy as np
from tqdm import tqdm
from collections import defaultdict
# Our modules
from ..lattice.stylers import DefaultNodeStyler
try:
import matplotlib.pyplot as plt
matplotlib_loaded = True
except:
matplotlib_loaded = False
try:
import networkx as nx
nx_loaded = True
except:
nx_loaded = False
log = logging.getLogger()
def _get_xy(n, pos):
"""Small helper function"""
labels = tuple(sorted(n.labels))
return pos[labels]
[docs]
class Node(object):
"""Represent an inflection class tree or lattice.
Attributes:
labels (list): labels of all the leaves under this node.
children (list): direct children of this node.
attributes (dict): attributes for this node.
Currently, three attributes are expected:
size (int): size of the group represented by this node.
DL (float): Description length for this node.
color (str): color of the splines from this node to its children, in a format usable by pyplot.
Currently, red ("r") is used when the node didn't decrease Description length, blue ("b") otherwise.
macroclass (bool): Is the node in a macroclass ?
macroclass_root (bool): Is the node the root of a macroclass ?
The attributes "_x" and "_rank" are reserved,
and will be overwritten by the draw function.
"""
[docs]
def __init__(self, labels, children=None, **kwargs):
""" Node constructor.
Arguments:
labels (Iterable): labels of all the leaves under this node.
children (list): direct children of this node.
**kwargs: any other keyword argument will be added as node attributes.
Note that certain algorithm expect the Node to have (int) "size",
(str) "color", (bool) "macroclass", or (float) "DL" attributes.
Note:
The attributes "_x" and "_rank" are reserved,
and will be overwritten by the draw function.
"""
self.labels = sorted(labels)
self.children = children if children else []
self.attributes = kwargs
self.istree = self._test_if_tree()
def _test_if_tree(self):
""" Test if this is a tree by checking in-degree."""
parents = {}
for node in self:
for child in node.children:
if child in parents:
return False
parents[child] = node
return True
def __str__(self):
"""Return a repr string for Nodes."""
attrs = " - ".join(
"{}={}".format(key, self.attributes[key]) for key in self.attributes)
return "< Node object - " + ", ".join(self.labels) + " - " + attrs + ">"
[docs]
def introduces_objects(self):
"""
Tests whether the node introduces new objects or not.
Returns:
bool: Whether this node introduces a new object.
"""
return bool(self.attributes.get('objects', False))
[docs]
def introduces_attributes(self):
"""
Tests whether the node introduces a new attribute or not.
Returns:
bool: Whether the node introduces a new attribute.
"""
return bool(self.attributes.get('common', False))
[docs]
def is_supremum(self):
"""
Tests whether the node is the supremum or not.
Returns:
bool: Whether the node is the supremum.
"""
return self.attributes.get('is_supremum', False)
[docs]
def macroclasses(self, parent_is_macroclass=False):
"""Find all the macroclasses nodes in this tree"""
self_is_macroclass = self.attributes["macroclass"]
if not parent_is_macroclass and self_is_macroclass:
labels = self.labels
return {labels[0]: labels}
elif self.children:
macroclasses_under = {}
for child in self.children:
child_macroclasses = child.macroclasses(
parent_is_macroclass=self_is_macroclass)
macroclasses_under.update(child_macroclasses)
return macroclasses_under
return {}
def _recursive_xy(self, ticks, pos, node_spacing, max_x, y_factor=1):
""" Recursively calculate the inner node positions using the Qumin layout.
Leaves positions must have already been calculated.
All other positions are calculated bottom-up: deciding on a node's position requires knowing all its children
position.
Inner nodes positions are calculated with:
- a y value higher than their highest children (with a separation of y_factor).
- a x value separated with `node_spacing` from existing points, in order of prefence:
a) The point at the middle of the children's x positions.
b) The closest point to (a) horizontally available, with proper node spacing.
Args:
ticks (dict): existing coordinates, with y positins as keys, and x positions as values.
For a given height, gives all the points which are already "taken".
pos (dict): a dictionary of node labels (sorted tuples) to x,y positions.
node_spacing (float): minimal spacing to ensure between nodex.
max_x (float): maximal x value (horizontal position)
y_factor (float): height separation between nodes.
Returns:
x, y the calculated positions of the node self.
"""
labels = tuple(sorted(self.labels))
if labels not in pos: # Calculate coords
xs, ys = zip(
*[child._recursive_xy(ticks, pos, node_spacing,
max_x, y_factor) for child in self.children])
self.height = max([child.height for child in self.children]) + 1
y = max(ys) + (y_factor ** (self.height - 1))
xs = sorted(xs)
x = xs[0] + ((xs[-1] - xs[0]) / 2) # mid-point of children
if y in ticks:
# If the preferred value is far enough, pick it
min_dist = min(abs(x - x2) for x2 in ticks[y])
if min_dist < node_spacing:
# We prefer candidates in the node span
candidates = np.arange(0 - node_spacing, max_x + node_spacing, node_spacing).tolist()
# Pick the candidate closest to the preferred center point
# ties are sorted by preferring positions further to existing points
candidates = [(x1, min(abs(x1 - x2) for x2 in ticks[y])) for x1 in candidates]
x, min_dist = max(candidates, key=lambda x: x[1])
ticks[y].append(x)
else:
ticks[y] = [x]
pos[labels] = x, y
return pos[labels]
def _erase_xy(self):
if "_x" in self.attributes:
del self.attributes["_x"]
if "_y" in self.attributes:
del self.attributes["_y"]
for child in self.children:
child._erase_xy()
[docs]
def get_layout(self, layout, y_factor=1, x_factor=15, seed=0):
""" Calculates positions to draw the hierarchy.
The qumin layout is ideal for trees (eg. macroclasses) or for
lattices unless they become really big. The y axis represents hierarchical relations.
All leaves (microclasses) are laid out in a line at the bottom.
>>> tree = Node("A", children=[Node("B"), Node("C")]) # minimal tree (A (B ) (C ))
>>> pos = tree.get_layout("qumin")
All other layouts rely on networkx.
>>> pos = tree.get_layout("spring")
You could also just use any networkx pos dictionary by doing:
>>> nx_node = tree.to_networkx(seed=42)
>>> pos = nx.drawing.spring_layout(nx_node)
In all case, the layout can then be passed to Node.draw().
Args:
layout: layout name. Available options are: qumin, dot,
spring, kamada_kawai and radial.
y_factor: vertical node spacing, default 1. Only for qumin layout. (TODO: move to styler)
seed: random seed.
Returns:
a dictionary of node labels to positions.
"""
if layout == "qumin":
# Calculate leaves position
leaves_ordered = self._sort_leaves()
x = 0
y = 1
pos = {}
for leaf in leaves_ordered:
leaf_label = tuple(sorted(leaf.labels))
pos[leaf_label] = (x, y)
leaf.height = 1
x += 2 * x_factor
# Calculate inner node positions
self._recursive_xy({}, pos, x_factor, x+x_factor, y_factor)
return pos
else:
graphviz_layout = nx.drawing.nx_agraph.graphviz_layout
nx_layouts = {"dot": lambda x: graphviz_layout(x, prog="dot"),
"spring": nx.drawing.spring_layout,
"kamada_kawai": nx.drawing.kamada_kawai_layout,
"radial": lambda x: graphviz_layout(x, prog="twopi"),
}
try:
layout_f = nx_layouts[layout]
except KeyError:
raise NotImplementedError("Layout method {} is not implemented."
"pick from: {}".format(layout,
", ".join(
nx_layouts)))
return layout_f(self.to_networkx(seed=seed))
def _sort_leaves(self):
"""Sorts leaves by similarity for plotting.
This is a greedy tsp implementation.
"""
leaves = list(self.leaves())
li = len(leaves)
similarities = np.full((li, li), -1.0, dtype=float)
ancestors = np.full((li, li), -1, dtype=int)
ancestors = defaultdict(set)
for node in self:
for l in node.labels:
ancestors[(l,)].add(tuple(node.labels))
for i, leaf in enumerate(leaves):
for j, leaf2 in enumerate(leaves):
if i != j:
a1 = ancestors[tuple(leaf.labels)]
a2 = ancestors[tuple(leaf2.labels)]
united = a1 | a2
jaccard = len(a1 & a2) / len(united) if united else 0
similarities[i, j] = similarities[j, i] = jaccard
paths = {i: [i] for i in range(li)}
def shortest_path(sim):
return np.unravel_index(np.argmax(sim, axis=None), sim.shape)
i = None
for x in range(li - 1):
i, j = shortest_path(similarities)
i_start = paths[i][0]
j_end = paths[j][-1]
similarities[i, :] = float("-inf")
similarities[:, j] = float("-inf")
similarities[j_end, i_start] = float("-inf") # don't loop
res = paths[i] + paths[j]
for k in res:
paths[k] = res
assert len(paths[i]) == li, ("This error might be caused by duplicated lexemes"
" that are not in the leaves dictionary. Ensure that you passed microclasses"
" that correspond to the incidence table for ICLattice()")
return [leaves[k] for k in paths[i]]
[docs]
def to_networkx(self, seed=0):
log.info('Converting to networkx...')
# Initialize random events
random.seed(seed)
if not nx_loaded:
raise ImportError("Can't convert to networkx, because it couldn't be loaded.")
G = nx.DiGraph()
for node in self:
name = tuple(sorted(node.labels))
G.add_node(name, **node.attributes)
for child in node.children:
childname = tuple(sorted(child.labels))
G.add_edge(name, childname)
return G
def __eq__(self, other):
return (self.labels == other.labels) & (set(self.children) == set(other.children))
def __repr__(self):
rules = [
str(node.labels) + " -> " + " ".join(str(c.labels) for c in sorted(node.children, key=lambda x: x.labels)) if node.children else str(node.labels)
for
node in self]
return "\n".join(sorted(rules))
def __hash__(self):
return hash(repr(self))
def __iter__(self):
agenda = [self]
nodes = []
while agenda:
node = agenda.pop(0)
if not node.attributes.get("visited", False):
node.attributes["visited"] = True
agenda = node.children + agenda
nodes.append(node)
# cleanup
for n in nodes:
del n.attributes["visited"]
yield from nodes
[docs]
def leaves(self):
return filter(lambda x: not bool(x.children), self)
[docs]
def tree_string(self):
"""Return the inflection class tree as a string with parenthesis.
Assumes size, DL and color attributes,
with color = "r" if this is above a macroclass.
Example:
In the label, fields are separated by "#" as such::
(<labels>#<size>#<DL>#<color> )
"""
if not self.istree:
raise NotImplementedError(
"Tree string is only possible with trees, this looks like a graph.")
labels = "&".join(self.labels)
ignore = ["_rank", "_x", "_y", "macroclass", "macroclass_root", "point_settings"]
attributes = "#".join(
"{}={}".format(key, str(self.attributes[key]).replace(" ", "_")) for key in
sorted(self.attributes) if
key not in ignore)
children_str = [child.tree_string() for child in self.children]
string = "(" + labels + "#" + attributes + " ".join([""] + children_str) + " )"
return string
[docs]
def draw(self,
styler=None,
seed=0,
interactive=False,
pos=None):
"""Draw the hierarchy as a pyplot graph.
By default, the Qumin layout and the DefaultNodeStyler are used.
You can pass a styler and a layout explicitly too:
>>> tree = Node("A", children=[Node("B"), Node("C")]) # minimal tree (A (B ) (C ))
>>> lines, nodes = tree.draw(DefaultNodeStyler, pos=tree.get_layout("spring"))
Arguments:
styler (qumin.lattice.stylers.LatticeStyler): Styling object
for advanced plot customization.
interactive (bool):
Whether this is destined to create an interactive plot.
pos (dict):
A dictionnary of node label to x,y positions.
Compatible with networkx layout functions.
If absent, wil use qumin's default layout.
seed (float):
A seed for reproducible random effects.
"""
# Set the properties of each node/arc.
if styler is None:
styler = DefaultNodeStyler
styler.set_size_scale(self)
# Shorthands
horizontal = styler.horizontal
topdown = styler.topdown
# Get the position of each node: default to qumin layout.
if pos is None:
pos = self.get_layout("qumin",
y_factor=styler.layout_y_factor,
x_factor=styler.layout_x_factor,
seed=seed)
# Set the coordinates of the node.
if not matplotlib_loaded:
return str(self)
else:
if horizontal:
factor = -1 if topdown else 1
def coords(node):
x, y = _get_xy(node, pos)
return y*factor, x
else:
factor = 1 if topdown else -1
def coords(node):
x, y = _get_xy(node, pos)
return x, y*factor
# Textoffset should be an offset value in points. This is not handled by mpld3,
# so instead we use an absolute value.
offsetvalue = styler.textoffset * (1 if topdown == horizontal else -1)
offset = (offsetvalue, 0) if horizontal else (0, offsetvalue)
ax = plt.gca()
lines = []
all_nodes = []
logging.info('Drawing nodes and arcs')
for node in tqdm(self, total=len(list(self))):
# Get node coordinates
this_x, this_y = coords(node)
# Plot the edges
for child in node.children:
child_x, child_y = coords(child)
attr = styler.get_edge_properties(node, child)
if styler.square:
if horizontal:
l = ax.plot((this_x, this_x, child_x),
(this_y, child_y, child_y), **attr)
else:
l = ax.plot((this_x, child_x, child_x),
(this_y, this_y, child_y), **attr)
else:
l = ax.plot((this_x, child_x), (this_y, child_y), **attr)
lines.extend(l)
# Plot the node
coll = ax.scatter((this_x,), (this_y,),
**styler.get_marker_properties(node))
lines.append(coll)
# Write annotations
label_properties = styler.get_label_properties(node)
for txt, opts in label_properties:
if txt:
options = dict(
xy=(this_x, this_y),
xycoords='data',
xytext=(this_x+offset[0], this_y+offset[1]),
textcoords="data",
)
options.update(opts)
plt.annotate(txt, **options)
all_nodes.append(node)
# Scale axes
ax.autoscale()
if interactive:
if horizontal:
ax.margins(x=0.3, y=0.1)
else:
ax.margins(y=0.3, x=0.1)
plt.tick_params(
axis='both', # changes apply to the x-axis
which='both', # both major and minor ticks
top='off', # ticks along the top edge
bottom='off', # ticks along the bottom edge
right='off', # ticks along the right edge
left='off', # ticks along the left edge
labelbottom='off'
)
plt.yticks([], [])
plt.xticks([], [])
return lines, all_nodes
[docs]
def string_to_node(string, legacy_annotation_name=None):
"""Parse an inflection tree written as a string.
Note: Keep or remove this function. It was created to read Macroclasses written
to the disk. It is not called currently by any script, but could be useful
to users who would like to manipulate macroclass computations.
Example:
In the label, fields are separated by "#" as such::
(<labels>#<size>#<DL>#<color> (... ) (... ) )
Returns:
Node: The root of the tree
"""
legacy = False
if "=" not in string:
legacy = True
def parse_node(line):
splitted = line[1:].split("#")
labels = splitted[0]
attributes = dict(attr.split("=") for attr in splitted[1:])
return labels, attributes
def parse_node_legacy(item):
item = item[1:].split("#")
return item
stack = []
# plus robuste que de splitter sur l'espace, autorise les espaces dans les lexèmes & attributs
items = re.split(" (?=[()])", string)
if legacy_annotation_name:
annotation_name = legacy_annotation_name
else:
annotation_name = "DL"
for item in items:
if item[0] == "(":
if legacy:
# Backward compatibility mode
labels, size, annotation, color = parse_node_legacy(item)
if not color:
color = "c"
if not annotation:
annotation = ""
attributes = {"size": float(size),
annotation_name: annotation,
"color": color,
"macroclass": color == "r"}
else:
labels, attributes = parse_node(item)
if 'color' not in attributes:
attributes['color'] = "c"
attributes['macroclass'] = attributes['color'] != 'r'
labels = sorted(labels.split("&"))
attributes['macroclass_root'] = False
if annotation_name in attributes:
try:
attributes[annotation_name] = float(attributes[annotation_name])
except ValueError:
pass # only convert numbers
stack.append(Node(labels, **attributes))
if item[0] == ")":
if len(item) > 1:
log.warning("Warning, bad format ! #{}#".format(item))
if len(stack) > 1:
child = stack.pop(-1)
parent = stack[-1]
# Macroclass are one level below the red :
child.attributes['macroclass_root'] = parent.attributes[
'color'] == 'r' and \
child.attributes['color'] != 'r'
stack[-1].children.append(child)
else:
return stack[0]
if len(stack) > 1:
log.warning("unmatched parenthesis or no root ! " + str(stack))
log.info(stack[0])
return stack[0]