hynet.utilities package

Submodules

hynet.utilities.base module

General utilities.

class hynet.utilities.base.Timer

Bases: object

Measure time since Timer object creation or time measurements.

interval()

Return the time in seconds since the last measurement or object creation.

For the first measurement, the time elapsed since object creation is returned. From the second measurement onwards, the time elapsed since the last measurement is returned.

reset()

Reset the timer.

total()

Return the time in seconds since object creation.

hynet.utilities.base.create_dense_vector(i, data, n, dtype=<class 'numpy.complex128'>)

Create n-dim. vector x with x[i] = data[i].

hynet.utilities.base.create_sparse_diag_matrix(diagonal, dtype=<class 'numpy.complex128'>)

Return a diagonal matrix.

hynet.utilities.base.create_sparse_matrix(i, j, data, m, n, dtype=<class 'numpy.complex128'>)

Return an m-by-n sparse matrix A with A[i[k], j[k]] = data[k].

hynet.utilities.base.create_sparse_zero_matrix(m, n, dtype=<class 'numpy.float64'>)

Return an m-by-n all-zeros matrix.

hynet.utilities.base.partition_iterable(iterable, num_blocks)

Partition the iterable into the specified number of consecutive blocks.

Parameters:

• iterable (Iterable) – Iterable to be partitioned.
• num_blocks (hynet_int_) – Number of blocks into which the iterable shall be partitioned.

Yields:

blocks (Iterable) – Blocks of the iterable.

hynet.utilities.base.truncate_with_ellipsis(string, max_len)

Truncate the string with an ellipsis if its length exceeds max_len.

hynet.utilities.chordal module

hynet.utilities.cvxopt module

Utilities related to CVXOPT.

hynet.utilities.cvxopt.cvxopt2scipy(matrix, nonzero_only=False)

Return the CVXOPT sparse matrix as a SciPy sparse matrix.

Parameters:

• matrix (cvxopt.spmatrix) – Matrix that shall be converted.
• nonzero_only (bool, optional) – If False (default), all entries are transferred, regardless of their value. If True, the data is checked and only nonzero entries are transferred.

Returns:

Input matrix as a SciPy sparse matrix.

Return type:

hynet_sparse_

hynet.utilities.cvxopt.scipy2cvxopt(matrix)

Return the SciPy sparse matrix as a CVXOPT sparse matrix.

Parameters:matrix (hynet_sparse_) – Matrix that shall be converted. Returns:Input matrix in CVXOPT’s sparse format. Return type:cvxopt.spmatrix

hynet.utilities.graph module

Graph-related utilities.

hynet.utilities.graph.eliminate_parallel_edges(edges)

Eliminates parallel edges from the graph and returns those edges.

The edges are considered undirected, i.e., and the source and destination node are interchangeable. In the returned edges, the source is set to the adjacent node with the higher node number.

hynet.utilities.graph.get_adjacency_matrix(edges, num_nodes=None, weights=None)

Return the adjacency matrix for an undirected graph specified by its edges.

Parameters:

• edges ((numpy.ndarray[hynet_int_], numpy.ndarray[hynet_int_])) – Edges of the graph in terms of node number tuples.
• num_nodes (int, optional) – Number of nodes in the graph. By default, this is set to the maximum node number in edges plus one.
• weights (numpy.ndarray[hynet_float_], optional) – Edge weights for a weighted adjacency matrix. For parallel edges, the weights are accumulated.

Returns:

A – Adjacency matrix of the undirected graph.

Return type:

hynet_sparse_

hynet.utilities.graph.get_graph_components(nodes, edges, roots=None)

Return a list of connected components.

The returned list contains an element for every connected component, where the element constitutes an array with all nodes of that component. The first element of the array is the root node of the respective component.

hynet.utilities.graph.get_laplacian_matrix(edges, num_nodes=None)

Return the Laplacian matrix for an undirected graph specified by its edges.

Parameters:

• edges ((numpy.ndarray[hynet_int_], numpy.ndarray[hynet_int_])) – Edges of the graph in terms of node number tuples.
• num_nodes (int, optional) – Number of nodes in the graph. By default, this is set to the maximum node number in edges plus one.

Returns:

L – Laplacian matrix of the undirected graph.

Return type:

hynet_sparse_

hynet.utilities.graph.get_minimum_spanning_tree(edges, weights)

Return the minimum spanning tree in terms of an edges tuple.

Parameters:

• edges ((numpy.ndarray[hynet_int_], numpy.ndarray[hynet_int_])) – Edges of the graph in terms of node number tuples.
• weights (numpy.ndarray[hynet_float_], optional) – Edge weights. For parallel edges, the weights are accumulated.

Returns:

mst_edges – Edges of the minimum spanning tree in terms of node number tuples.

Return type:

(numpy.ndarray[hynet_int_], numpy.ndarray[hynet_int_])

hynet.utilities.graph.get_num_spanning_trees(edges)

Return the number of spanning trees for the given undirected graph.

The number of spanning trees is determined using Kirchhoff’s matrix tree theorem, see e.g. [1].

Caution: The vertices must be numbered consecutively starting from zero. If the graph is not connected, the number of spanning trees is zero.

Remark: As SciPy does not inherently support the computation of the determinant of a sparse matrix, the Laplacian matrix is converted to a dense (NumPy) matrix for the computation of a cofactor of the Laplacian. Due to this, the performance is potentially poor for large graphs.

Parameters:edges ((numpy.ndarray[hynet_int_], numpy.ndarray[hynet_int_])) – Edges of the graph in terms of node number tuples. Returns:Number of spanning trees of the undirected graph. Return type:numpy.float64

:raises OverflowError : If the computation results in an overflow.:

References

[1]	Russell Merris, “Laplacian Matrices of Graphs: A Survey”, Linear Algebra and its Applications, vol. 197-198, p. 143-176, 1994.

hynet.utilities.graph.is_acyclic_component(nodes, edges, root)

Return True if the root’s component is acyclic and False otherwise.

hynet.utilities.graph.is_acyclic_graph(nodes, edges)

Return True if the graph is acyclic and False otherwise.

hynet.utilities.graph.traverse_graph(nodes, edges, callback, roots=None, auto_root=True)

Traverse the graph and run a callback at every node.

The graph is traversed in a depth-first fashion and, at every visited node, the provided callback function is called, which must exhibit the signature:

def callback(node, node_pre, cycle)

Therein, node is the currently visited node, node_pre is the previously visited node (or numpy.nan if the current node is the component’s root, i.e., the traversal entered a new component), and cycle is True if the current node was already visited, i.e., the edge traversed from the previous to the current node closes a cycle. The callback function returns an abort flag, i.e., if the callback returns True, the traversal is aborted.

Remark: This function is most efficient if the nodes are numbered consecutively from zero to the number of nodes minus one. Negative node numbers are not supported.

Parameters:

• nodes (numpy.ndarray[hynet_int_]) – Node numbers of the graph.
• edges ((numpy.ndarray[hynet_int_], numpy.ndarray[hynet_int_])) – Edges of the graph in terms of node number tuples.
• callback (function) – Node visit callback function.
• roots (numpy.ndarray[hynet_int_], optional) – Numbers of the root nodes of the graph.
• auto_root (bool, optional) – If True (default), components without a root node are assigned an arbitrary node as its root.

hynet.utilities.rank1approx module

Rank-1 approximation of a partial Hermitian matrix.

hynet.utilities.rank1approx.calc_rank1approx_mse(V, v, edges)

Calculate the mean squared error for the rank-1 approximation.

Returns the mean of the squared error of the elements on the diagonal as well as those on sparsity pattern defined by edges.

hynet.utilities.rank1approx.calc_rank1approx_rel_err(V, v, edges)

Calculate the relative reconstruction error for all edges.

hynet.utilities.rank1approx.get_armijo_step_size(f, x, grad_fx, gamma=1, epsilon=0.2, alpha=2)

Return a step size based on the Armijo-Goldstein condition.

This step size is designed for a Wirtinger calculus based gradient descent method that minimizes the function f(x), where x in C^N is the current candidate solution, grad_fx is the gradient vector w.r.t. conj(x) evaluated at x, and the step direction d = -grad_fx. This function returns a step size s in R_(+), such that the algorithmic map reads x -> x + s * d.

hynet.utilities.rank1approx.rank1approx_via_least_squares(V, edges, roots, grad_thres=1e-07, mse_rel_thres=0.002, max_iter=300, show_convergence_plot=False)

Return a rank-1 approximation vv^H of V by minimizing the squared error.

The rank-1 approximation may be put as the following optimization problem:

minimize  ||P(vv^H - V)||_F^2
v in C^N

Therein, P(X) is the projection of the matrix X onto the sparsity pattern defined by edges, i.e., all diagonal elements and the off-diagonal elements (edges[k][0], edges[k][1]) and (edges[k][1], edges[k][0]) for k = 0,...,K-1, where K is the number of edges. ||.||_F denotes the Frobenius norm. For V >= 0 (psd) and V != 0, this problem is nonconvex, i.e., the objective is not convex over the entire C^N. (If rank(V) = 1 and V = xx^H, then the objective is locally convex at x.)

This function finds a (local) optimizer of this problem using a Wirtinger calculus based gradient descent with an Armijo-Goldstein step size control, which is initialized with the vector v obtained from the graph traversal rank-1 approximation method. (During the iterations it is ensured that the least squares error decreases, otherwise the iterations are aborted with a warning. Consequently, in terms of the least squares error, this approximation is at least as accurate as the traversal-based approximation.)

Parameters:

• V (hynet_sparse_) – Matrix that should be approximated by vv^H.
• edges ((numpy.ndarray[hynet_int_], numpy.ndarray[hynet_int_])) – Specification of the sparsity pattern of the matrix V.
• roots (numpy.ndarray[hynet_int_]) – Root nodes for the graph components of the sparsity pattern. The absolute angle in v is adjusted such that the absolute angle at the root nodes is zero.
• grad_thres (hynet_float_, optional) – Absolute threshold on the 2-norm of the objective’s gradient w.r.t. v divided by N. (Termination criterion on the first order condition for local optimality.)
• mse_rel_thres (hynet_float_, optional) – Threshold on the relative improvement of ||P(vv^H - V)||_F^2 / N from the candidate solution v in iteration i to v in iteration i + 1. (Termination criterion on stalling progress.)
• max_iter (hynet_int_, optional) – Maximum number of iterations. (Fallback in case the other termination criteria are not met in a reasonable number of iterations.)
• show_convergence_plot (bool, optional) – If True, a plot is shown to illustrate the convergence behavior.

Returns:

v – Vector v, where vv^H approximates V on the sparsity pattern.

Return type:

numpy.ndarray

hynet.utilities.rank1approx.rank1approx_via_traversal(V, edges, roots)

Return a rank-1 approximation vv^H of V based on a graph traversal.

Assuming that V = vv^H (i.e., rank(V) = 1), the off-diagonal element in row i and column j is V_ij = v_i*conj(v_j). Thus, |v_j| = sqrt(V_jj) and arg(v_j) = arg(v_i) - arg(V_ij). This is utilized to recover v by setting its element’s magnitude to the square root of the diagonal elements of V and reconstructing the angle of its elements by accumulating the angle differences from the respective root node of in the graph associated with V. The angle at the root node(s) is set to zero.

hynet.utilities.worker module

Management of worker processes in hynet.

param workers:Worker manager created at import time for parallel processing within the hynet package. type workers:WorkerManager

class hynet.utilities.worker.WorkerManager

Bases: object

Manage operations on a pool of workers.

This class provides operations on a pool of worker processes in case that parallel processing in hynet is enabled and, otherwise, it performs the operations in the current process. The pool of workers is maintained lazily, i.e., it is created on demand.

See also

hynet.config

close_pool()

Close the pool of worker processes.

is_multiprocessing

Return True if the operations utilize multiprocessing.

map(func, iterable, show_progress=False, unit='it', **kwds)

Apply the function to every item (single argument) in the iterable.

Parameters:

• func (function) – Function that shall be applied to the items in the iterable. The function object must support pickling.
• iterable (iterable) – Iterable containing the function arguments. An item in this iterable is the single argument passed to the function. The iterable must support len(iterable).
• show_progress (bool, optional) – If True (default False), the progress is reported to the standard output.
• unit (str, optional) – Name of one unit of iteration for the progress visualization (default it).
• kwds (dict, optional) – If parallel processing is enabled, the keyword arguments are passed to the map-method of multiprocessing.Pool.

Returns:

result – List of the function result for every item in the iterable.

Return type:

list

See also

multiprocessing.Pool.map()

num_workers

Return the number of worker processes.

These workers are only active if parallel processing is enabled.

See also

hynet.config

starmap(func, iterable, **kwds)

Apply the function to every item (argument tuple) in the iterable.

Parameters:

• func (function) – Function that shall be applied to the items in the iterable. The function object must support pickling.
• iterable (iterable) – Iterable containing the function arguments. An item in this iterable is a tuple of the arguments passed to the function.
• kwds (dict, optional) – If parallel processing is enabled, the keyword arguments are passed to the starmap-method of multiprocessing.Pool.

Returns:

result – List of the function result for every item in the iterable.

Return type:

list

See also

multiprocessing.Pool.starmap()

hynet.utilities.worker.pool_operation(method)

Decorates a worker operation method with a pool state verification.

The worker manager maintains its pool of workers lazily, i.e., it is only created on demand. Due to this, every potential pool operation in the worker manager class has to verify and, if necessary, update the pool state prior to the operation itself. This decorator manages this task. In the worker operation method, the code only needs to adapt to the availability of the pool.

Module contents

Collection of utilities for hynet.