DDD 1.9.0.20250409152518
DDD.h
Go to the documentation of this file.
1/****************************************************************************/
2/* */
3/* This file is part of libDDD, a library for manipulation of DDD and SDD. */
4/* */
5/* Copyright (C) 2001-2008 Yann Thierry-Mieg, Jean-Michel Couvreur */
6/* and Denis Poitrenaud */
7/* */
8/* This program is free software; you can redistribute it and/or modify */
9/* it under the terms of the GNU Lesser General Public License as */
10/* published by the Free Software Foundation; either version 3 of the */
11/* License, or (at your option) any later version. */
12/* This program is distributed in the hope that it will be useful, */
13/* but WITHOUT ANY WARRANTY; without even the implied warranty of */
14/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
15/* GNU LEsserGeneral Public License for more details. */
16/* */
17/* You should have received a copy of the GNU Lesser General Public License */
18/* along with this program; if not, write to the Free Software */
19/*Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
20/* */
21/****************************************************************************/
22
23/* -*- C++ -*- */
24#ifndef DDD_H
25#define DDD_H
26
27#include <iosfwd>
28#include <string>
29#include <vector>
30
31#include "ddd/DataSet.h"
32#include "ddd/hashfunc.hh"
33
35class _GDDD;
36
38class DDD;
39
48class GDDD
49{
50public:
51 typedef unsigned int id_t;
52private:
55 friend std::ostream& operator<<(std::ostream &os,const GDDD &g);
57 friend class DDD;
58
64 GDDD(const id_t &_g);
67 GDDD(_GDDD *_g);
69 void print(std::ostream& os,std::string s) const;
71 void saveNode(std::ostream&, std::vector<id_t>& )const;
73 unsigned long int nodeIndex(const std::vector<id_t> &)const;
74
75public:
77
78
79 typedef short val_t;
81 typedef unsigned short valsz_t;
83 typedef std::pair<val_t,GDDD> edge_t;
85 typedef std::vector<edge_t > Valuation;
88 typedef const edge_t * const_iterator;
90 int variable() const;
91
98 const_iterator begin() const;
105 const_iterator end() const;
107
109
110
115 GDDD(int variable,const Valuation & value);
125 GDDD(int var,val_t val,const GDDD &d=one );
133 GDDD(int var,val_t val1,val_t val2,const GDDD &d=one); //var-[val1,var2]->d
135
136
138
139
140 static const GDDD one;
143 static const GDDD null;
146 static const GDDD top;
148
150
151
154 bool operator==(const GDDD& g) const{return concret==g.concret;};
158 bool operator!=(const GDDD& g) const{return concret!=g.concret;};
163 bool operator<(const GDDD& g) const;
165
166 /* Accessors */
170 unsigned int refCounter() const;
172 unsigned long int size() const;
174 size_t nbsons () const;
176 long double nbStates() const;
178 long double noSharedSize() const;
179#ifdef EVDDD
181 int getMinDistance () const;
182 GDDD normalizeDistance (int n) const;
183#endif
184
185
187
188
192 static void varName( int var, const std::string& name );
197 static const std::string getvarName( int var );
199
201
202
203 static unsigned int statistics();
206 void mark() const;
208 size_t hash () const {
209 return ddd::int32_hash(concret);
210 }
213 static void garbage();
217 static void pstats(bool reinit=true);
219 static size_t peak();
221
223
224 friend void saveDDD(std::ostream&, std::vector<DDD>);
226 friend void loadDDD(std::istream&, std::vector<DDD>&);
228};
229
230
232std::ostream& operator<<(std::ostream &,const GDDD &);
233/* Binary operators */
236GDDD operator^(const GDDD&,const GDDD&);
239GDDD operator+(const GDDD&,const GDDD&);
242GDDD operator*(const GDDD&,const GDDD&);
245GDDD operator-(const GDDD&,const GDDD&);
246
247
248
254class DDD : public GDDD, public DataSet
255{
256public:
257 /* Constructors */
260 DDD(const DDD &);
263 DDD(const GDDD &g=GDDD::null);
264
273 DDD(int var,val_t val,const GDDD &d=one );
281 DDD(int var,val_t val1,val_t val2,const GDDD &d=one);
285 ~DDD();
286
288
289
290 DDD &operator=(const GDDD&);
292 DDD &operator=(const DDD&);
294
302
303
305 DataSet *newcopy () const { return new DDD(*this); }
307 DataSet *set_intersect (const DataSet & b) const ;
309 DataSet *set_union (const DataSet & b) const;
311 DataSet *set_minus (const DataSet & b) const;
313 bool empty() const;
315 DataSet *empty_set() const;
317 bool set_equal(const DataSet & b) const;
319 bool set_less_than (const DataSet & b) const ;
321 long double set_size() const;
323 size_t set_hash() const;
325 void set_print (std::ostream &os) const { os << *this; }
327 void mark() const { GDDD::mark(); }
328#ifdef EVDDD
329 DataSet *normalizeDistance(int n) const { return new DDD(GDDD::normalizeDistance(n)); }
330 int getMinDistance() const { return GDDD::getMinDistance();}
331#endif
332
334
335
336}; // DDD class
337
338
339
340namespace std {
343 template<>
344 struct less<GDDD> {
345 bool operator()(const GDDD &g1,const GDDD &g2) const{
346 return g1<g2;
347 }
348 };
349}
350
351
352#ifdef EVDDD
353// the variable id of distance nodes
354#define DISTANCE -3
355#endif
356
357#endif
358
359
360
361
362
363
GDDD operator-(const GDDD &, const GDDD &)
Operator for set difference of DDD.
Definition DED.cpp:663
GDDD operator*(const GDDD &, const GDDD &)
Operator for intersection of DDD.
Definition DED.cpp:655
GDDD operator^(const GDDD &, const GDDD &)
Operator for concatenation of DDD.
Definition DED.cpp:659
std::ostream & operator<<(std::ostream &, const GDDD &)
Textual output of DDD into a stream in (relatively) human readable format.
Definition DDD.cpp:352
GDDD operator+(const GDDD &, const GDDD &)
Operator for union of DDD.
Definition DED.cpp:648
This class is the public interface for manipulating Data Decision Diagrams.
Definition DDD.h:255
DataSet * empty_set() const
Returns a pointer to GDDD::null.
Definition DDD.cpp:649
bool empty() const
Return true if this is the empty set.
Definition DDD.cpp:645
DDD & operator=(const GDDD &)
Overloaded behavior for assignment operator, maintains reference counting.
Definition DDD.cpp:573
bool set_less_than(const DataSet &b) const
Compares two sets with a total order.
Definition DDD.cpp:657
long double set_size() const
Compares to DataSet for equality.
Definition DDD.cpp:662
void set_print(std::ostream &os) const
Textual (human readable) output of a DDD.
Definition DDD.h:325
DataSet * set_union(const DataSet &b) const
Compute union of two DDD.
Definition DDD.cpp:638
DataSet * set_minus(const DataSet &b) const
Compute set difference of two DDD.
Definition DDD.cpp:641
bool set_equal(const DataSet &b) const
Compares to DataSet for equality.
Definition DDD.cpp:653
DataSet * newcopy() const
Return a new copy of a DDD.
Definition DDD.h:305
~DDD()
Destructor, maintains refCount.
Definition DDD.cpp:569
size_t set_hash() const
Returns a hash key for the DDD.
Definition DDD.cpp:664
void mark() const
mark() from DataSet interface
Definition DDD.h:327
DataSet * set_intersect(const DataSet &b) const
Compute intersection of two DDD.
Definition DDD.cpp:635
This class is an abstraction of a set of data.
Definition DataSet.h:44
This class is the base class representing a Data Decision Diagram.
Definition DDD.h:49
static const GDDD top
The approximation terminal.
Definition DDD.h:146
bool operator==(const GDDD &g) const
Comparison between DDD.
Definition DDD.h:154
friend std::ostream & operator<<(std::ostream &os, const GDDD &g)
A textual output.
Definition DDD.cpp:352
friend void loadDDD(std::istream &, std::vector< DDD > &)
Function for deserialization. Load a set of DDD from a stream.
Definition DDD.cpp:734
void print(std::ostream &os, std::string s) const
Internal function used in recursion for textual printing of GDDD.
Definition DDD.cpp:335
void mark() const
For garbage collection internals.
Definition DDD.cpp:308
static unsigned int statistics()
Returns unicity table current size. Gives the number of different nodes created and not yet destroyed...
Definition DDD.cpp:303
static void garbage()
For garbage collection, do not call this directly, use MemoryManager::garbage() instead.
Definition DDD.cpp:498
unsigned short valsz_t
A type wide enough to count how many outgoing edges a DDD node has, should be congruent to val_t.
Definition DDD.h:81
static const GDDD one
The accepting terminal. This is the basic leaf for accepted sequences.
Definition DDD.h:140
unsigned int refCounter() const
Returns current reference count of a node.
unsigned long int size() const
Returns the size in number of nodes of a DDD structure.
Definition DDD.cpp:428
const_iterator begin() const
API for iterating over the arcs of a DDD manually.
Definition DDD.cpp:386
std::vector< edge_t > Valuation
To hide how arcs are actually stored. Use GDDD::Valuation to refer to arcs type.
Definition DDD.h:85
const_iterator end() const
API for iterating over the arcs of a DDD manually.
Definition DDD.cpp:390
static void varName(int var, const std::string &name)
Sets a variable's name.
Definition DDD.cpp:588
const edge_t * const_iterator
To hide how arcs are stored.
Definition DDD.h:88
size_t nbsons() const
Returns the number of successors of a given node. This is the size of the arc array of the node.
Definition DDD.cpp:382
friend class DDD
Open access to concret for reference counting in DDD.
Definition DDD.h:57
long double noSharedSize() const
Returns the number of nodes that would be used to represent a DDD if no unicity table was used.
Definition DDD.cpp:492
unsigned int id_t
Definition DDD.h:51
GDDD()
Default constructor creates the empty set DDD.
Definition DDD.h:117
unsigned long int nodeIndex(const std::vector< id_t > &) const
Another function used in serialization.
Definition DDD.cpp:673
friend void saveDDD(std::ostream &, std::vector< DDD >)
Function for serialization. Save a set of DDD to a stream.
Definition DDD.cpp:706
GDDD(_GDDD *_g)
UNIMPLEMENTED DELIBERATELY: see SHom.h for details.
static size_t peak()
Returns the peak size of the DDD unicity table. This value is maintained up to date upon GarbageColle...
Definition DDD.cpp:313
bool operator!=(const GDDD &g) const
Comparison between DDD.
Definition DDD.h:158
int variable() const
Returns a node's variable.
Definition DDD.cpp:378
static const GDDD null
The non-accepting terminal.
Definition DDD.h:143
static void pstats(bool reinit=true)
Prints some statistics to std::cout.
Definition DDD.cpp:318
long double nbStates() const
Returns the number of states or paths represented by a given node.
Definition DDD.cpp:482
void saveNode(std::ostream &, std::vector< id_t > &) const
A function for DDD serialization (beta).
Definition DDD.cpp:683
id_t concret
The real implementation class.
Definition DDD.h:61
short val_t
The type used as values of variables in a DDD.
Definition DDD.h:79
size_t hash() const
For storage in a hash table.
Definition DDD.h:208
static const std::string getvarName(int var)
Gets a variable's name.
Definition DDD.cpp:592
bool operator<(const GDDD &g) const
Total ordering function between DDD.
Definition DDD.cpp:375
std::pair< val_t, GDDD > edge_t
An edge is a pair <value,child node>
Definition DDD.h:83
Definition DDD.cpp:57
uint32_t int32_hash(uint32_t a)
Another of Wang's fast hash with a magic number.
Definition hashfunc.hh:56
Definition DDD.h:340
bool operator()(const GDDD &g1, const GDDD &g2) const
Definition DDD.h:345

Please comment this page and report errors about it on the RefDocComments page.
Generated on Wed Apr 9 2025 15:27:42 for DDD by doxygen 1.9.8