UFLPOrder

Module summary

Implements an algorithm to find a var order for BDD representing an UFLP.

Assuming overlap costs and instance parameterization with S, f, c.

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

❖❖❖

Implements classes:

N2RList(S[, directSort])

Implements a heap of N2-neighborhoods keyed by size.

Implements functions (outside the classes above):

UFLP_greedy_order(S[, directSort])	Finds a good order for BDD representing UFLP.
test_greedy_order_simple()	Testing over a toy instance.
test_greedy_order_toy2()	Another toy-instance test.

❖❖❖

Implementation details

❖❖❖

N2RList

class UFLPOrder.N2RList(S, directSort=True)

Implements a heap of N2-neighborhoods keyed by size.

Note

Based on implementation suggested in heapq, see heapq docs for more info.

Public Methods:

__init__(S[, directSort])	Initializes the prio que structure.
pop()	Pops a smallest-2-neighborhood point (adjusting the heap).
__len__()

Private Methods:

_remove(N2)

Removes points N2 from the heap (adjusting it as necessary).

---

_remove(N2)

Removes points N2 from the heap (adjusting it as necessary).

pop()

Pops a smallest-2-neighborhood point (adjusting the heap).

❖❖❖

Functions

UFLPOrder.UFLP_greedy_order(S, directSort=True)

Finds a good order for BDD representing UFLP.

Parameters

• S (list) – adjacencies,

• f (list) – overlap costs,

• c (list) – location costs.

Note

As usual, point numbers are 1-based. Uses a simple greedy algorithm that adds fewest possible points to ‘forget’ the next distance-two neighborhood. (See Example 5 in Appendix H.)

Returns

A list of nodes to add to a BDD (according to a greedy algo).

UFLPOrder.test_greedy_order_simple()

Testing over a toy instance.

UFLPOrder.test_greedy_order_toy2()

Another toy-instance test.