# Constrained connectivity hierarchy¶

 Alpha-omega constrained connectivity hierarchy based on the given vertex weighted graph. Strongly constrained connectivity hierarchy based on the given edge weighted graph.
constrained_connectivity_hierarchy_alpha_omega(graph, vertex_weights)[source]

Alpha-omega constrained connectivity hierarchy based on the given vertex weighted graph.

For $$(i,j)$$ be an edge of the graph, we define $$w(i,j)=|w(i) - w(j)|$$, the weight of this edge. Let $$X$$ be a set of vertices, the range of $$X$$ is the maximal absolute difference between the weights of any two vertices in $$X$$: $$R(X) = \max\{|w(i) - w(j)|, (i,j)\in X^2\}$$

Let $$\alpha$$ be a positive real number, a set of vertices $$X$$ is $$\alpha$$-connected, if for any two vertices $$i$$ and $$j$$ in $$X$$, there exists a path from $$i$$ to $$j$$ in $$X$$ composed of edges of weights lower than or equal to $$\alpha$$.

Let $$\alpha$$ and $$\omega$$ be a two positive real numbers, the $$\alpha-\omega$$-connected components of the graph are the maximal $$\alpha'$$-connected sets of vertices with a range lower than or equal to $$\omega$$, with $$\alpha'\leq\alpha$$.

Finally, the alpha-omega constrained connectivity hierarchy is defined as the hierarchy composed of all the $$k-k$$-connected components for all positive $$k$$.

The definition used follows the one given in:

P. Soille, “Constrained connectivity for hierarchical image partitioning and simplification,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 7, pp. 1132-1145, July 2008. doi: 10.1109/TPAMI.2007.70817

The algorithm runs in time $$\mathcal{O}(n\log(n))$$ and proceeds by filtering a quasi-flat zone hierarchy (see quasi_flat_zones_hierarchy())

Parameters
• graph – input graph

• vertex_weights – edge_weights: edge weights of the input graph

Returns

a tree (Concept CptHierarchy) and its node altitudes

constrained_connectivity_hierarchy_strong_connection(graph, edge_weights)[source]

Strongly constrained connectivity hierarchy based on the given edge weighted graph.

Let $$X$$ be a set of vertices, the range of $$X$$ is the maximal weight of the edges linking two vertices inside $$X$$.

Let $$\alpha$$ be a positive real number, a set of vertices $$X$$ is $$\alpha$$-connected, if for any two vertices $$i$$ and $$j$$ in $$X$$, there exists a path from $$i$$ to $$j$$ in $$X$$ composed of edges of weights lower than or equal to $$\alpha$$.

Let $$\alpha$$ be a positive real numbers, the $$\alpha$$-strongly connected components of the graph are the maximal $$\alpha'$$-connected sets of vertices with a range lower than or equal to $$\alpha$$ with $$\alpha'\leq\alpha$$.

Finally, the strongly constrained connectivity hierarchy is defined as the hierarchy composed of all the $$\alpha$$- strongly connected components for all positive $$\alpha$$.

The definition used follows the one given in:

P. Soille, “Constrained connectivity for hierarchical image partitioning and simplification,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 7, pp. 1132-1145, July 2008. doi: 10.1109/TPAMI.2007.70817

The algorithm runs in time $$\mathcal{O}(n\log(n))$$ and proceeds by filtering a quasi-flat zone hierarchy (see quasi_flat_zones_hierarchy())

Parameters
• graph – input graph

• edge_weights – edge_weights: edge weights of the input graph

Returns

a tree (Concept CptHierarchy) and its node altitudes