Biddy  2.0.1
An academic Binary Decision Diagrams package
biddyStat.c File Reference

File biddyStat.c contains statistical functions. More...

#include "biddyInt.h"
Include dependency graph for biddyStat.c:

Go to the source code of this file.

Functions

unsigned int Biddy_Managed_CountNodes (Biddy_Manager MNG, Biddy_Edge f)
 Function Biddy_Managed_CountNodes. More...
 
unsigned int Biddy_MaxLevel (Biddy_Edge f)
 Function Biddy_MaxLevel. More...
 
float Biddy_AvgLevel (Biddy_Edge f)
 Function Biddy_AvgLevel. More...
 
unsigned int Biddy_Managed_SystemStat (Biddy_Manager MNG, unsigned int stat)
 Function Biddy_Managed_SystemStat. More...
 
unsigned long long int Biddy_Managed_SystemLongStat (Biddy_Manager MNG, unsigned int longstat)
 Function Biddy_Managed_SystemLongStat. More...
 
unsigned int Biddy_Managed_NodeTableNumVar (Biddy_Manager MNG, Biddy_Variable v)
 Function Biddy_Managed_NodeTableNumVar returns number of nodes with a given variable currently in node table. More...
 
unsigned long long int Biddy_Managed_NodeTableGCObsoleteNumber (Biddy_Manager MNG)
 Function Biddy_Managed_NodeTableGCObsoleteNumber. More...
 
unsigned int Biddy_Managed_ListUsed (Biddy_Manager MNG)
 Function Biddy_Managed_ListUsed. More...
 
unsigned int Biddy_Managed_ListMaxLength (Biddy_Manager MNG)
 Function Biddy_Managed_ListMaxLength. More...
 
float Biddy_Managed_ListAvgLength (Biddy_Manager MNG)
 Function Biddy_Managed_ListAvgLength. More...
 
unsigned int Biddy_Managed_CountNodesPlain (Biddy_Manager MNG, Biddy_Edge f)
 Function Biddy_Managed_CountNodesPlain. More...
 
unsigned int Biddy_Managed_DependentVariableNumber (Biddy_Manager MNG, Biddy_Edge f, Biddy_Boolean select)
 Function Biddy_Managed_DependentVariableNumber. More...
 
unsigned int Biddy_Managed_CountComplementedEdges (Biddy_Manager MNG, Biddy_Edge f)
 Function Biddy_Managed_CountComplementedEdges count the number of complemented edges. More...
 
unsigned long long int Biddy_Managed_CountPaths (Biddy_Manager MNG, Biddy_Edge f)
 Function Biddy_Managed_CountPaths count the number of 1-paths. More...
 
double Biddy_Managed_CountMinterms (Biddy_Manager MNG, Biddy_Edge f, int nvars)
 Function Biddy_Managed_CountMinterms. More...
 
double Biddy_Managed_DensityOfFunction (Biddy_Manager MNG, Biddy_Edge f, unsigned int nvars)
 Function Biddy_Managed_DensityOfFunction calculates the ratio of the number of on-set minterms to the number of all minterms. More...
 
double Biddy_Managed_DensityOfBDD (Biddy_Manager MNG, Biddy_Edge f, unsigned int nvars)
 Function Biddy_Managed_DensityOfBDD calculates the ratio of the number of on-set minterms to the number of nodes. More...
 
unsigned int Biddy_Managed_MinNodes (Biddy_Manager MNG, Biddy_Edge f)
 Function Biddy_Managed_MinNodes reports number of nodes in the optimal ordering. More...
 
unsigned int Biddy_Managed_MaxNodes (Biddy_Manager MNG, Biddy_Edge f)
 Function Biddy_Managed_MaxNodes reports number of nodes in the worst ordering. More...
 
unsigned long long int Biddy_Managed_ReadMemoryInUse (Biddy_Manager MNG)
 Function Biddy_Managed_ReadMemoryInUse reports memory consumption of main data strucutures in bytes (nodes, node table, variable table, ordering table, formula table, ITE cache, EA cache, RC cache, REPLACEcache). More...
 
void Biddy_Managed_PrintInfo (Biddy_Manager MNG, FILE *f)
 Function Biddy_Managed_PrintInfo prepares a file with stats. More...
 

Detailed Description

Description

PackageName [Biddy]
Synopsis    [Biddy provides data structures and algorithms for the
             representation and manipulation of Boolean functions with
             ROBDDs, 0-sup-BDDs, and TZBDDs. A hash table is used for quick
             search of nodes. Complement edges decreases the number of
             nodes. An automatic garbage collection with a system age is
             implemented. Variable swapping and sifting are implemented.]

FileName    [biddyStat.c]
Revision    [$Revision: 617 $]
Date        [$Date: 2020-03-27 23:43:46 +0100 (pet, 27 mar 2020) $]
Authors     [Robert Meolic (robert@meolic.com),
             Ales Casar (ales@homemade.net)]

Copyright

Copyright (C) 2006, 2019 UM FERI, Koroska cesta 46, SI-2000 Maribor, Slovenia. Copyright (C) 2019, 2020 Robert Meolic, SI-2000 Maribor, Slovenia.

Biddy is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

Biddy is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

More info

See also: biddy.h, biddyInt.h

Definition in file biddyStat.c.

Function Documentation

◆ Biddy_AvgLevel()

float Biddy_AvgLevel ( Biddy_Edge  f)

Description

Side effects

The result may not be compatible with your definition of Average Level for DAG. The result is especially problematic if there exist nodes with two equal descendants (e.g for ZBDDs and TZBDDs).

More info

Macro Biddy_Managed_AvgLevel(f) is defined for user convenience.

Definition at line 163 of file biddyStat.c.

◆ Biddy_Managed_CountComplementedEdges()

unsigned int Biddy_Managed_CountComplementedEdges ( Biddy_Manager  MNG,
Biddy_Edge  f 
)

Description

Count number of complemented edges in a given BDD.

Side effects

Terminal 0 is represented by complemented edge to terminal 1 with all BDD types but this edge is counted as a complemented one only if complemented edges are explicitly used.

More info

Macro Biddy_CountComplementedEdges(f) is defined for use with anonymous manager.

Definition at line 633 of file biddyStat.c.

◆ Biddy_Managed_CountMinterms()

double Biddy_Managed_CountMinterms ( Biddy_Manager  MNG,
Biddy_Edge  f,
int  nvars 
)

Description

For combination sets, this function coincides with combinations counting. Parameter nvars is a user-defined number of dependent variables. If (nvars == 0) then all noticeable variables are considered. If (nvars == -1) then all created variables are considered.

Side effects

We are using GNU Multiple Precision Arithmetic Library (GMP). For ZBDDs, this function coincides with the 1-path count. For ZBDDs, result does not depend on the number of considered variables. For OBDD, noticeable variables are all variables existing in the graph. For TZBDD, noticeable variables are all variables equal or below a tag of the top node. For OBDDs and TZBDDs, if (nvars == 0) the result may not be consistent with Biddy_PrintfMinterms because this call considers noticeable variables, while Biddy_PrintfMinterms considers all created variables.

More info

Macro Biddy_CountMinterms(f,nvars) is defined for use with anonymous manager. Macros Biddy_Managed_CountCombinations(MNG,f) and Biddy_CountCombinations(f) are similar functions defined for use with combination sets.

Definition at line 745 of file biddyStat.c.

◆ Biddy_Managed_CountNodes()

unsigned int Biddy_Managed_CountNodes ( Biddy_Manager  MNG,
Biddy_Edge  f 
)

Description

Count number of nodes in a BDD.

Side effects

This function must be managed because node selection is used.

More info

Macro Biddy_CountNodes(f) is defined for use with anonymous manager.

Definition at line 90 of file biddyStat.c.

◆ Biddy_Managed_CountNodesPlain()

unsigned int Biddy_Managed_CountNodesPlain ( Biddy_Manager  MNG,
Biddy_Edge  f 
)

Description

Count number of nodes in a corresponding BDD without complement edges.

Side effects

More info

Macro Biddy_CountNodesPlain(f) is defined for use with anonymous manager.

Definition at line 524 of file biddyStat.c.

◆ Biddy_Managed_CountPaths()

unsigned long long int Biddy_Managed_CountPaths ( Biddy_Manager  MNG,
Biddy_Edge  f 
)

Description

Side effects

TO DO: implement this using GNU Multiple Precision Arithmetic Library (GMP).

More info

Macro Biddy_CountPaths(f) is defined for use with anonymous manager.

Definition at line 681 of file biddyStat.c.

◆ Biddy_Managed_DensityOfBDD()

double Biddy_Managed_DensityOfBDD ( Biddy_Manager  MNG,
Biddy_Edge  f,
unsigned int  nvars 
)

Description

If nvars == 0 then number of dependent variables is used.

Side effects

More info

Macro Biddy_DensityOfBDD(f,nvars) is defined for use with anonymous manager.

Definition at line 845 of file biddyStat.c.

◆ Biddy_Managed_DensityOfFunction()

double Biddy_Managed_DensityOfFunction ( Biddy_Manager  MNG,
Biddy_Edge  f,
unsigned int  nvars 
)

Description

If nvars == 0 then number of dependent variables is used.

Side effects

More info

Macro Biddy_DensityOfFunction(f,nvars) is defined for use with anonymous manager.

Definition at line 795 of file biddyStat.c.

◆ Biddy_Managed_DependentVariableNumber()

unsigned int Biddy_Managed_DependentVariableNumber ( Biddy_Manager  MNG,
Biddy_Edge  f,
Biddy_Boolean  select 
)

Description

Count number of dependent variables. For OBDDs, the number of dependent variables is the same as the number of variables in the graph. For ZBDDs and TZBDDs, this is not true. If (select == TRUE) then dependent variables remain selected otherwise the function will unselect them.

Side effects

For ZBDDs, variables above the top variable (which are always all dependent) are also counted and selected!

More info

Macro Biddy_DependentVariableNumber(f) is defined for use with anonymous manager.

Definition at line 579 of file biddyStat.c.

◆ Biddy_Managed_ListAvgLength()

float Biddy_Managed_ListAvgLength ( Biddy_Manager  MNG)

Description

Side effects

More info

Macro Biddy_ListAvgLength() is defined for use with anonymous manager.

Definition at line 475 of file biddyStat.c.

◆ Biddy_Managed_ListMaxLength()

unsigned int Biddy_Managed_ListMaxLength ( Biddy_Manager  MNG)

Description

Side effects

More info

Macro Biddy_ListMaxLength() is defined for use with anonymous manager.

Definition at line 428 of file biddyStat.c.

◆ Biddy_Managed_ListUsed()

unsigned int Biddy_Managed_ListUsed ( Biddy_Manager  MNG)

Description

Side effects

More info

Macro Biddy_ListUsed() is defined for use with anonymous manager.

Definition at line 381 of file biddyStat.c.

◆ Biddy_Managed_MaxNodes()

unsigned int Biddy_Managed_MaxNodes ( Biddy_Manager  MNG,
Biddy_Edge  f 
)

Description

BDD is copied into new empty manager and then Steinhaus–Johnson–Trotter algorithm is used to check the node number for all possible orderings.

Side effects

Function will finish in a good time only for small number of variables.

More info

Macro Biddy_MaxNodes() is defined for use with anonymous manager.

Definition at line 947 of file biddyStat.c.

◆ Biddy_Managed_MinNodes()

unsigned int Biddy_Managed_MinNodes ( Biddy_Manager  MNG,
Biddy_Edge  f 
)

Description

BDD is copied into new empty manager and then Steinhaus–Johnson–Trotter algorithm is used to check the node number for all possible orderings.

Side effects

Function will finish in a good time only for small number of variables.

More info

Macro Biddy_MinNodes() is defined for use with anonymous manager.

Definition at line 896 of file biddyStat.c.

◆ Biddy_Managed_NodeTableGCObsoleteNumber()

unsigned long long int Biddy_Managed_NodeTableGCObsoleteNumber ( Biddy_Manager  MNG)

Description

Return the number of nodes deleted by GC.

Side effects

Obsolete nodes deleted by GC are counted only if Biddy is compiled using directive BIDDYEXTENDEDSTATS_YES.

More info

Macro Biddy_NodeTableGCObsoleteNumber() is defined for use with anonymous manager.

Definition at line 334 of file biddyStat.c.

◆ Biddy_Managed_NodeTableNumVar()

unsigned int Biddy_Managed_NodeTableNumVar ( Biddy_Manager  MNG,
Biddy_Variable  v 
)

Description

Side effects

More info

Macro Biddy_NodeTableNumVar(v) is defined for use with anonymous manager.

Definition at line 283 of file biddyStat.c.

◆ Biddy_Managed_PrintInfo()

void Biddy_Managed_PrintInfo ( Biddy_Manager  MNG,
FILE *  f 
)

Description

Side effects

More info

Macro Biddy_PrintInfo(f) is defined for use with anonymous manager.

Definition at line 1044 of file biddyStat.c.

◆ Biddy_Managed_ReadMemoryInUse()

unsigned long long int Biddy_Managed_ReadMemoryInUse ( Biddy_Manager  MNG)

Description

Side effects

More info

Macro Biddy_ReadMemoryInUse() is defined for use with anonymous manager.

Definition at line 997 of file biddyStat.c.

◆ Biddy_Managed_SystemLongStat()

unsigned long long int Biddy_Managed_SystemLongStat ( Biddy_Manager  MNG,
unsigned int  longstat 
)

Description

Side effects

These statistics are counted only if Biddy is compiled using directive BIDDYEXTENDEDSTATS_YES.

More info

Macro Biddy_SystemLongStat() is defined for use with anonymous manager.

Definition at line 235 of file biddyStat.c.

◆ Biddy_Managed_SystemStat()

unsigned int Biddy_Managed_SystemStat ( Biddy_Manager  MNG,
unsigned int  stat 
)

Description

Side effects

More info

Macro Biddy_SystemStat() is defined for use with anonymous manager.

Definition at line 186 of file biddyStat.c.

◆ Biddy_MaxLevel()

unsigned int Biddy_MaxLevel ( Biddy_Edge  f)

Description

Side effects

More info

Macro Biddy_Managed_MaxLevel(f) is defined for user convenience.

Definition at line 137 of file biddyStat.c.