Horizontal Cut¶
This module offers two classes to ease the navigation through the horizontal cuts of a hierarchy.
This class helps to explore and to browse the horizontal cuts of a valued hierarchy. 

Represents an horizontal cut in a hierarchy as a set of nodes. 

Labelize tree leaves according to an horizontal cut of the tree given by its number of regions. 

Labelize tree leaves according to an horizontal cut of the tree given by its altitude. 

labelisation_horizontal_cut_from_num_regions
(tree, altitudes, num_regions, mode='at_least', leaf_graph=None)[source]¶ Labelize tree leaves according to an horizontal cut of the tree given by its number of regions.
If
mode
is"at_least"
(default), the the smallest horizontal cut having at least the given number of regions is considered. Ifmode
is"at_most"
, the the largest horizontal cut having at most the given number of regions is considered.Consider using the class
HorizontalCutExplorer
if you plan to compute several horizontal cuts from a same hierarchy. Parameters
tree – input tree (deduced from
CptHierarchy
)altitudes – node altitudes of the input tree
num_regions – a number of regions
mode –
"at_least"
or"at_most"
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
Leaf labels

labelisation_horizontal_cut_from_threshold
(tree, altitudes, threshold, leaf_graph=None)[source]¶ Labelize tree leaves according to an horizontal cut of the tree given by its altitude.
Two leaves are in the same region (ie. have the same label) if the altitude of their lowest common ancestor is strictly greater than the specified threshold.
Consider using the class
HorizontalCutExplorer
if you plan to compute several horizontal cuts from a same hierarchy. Parameters
tree – input tree (deduced from
CptHierarchy
)altitudes – node altitudes of the input tree
threshold – a threshold level
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
Leaf labels

class
HorizontalCutExplorer
¶ This class helps to explore and to browse the horizontal cuts of a valued hierarchy. Construction of the HorizontalCutExplorer if performed in linear time \(\mathcal{O}(n)\) w.r.t. the number of nodes in the tree. Each cut of the hierarchy can be accessed through:
its index (the first single region cut has index 0). This operations runs in \(\mathcal{O}(k)\), with \(k\) the number of regions in the retrieved cut ;
the number of regions in the cut (the smallest partition having at least the given number of regions if found). This operations runs in \(\mathcal{O}(k*\log(n))\), with \(k\) the number of regions in the retrieved cut;
the altitude of the cut. This operations runs in \(\mathcal{O}(k*\log(n))\), with \(k\) the number of regions in the retrieved cut.

__new__
(tree, altitudes)¶ Creates an horizontal cut explorer for the given valued hierarchy.
Altitudes must be increasing
 Parameters
tree – input tree
altitudes – tree nodes altitudes
 Returns
an
HorizontalCutExplorer

altitude_cut
(self: higra.higram.HorizontalCutExplorer, cut_index: int) → float¶ Altitude of the ith cut of the hierarchy (cut numbering start at 0 with the cut with a single region).

altitude_cuts
(self: higra.higram.HorizontalCutExplorer) → List[float]¶ Altitude of each cut of the hierarchy.

horizontal_cut_from_altitude
(self: higra.higram.HorizontalCutExplorer, threshold: float) → higra.higram.HorizontalCutNodes¶ Retrieve the horizontal cut for given threshold level.

horizontal_cut_from_index
(self: higra.higram.HorizontalCutExplorer, i: int) → higra.higram.HorizontalCutNodes¶ Retrieve the ith horizontal cut of tree (cut numbering start at 0 with the cut with a single region).

horizontal_cut_from_num_regions
(self: higra.higram.HorizontalCutExplorer, num_regions: int, at_least: bool = True) → higra.higram.HorizontalCutNodes¶ Horizontal cut with a given number of regions.
If
at_least
isTrue
(default), the the smallest horizontal cut having at least the given number of regions is returned. Ifat_least
isFalse
, the the largest horizontal cut having at most the given number of regions is returned.

num_cuts
(self: higra.higram.HorizontalCutExplorer) → int¶ Number of horizontal cuts in the hierarchy.

num_regions_cut
(self: higra.higram.HorizontalCutExplorer, i: int) → int¶ Number of regions in the ith cut of the hierarchy (cut numbering start at 0 with the cut with a single region).

num_regions_cuts
(self: higra.higram.HorizontalCutExplorer) → List[int]¶ Number of regions in each cut of the hierarchy.

class
HorizontalCutNodes
¶ Represents an horizontal cut in a hierarchy as a set of nodes.

__init__
()¶ Initialize self. See help(type(self)) for accurate signature.

altitude
(self: higra.higram.HorizontalCutNodes) → float¶ Altitude of the cut.

graph_cut
(tree, leaf_graph, handle_rag=True)¶ Graph cut corresponding to the tree cut. The edge (i, j) has a non zero value if the closest ancestors of i and j in the cut are different.
 Parameters
tree – input tree (Concept
CptHierarchy
)leaf_graph – graph on the tree leaves (deduced from
CptHierarchy
)handle_rag – if True and if leaf_graph is a region adjacency graph then the cut is given for the original graph (the pregraph of the region adjacency graph).
 Returns
a graph cut

labelisation_leaves
(tree, leaf_graph, handle_rag=True)¶ Labelize tree leaves according to the horizontal cut. Two leaves are in the same region (ie. have the same label) if their lowest common ancestor is a subset or equal to one the node of the cut.,
 Parameters
tree – input tree (Concept
CptHierarchy
)leaf_graph – graph on the tree leaves (deduced from
CptHierarchy
)handle_rag – if True and if leaf_graph is a region adjacency graph then the labels are given for the original graph (the pregraph of the region adjacency graph).
 Returns
a 1d array

nodes
(self: higra.higram.HorizontalCutNodes) → xt::xtensor¶ Array containing the indices of the nodes of the cut.

reconstruct_leaf_data
(tree, altitudes, leaf_graph, handle_rag=True)¶ Reconstruct the cut at leaf level of the provided tree. A leaf of the tree is valued by the altitude of the single cut node which is an ancestor of the leaf.
 Parameters
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
leaf_graph – graph on the tree leaves (deduced from
CptHierarchy
)handle_rag – if True and if leaf_graph is a region adjacency graph then the cut is given for the original graph (the pregraph of the region adjacency graph).
 Returns
leaf weights
