Constrained connectivity hierarchy¶

`constrained_connectivity_hierarchy_alpha_omega`(…)	Alpha-omega constrained connectivity hierarchy based on the given vertex weighted graph.
`constrained_connectivity_hierarchy_strong_connection`(…)	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\).