source: vis_dev/glu-2.3/src/cuBdd/doc/node1.html @ 20

Last change on this file since 20 was 13, checked in by cecile, 13 years ago

library glu 2.3
File size: 6.4 KB
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
2
3<!--Converted with LaTeX2HTML 2K.1beta (1.47)
4original version by:  Nikos Drakos, CBLU, University of Leeds
5* revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
6* with significant contributions from:
7  Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
8<HTML>
9<HEAD>
10<TITLE>Introduction</TITLE>
11<META NAME="description" CONTENT="Introduction">
12<META NAME="keywords" CONTENT="cuddIntro">
13<META NAME="resource-type" CONTENT="document">
14<META NAME="distribution" CONTENT="global">
15
16<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
17<META NAME="Generator" CONTENT="LaTeX2HTML v2K.1beta">
18<META HTTP-EQUIV="Content-Style-Type" CONTENT="text/css">
19
20<LINK REL="STYLESHEET" HREF="cuddIntro.css">
21
22<LINK REL="next" HREF="node2.html">
23<LINK REL="previous" HREF="cuddIntro.html">
24<LINK REL="up" HREF="cuddIntro.html">
25<LINK REL="next" HREF="node2.html">
26</HEAD>
27
28<BODY >
29<!--Navigation Panel-->
30<A NAME="tex2html246"
31  HREF="node2.html">
32<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
33 SRC="icons/next.png"></A> 
34<A NAME="tex2html242"
35  HREF="cuddIntro.html">
36<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
37 SRC="icons/up.png"></A> 
38<A NAME="tex2html236"
39  HREF="cuddIntro.html">
40<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
41 SRC="icons/prev.png"></A> 
42<A NAME="tex2html244"
43  HREF="node8.html">
44<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
45 SRC="icons/index.png"></A> 
46<BR>
47<B> Next:</B> <A NAME="tex2html247"
48  HREF="node2.html">How to Get CUDD</A>
49<B> Up:</B> <A NAME="tex2html243"
50  HREF="cuddIntro.html">CUDD: CU Decision Diagram</A>
51<B> Previous:</B> <A NAME="tex2html237"
52  HREF="cuddIntro.html">CUDD: CU Decision Diagram</A>
53 &nbsp <B>  <A NAME="tex2html245"
54  HREF="node8.html">Index</A></B> 
55<BR>
56<BR>
57<!--End of Navigation Panel-->
58
59<H1><A NAME="SECTION00010000000000000000"></A>
60<A NAME="sec:intro"></A>
61<BR>
62Introduction
63</H1>
64
65<P>
66The CUDD package provides functions to manipulate Binary Decision
67Diagrams<A NAME="13"></A> (BDDs) [<A
68 HREF="node7.html#BDD">5</A>,<A
69 HREF="node7.html#BBR">3</A>],
70Algebraic Decision Diagrams<A NAME="15"></A> (ADDs)
71[<A
72 HREF="node7.html#Bahar93">1</A>], and Zero-suppressed Binary Decision
73Diagrams<A NAME="17"></A> (ZDDs)
74[<A
75 HREF="node7.html#Minato93">12</A>]. BDDs are used to represent
76switching<A NAME="19"></A> functions; ADDs are used to
77represent function from <IMG
78 WIDTH="58" HEIGHT="37" ALIGN="MIDDLE" BORDER="0"
79 SRC="img3.png"
80 ALT="$\{0,1\}^n$"> to an arbitrary set.  ZDDs
81represent switching<A NAME="20"></A> functions like BDDs;
82however, they are much more efficient than BDDs when the functions to
83be represented are characteristic<A NAME="21"></A>
84functions of cube<A NAME="22"></A> sets, or in general, when the
85ON-set<A NAME="23"></A> of the function to be represented is
86very sparse. They are inferior to BDDs in other cases.
87
88<P>
89The package provides a large set of operations on BDDs, ADDs, and
90ZDDs, functions to convert BDDs into ADDs or ZDDs and vice versa, and
91a large assortment of variable reordering<A NAME="24"></A> methods.
92
93<P>
94The CUDD package can be used in three ways:
95
96<UL>
97<LI>As a black box<A NAME="26"></A>.  In this case, the application
98  program that needs to manipulate decision diagrams only uses the
99  exported functions of the package. The rich set of functions
100  included in the CUDD package allows many applications to be written
101  in this way.  Section&nbsp;<A HREF="node3.html#sec:user">3</A> describes how to use the
102  exported functions of the package. An application written in terms
103  of the exported functions of the package needs not concern itself
104  with the details of variable reordering<A NAME="28"></A>, which may
105  take place behind the scenes.
106Click <A NAME="tex2html1"
107  HREF="cuddExtAbs.html">here</A>
108for a list of the
109  exported functions.
110</LI>
111<LI>As a clear box<A NAME="31"></A>. When writing a sophisticated
112  application based on decision diagrams, efficiency often dictates
113  that some functions be implemented as direct recursive manipulation
114  of the diagrams, instead of being written in terms of existing
115  primitive functions.  Section&nbsp;<A HREF="node4.html#sec:prog">4</A> explains how to add new
116  functions to the CUDD package. It also details how to write a
117  recursive function that can be interrupted by
118  dynamic<A NAME="33"></A> variable reordering.
119Click <A NAME="tex2html2"
120  HREF="cuddAllAbs.html">here</A>
121for a list of the
122  exported and internal functions.
123</LI>
124<LI>Through an interface. Object-oriented languages like C++ and
125  Perl5 can free the programmer from the burden of memory management.
126  A C++ interface is included in the distribution of CUDD. It
127  automatically frees decision diagrams that are no longer used by the
128  application and overloads operators. Almost all the functionality
129  provided by the CUDD exported functions is available through the C++
130  interface, which is especially recommended for fast prototyping.
131  Section&nbsp;<A HREF="node5.html#sec:cpp">5</A> explains how to use the interface. A Perl5
132  interface also exists and is ditributed separately. (See
133  Section&nbsp;<A HREF="node2.html#sec:getFriends">2.2</A>.) Some applications define their own
134  interfaces. See for example Section&nbsp;<A HREF="node3.html#sec:sis-vis">3.17</A>.
135</LI>
136</UL>
137In the following, the reader is supposed to be familiar with the basic
138ideas about decision diagrams, as found, for instance, in [<A
139 HREF="node7.html#BBR">3</A>].
140
141<P>
142<HR>
143<!--Navigation Panel-->
144<A NAME="tex2html246"
145  HREF="node2.html">
146<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
147 SRC="icons/next.png"></A> 
148<A NAME="tex2html242"
149  HREF="cuddIntro.html">
150<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
151 SRC="icons/up.png"></A> 
152<A NAME="tex2html236"
153  HREF="cuddIntro.html">
154<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
155 SRC="icons/prev.png"></A> 
156<A NAME="tex2html244"
157  HREF="node8.html">
158<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
159 SRC="icons/index.png"></A> 
160<BR>
161<B> Next:</B> <A NAME="tex2html247"
162  HREF="node2.html">How to Get CUDD</A>
163<B> Up:</B> <A NAME="tex2html243"
164  HREF="cuddIntro.html">CUDD: CU Decision Diagram</A>
165<B> Previous:</B> <A NAME="tex2html237"
166  HREF="cuddIntro.html">CUDD: CU Decision Diagram</A>
167 &nbsp <B>  <A NAME="tex2html245"
168  HREF="node8.html">Index</A></B> 
169<!--End of Navigation Panel-->
170<ADDRESS>
171Fabio Somenzi
1722005-05-17
173</ADDRESS>
174</BODY>
175</HTML>
Note: See TracBrowser for help on using the repository browser.