pymdd.mdd module

class pymdd.mdd.MDD(name='mdd', nodes=None)

Bases: object

MDD represents a multivalued decision diagram (MDD).

MDD represents a multivalued decision diagram, or MDD.

Parameters:

• name (str) – name of MDD (default: ‘mdd’)
• nodes (List[Dict[MDDNode, MDDNodeInfo]]) – nodes of MDD; if None (default), set to empty list

add_arc(newarc)

Add an arc to the MDD.

Add an arc to the MDD (with sanity checks).

Parameters:

newarc (MDDArc) – arc to be added

Raises:

• RuntimeError – head/tail node of arc does not exist
• ValueError – head and tail nodes must be one layer apart

add_node(newnode)

Add a new node to the MDD.

Add a new node to the MDD (with sanity checks).

Parameters:

newnode (MDDNode) – node to be added

Raises:

• IndexError – the MDD does not contain the specified node layer
• ValueError – a duplicate node already exists in the MDD

allincomingarcs()

Return all incoming arcs in the MDD.

allnodeitems_in_layer(layer)

Return all (MDDNode, MDDNodeInfo) pairs in a particular layer.

allnodes()

Return all MDDNodes in the MDD.

allnodes_in_layer(layer)

Return all MDDNodes in a particular layer.

alloutgoingarcs()

Return all outgoing arcs in the MDD.

compile_pathlist(pathList, minArcCostFunc=None, nodeStateFunc=None)

Compile an MDD from a list of paths.

Compile an MDD based on a list of paths (and their associated weights). The weight of each arc is determined according to the canonical arc cost construction. If ‘minArcCost(k)’ is ‘L’, then in the constructed MDD the weight of every arc in layer ‘k’ will be at least ‘L’.

Parameters:

• pathList (List[Tuple[float, List[object]]]) – list of tuples of path weights and paths
• minArcCostFunc (Callable[[int], float]) – minArcCostFunc(j) returns the desired minimum arc weight in layer ‘j’ of the constructed MDD (layer 0 is not considered); if None (default), returns 0.0 for every layer
• nodeStateFunc (Callable[[int,int], object]) – nodeStateFunc(j,k) returns the node state of the ‘k’th node in layer ‘j’; if None (default), returns the tuple ‘(j,k)’

Raises:

RuntimeError – numLayers is not consistent with pathList

compile_top_down(numLayers, domainFunc, trFunc, costFunc, rootState, isFeas, maxWidth=None, mergeFunc=None, adjFunc=None, nodeSelFunc=None)

Compile the MDD top-down according to a DP formulation.

Perform a top-down compilation of the MDD according to a dynamic programming (DP) formulation. For the DP-specifying functions domainFunc, trFunc, and costFunc, layers should be numbered 0, 1, ..., numLayers-1.

Note that ‘mergeFunc’, ‘adjFunc’, and ‘nodeSelFunc’ are only used when compiling restricted/relaxed MDDs, so if ‘maxWidth’ is None, (i.e., compiling an exact MDD), they do not need to be set.

Parameters:

• numLayers (int) – number of (arc) layers (i.e., variables)
• domainFunc (Callable[[int], List[int]]) – domainFunc(j) returns the domain of layer ‘j’
• trFunc (Callable[[object, int, int], object]) – trFunc(s,d,j) returns the state transitioned to when domain value ‘d’ is selected at current state ‘s’, current layer ‘j’
• costFunc (Callable[[object, int, int, object], float]) – costFunc(s,d,j,ns) returns the cost of selecting domain value ‘d’ at current state ‘s’, current layer ‘j’, resulting in next state ‘ns’ (i.e., the output of trFunc(s,d,j))
• rootState (object) – state of the root node
• isFeas (Callable[[object, int], bool]) – isFeas(s,j) returns True if node state ‘s’ in layer ‘j’ is feasible and False otherwise
• maxWidth (Callable[[int], int]) – maxWidth(j) returns the maximum allowable width for layer ‘j’ of the MDD; if None (default), the maximum width is set to +inf and compile_top_down(...) returns an exact MDD
• mergeFunc (Callable[[List[object], int], object]) – mergeFunc(slist,j) returns the node state resulting from merging node states in ‘slist’ in layer ‘j’ (default: None)
• adjFunc (Callable[[float, object, object, int], float]) – adjFunc(w,os,ms,j) returns the adjusted weight of an arc with weight ‘w’, old head node state ‘os’, and new head node (i.e., merged supernode in layer ‘j’) state ‘ms’ (default: None)
• nodeSelFunc (Callable[[List[MDDNode], int], List[MDDNode]]) – nodeSelFunc(vlist,j) returns a list of nodes selected from ‘vlist’ in layer ‘j’ to be either merged (if mergeFunc and adjFunc are defined) or removed (if mergeFunc and adjFunc are None); if nodeSelFunc is None (default), it picks either two (if merging) or one (if removing) node(s) at random

Raises:

• RuntimeError – mergeFunc and adjFunc must be defined together
• RuntimeError – no more nodes to remove/merge but currWidth > maxWidth

compile_trivial(numLayers, domainFunc, costFunc, nodeStateFunc)

Compile a trivial MDD.

Compile a trivial MDD, i.e., one that represents all possible solutions based on the given domains and costs. This MDD contains one node in each layer, and an arc for every possible domain value. For domainFunc costFunc, and nodeStateFunc, the layers should be numbered 0, 1, ..., numLayers-1.

Parameters:

• numLayers (int) – number of (arc) layers (i.e., variables)
• domainFunc (Callable[[int], List[int]]) – domainFunc(j) returns the domain of layer ‘j’
• costFunc (Callable[[int, int], float]) – costFunc(d,j) returns the cost of selecting domain value ‘d’ at current layer ‘j’
• nodeStateFunc (Callable[[int], object]) – nodeStateFunc(j) returns the node state of the node in layer ‘j’

dumpJSON(fname=None, stateDumpFunc=<built-in function repr>, labelDumpFunc=<built-in function repr>)

Dump the MDD into a JSON file.

Dump the contents of the MDD into a JSON file for later retrieval.

Parameters:

• fname (str) – name of json file (default: self.name + ‘.json’)
• stateDumpFunc (Callable[[object], str]) – stateDumpFunc(s) returns a string representation of the node state ‘s’ (default: repr)
• labelDumpFunc (Callable[[object], str]) – labelDumpFunc(l) returns a string representation of the arc label ‘l’ (default: repr)

enumerate_all_paths()

Enumerate all root-terminal paths in the MDD.

Returns:list of path weights/paths Return type:List[Tuple[float, List[object]]]

enumerate_all_prefixes(node)

Enumerate all prefixes of a node.

Parameters:node (MDDNode) – node to examine Returns:list of prefix weights/prefixes Return type:List[Tuple[float, List[object]]]

enumerate_all_suffixes(node)

Enumerate all suffixes of a node.

Parameters:node (MDDNode) – node to examine Returns:list of suffix weights/suffixes Return type:List[Tuple[float, List[object]]]

filter_and_refine_constraint(trFunc, rootState, isFeas, nodeStateFunc, maxWidth=None)

Filter and refine MDD for a constraint.

Perform incremental refinement of a particular constraint on the MDD.

Parameters:

• trFunc (Callable[[object, int, int], object]) – trFunc(s,d,j) returns the state transitioned to when domain value ‘d’ is selected at current state ‘s’, current layer ‘j’
• rootState (object) – state assigned to root node
• isFeas (Callable[[object, int], bool]) – isFeas(s,j) returns True if node state ‘s’ in layer ‘j’ is feasible and False otherwise
• nodeStateFunc (Callable[[object, int], object]) – nodeStateFunc(s,j) returns the node state resulting from transitioning to state ‘s’ in layer ‘j’
• maxWidth (Callable[[int], int]) – maxWidth(j) returns the maximum allowable width for layer ‘j’ of the MDD; if None (default), the maximum width is set to 100 for all layers

find_longest_path()

Find a longest root-terminal path in the MDD.

Returns:maximum weight and longest path Return type:Tuple[float, List[object]]

find_shortest_path()

Find a shortest root-terminal path in the MDD.

Returns:minimum weight and shortest path Return type:Tuple[float, List[object]]

loadJSON(fname, stateLoadFunc=<built-in function eval>, labelLoadFunc=<built-in function eval>)

Load an MDD from a JSON file.

Load the contents of an MDD from a JSON file. NOTE: Since node states and arc labels can be arbitrary python objects, loadJSON uses eval() by default to construct these attributes. THIS ALLOWS FOR ARBITRARY CODE EXECUTION! USE RESPONSIBLY!!!

Parameters:

• fname (str) – name of input file (e.g., mdd.json)
• stateLoadFunc (Callable[[str], object]) – stateLoadFunc(s) returns the node state corresponding to string ‘s’ (default: eval)
• labelLoadFunc (Callable[[str], object]) – labelLoadFunc(s) returns the arc label corresponding to string ‘s’ (default: eval)

Raises:

ValueError – unknown item type (e.g., incorrect input file format)

maxWidth

Maximum number of nodes in a single node layer.

merge_nodes(mnodes, nsfun, awinfun=None, awoutfun=None)

Merge specified nodes into a new node.

Merge nodes in mnodes into a new supernode. The state of the new merged node is specified by nsfun, while the weights of incoming and/or outgoing arcs are specified by awinfun/awoutfun.

Parameters:

• mnodes (List[MDDNode]) – nodes to be merged together
• nsfun (Callable[[List[object], int], object]) – nsfun(slist, j) returns the node state resulting from merging node states in ‘slist’ in layer ‘j’
• awinfun (Callable[[float, object, object, int], float]) – awinfun(w,os,ms,j) returns the adjusted weight of an arc with weight ‘w’, old head node state ‘os’, and new head node (i.e., merged supernode in layer ‘j’) state ‘ms’; if awinfun is None (default), the original weight is used
• awoutfun (Callable[[float, object, object, int], float]) – awoutfun(w,os,ms,j) returns the adjusted weight of an arc with weight ‘w’, old tail node state ‘os’, and new tail node (i.e., merged supernode in layer ‘j’) state ‘ms’; if awoutfun is None (default), the original weight is used

Returns:

new merged supernode

Return type:

MDDNode

Raises:

ValueError – cannot merge nodes in different layers

numArcLayers

Number of arc layers; equal to number of ‘variables’.

numNodeLayers

Number of node layers; equal to number of ‘variables’ + 1.

output_to_dot(nodeDotFunc=None, arcDotFunc=None, arcSortArgs=None, nodeSortArgs=None, reverseDir=False, fname=None)

Write the graphical structure of the MDD to a file.

Write the graphical structure of the MDD to a file (<MDDName>.gv) in the DOT language. The MDD can then be visualized with GraphViz.

Parameters:

• nodeDotFunc (Callable[[object, int], str]) – nodeDotFunc(s,j) returns a string with the DOT options to use given node state ‘s’ in layer ‘j’; if None (default), a sensible default is used
• arcDotFunc (Callable[[object, float, int], str]) – arcDotFunc(l,w,j) returns a string with the DOT options to use given arc label ‘l’, arc weight ‘w’, and tail node layer ‘j’; if None (default), a sensible default is used
• arcSortArgs (dict) – arguments specifying how to sort a list of arcs via list.sort() (i.e., ‘key’ and, optionally, ‘reverse’); GraphViz then attempts to order the arcs accordingly in the output graph; if arcSortArgs is None (default), no such order is enforced
• nodeSortArgs (dict) – arguments specifying how to sort a list of nodes via list.sort() (i.e., ‘key’ and, optionally, ‘reverse’); GraphViz then attempts to order the nodes accordingly in the output graph; if nodeSortArgs is None (default), no such order is enforced
• reverseDir (bool) – if True, show the MDD with arcs oriented in the opposite direction, so the terminal node appears at the top and the root node at the bottom (default: False)
• fname (str) – name of output file; if None, default to <MDDName>.gv

prune_all()

Prune all dead nodes with no root/terminal path.

Prune all nodes from the MDD that do not have a path to the first or last layer. This procedure employs two passes to prune all dead nodes in the MDD. To prune more selectively (e.g., after removing a small number of nodes/arcs), use prune_recusive(...).

prune_recursive(origNodeList)

Recursively prune dead nodes with no root/terminal path.

Recursively prune nodes from the MDD that do not have a path to the first or last layer. Specifically, this procedure first initializes a FIFO queue of nodes to be pruned from ‘origNodeList’. Then, it pops a node ‘u’ from the queue, removes it from the MDD, then adds any nodes ‘v’ neighboring ‘u’ to the queue if the removal of ‘u’ results in ‘v’ having no incoming or outgoing arcs. The process is repeated until the queue is empty. Note that if one wishes to prune all dead nodes, prune_all() may be more efficient.

Parameters:origNodeList (List[MDDNode]) – nodes to be potentially pruned

reduce_bottom_up(mergeFunc, adjInFunc=None, adjOutFunc=None, ignoreLastLayer=False)

Reduce the MDD bottom-up by merging equivalent nodes.

Merge all equivalent nodes in the MDD, i.e., nodes which have the same suffix set. The state of the new node is determined by mergeFunc, and the weight of incoming and outgoing arcs of the new node is adjusted by adjInFunc and adjOutFunc respectively.

Parameters:

• mergeFunc (Callable[[List[object], int], object]) – mergeFunc(slist,j) returns the node state resulting from merging node states in ‘slist’ in layer ‘j’
• adjInFunc (Callable[[float, object, object, int], float]) – adjInFunc(w,os,ms,j) returns the adjusted weight of an arc with weight ‘w’, old head node state ‘os’, and new head node (i.e., merged supernode in layer ‘j’) state ‘ms’ (default: None)
• adjOutFunc (Callable[[float, object, object, int], float]) – adjOutFunc(w,os,ms,j) returns the adjusted weight of an arc with weight ‘w’, old tail node state ‘os’, and new tail node (i.e., merged supernode in layer ‘j’) state ‘ms’ (default: None)
• ignoreLastLayer (bool) – whether to avoid merging last layer (i.e., merge all terminal nodes into one) or not (default: False)

remove_arc(rmvarc)

Remove an arc from the MDD.

Remove an arc from the MDD (with sanity checks).

Parameters:

rmvarc (MDDArc) – arc to be removed

Raises:

• RuntimeError – head/tail node of arc does not exist
• KeyError – no such incoming/outgoing arc exists in the MDD

remove_node(rmvnode)

Remove a node from the MDD.

Remove a node from the MDD (with sanity checks).

Parameters:

rmvnode (MDDNode) – node to be removed

Raises:

• IndexError – the MDD does not contain the specified node layer
• KeyError – no such node exists in the MDD

widthList

Number of nodes in each layer

class pymdd.mdd.MDDArc(label, weight, tail, head)

Bases: object

MDDArc represents a single arc in the MDD.

MDDArc represents a single arc in the MDD. An MDDArc is uniquely identified by its head/tail nodes, label, and weight.

Parameters:

• label (object) – label of arc (e.g., assigned value)
• weight (float) – weight of arc (e.g., coefficient)
• tail (MDDNode) – tail/source node
• head (MDDNode) – head/destination node

class pymdd.mdd.MDDNode(layer, state)

Bases: object

MDDNode represents a single node in the MDD.

MDDNode represents a single node in the MDD. An MDDNode is uniquely identified by its layer and state. The (node) state must be a hashable object.

Parameters:

• layer (int) – layer the node is in
• state (object) – state associated with node

class pymdd.mdd.MDDNodeInfo(incoming=None, outgoing=None)

Bases: object

MDDNodeInfo represents information associated with an MDDNode.

MDDNodeInfo represents information associated with an MDDNode.

Parameters:

• incoming (set) – set of incoming arcs (default: set())
• outgoing (set) – set of outgoing arcs (default: set())