BDD_test

Module summary

Tests some key procedures for BDD .

(In the implementation details below, click on class/function names for additional documentation and links to the source code.)

❖❖❖

Implements functions (outside the classes above):

gen_4BDD()	creates a simple 4-var BDD
save_load(bdd)	Quickly tests the load-save functionality (for visual inspection).
show_align()
show_bruteforcing()
show_create_render()	Tests the BDD creation and rendering code.
show_intersections()	Tests intersection function.
show_rnd()
show_rnd_naming()
show_swap_sift(bdd)	quick test of swap and sift operations
show_swapping_2()
test_alignto(i)	Tests align_to operation (random instances).
test_intersect(i)	Tests intersection function, BDD.intersect().
test_load_save(D)	Tests that load/save functionality works as intended.
test_random_swapping(test_inst)	Tests if BDD.BDD.swap() work correctly (random problems).
test_save_load_noargs()	Tests load/save for a specific situation.
test_shortest_path(test_inst)	Tests the shortest path procedure (with Gurobi model)
test_swaps_uweighted(i)
test_swaps_w()	Tests BDD.BDD.swap() for a weighted BDD (a simple case).
test_swaps_weighted(i)	Tests swap operation for weighted diagrams (random instances).

❖❖❖

Implementation details

❖❖❖

Functions

BDD_test.gen_4BDD()

creates a simple 4-var BDD

BDD_test.save_load(bdd)

Quickly tests the load-save functionality (for visual inspection).

must result in two equivalent graphs (BDDs) on the screen

BDD_test.show_align()

BDD_test.show_bruteforcing()

BDD_test.show_create_render()

Tests the BDD creation and rendering code.

BDD_test.show_intersections()

Tests intersection function.

BDD_test.show_rnd()

BDD_test.show_rnd_naming()

BDD_test.show_swap_sift(bdd)

quick test of swap and sift operations

BDD_test.show_swapping_2()

BDD_test.test_alignto(i)

Tests align_to operation (random instances).

BDD_test.test_intersect(i)

Tests intersection function, BDD.intersect().

BDD_test.test_load_save(D)

Tests that load/save functionality works as intended.

BDD_test.test_random_swapping(test_inst)

Tests if BDD.BDD.swap() work correctly (random problems).

Generates a random BDD, makes some random swaps (or sifts), and then checks that the function encoded by the BDD remained the same (that is, every set of var values result in the same terminal node for the original BDD and for the randomly changed BDD).

Parameters

• N – no. of variables in the diagram

• m – no. of consecutive test swaps per BDD

• p – BDD expansion prob parameter

• mode – swaps or sifts, determines what kind of events are to be generated

Notes

• Arguments are packed into a single tuple (for compatibility)

  with pytest module.

• Involves brute-force enumaration of all the 2^n possible decisions

  (concerning all vars), so choose n wisely (<=8 seems OK)

Example

test_random_swapping((8,20,0.8,sys.argv[1]))

BDD_test.test_save_load_noargs()

Tests load/save for a specific situation.

BDD_test.test_shortest_path(test_inst)

Tests the shortest path procedure (with Gurobi model)

BDD_test.test_swaps_uweighted(i)

BDD_test.test_swaps_w()

Tests BDD.BDD.swap() for a weighted BDD (a simple case).

Uses a simple problem instance (tests/simple_DD.wbdd) to run a test: all paths costs and terminals must coincide after a series of swaps.

BDD_test.test_swaps_weighted(i)

Tests swap operation for weighted diagrams (random instances).