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: Callable[[T], Key] | None = None)

Bases: Generic[T, Key]

A Fibonacci Heap.

__init__(key: Callable[[T], Key] | None = 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: HeapNode[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]

The function to extract comparison keys from items.

property min_node: HeapNode[T, Key]

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

nodes() → Iterator[HeapNode[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) → HeapNode[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: HeapNode[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: ~graphtage.fibonacci.T, key: ~graphtage.fibonacci.Key = <object object>)

Bases: Generic[T, Key]

A node in a FibonacciHeap.

__init__(item: ~graphtage.fibonacci.T, key: ~graphtage.fibonacci.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[HeapNode[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: HeapNode[T, Key] | None

The node’s child.

property children: Iterator[HeapNode[T, Key]]

Iterates over this node’s children.

Equivalent to:

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

degree: int

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

deleted: bool

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

The item associated with this heap node.

key: Key

The key to be used when sorting this heap node.

left: HeapNode[T, Key]

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

mark: bool

The node’s marked state.

parent: 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]

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

property siblings: Iterator[HeapNode[T, Key]]

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: Callable[[T], Key] | None = None)

Bases: Generic[T, Key], FibonacciHeap[T, ReversedComparator[Key]]

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

__init__(key: Callable[[T], Key] | None = 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: HeapNode[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]

The function to extract comparison keys from items.

property min_node: HeapNode[T, Key]

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

nodes() → Iterator[HeapNode[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) → HeapNode[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: HeapNode[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: Generic[Key]

A wrapper that reverses the semantics of its comparison operators.

__init__(key: Key)