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 permutedmatching (
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 ofblock_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 theget_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 ofblock_triangularize
is still available via themap_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 intoblock_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 useblock_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:
- 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