didppy.minimum_spanning_tree

didppy.minimum_spanning_tree(nodes, edge_costs, connected=None)

Returns a minimum spanning tree expression.

Parameters:

  • nodes (SetExpr, SetVar, SetResourceVar, or SetConst) – Set of nodes.

  • edge_costs (IntTable2D, FloatTable2D, list of tuples, or list of tuples) – Edge costs. A table gives the cost of every pair of nodes. Alternatively, an explicit list of edges can be given as (i, j, weight) tuples, or as (i, j, weight, connected) tuples if each edge also specifies its own connectivity condition instead of using the separate connected argument.

  • connected (BoolTable2D or None) – Edge connectivity, used only when edge_costs is a table. If omitted, all pairs of nodes are considered connected. The graph is interpreted as undirected: for each pair, connected directions are available, and if both directions are available, the smaller edge cost is used.

Returns:

Expression representing the cost of the minimum spanning tree.

Return type:

IntExpr or FloatExpr

Raises:

  • TypeError – If connected is specified while edge_costs is an explicit list of edges.

  • PanicException – If the selected nodes are disconnected under the given connectivity relation.

Examples

>>> import didppy as dp
>>> model = dp.Model()
>>> obj = model.add_object_type(number=4)
>>> nodes = model.create_set_const(object_type=obj, value=[0, 1, 2, 3])
>>> edge_costs = model.add_int_table([[0, 1, 4, 3], [1, 0, 2, 5], [4, 2, 0, 6], [3, 5, 6, 0]])
>>> expr = dp.minimum_spanning_tree(nodes, edge_costs)
>>> expr.eval(model.target_state, model)
6
>>> connected = model.add_bool_table([[True, True, True, False], [True, True, True, True], [True, True, True, True], [False, True, True, True]])
>>> expr = dp.minimum_spanning_tree(nodes, edge_costs, connected)
>>> expr.eval(model.target_state, model)
8
>>> edges = [(0, 1, 1), (0, 2, 4), (0, 3, 3), (1, 2, 2), (2, 3, 6)]
>>> expr = dp.minimum_spanning_tree(nodes, edges)
>>> expr.eval(model.target_state, model)
6