Ошибка при передаче логического выражения в CUDD (работает в BuDDy)

Я пытаюсь найти общее количество узлов в Shared-BDD, используя CUDD. Я уже написал код C, используя BuDDy-2.4, и он работает нормально. Но когда я использую CUDD вместо BuDDy, Моя программа показывает ошибку.

Мой файл BuDDY C:

//BuDDY_C Code for Node Count:    

#define X1 (a&b&c&d)|(!c&d&f)|(g&!g)    //Define Function-1 here
#define X2 (a&b&d&!c)|(!c&!c&d)^(g) //Define Function-2 here


#include<bdd.h>
#include<stdio.h>
#include<stdlib.h>

int main(void)
{
bdd z[2],a,b,c,d,e,f,g,h;
int i,INPUT=8,node_count,order[8]={2,5,1,6,0,4,3,7};

printf("\nGiven Variable Order:\t ");
    for(i=0;i<INPUT;i++)
        printf("%d \t",order[i]); 

   bdd_init(1000,100);
   bdd_setvarnum(INPUT);

        a = bdd_ithvar(order[0]);  //Assign Variable order stored in order[0] to a
        b = bdd_ithvar(order[1]);  //Assign Variable order stored in order[1] to b
        c = bdd_ithvar(order[2]);  //Assign Variable order stored in order[2] to c
        d = bdd_ithvar(order[3]);  //Assign Variable order stored in order[3] to d
        e = bdd_ithvar(order[4]);  //Assign Variable order stored in order[4] to e
        f = bdd_ithvar(order[5]);  //Assign Variable order stored in order[5] to f
        g = bdd_ithvar(order[6]);  //Assign Variable order stored in order[6] to g
        h = bdd_ithvar(order[7]);  //Assign Variable order stored in order[7] to h


    z[0]=X1; 
    z[1]=X2;
   node_count=bdd_anodecount(z,2);
   bdd_done();
   printf("\n Total no of nodes are %d\n",node_count);
   return 0;

}

Моя программа CUDD C:

//CUDD_C Code for Node Count
#define X1 (a&b&c&d)|(!c&d&f)|(g&!g)    //Define Function-1 here
#define X2 (a&b&d&!c)|(!c&!c&d)^(g) //Define Function-2 here

#include <stdio.h>
#include <stdlib.h>
#include "cudd.h"

int main(void) {
DdNode *z[2],*a,*b,*c,*d,*e,*f,*g,*h;
int i,INPUT=8,node_count,order[8]={2,5,1,6,0,4,3,7};

printf("\nGiven Variable Order:\t ");
    for(i=0;i<INPUT;i++)
        printf("%d \t",order[i]); 

DdManager * mgr = Cudd_Init(INPUT,0,CUDD_UNIQUE_SLOTS,CUDD_CACHE_SLOTS,0);


 a = Cudd_bddIthVar(mgr, order[0]);  //Assign Variable order stored in order[0] to a
 b = Cudd_bddIthVar(mgr, order[1]);  //Assign Variable order stored in order[0] to b
 c = Cudd_bddIthVar(mgr, order[2]);  //Assign Variable order stored in order[0] to c
 d = Cudd_bddIthVar(mgr, order[3]);  //Assign Variable order stored in order[0] to d
 e = Cudd_bddIthVar(mgr, order[4]);  //Assign Variable order stored in order[0] to e
 f = Cudd_bddIthVar(mgr, order[5]);  //Assign Variable order stored in order[0] to f
 g = Cudd_bddIthVar(mgr, order[6]);  //Assign Variable order stored in order[0] to g
 h = Cudd_bddIthVar(mgr, order[7]);  //Assign Variable order stored in order[0] to h


    z[0]=X1; 
    z[1]=X2;


  Cudd_Ref(z[0]);
  Cudd_Ref(z[1]);
/*-----Calculate no of nodes and number of shared nodes*/

        node_count= Cudd_SharingSize( z, 2);   
    printf("\n Total no of nodes are %d\n",node_count);

  int err = Cudd_CheckZeroRef(mgr);
  Cudd_Quit(mgr);
  return err;
}

Но эта программа CUDD C показывает ошибку

balal@balal-HP-H710:~/Desktop/cudd-3.0.0$ g++ -o test test2_cudd.c -lbdd
test2_cudd.c: In function ‘int main()’:
test2_cudd.c:2:14: error: invalid operands of types ‘DdNode*’ and ‘DdNode*’ to binary ‘operator&’
 #define X1 (a&b&c&d)|(!c&d&f)|(g&!g) //Define Function-1 here
             ~^~
test2_cudd.c:30:7: note: in expansion of macro ‘X1’
  z[0]=X1;
       ^~
test2_cudd.c:2:25: error: invalid operands of types ‘bool’ and ‘DdNode*’ to binary ‘operator&’
 #define X1 (a&b&c&d)|(!c&d&f)|(g&!g) //Define Function-1 here
                       ~~^~
test2_cudd.c:30:7: note: in expansion of macro ‘X1’
  z[0]=X1;
       ^~
test2_cudd.c:2:33: error: invalid operands of types ‘DdNode*’ and ‘bool’ to binary ‘operator&’
 #define X1 (a&b&c&d)|(!c&d&f)|(g&!g) //Define Function-1 here
                                ~^~~
test2_cudd.c:30:7: note: in expansion of macro ‘X1’
  z[0]=X1;
       ^~
test2_cudd.c:3:14: error: invalid operands of types ‘DdNode*’ and ‘DdNode*’ to binary ‘operator&’
 #define X2 (a&b&d&!c)|(!c&!c&d)^(g) //Define Function-2 here
             ~^~
test2_cudd.c:31:7: note: in expansion of macro ‘X2’
  z[1]=X2;
       ^~
test2_cudd.c:3:29: error: invalid operands of types ‘int’ and ‘DdNode*’ to binary ‘operator&’
 #define X2 (a&b&d&!c)|(!c&!c&d)^(g) //Define Function-2 here
                        ~~~~~^~
test2_cudd.c:31:7: note: in expansion of macro ‘X2’
  z[1]=X2;
       ^~
balal@balal-HP-H710:~/Desktop/cudd-3.0.0$ 

person user1868625    schedule 11.02.2020    source источник


Ответы (2)


Вы пытаетесь использовать оператор «&» на узлах BDD при написании своей программы на C. Поскольку C не поддерживает перегрузку операторов, это не сработает, потому что оператор «&» может в лучшем случае означать побитовое И для адреса, а это не то, что вам нужно.

Чтобы вычислить И двух BDD, вы должны использовать функцию Cudd_bddAnd. См., например, здесь. Обратите внимание, что таким образом ваши макросы станут намного длиннее и должны включать локальные переменные помимо областей.

Альтернативой является использование интерфейса C++ для CUDD, где BDD могут быть инкапсулированы в объекты, поддерживающие перегрузку операторов.

Обратите внимание, что

z[0]=X1; 
z[1]=X2;
Cudd_Ref(z[0]);
Cudd_Ref(z[1]);

также потенциально может вызвать проблемы. В CUDD на узлы необходимо ссылаться с помощью Cudd_Ref(...) перед вызовом любой другой функции CUDD, которая может создавать новые узлы. Поскольку ваш макрос X2 включает операции над BDD, это может произойти. Так что лучше всего немедленно использовать Cudd_Ref(...) BDD. Следующее выглядит лучше:

z[0]=X1; 
Cudd_Ref(z[0]);
z[1]=X2;
Cudd_Ref(z[1]);

Обратите внимание, что ваш код друга также неверен по той же причине. Однако, поскольку тип BDD определяется как "typedef int BDD;" вместо этого компилятор использовал побитовые И и ИЛИ для номеров узлов BDD, поэтому он скомпилировал код, который дает неверные результаты.

person DCTLib    schedule 12.02.2020

Другой возможностью является использование интерфейса Cython для CUDD, включенного в пакет Python dd. Установка dd с модулем dd.cudd описана здесь и может быть обобщена следующим образом:

pip download dd --no-deps
tar -xzf dd-*.tar.gz
cd dd-*/
python setup.py install --fetch --cudd

Это загрузит и создаст CUDD, а также создаст и установит привязки Cython dd к CUDD. dd также имеет привязку Cython к BuDDy, и они могут быть построены аналогичным образом, когда пользователь загружает и создает BuDDy и передать --buddy скрипту setup.py.

Код примера можно преобразовать в следующий код Python.

from dd import cudd as _bdd

bdd = _bdd.BDD()
bdd.declare('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h')
# /\ is conjunction in TLA+, \/ disjunction, ~ negation
X1 = bdd.add_expr('(a /\ b /\ c /\ d) \/ (~ c /\ d /\ f) \/ (g /\ ~ g)')
    # note that g /\ ~ g is FALSE
X2 = bdd.add_expr('(a /\ b /\ d /\ ~ c) \/ ((~ c /\ ~ c /\ d) ^ g)')
    # note that ~ c /\ ~ c is ~ c


# using the operators &, |, ! for conjunction, disjunction, and negation
X1_ = bdd.add_expr('(a & b & c & d) \/ (!c & d & f) \/ (g & !g)')
X2_ = bdd.add_expr('(a & b & d & !c) \/ ((!c & !c & d) ^ g)')
assert X1 == X1_, (X1, X1_)
assert X2 == X2_, (X2, X2_)


def descendants(roots):
    """Return nodes reachable from `roots`.

    Nodes in `roots` are included.
    """
    if not roots:
        return set()
    visited = set()
    for u in roots:
        _descendants(u, visited)
    assert set(roots).issubset(visited), (roots, visited)
    return visited

def _descendants(u, visited):
    v, w = u.low, u.high
    # terminal node or visited ?
    if u.low is None or u in visited:
        return
    _descendants(v, visited)
    _descendants(w, visited)
    visited.add(u)


r = descendants([X1, X2])
print(len(r))

# plot diagrams of the results using GraphViz
bdd.dump('X1.pdf', [X1])
bdd.dump('X2.pdf', [X2])

Функция descendants вычисляет набор узлов, достижимых из заданных узлов (узлов, на которые ссылаются X1 и X2), включая заданные узлы. Ответ для переменного порядка в моем прогоне — 16 узлов. Диаграммы для BDD булевых функций X1 и X2 следующие.

BDD булевой функции X1

Булевая функция ‹code›X1‹/code›

BDD булевой функции X2

Булевая функция ‹code›X2‹/code›

person Ioannis Filippidis    schedule 23.02.2020