pygsti.layouts.prefixtable.tree_partition_kundu_misra

pygsti.layouts.prefixtable.tree_partition_kundu_misra#

tree_partition_kundu_misra(tree, max_weight, weight_key='cost', test_leaves=True, return_levels_and_weights=False, precomp_levels=None, precomp_weights=None)#

Algorithm for optimal minimum cardinality k-partition of tree (a partition of a tree into cluster of size at most k) based on a slightly less sophisticated implementation of the algorithm from “A Linear Tree Partitioning Algorithm” by Kundu and Misra (SIAM J. Comput. Vol. 6, No. 1, March 1977). Less sophisiticated because the strictly linear time implementation uses linear-time median estimation routine, while this implementation uses sorting (n log(n)-time), in practice it is likely that the highly-optimized C implementation of sorting would beat an uglier python implementation of median finding for most problem instances of interest anyhow.

Parameters:

  • tree (networkx.DiGraph) – An input graph representing the directed tree to perform partitioning on.

  • max_weight (int) – Maximum node weight allowed for each partition.

  • weight_key (str, optional (default 'cost')) – An optional string denoting the node attribute label to use for node weights in partitioning.

  • test_leaves (bool, optional (default True)) – When True an initial test is performed to ensure that the weight of the leaves are all less than the maximum weight. Only turn off if you know for certain this is true.

  • return_levels_and_weights (bool, optional (default False)) – If True return the constructed tree level structure (the lists of nodes partitioned by distance from the root) and subtree weights.

  • precomp_levels (list of sets, optional (default None)) – A list where each set contains nodes that are equidistant from the root.

  • precomp_weights (dict, optional (default None)) – A dictionary where keys are nodes and values are the total weights of the subtrees rooted at those nodes.

Returns:

  • partitioned_tree (networkx.DiGraph) – A new DiGraph corresponding to the partitioned tree. I.e. a copy of the original tree with the requisite edge cuts performed.

  • cut_edges (list of tuples) – A list of the parent-child node pairs whose edges were cut in partitioning the tree.