directed_helmholtz
DirectedHelmholtz
Bases: Algorithm
Performs the Directed Helmholtz decomposition for valued (weighted) directed graphs. The decomposition decomposes the edge weights X into a curl-free X_G and gradient-free X_C component.
The algorithm employs the cut method, which calculates X_G from the cut matrix D of the graph by minimizing the difference (X - X_C).(X - X_C)^T with the restriction that D.X_C = 0, a condition that translates into the incoming edge values of X_C being equal to the outgoing edge values (divergence-free). X_G = X - X_C has the property that the sum of edge values along every cycle equals 0 (curl-free).
Taken from DOI: 10.13140/RG.2.2.18011.64807
graph = graph
instance-attribute
matrix = None
instance-attribute
method = 'cut'
instance-attribute
projector = None
instance-attribute
use_points = False
instance-attribute
__init__(graph)
calc_cut_matrix(incidence_matrix)
staticmethod
Given a spanning tree, the cut matrix (n_nodes x n_edges) is the collection of directional edges (+-1) contained in the cut for each node, where only nodes containing one edge from the spanning tree are considered. The cut matrix can be obtained by removing one row from the incidence matrix, yielding a matrix with linearly independent rows.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
incidence_matrix |
ndarray[n_nodes, n_edges]
|
Incidence matrix. |
required |
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[n_cuts, n_edges]: Cut matrix. |
calc_cycle_matrix(span_forest)
The cycle matrix (n_cycles x n_edges) contains for each elementary cycle (cycle basis) in the graph the direction (+-1) of the edges contained in this cycle. The cycle basis can be used to obtain all possible cycles in the graph. This cycle basis can be constructed by calculating the undirected Spanning Tree (span_forest), consisting of the birth edges of the graph, iteratively adding the remaining edges (death edges), and searching for cycles for each iteration. As each death edge adds one elementary cycle to the graph, the number of cycles is equal to the number of death edges.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
span_forest |
ndarray[n_edges, 2]
|
Spanning forest |
required |
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[n_cycles, n_edges]: Cycle matrix. |
calc_incidence_matrix()
The incidence matrices with dimensions n_nodes x n_edges contains for each directed edge a -1 for the node at the base and +1 for the node at the tip of the edge.
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[n_nodes, n_edges]: Incidence matrix. |
calc_matrix()
calc_projector()
Matrix that projects the edge values to their gradient-free subspace.
This matrix is obtained from the generalized restricted least square estimation of (X - X_C).(X - X_C).T with the restriction D.X_C = 0. The reduced laplacian matrix DD^T has the same eigenvalues as the laplacian matrix II^T but has linearly independent rows (with D the cut matrix and I the incidence matrix).
Matrix that projects the edge values to their curl-free subspace. This matrix is obtained from the generalized restricted least square estimation of (X - X_G).(X - X_G).T with the restriction C.X_G = 0. The cycle overlap matrix CC^T contains the lengths of the elementary cycles on the diagonal and the signed overlap of two cycles for the off diagonal elements.
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[n_edges, n_edges]: Projection matrix. |
get_undirected_cycle(graph, source, target)
staticmethod
Calculates the cycle starting from a source node and ending in a target node from a graph where the connection between the source node and target node is missing.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
source |
int
|
Source node. |
required |
target |
int
|
Target node. |
required |
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[n_cycle_edges, 2]: Edges of the undirected cycle. |
mask_approx_zero(edges, edge_scalar, threshold=0.05)
staticmethod
Mask edge values that are close to zero using a threshold.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
edges |
ndarray[n_edges, 2]
|
Edges of the graph. |
required |
edge_scalar |
ndarray[n_edges]
|
Edge values. |
required |
threshold |
float
|
Mask threshold. |
0.05
|
Returns:
| Name | Type | Description |
|---|---|---|
tuple |
(ndarray[n_unmasked, 2], ndarray[n_unmasked])
|
Unmasked edges and edge values. |
orient_cycle(points, cycle_edges)
staticmethod
Orients a given cycle so that the cycle normal points away from the origin.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
points |
ndarray[N, 3]
|
Coordinates of the graph. |
required |
cycle_edges |
ndarray[n_cycle_edges, 2]
|
Edges of the cycle. |
required |
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[n_cycle_edges, 2]: Oriented edges of the cycle. |
run()
Applies the curl or gradient projection matrix of the input edge values X to yield the curl-free and gradient-free components X_G andX_C. Returns: tuple(np.ndarray[n_edges], np.ndarray[n_edges]): Curl-free and gradient-free component.
set_method(method)
Define the decomposition method, default: 'cut'