cudd
3.0.0
The University of Colorado Decision Diagram Package
|
Multiway-branch tree manipulation. More...
#include <stdio.h>
Go to the source code of this file.
Macros | |
#define | MTR_DEFAULT 0x00000000 |
#define | MTR_TERMINAL 0x00000001 |
#define | MTR_SOFT 0x00000002 |
#define | MTR_FIXED 0x00000004 |
#define | MTR_NEWNODE 0x00000008 |
Typedefs | |
typedef struct MtrNode_ | MtrNode |
multi-way tree node. | |
Functions | |
MtrNode * | Mtr_AllocNode (void) |
Allocates new tree node. More... | |
void | Mtr_DeallocNode (MtrNode *node) |
Deallocates tree node. More... | |
MtrNode * | Mtr_InitTree (void) |
Initializes tree with one node. More... | |
void | Mtr_FreeTree (MtrNode *node) |
Disposes of tree rooted at node. More... | |
MtrNode * | Mtr_CopyTree (MtrNode const *node, int expansion) |
Makes a copy of tree. More... | |
void | Mtr_MakeFirstChild (MtrNode *parent, MtrNode *child) |
Makes child the first child of parent. More... | |
void | Mtr_MakeLastChild (MtrNode *parent, MtrNode *child) |
Makes child the last child of parent. More... | |
MtrNode * | Mtr_CreateFirstChild (MtrNode *parent) |
Creates a new node and makes it the first child of parent. More... | |
MtrNode * | Mtr_CreateLastChild (MtrNode *parent) |
Creates a new node and makes it the last child of parent. More... | |
void | Mtr_MakeNextSibling (MtrNode *first, MtrNode *second) |
Makes second the next sibling of first. More... | |
void | Mtr_PrintTree (MtrNode const *node) |
Prints a tree, one node per line. More... | |
MtrNode * | Mtr_InitGroupTree (int lower, int size) |
Allocate new tree. More... | |
MtrNode * | Mtr_MakeGroup (MtrNode *root, unsigned int low, unsigned int high, 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 high) |
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... | |
Multiway-branch tree manipulation.
This package provides two layers of functions. Functions of the lower level manipulate multiway-branch trees, implemented according to the classical scheme whereby each node points to its first child and its previous and next siblings. These functions are collected in mtrBasic.c.
Functions of the upper layer deal with group trees, that is the trees used by group sifting to represent the grouping of variables. These functions are collected in mtrGroup.c.
Copyright (c) 1995-2015, Regents of the University of Colorado
All rights reserved.
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.
MtrNode* Mtr_AllocNode | ( | void | ) |
Makes a copy of tree.
If parameter expansion is greater than 1, it will expand the tree by that factor. It is an error for expansion to be less than 1.
Creates a new node and makes it the first child of parent.
Creates a new node and makes it the last child of parent.
void Mtr_DeallocNode | ( | MtrNode * | node | ) |
Deallocates tree node.
node | node to be deallocated |
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.
group | group to be dissolved |
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.
root | root of the group tree |
low | lower bound of the group |
size | upper bound of the group |
void Mtr_FreeTree | ( | MtrNode * | node | ) |
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.
MtrNode* Mtr_InitTree | ( | void | ) |
Initializes tree with one node.
Makes child the first child of parent.
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.’
root | root of the group tree |
low | lower bound of the group |
size | size of the group |
flags | flags for the new group |
Makes child the last child of parent.
Makes second the next sibling of first.
Second becomes a child of the parent of first.
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.
The second argument, gives the map from levels to variable indices.
root | root of the group tree |
invperm | map from levels to indices |
fp | output file |
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.
The second argument, silent, if different from 0, causes Mtr_PrintGroups to only check the syntax of the group tree.
root | root of the group tree |
silent | flag to check tree syntax only |
void Mtr_PrintTree | ( | MtrNode const * | node | ) |
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):
Normally, the only flags that are needed are D and F. Groups and fields are separated by white space (spaces, tabs, and newlines).
fp | file pointer |
nleaves | number of leaves of the new tree |
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.
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.
first | first node to be swapped |
second | second node to be swapped |