Block Triangularization

pyomo.contrib.incidence_analysis.triangularize.block_triangularize(matrix, matching=None)[source]

Compute ordered partitions of the matrix’s rows and columns that permute the matrix to block lower triangular form

Subsets in the partition correspond to diagonal blocks in the block triangularization. The order is topological, with ties broken “lexicographically”.

Parameters:

  • matrix (scipy.sparse.coo_matrix) – Matrix whose rows and columns will be permuted

  • matching (dict) – A perfect matching. Maps rows to columns and columns back to rows.

Returns:

  • row_partition (list of lists) – A partition of rows. The inner lists hold integer row coordinates.

  • col_partition (list of lists) – A partition of columns. The inner lists hold integer column coordinates.

Note

Breaking change in Pyomo 6.5.0

The pre-6.5.0 block_triangularize function returned maps from each row or column to the index of its block in a block lower triangularization as the original intent of this function was to identify when coordinates do or don’t share a diagonal block in this partition. Since then, the dominant use case of block_triangularize has been to partition variables and constraints into these blocks and inspect or solve each block individually. A natural return type for this functionality is the ordered partition of rows and columns, as lists of lists. This functionality was previously available via the get_diagonal_blocks method, which was confusing as it did not capture that the partition was the diagonal of a block triangularization (as opposed to diagonalization). The pre-6.5.0 functionality of block_triangularize is still available via the map_coords_to_block_triangular_indices function.

pyomo.contrib.incidence_analysis.triangularize.get_blocks_from_maps(row_block_map, col_block_map)[source]

DEPRECATED.

Deprecated since version 6.5.0: get_blocks_from_maps is deprecated. This functionality has been incorporated into block_triangularize.

pyomo.contrib.incidence_analysis.triangularize.get_diagonal_blocks(matrix, matching=None)[source]

DEPRECATED.

Deprecated since version 6.5.0: get_diagonal_blocks has been deprecated. Please use block_triangularize instead.

pyomo.contrib.incidence_analysis.triangularize.get_scc_of_projection(graph, top_nodes, matching=None)[source]

Return the topologically ordered strongly connected components of a bipartite graph, projected with respect to a perfect matching

The provided undirected bipartite graph is projected into a directed graph on the set of “top nodes” by treating “matched edges” as out-edges and “unmatched edges” as in-edges. Then the strongly connected components of the directed graph are computed. These strongly connected components are unique, regardless of the choice of perfect matching. The strongly connected components form a directed acyclic graph, and are returned in a topological order. The order is unique, as ambiguities are resolved “lexicographically”.

The “direction” of the projection (where matched edges are out-edges) leads to a block lower triangular permutation when the top nodes correspond to rows in the bipartite graph of a matrix.

Parameters:

  • graph (NetworkX Graph) – A bipartite graph

  • top_nodes (list) – One of the bipartite sets in the graph

  • matching (dict) – Maps each node in top_nodes to its matched node

Returns:

The outer list is a list of strongly connected components. Each strongly connected component is a list of tuples of matched nodes. The first node is a “top node”, and the second is an “other node”.

Return type:

list of lists