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

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 (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.

See also: biddy.h, biddyInt.h

Definition in file biddyStat.c.

float Biddy_AvgLevel | ( | Biddy_Edge | f | ) |

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).

Macro Biddy_Managed_AvgLevel(f) is defined for user convenience.

Definition at line 163 of file biddyStat.c.

unsigned int Biddy_Managed_CountComplementedEdges | ( | Biddy_Manager | MNG, |

Biddy_Edge | f |
||

) |

Count number of complemented edges in a given BDD.

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.

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

Definition at line 633 of file biddyStat.c.

double Biddy_Managed_CountMinterms | ( | Biddy_Manager | MNG, |

Biddy_Edge | f, |
||

int | nvars |
||

) |

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.

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.

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.

unsigned int Biddy_Managed_CountNodes | ( | Biddy_Manager | MNG, |

Biddy_Edge | f |
||

) |

Count number of nodes in a BDD.

This function must be managed because node selection is used.

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

Definition at line 90 of file biddyStat.c.

unsigned int Biddy_Managed_CountNodesPlain | ( | Biddy_Manager | MNG, |

Biddy_Edge | f |
||

) |

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

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

Definition at line 524 of file biddyStat.c.

unsigned long long int Biddy_Managed_CountPaths | ( | Biddy_Manager | MNG, |

Biddy_Edge | f |
||

) |

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

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

Definition at line 681 of file biddyStat.c.

double Biddy_Managed_DensityOfBDD | ( | Biddy_Manager | MNG, |

Biddy_Edge | f, |
||

unsigned int | nvars |
||

) |

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

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

Definition at line 845 of file biddyStat.c.

double Biddy_Managed_DensityOfFunction | ( | Biddy_Manager | MNG, |

Biddy_Edge | f, |
||

unsigned int | nvars |
||

) |

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

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

Definition at line 795 of file biddyStat.c.

unsigned int Biddy_Managed_DependentVariableNumber | ( | Biddy_Manager | MNG, |

Biddy_Edge | f, |
||

Biddy_Boolean | select |
||

) |

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.

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

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

Definition at line 579 of file biddyStat.c.

float Biddy_Managed_ListAvgLength | ( | Biddy_Manager | MNG | ) |

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

Definition at line 475 of file biddyStat.c.

unsigned int Biddy_Managed_ListMaxLength | ( | Biddy_Manager | MNG | ) |

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

Definition at line 428 of file biddyStat.c.

unsigned int Biddy_Managed_ListUsed | ( | Biddy_Manager | MNG | ) |

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

Definition at line 381 of file biddyStat.c.

unsigned int Biddy_Managed_MaxNodes | ( | Biddy_Manager | MNG, |

Biddy_Edge | f |
||

) |

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

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

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

Definition at line 947 of file biddyStat.c.

unsigned int Biddy_Managed_MinNodes | ( | Biddy_Manager | MNG, |

Biddy_Edge | f |
||

) |

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

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

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

Definition at line 896 of file biddyStat.c.

unsigned long long int Biddy_Managed_NodeTableGCObsoleteNumber | ( | Biddy_Manager | MNG | ) |

Return the number of nodes deleted by GC.

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

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

Definition at line 334 of file biddyStat.c.

unsigned int Biddy_Managed_NodeTableNumVar | ( | Biddy_Manager | MNG, |

Biddy_Variable | v |
||

) |

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

Definition at line 283 of file biddyStat.c.

void Biddy_Managed_PrintInfo | ( | Biddy_Manager | MNG, |

FILE * | f |
||

) |

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

Definition at line 1044 of file biddyStat.c.

unsigned long long int Biddy_Managed_ReadMemoryInUse | ( | Biddy_Manager | MNG | ) |

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

Definition at line 997 of file biddyStat.c.

unsigned long long int Biddy_Managed_SystemLongStat | ( | Biddy_Manager | MNG, |

unsigned int | longstat |
||

) |

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

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

Definition at line 235 of file biddyStat.c.

unsigned int Biddy_Managed_SystemStat | ( | Biddy_Manager | MNG, |

unsigned int | stat |
||

) |

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

Definition at line 186 of file biddyStat.c.

unsigned int Biddy_MaxLevel | ( | Biddy_Edge | f | ) |

Macro Biddy_Managed_MaxLevel(f) is defined for user convenience.

Definition at line 137 of file biddyStat.c.