Giter Club home page Giter Club logo

com.github.javabdd's Introduction

com.github.javabdd

Intro

JavaBDD is a Java library for manipulating BDDs (Binary Decision Diagrams). Binary decision diagrams are widely used in model checking, formal verification, optimizing circuit diagrams, etc.

The JavaBDD API is based on that of the popular BuDDy package, a BDD package written in C by Jørn Lind-Nielsen. However, JavaBDD's API is designed to be object-oriented. The ugly C function interface and reference counting schemes have been hidden underneath a uniform, object-oriented interface.

JavaBDD includes multiple 100% Java implementations. JavaBDD provides a uniform interface to all of these implementations, so you can easily switch between them without having to make changes to your application.

JavaBDD is designed for high performance applications, so it also exposes many of the lower level options of the BDD library, like cache sizes and advanced variable reordering.

History

This version of JavaBDD is a fork of the Sourceforge version, see:

It is based on trunk revision r483 from 2011-11-24.

See CHANGES.md for all changes that have been made in this fork.

See CONTRIBUTORS.md for all contributors.

License

This project inherits the license from the Sourceforge project it is forked from, the GNU Library General Public License v2 (LGPLv2) or later. See the LICENSE.txt file.

SPDX-License-Identifier: LGPL-2.0-or-later

com.github.javabdd's People

Contributors

dhendriks avatar magoorden avatar

Stargazers

 avatar  avatar

Watchers

 avatar  avatar

com.github.javabdd's Issues

Clean up todo's

In the code, TODOs are inserted in numerous places. We should identify all TODOs, try to decrypt them, and create separate issues for those that make sense.

Clean up source code

Ideas:

  • Reformat all code with a proper formatting profile. For instance the one from Eclipse ESCET.
  • Use a proper Eclipse JDT warning profile. For instance the one from Eclipse ESCET. Fix all warnings.
  • Use Checkstyle to check the code for issues. For instance use the Eclipse ESCET Checkstyle profile. Address any issues. Integrate the check into the Maven build.
  • Remove all SVN attributes, such as $Id, revisions, etc. Get rid of revisions completely.

Performance measuring of data-based synthesis

In his graduation work, Sander Thuijsman worked on performance measurements of data-based synthesis in CIF. He proposed to use the following two metrics to measure computational effort:

  • Total BDD operations. This is the total number of BDD operations performed by the tool excluding cache hits, which relates to time effort.
  • Max BDD nodes. This is the maximum number of nodes of the BDD encountered during synthesis, which relates to space effort.

More information on these statistics can be found in his Master Thesis or in the paper Thuijsman et al., Computational Effort of BDD-Based Supervisor Synthesis of Extended Finite Automata, IEEE Conference on Automation Science and Engineering, 2019, DOI:10.1109/COASE.2019.8843327.

During his thesis project, Sander adopted the JavaBDD package to collect these statistics. I have cleaned up and enhanced Sander's code such that, for example, an end user can request these statistics (and not by changing hard coded variables in the source code as Sander originally did).

The cache statistic swapCount is never recorded

The recording of the cache statistic swapCount is guarded in JFactory:

if (SWAPCOUNT) {
    cachestats.swapCount++;
}

The constant SWAPCOUNT is hard-coded in JFactory to be false. Therefore, the cachestats will never record this statistic.

Remove @author tags

Remove all @author tags and instead make a CONTRIBUTORS file in the root of the repo with their information.

Remove unused functionality

In #1, we noted that adapting BDDFactory needs updates for every factory implementation, not just JFactory. If we don't use any other factories, besides JFactory, we could opt to remove the other factories, to easy maintenance.

I've looked at which factories there are besides JFactory.

MicroFactory
 * <p>BDD factory where each node only takes 16 bytes.
 * This is accomplished by tightly packing the bits and limiting the
 * maximum number of BDD variables to 2^10 = 1024.</p>
 * 
 * <p>Because of the extra computation required for packing/unpacking,
 * this BDD factory is a little slower than JFactory, but it also uses
 * 20% less memory.</p>

UberMicroFactory
 * <p>BDD factory where each node only takes 16 bytes.
 * This is accomplished by tightly packing the bits, eliminating
 * the refcount, splitting out the unique table and limiting the
 * maximum number of BDD variables to 2^11 = 2048.</p>
 * 
 * <p>This BDD factory is not only more memory efficient than 
 * JFactory, it also seems to perform better, probably due to
 * better memory locality.  It performs cache-aware BDD node
 * placement.</p>

TestBDDFactory
 * This BDD factory is used to test other BDD factories. It is a wrapper around
 * two BDD factories, and all operations are performed on both factories. It
 * throws an exception if the results from the two implementations do not match.

TypedBDDFactory
 * <p>This BDD factory keeps track of what domains each BDD uses, and complains
 * if you try to do an operation where the domains do not match.</p>

MicroFactory and UberMicroFactory use less memory. MicroFactory may actually be slower, while UberMicroFactory is indicated to be a bit faster. However, both are more restricted than JFactory in the number of variables, nodes, references, etc they can story (due to using less bits to represent a node). From a practical point of view, for Eclipse ESCET we already run out of memory (Java array size) for large supervisor synthesis inputs. As such, I can imagine just removing these micro-variants from the code base here.

I see that TestBDDFactory is not used anywhere, and neither is TypedBDDFactory. We could opt to remove these as well. In fact, we could get rid of anything we don't use in practice.

@magoorden What do you think?

Upgrade to Java 11

Compilation level is now Java 7. Make sure code works with Java 11. Maybe also use some of the new features of Java 8-11. For instance, diamond notation. Require Java 11 as minimum version.

Change callbacks to use functional interfaces

The current callbacks are method references and use reflection. This should be changed to functional interfaces to allow using Java lambdas and method references. This leads to simpler code, improved type safety, and probably also better performance.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.