source: vis_dev/glu-2.1/src/cuBdd/doc/node1.html@ 8

Last change on this file since 8 was 8, checked in by cecile, 15 years ago

src glu
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.