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 thank
.

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
isFalse
. 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
toTrue
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 thank
.

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
isFalse
. 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.
