pykp.knapsack.Knapsack.

initialise_graph

Knapsack.initialise_graph()

Construct a graph representation of the knapsack problem.

Each node in the graph represents a unique arrangement of items inside the knapsack. An edge represents an elementary operation of adding or removing a single item from the knapsack. Edges connect nodes whose differs by exactly one item.

Returns:

networkx.DiGraph

The graph representation of the knapsack problem.

Examples

>>> from pykp.knapsack import Knapsack, Item
>>> items = [Item(10, 5), Item(15, 10), Item(7, 3)]
>>> knapsack = Knapsack(items=items, capacity=15)
>>> knapsack.initialise_graph()
<networkx.classes.digraph.DiGraph object at 0x...>