Horizontal Cut

This module offers two classes to ease the navigation through the horizontal cuts of a hierarchy.

HorizontalCutExplorer(tree, altitudes)

This class helps to explore and to browse the horizontal cuts of a valued hierarchy.

HorizontalCutNodes

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

labelisation_horizontal_cut_from_num_regions(...)

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

labelisation_horizontal_cut_from_threshold(...)

Labelize tree leaves according to a 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 a horizontal cut of the tree given by its number of regions.

If mode is "at_least" (default), the smallest horizontal cut having at least the given number of regions is considered. If mode is "at_most", 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 a horizontal cut of the tree given by its altitude.

Two leaves are in the same region (i.e. 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(tree, altitudes)

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.

__init__()
__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 i-th 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 i-th 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 is True (default), the the smallest horizontal cut having at least the given number of regions is returned. If at_least is False, 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 i-th 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__(*args, **kwargs)
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 pre-graph 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 pre-graph of the region adjacency graph).

Returns:

a 1d array

nodes(self: higra.higram.HorizontalCutNodes) → numpy.ndarray[numpy.int64]

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 pre-graph of the region adjacency graph).

Returns:

leaf weights