graphtage.fibonacci

A pure Python implementation of a Fibonacci Heap.

Many of the algorithms in Graphtage only require partially sorting collections, so we can get a speedup from using a Fibonacci Heap that has amortized constant time insertion.

fibonacci classes

FibonacciHeap

class graphtage.fibonacci.FibonacciHeap(key: Optional[Callable[[T], Key]] = None)

Bases: typing.Generic

A Fibonacci Heap.

__init__(key: Optional[Callable[[T], Key]] = None)

Initializes a Fibonacci heap.

Parameters

key –

An optional function that accepts an item and returns the key to be used for comparing that item. If omitted, it is equivalent to:

lambda item: item

clear()

Removes all items from this heap.

decrease_key(x: graphtage.fibonacci.HeapNode[~ T, ~ Key][T, Key], k: Key)

Decreases the key value associated with the given node.

Parameters

• x – The node to modify.

• k – The new key value.

Raises

ValueError – If x.key is less than k.

key: Callable[[T], Key] = None

The function to extract comparison keys from items.

property min_node

Returns the heap node associated with the smallest item in the heap, without removing it.

nodes() → Iterator[graphtage.fibonacci.HeapNode[~T, ~Key][T, Key]]

Iterates over all of the heap nodes in this heap.

peek() → T

Returns the smallest element of the heap without removing it.

Returns

The smallest element of the heap.

Return type

T

pop() → T

Returns and removes the smallest item from this heap.

push(item: T) → graphtage.fibonacci.HeapNode[~T, ~Key][T, Key]

Adds a new item to this heap.

Returns

The heap node created to store the new item.

Return type

HeapNode[T, Key]

remove(node: graphtage.fibonacci.HeapNode[~ T, ~ Key][T, Key])

Removes the given node from this heap.

Parameters

node – The node to be removed.

Warning

This function assumes that the provided node is actually a member of this heap. It also assumes (but does not check) that node.deleted is False. If either of these assumptions is incorrect, it will lead to undefined behavior and corruption of the heap.

HeapNode

class graphtage.fibonacci.HeapNode(item: T, key: Key = <object object>)

Bases: typing.Generic

A node in a FibonacciHeap.

__init__(item: T, key: Key = <object object>)

Initializes a Fibonacci heap node.

Parameters

• item – The heap item associated with the node.

• key – An optional key to use for the item in sorting. If omitted, the item itself will be used.

__iter__() → Iterator[graphtage.fibonacci.HeapNode[~T, ~Key][T, Key]]

Iterates over all of this node’s descendants, including itself.

add_child(node)

Adds a child to this heap node, incrementing its degree.

child: Optional[HeapNode[T, Key]] = None

The node’s child.

property children

Iterates over this node’s children.

Equivalent to:

if self.child is not None:
    yield self.child
    yield from self.child.siblings

degree: int = None

The degree of this node (i.e., the number of its children).

deleted: bool = None

Whether the node has been deleted.

This is to prevent nodes from being manipulated after they have been removed from a heap.

Warning

Do not set HeapNode.deleted to True unless the node has already been removed from the heap.

item: T = None

The item associated with this heap node.

key: Key = None

The key to be used when sorting this heap node.

left: HeapNode[T, Key] = None

The left sibling of this node, or self if it has no left sibling.

mark: bool = None

The node’s marked state.

parent: Optional[HeapNode[T, Key]] = None

The node’s parent.

remove_child(node)

Removes a child from this heap node, decrementing its degree.

right: HeapNode[T, Key] = None

The right sibling of this node, or self if it has no left sibling.

property siblings

Iterates over this node’s siblings.

Equivalent to:

node = self.right
while node != self:
    yield node
    node = node.right

MaxFibonacciHeap

class graphtage.fibonacci.MaxFibonacciHeap(key: Optional[Callable[[T], Key]] = None)

Bases: graphtage.fibonacci.FibonacciHeap

A Fibonacci Heap that yields items in decreasing order, using a ReversedComparator.

__init__(key: Optional[Callable[[T], Key]] = None)

Initializes a Fibonacci heap.

Parameters

key –

An optional function that accepts an item and returns the key to be used for comparing that item. If omitted, it is equivalent to:

lambda item: item

clear()

Removes all items from this heap.

decrease_key(x: graphtage.fibonacci.HeapNode[~ T, ~ Key][T, Key], k: Key)

Decreases the key value associated with the given node.

Parameters

• x – The node to modify.

• k – The new key value.

Raises

ValueError – If x.key is less than k.

property min_node

Returns the heap node associated with the smallest item in the heap, without removing it.

nodes() → Iterator[graphtage.fibonacci.HeapNode[~T, ~Key][T, Key]]

Iterates over all of the heap nodes in this heap.

peek() → T

Returns the smallest element of the heap without removing it.

Returns

The smallest element of the heap.

Return type

T

pop() → T

Returns and removes the smallest item from this heap.

push(item: T) → graphtage.fibonacci.HeapNode[~T, ~Key][T, Key]

Adds a new item to this heap.

Returns

The heap node created to store the new item.

Return type

HeapNode[T, Key]

remove(node: graphtage.fibonacci.HeapNode[~ T, ~ Key][T, Key])

Removes the given node from this heap.

Parameters

node – The node to be removed.

Warning

This function assumes that the provided node is actually a member of this heap. It also assumes (but does not check) that node.deleted is False. If either of these assumptions is incorrect, it will lead to undefined behavior and corruption of the heap.

ReversedComparator

class graphtage.fibonacci.ReversedComparator(key: Key)

Bases: typing.Generic

A wrapper that reverses the semantics of its comparison operators.

__init__(key: Key)

Initialize self. See help(type(self)) for accurate signature.