matroiDD

English | 日本語

A header-only C++20 library for matroids using ZDDs.

Dependencies

This library depends on the following ZDD package:

• SAPPOROBDD

Requirements

• C++ compiler
  • GCC >= 11
  • Clang >= 15
• CMake >= 3.12

Tested Environments

SAPPOROBDD	OS	Compiler
v.20230102	Ubuntu 22.04	GCC 11.4.0
	Ubuntu 24.04	Clang 16.0.6
	macOS 14	GCC 12.4.0
		Clang 15.0.7

Installation

Installing SAPPOROBDD

If you have not installed SAPPOROBDD, please follow these steps:

1. Clone this repository with submodules.

   git clone --recursive https://github.com/emthrm/matroidd.git -b v0.1.0

2. Install SAPPOROBDD using dd_package.

   cd ./matroidd/third_party/dd_package
   sh ./downloader.sh

3. Specify /path/to/matroidd/third_party/dd_package/SAPPOROBDD/include as an include path.

Installing matroiDD

1. Clone this repository.

   git clone https://github.com/emthrm/matroidd.git -b v0.1.0

2. cd ./matroidd

3. Generate a project buildsystem. It is recommended to specify the absolute path to the static library of SAPPOROBDD in MATROIDD_SAPPOROBDD_FULL_LIBPATH.

   cmake -S . -B ./build -DMATROIDD_SAPPOROBDD_FULL_LIBPATH=/path/to/matroidd/third_party/dd_package/SAPPOROBDD/lib/BDD64.a

4. Install this library.

   cmake --install ./build

Usage

See matroiDD User Guide.

Example

#include <array>
#include <cassert>
#include <iostream>
#include <ranges>
#include <vector>

// SAPPOROBDD
#define B_64       // Use SAPPOROBDD in 64-bit mode.
#include "BDD.h"   // BDD_NewVar
#include "ZBDD.h"  // ZBDD::Card
// matroiDD
#include "matroidd/generators.hpp"  // matroidd::FromBases
#include "matroidd/matroid.hpp"     // matroidd::Matroid
#include "matroidd/util/util.hpp"   // matroidd::BddVarType

int main() {
  constexpr int kN = 3;
  // Create input variables for SAPPOROBDD.
  for (const matroidd::BddVarType i : std::views::iota(1, kN + 1)) {
    assert(BDD_NewVar() == i);
  }
  // Create a matroid object
  // corresponding to the collection of bases {{1, 2}, {1, 3}}.
  const matroidd::Matroid matroid = matroidd::FromBases(
      std::vector{std::array<int, 2>{1, 2}, std::array<int, 2>{1, 3}});
  // Output the number of independent sets.
  std::cout << matroid.IndependentSets().Card() << '\n';  // 6
  return 0;
}

BDDopID

(For developers using SAPPOROBDD)

See BDDopID.yml.

License

matroiDD is released under the MIT License.