search

flamapy / bdd_metamodel

BDD plugin for the automated analysis of feature models using a BDD.
1 stars 2 forks source link

Reimplement "Product Distribution" and "Feature Inclusion Probability" efficiently #3

Open jmhorcas opened 2 years ago

jmhorcas commented 2 years ago

Actually, those operations are implemented in a brute force way, that is, enumerating all products with the BDD. Both operations can be implement very efficiently using the algorithms provided by the UNED guys that are available in this paper:

The difficulty is that the BDD implementation uses complemented arcs and therefore the algorithms are not exactly the same. Some attempts (still uncompleted) of the "Product Distribution" algorithm can be found here.

image

The documentation of the library used "dd" can be found here and here.

jmhorcas commented 2 years ago

I have tried again to implement the Product Distribution algorithm from UNED, but without success. @rheradio could you please take a look to the product_derivation and get_prod_dist methods here. In that branch I've updated the BDDModel to expose a clear interface to work with complemented arcs. Feel free to modify the BDDModel methods too if needed (I am not sure if I am working with complemented arc correctly).

Actually, from this feature model: image

I obtain the following BDD with complement arcs: image

The PD algorithm traversing the BDD gives to me this:

Node: @-105, id: -105, my_id: -105, index: 1, var: Pizza, negated: True
  |- Low node: @104, id: 104, my_id: 104, index: 2, var: Topping, negated: False
  |- High node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
Node: @104, id: 104, my_id: 104, index: 2, var: Topping, negated: False
  |- Low node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
  |- High node: @103, id: 103, my_id: 103, index: 3, var: Salami, negated: False
Node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
Node: @103, id: 103, my_id: 103, index: 3, var: Salami, negated: False
  |- Low node: @102, id: 102, my_id: 102, index: 4, var: Ham, negated: False
  |- High node: @100, id: 100, my_id: 100, index: 6, var: Size, negated: False
Node: @102, id: 102, my_id: 102, index: 4, var: Ham, negated: False
  |- Low node: @101, id: 101, my_id: 101, index: 5, var: Mozzarella, negated: False
  |- High node: @100, id: 100, my_id: 100, index: 6, var: Size, negated: False
Node: @101, id: 101, my_id: 101, index: 5, var: Mozzarella, negated: False
  |- Low node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
  |- High node: @100, id: 100, my_id: 100, index: 6, var: Size, negated: False
Node: @100, id: 100, my_id: 100, index: 6, var: Size, negated: False
  |- Low node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
  |- High node: @99, id: 99, my_id: 99, index: 7, var: Normal, negated: False
Node: @99, id: 99, my_id: 99, index: 7, var: Normal, negated: False
  |- Low node: @80, id: 80, my_id: 80, index: 8, var: Big, negated: False
  |- High node: @98, id: 98, my_id: 98, index: 8, var: Big, negated: False
Node: @80, id: 80, my_id: 80, index: 8, var: Big, negated: False
  |- Low node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
  |- High node: @79, id: 79, my_id: 79, index: 9, var: Dough, negated: False
Node: @79, id: 79, my_id: 79, index: 9, var: Dough, negated: False
  |- Low node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
  |- High node: @78, id: 78, my_id: 78, index: 10, var: Neapolitan, negated: False
Node: @78, id: 78, my_id: 78, index: 10, var: Neapolitan, negated: False
  |- Low node: @-64, id: -64, my_id: -64, index: 11, var: Sicilian, negated: True
  |- High node: @64, id: 64, my_id: 64, index: 11, var: Sicilian, negated: False
Node: @-64, id: -64, my_id: -64, index: 11, var: Sicilian, negated: True
  |- Low node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
  |- High node: @-1, id: -1, my_id: 0, index: 13, var: None, negated: True
Node: @-1, id: -1, my_id: 0, index: 13, var: None, negated: True
Node: @64, id: 64, my_id: 64, index: 11, var: Sicilian, negated: False
  |- Low node: @-1, id: -1, my_id: 0, index: 13, var: None, negated: True
  |- High node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
Node: @98, id: 98, my_id: 98, index: 8, var: Big, negated: False
  |- Low node: @97, id: 97, my_id: 97, index: 9, var: Dough, negated: False
  |- High node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
Node: @97, id: 97, my_id: 97, index: 9, var: Dough, negated: False
  |- Low node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
  |- High node: @96, id: 96, my_id: 96, index: 10, var: Neapolitan, negated: False
Node: @96, id: 96, my_id: 96, index: 10, var: Neapolitan, negated: False
  |- Low node: @94, id: 94, my_id: 94, index: 11, var: Sicilian, negated: False
  |- High node: @95, id: 95, my_id: 95, index: 11, var: Sicilian, negated: False
Node: @94, id: 94, my_id: 94, index: 11, var: Sicilian, negated: False
  |- Low node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
  |- High node: @91, id: 91, my_id: 91, index: 12, var: CheesyCrust, negated: False
Node: @91, id: 91, my_id: 91, index: 12, var: CheesyCrust, negated: False
  |- Low node: @-1, id: -1, my_id: 0, index: 13, var: None, negated: True
  |- High node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False
Node: @95, id: 95, my_id: 95, index: 11, var: Sicilian, negated: False
  |- Low node: @91, id: 91, my_id: 91, index: 12, var: CheesyCrust, negated: False
  |- High node: @1, id: 1, my_id: 1, index: 13, var: None, negated: False

and I've obtaining the following product distribution: [1, 12, 66, 220, 495, 792, 912, 774, 485, 218, 66, 12, 1] which of course is wrong.

The correct one is (calculated with the brute force algorithm): [0, 0, 0, 0, 0, 0, 0, 12, 18, 10, 2, 0, 0]

Here the algorithm I am based on: image

jmhorcas commented 3 months ago