Functions to support group specification for reordering. More...

#include "util.h"
#include "mtrInt.h"

Include dependency graph for mtrGroup.c:

Functions
MtrNode *	Mtr_InitGroupTree (int lower, int size)
	Allocate new tree. More...

MtrNode *	Mtr_MakeGroup (MtrNode *root, unsigned int low, unsigned int size, unsigned int flags)
	Makes a new group with size leaves starting at low. More...

MtrNode *	Mtr_DissolveGroup (MtrNode *group)
	Merges the children of ‘group’ with the children of its parent. More...

MtrNode *	Mtr_FindGroup (MtrNode *root, unsigned int low, unsigned int size)
	Finds a group with size leaves starting at low, if it exists. More...

int	Mtr_SwapGroups (MtrNode first, MtrNode second)
	Swaps two children of a tree node. More...

void	Mtr_ReorderGroups (MtrNode treenode, int permutation)
	Fix variable tree at the end of tree sifting. More...

void	Mtr_PrintGroups (MtrNode const *root, int silent)
	Prints the groups as a parenthesized list. More...

int	Mtr_PrintGroupedOrder (MtrNode const root, int const invperm, FILE *fp)
	Prints the variable order as a parenthesized list. More...

MtrNode *	Mtr_ReadGroups (FILE *fp, int nleaves)
	Reads groups from a file and creates a group tree. More...

static int	mtrShiftHL (MtrNode *node, int shift)
	Adjusts the low fields of a node and its descendants. More...

Detailed Description

Functions to support group specification for reordering.

See also: cudd package

Author: Fabio Somenzi

Copyright

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Function Documentation

◆ Mtr_DissolveGroup()

MtrNode* Mtr_DissolveGroup ( MtrNode * group )

Merges the children of ‘group’ with the children of its parent.

Disposes of the node pointed by group. If group is the root of the group tree, this procedure leaves the tree unchanged.

Returns: the pointer to the parent of ‘group’ upon successful termination; NULL otherwise.

Side effects None

See also: Mtr_MakeGroup

Parameters

group group to be dissolved

◆ Mtr_FindGroup()

MtrNode* Mtr_FindGroup	(	MtrNode *	root,
		unsigned int	low,
		unsigned int	size
	)

Finds a group with size leaves starting at low, if it exists.

This procedure relies on the low and size fields of each node. It also assumes that the children of each node are sorted in order of increasing low.

Returns: the pointer to the root of the group upon successful termination; NULL otherwise.

Side effects None

Parameters

root	root of the group tree
low	lower bound of the group
size	upper bound of the group

◆ Mtr_InitGroupTree()

MtrNode* Mtr_InitGroupTree	(	int	lower,
		int	size
	)

Allocate new tree.

Allocate new tree with one node, whose low and size fields are specified by the lower and size parameters.

Returns: pointer to tree root.

Side effects None

See also: Mtr_InitTree Mtr_FreeTree

◆ Mtr_MakeGroup()

MtrNode* Mtr_MakeGroup	(	MtrNode *	root,
		unsigned int	low,
		unsigned int	size,
		unsigned int	flags
	)

Makes a new group with size leaves starting at low.

If the new group intersects an existing group, it must either contain it or be contained by it. This procedure relies on the low and size fields of each node. It also assumes that the children of each node are sorted in order of increasing low. In case of a valid request, the flags of the new group are set to the value passed in ‘flags.’

Returns: the pointer to the root of the new group upon successful termination; NULL otherwise. If the group already exists, the pointer to its root is returned.

Side effects None

See also: Mtr_DissolveGroup Mtr_ReadGroups Mtr_FindGroup

Parameters

root	root of the group tree
low	lower bound of the group
size	size of the group
flags	flags for the new group

◆ Mtr_PrintGroupedOrder()

int Mtr_PrintGroupedOrder	(	MtrNode const *	root,
		int const *	invperm,
		FILE *	fp
	)

Prints the variable order as a parenthesized list.

After each group, the group's flag are printed, preceded by a ‘|’. For each flag (except MTR_TERMINAL) a character is printed.

F: MTR_FIXED
N: MTR_NEWNODE
S: MTR_SOFT

The second argument, gives the map from levels to variable indices.

Returns: 1 if successful; 0 otherwise.

Side effects None

See also: Mtr_PrintGroups

Parameters

root	root of the group tree
invperm	map from levels to indices
fp	output file

◆ Mtr_PrintGroups()

void Mtr_PrintGroups	(	MtrNode const *	root,
		int	silent
	)

Prints the groups as a parenthesized list.

After each group, the group's flag are printed, preceded by a ‘|’. For each flag (except MTR_TERMINAL) a character is printed.

F: MTR_FIXED
N: MTR_NEWNODE
S: MTR_SOFT

The second argument, silent, if different from 0, causes Mtr_PrintGroups to only check the syntax of the group tree.

Side effects None

See also: Mtr_PrintTree

Parameters

root	root of the group tree
silent	flag to check tree syntax only

◆ Mtr_ReadGroups()

MtrNode* Mtr_ReadGroups	(	FILE *	fp,
		int	nleaves
	)

Reads groups from a file and creates a group tree.

Each group is specified by three fields:

 low size flags.

Low and size are (short) integers. Flags is a string composed of the following characters (with associated translation):

D: MTR_DEFAULT
F: MTR_FIXED
N: MTR_NEWNODE
S: MTR_SOFT
T: MTR_TERMINAL

Normally, the only flags that are needed are D and F. Groups and fields are separated by white space (spaces, tabs, and newlines).

Returns: a pointer to the group tree if successful; NULL otherwise.

Side effects None

See also: Mtr_InitGroupTree Mtr_MakeGroup

Parameters

fp	file pointer
nleaves	number of leaves of the new tree

◆ Mtr_ReorderGroups()

void Mtr_ReorderGroups	(	MtrNode *	treenode,
		int *	permutation
	)

Fix variable tree at the end of tree sifting.

Fix the levels in the variable tree sorting siblings according to them. It should be called on a non-NULL tree. It then maintains this invariant. It applies insertion sorting to the list of siblings The order is determined by permutation, which is used to find the new level of the node index. Index must refer to the first variable in the group.

Side effects The tree is modified.

◆ Mtr_SwapGroups()

int Mtr_SwapGroups	(	MtrNode *	first,
		MtrNode *	second
	)

Swaps two children of a tree node.

Adjusts the high and low fields of the two nodes and their descendants. The two children must be adjacent. However, first may be the younger sibling of second.

Returns: 1 in case of success; 0 otherwise.

Side effects None

Parameters

first	first node to be swapped
second	second node to be swapped

◆ mtrShiftHL()

static int mtrShiftHL	(	MtrNode *	node,
		int	shift
	)

static

Adjusts the low fields of a node and its descendants.

Adds shift to low of each node. Checks that no out-of-bounds values result.

Returns: 1 in case of success; 0 otherwise.

Side effects None

Parameters

node	group tree node
shift	amount by which low should be changed