Algorithms (sds.algorithms)

This module gathers the algorithmic logic of the library: sorting, traversing, searching and optimizing. None of it lives inside the structure classes. Every algorithm is a free function that receives the structure it works on as a parameter.

Overview

Important

Structures and algorithms are kept apart. A structure models a container and its relations; an algorithm computes something from a structure. Keeping them in separate modules means an algorithm can be read, tested and replaced without touching the structure, and one algorithm serves every structure that offers what it needs.

Each function types its structure parameter against the broadest abstract interface that provides the capabilities the algorithm requires, and only narrows it when no interface does. For instance, a graph traversal accepts any AbstractGraph, whatever its internal representation.

        graph LR
    subgraph "Structures"
    L[sds.linear]
    T[sds.tree]
    G[sds.graph]
    end

    subgraph "sds.algorithms"
    S[sorting]
    TA[tree_algorithms]
    GA[graph_algorithms]
    PA[probabilistic_algorithms]
    end

    L -- "to_list() / from_list()" --> S
    T -- "root, children()" --> TA
    G -- "neighbors(), outgoing_edges()" --> GA
    P[sds.probabilistic] -- "factors(), scope, value()" --> PA

    style S fill:#3498db,color:#fff
    style TA fill:#3498db,color:#fff
    style GA fill:#3498db,color:#fff
    style PA fill:#3498db,color:#fff

Module Contents

Subpackage

Contents

Operates on

Sorting Algorithms

merge_sort, quick_sort

Python list

Tree Algorithms

inorder, preorder, postorder, level_order, is_balanced, rebalance

any binary tree (rebalance: BinarySearchTree)

Graph Algorithms

bfs, dfs, dijkstra, kruskal

graphs, weighted graphs

Probabilistic Inference

variable_elimination, belief_propagation, forward, viterbi

Bayesian networks, Markov random fields, HMMs

Detailed Documentation