Algorithms (`alnoms.dsa.algorithms`)

The algorithm pillar provides precision implementations for complex computational problems.

🕸️ Graph Theory

Breadth‑First Search Paths.

Provides a breadth‑first search (BFS)–based shortest‑path finder for undirected graphs. BFS computes the shortest path in terms of number of edges from a designated source vertex to all reachable vertices.

Design Characteristics: - Computes unweighted shortest paths - Produces predecessor links and distance levels - Time Complexity: O(V + E) - Space Complexity: O(V)

`BreadthFirstPaths`

Computes BFS‑based shortest paths from a single source vertex.

This class performs a breadth‑first search from a specified source vertex and records both predecessor links and distance levels. BFS guarantees shortest paths in unweighted graphs.

Attributes:

Name	Type	Description
`_s`	`int`	The source vertex.
`_marked`	`List[bool]`	Marks whether each vertex has been visited.
`_edge_to`	`List[int]`	Predecessor links for path reconstruction.
`_dist_to`	`List[float]`	Number of edges in the shortest path.

Source code in src/alnoms/dsa/algorithms/graph/breadth_first_paths.py

class BreadthFirstPaths:
    """Computes BFS‑based shortest paths from a single source vertex.

    This class performs a breadth‑first search from a specified source
    vertex and records both predecessor links and distance levels. BFS
    guarantees shortest paths in unweighted graphs.

    Attributes:
        _s (int): The source vertex.
        _marked (List[bool]): Marks whether each vertex has been visited.
        _edge_to (List[int]): Predecessor links for path reconstruction.
        _dist_to (List[float]): Number of edges in the shortest path.
    """

    def __init__(self, G: Graph, s: int):
        """Initializes BFS search from a source vertex.

        Args:
            G (Graph): The graph to search.
            s (int): The source vertex.

        Raises:
            IndexError: If the source vertex is out of bounds.
        """
        self._s = s
        self._marked = [False] * G.V()
        self._edge_to = [0] * G.V()
        self._dist_to = [float("inf")] * G.V()

        self._validate_vertex(s, G.V())
        self._bfs(G, s)

    def _bfs(self, G: Graph, s: int) -> None:
        """Performs BFS from the source vertex.

        Args:
            G (Graph): The graph being searched.
            s (int): The source vertex.
        """
        q: Deque[int] = deque()
        self._marked[s] = True
        self._dist_to[s] = 0
        q.append(s)

        while q:
            v = q.popleft()
            for w in G.adj(v):
                if not self._marked[w]:
                    self._marked[w] = True
                    self._edge_to[w] = v
                    self._dist_to[w] = self._dist_to[v] + 1
                    q.append(w)

    def has_path_to(self, v: int) -> bool:
        """Checks whether a path exists from the source to a vertex.

        Args:
            v (int): The vertex to check.

        Returns:
            bool: True if reachable, otherwise False.

        Raises:
            IndexError: If the vertex is out of bounds.
        """
        self._validate_vertex(v, len(self._marked))
        return self._marked[v]

    def dist_to(self, v: int) -> float:
        """Returns the BFS shortest‑path distance to a vertex.

        Args:
            v (int): The vertex whose distance is requested.

        Returns:
            float: Number of edges in the shortest path.

        Raises:
            IndexError: If the vertex is out of bounds.
        """
        self._validate_vertex(v, len(self._marked))
        return self._dist_to[v]

    def path_to(self, v: int) -> Optional[Iterable[int]]:
        """Returns the shortest path from the source to a vertex.

        Args:
            v (int): The destination vertex.

        Returns:
            Optional[Iterable[int]]: A sequence of vertices forming the
            shortest path, or None if no path exists.

        Raises:
            IndexError: If the vertex is out of bounds.
        """
        self._validate_vertex(v, len(self._marked))
        if not self.has_path_to(v):
            return None

        path: Deque[int] = deque()
        x = v
        while x != self._s:
            path.appendleft(x)
            x = self._edge_to[x]
        path.appendleft(self._s)
        return path

    def _validate_vertex(self, v: int, V: int) -> None:
        """Validates that a vertex index is within bounds.

        Args:
            v (int): The vertex to validate.
            V (int): Total number of vertices.

        Raises:
            IndexError: If the vertex is out of bounds.
        """
        if v < 0 or v >= V:
            raise IndexError(f"Vertex {v} is out of bounds")

`init(G, s)`

Initializes BFS search from a source vertex.

Parameters:

Name	Type	Description	Default
`G`	`Graph`	The graph to search.	required
`s`	`int`	The source vertex.	required

Raises:

Type	Description
`IndexError`	If the source vertex is out of bounds.

Source code in src/alnoms/dsa/algorithms/graph/breadth_first_paths.py

def __init__(self, G: Graph, s: int):
    """Initializes BFS search from a source vertex.

    Args:
        G (Graph): The graph to search.
        s (int): The source vertex.

    Raises:
        IndexError: If the source vertex is out of bounds.
    """
    self._s = s
    self._marked = [False] * G.V()
    self._edge_to = [0] * G.V()
    self._dist_to = [float("inf")] * G.V()

    self._validate_vertex(s, G.V())
    self._bfs(G, s)

`dist_to(v)`

Returns the BFS shortest‑path distance to a vertex.

Parameters:

Name	Type	Description	Default
`v`	`int`	The vertex whose distance is requested.	required

Returns:

Name	Type	Description
`float`	`float`	Number of edges in the shortest path.

Raises:

Type	Description
`IndexError`	If the vertex is out of bounds.

Source code in src/alnoms/dsa/algorithms/graph/breadth_first_paths.py

def dist_to(self, v: int) -> float:
    """Returns the BFS shortest‑path distance to a vertex.

    Args:
        v (int): The vertex whose distance is requested.

    Returns:
        float: Number of edges in the shortest path.

    Raises:
        IndexError: If the vertex is out of bounds.
    """
    self._validate_vertex(v, len(self._marked))
    return self._dist_to[v]

`has_path_to(v)`

Checks whether a path exists from the source to a vertex.

Parameters:

Name	Type	Description	Default
`v`	`int`	The vertex to check.	required

Returns:

Name	Type	Description
`bool`	`bool`	True if reachable, otherwise False.

Raises:

Type	Description
`IndexError`	If the vertex is out of bounds.

Source code in src/alnoms/dsa/algorithms/graph/breadth_first_paths.py

def has_path_to(self, v: int) -> bool:
    """Checks whether a path exists from the source to a vertex.

    Args:
        v (int): The vertex to check.

    Returns:
        bool: True if reachable, otherwise False.

    Raises:
        IndexError: If the vertex is out of bounds.
    """
    self._validate_vertex(v, len(self._marked))
    return self._marked[v]

`path_to(v)`

Returns the shortest path from the source to a vertex.

Parameters:

Name	Type	Description	Default
`v`	`int`	The destination vertex.	required

Returns:

Type	Description
`Optional[Iterable[int]]`	Optional[Iterable[int]]: A sequence of vertices forming the
`Optional[Iterable[int]]`	shortest path, or None if no path exists.

Raises:

Type	Description
`IndexError`	If the vertex is out of bounds.

Source code in src/alnoms/dsa/algorithms/graph/breadth_first_paths.py

def path_to(self, v: int) -> Optional[Iterable[int]]:
    """Returns the shortest path from the source to a vertex.

    Args:
        v (int): The destination vertex.

    Returns:
        Optional[Iterable[int]]: A sequence of vertices forming the
        shortest path, or None if no path exists.

    Raises:
        IndexError: If the vertex is out of bounds.
    """
    self._validate_vertex(v, len(self._marked))
    if not self.has_path_to(v):
        return None

    path: Deque[int] = deque()
    x = v
    while x != self._s:
        path.appendleft(x)
        x = self._edge_to[x]
    path.appendleft(self._s)
    return path

Depth‑First Search Orderings.

Computes preorder, postorder, and reverse‑postorder vertex orderings for a directed graph using depth‑first search (DFS). These orderings are fundamental in algorithms such as topological sorting and strongly connected components.

Design Characteristics: - DFS‑based vertex ordering - Reverse postorder supports topological sorting in DAGs - Time Complexity: O(V + E) - Space Complexity: O(V)

`DepthFirstOrder`

Computes DFS‑based vertex orderings for a directed graph.

This class performs a full DFS over all vertices of a directed graph and records the reverse postorder sequence. Reverse postorder is particularly useful for topological sorting in directed acyclic graphs (DAGs).

Attributes:

Name	Type	Description
`_marked`	`List[bool]`	Marks whether each vertex has been visited.
`_reverse_post`	`Deque[int]`	Vertices in reverse postorder.

Source code in src/alnoms/dsa/algorithms/graph/depth_first_order.py

class DepthFirstOrder:
    """Computes DFS‑based vertex orderings for a directed graph.

    This class performs a full DFS over all vertices of a directed graph
    and records the reverse postorder sequence. Reverse postorder is
    particularly useful for topological sorting in directed acyclic
    graphs (DAGs).

    Attributes:
        _marked (List[bool]): Marks whether each vertex has been visited.
        _reverse_post (Deque[int]): Vertices in reverse postorder.
    """

    def __init__(self, G: Digraph):
        """Initializes DFS order computation.

        Args:
            G (Digraph): The directed graph whose orderings are computed.
        """
        self._marked = [False] * G.V()
        self._reverse_post: Deque[int] = deque()

        for v in range(G.V()):
            if not self._marked[v]:
                self._dfs(G, v)

    def _dfs(self, G: Digraph, v: int) -> None:
        """Performs DFS from a vertex and records postorder.

        Args:
            G (Digraph): The graph being searched.
            v (int): The current vertex.
        """
        self._marked[v] = True
        for w in G.adj(v):
            if not self._marked[w]:
                self._dfs(G, w)

        # Postorder: add after exploring all descendants
        self._reverse_post.appendleft(v)

    def reverse_post(self) -> Iterable[int]:
        """Returns vertices in reverse postorder.

        Returns:
            Iterable[int]: A sequence of vertices in reverse postorder.
        """
        return self._reverse_post

`init(G)`

Initializes DFS order computation.

Parameters:

Name	Type	Description	Default
`G`	`Digraph`	The directed graph whose orderings are computed.	required

Source code in src/alnoms/dsa/algorithms/graph/depth_first_order.py

def __init__(self, G: Digraph):
    """Initializes DFS order computation.

    Args:
        G (Digraph): The directed graph whose orderings are computed.
    """
    self._marked = [False] * G.V()
    self._reverse_post: Deque[int] = deque()

    for v in range(G.V()):
        if not self._marked[v]:
            self._dfs(G, v)

`reverse_post()`

Returns vertices in reverse postorder.

Returns:

Type	Description
`Iterable[int]`	Iterable[int]: A sequence of vertices in reverse postorder.

Source code in src/alnoms/dsa/algorithms/graph/depth_first_order.py

def reverse_post(self) -> Iterable[int]:
    """Returns vertices in reverse postorder.

    Returns:
        Iterable[int]: A sequence of vertices in reverse postorder.
    """
    return self._reverse_post

Depth‑First Search Paths.

Provides a depth‑first search (DFS)–based path finder for undirected graphs. Starting from a designated source vertex, the algorithm explores all reachable vertices and records predecessor links that allow path reconstruction.

Design Characteristics: - Computes reachability from a single source - Produces DFS tree predecessor links - Paths are not guaranteed to be shortest - Time Complexity: O(V + E) - Space Complexity: O(V)

`DepthFirstPaths`

Computes DFS‑based paths from a single source vertex.

This class performs a depth‑first search from a specified source vertex and records the predecessor of each visited vertex. These predecessor links allow reconstruction of any path from the source to a reachable vertex.

Attributes:

Name	Type	Description
`_s`	`int`	The source vertex.
`_marked`	`List[bool]`	Marks whether each vertex has been visited.
`_edge_to`	`List[int]`	Predecessor links for path reconstruction.

Source code in src/alnoms/dsa/algorithms/graph/depth_first_paths.py

class DepthFirstPaths:
    """Computes DFS‑based paths from a single source vertex.

    This class performs a depth‑first search from a specified source
    vertex and records the predecessor of each visited vertex. These
    predecessor links allow reconstruction of any path from the source
    to a reachable vertex.

    Attributes:
        _s (int): The source vertex.
        _marked (List[bool]): Marks whether each vertex has been visited.
        _edge_to (List[int]): Predecessor links for path reconstruction.
    """

    def __init__(self, G: Graph, s: int):
        """Initializes DFS search from a source vertex.

        Args:
            G (Graph): The graph to search.
            s (int): The source vertex.

        Raises:
            IndexError: If the source vertex is out of bounds.
        """
        self._s = s
        self._marked = [False] * G.V()
        self._edge_to = [0] * G.V()

        self._validate_vertex(s, G.V())
        self._dfs(G, s)

    def _dfs(self, G: Graph, v: int) -> None:
        """Performs recursive DFS from a vertex.

        Args:
            G (Graph): The graph being searched.
            v (int): The current vertex.
        """
        self._marked[v] = True
        for w in G.adj(v):
            if not self._marked[w]:
                self._edge_to[w] = v
                self._dfs(G, w)

    def has_path_to(self, v: int) -> bool:
        """Checks whether a path exists from the source to a vertex.

        Args:
            v (int): The vertex to check.

        Returns:
            bool: True if reachable, otherwise False.

        Raises:
            IndexError: If the vertex is out of bounds.
        """
        self._validate_vertex(v, len(self._marked))
        return self._marked[v]

    def path_to(self, v: int) -> Optional[Iterable[int]]:
        """Returns a path from the source to a vertex.

        Args:
            v (int): The destination vertex.

        Returns:
            Optional[Iterable[int]]: A sequence of vertices forming a path
            from the source to `v`, or None if no such path exists.

        Raises:
            IndexError: If the vertex is out of bounds.
        """
        self._validate_vertex(v, len(self._marked))
        if not self.has_path_to(v):
            return None

        path: Deque[int] = deque()
        x = v
        while x != self._s:
            path.appendleft(x)
            x = self._edge_to[x]
        path.appendleft(self._s)
        return path

    def _validate_vertex(self, v: int, V: int) -> None:
        """Validates that a vertex index is within bounds.

        Args:
            v (int): The vertex to validate.
            V (int): Total number of vertices.

        Raises:
            IndexError: If the vertex is out of bounds.
        """
        if v < 0 or v >= V:
            raise IndexError(f"Vertex {v} is out of bounds")

`init(G, s)`

Initializes DFS search from a source vertex.

Parameters:

Name	Type	Description	Default
`G`	`Graph`	The graph to search.	required
`s`	`int`	The source vertex.	required

Raises:

Type	Description
`IndexError`	If the source vertex is out of bounds.

Source code in src/alnoms/dsa/algorithms/graph/depth_first_paths.py

def __init__(self, G: Graph, s: int):
    """Initializes DFS search from a source vertex.

    Args:
        G (Graph): The graph to search.
        s (int): The source vertex.

    Raises:
        IndexError: If the source vertex is out of bounds.
    """
    self._s = s
    self._marked = [False] * G.V()
    self._edge_to = [0] * G.V()

    self._validate_vertex(s, G.V())
    self._dfs(G, s)

`has_path_to(v)`

Checks whether a path exists from the source to a vertex.

Parameters:

Name	Type	Description	Default
`v`	`int`	The vertex to check.	required

Returns:

Name	Type	Description
`bool`	`bool`	True if reachable, otherwise False.

Raises:

Type	Description
`IndexError`	If the vertex is out of bounds.

Source code in src/alnoms/dsa/algorithms/graph/depth_first_paths.py

def has_path_to(self, v: int) -> bool:
    """Checks whether a path exists from the source to a vertex.

    Args:
        v (int): The vertex to check.

    Returns:
        bool: True if reachable, otherwise False.

    Raises:
        IndexError: If the vertex is out of bounds.
    """
    self._validate_vertex(v, len(self._marked))
    return self._marked[v]

`path_to(v)`

Returns a path from the source to a vertex.

Parameters:

Name	Type	Description	Default
`v`	`int`	The destination vertex.	required

Returns:

Type	Description
`Optional[Iterable[int]]`	Optional[Iterable[int]]: A sequence of vertices forming a path
`Optional[Iterable[int]]`	from the source to `v`, or None if no such path exists.

Raises:

Type	Description
`IndexError`	If the vertex is out of bounds.

Source code in src/alnoms/dsa/algorithms/graph/depth_first_paths.py

def path_to(self, v: int) -> Optional[Iterable[int]]:
    """Returns a path from the source to a vertex.

    Args:
        v (int): The destination vertex.

    Returns:
        Optional[Iterable[int]]: A sequence of vertices forming a path
        from the source to `v`, or None if no such path exists.

    Raises:
        IndexError: If the vertex is out of bounds.
    """
    self._validate_vertex(v, len(self._marked))
    if not self.has_path_to(v):
        return None

    path: Deque[int] = deque()
    x = v
    while x != self._s:
        path.appendleft(x)
        x = self._edge_to[x]
    path.appendleft(self._s)
    return path

Dijkstra's Shortest Paths.

Implements the single‑source shortest‑path algorithm for edge‑weighted directed graphs with non‑negative edge weights. The algorithm computes the shortest path tree rooted at a specified source vertex using a binary heap–based priority queue.

Design Characteristics: - Supports arbitrary directed graphs with non‑negative weights - Produces shortest‑path distances and predecessor edges - Uses lazy deletion in the priority queue - Time Complexity: O(E log V) - Space Complexity: O(V)

`DijkstraSP`

Computes shortest paths in a weighted directed graph.

This class computes the shortest path from a single source vertex to all other vertices in an edge‑weighted digraph with non‑negative edge weights. Distances and predecessor edges are stored for subsequent queries.

Attributes:

Name	Type	Description
`_dist_to`	`List[float]`	Shortest known distance to each vertex.
`_edge_to`	`List[Optional[DirectedEdge]]`	Last edge on the shortest known path to each vertex.
`_pq`	`List[tuple]`	Min‑heap storing (distance, vertex) pairs.

Source code in src/alnoms/dsa/algorithms/graph/dijkstra_sp.py

class DijkstraSP:
    """Computes shortest paths in a weighted directed graph.

    This class computes the shortest path from a single source vertex to
    all other vertices in an edge‑weighted digraph with non‑negative edge
    weights. Distances and predecessor edges are stored for subsequent
    queries.

    Attributes:
        _dist_to (List[float]): Shortest known distance to each vertex.
        _edge_to (List[Optional[DirectedEdge]]): Last edge on the shortest
            known path to each vertex.
        _pq (List[tuple]): Min‑heap storing (distance, vertex) pairs.
    """

    def __init__(self, G: EdgeWeightedDigraph, s: int):
        """Initializes the shortest‑path computation from a source vertex.

        Args:
            G (EdgeWeightedDigraph): The input directed graph.
            s (int): The source vertex.

        Raises:
            ValueError: If any edge in the graph has a negative weight.
        """
        self._validate_edges(G)

        self._dist_to = [float("inf")] * G.V()
        self._edge_to: List[Optional[DirectedEdge]] = [None] * G.V()
        self._pq: List[tuple] = []

        self._dist_to[s] = 0.0
        heapq.heappush(self._pq, (0.0, s))

        while self._pq:
            dist, v = heapq.heappop(self._pq)

            # Skip stale entries
            if dist > self._dist_to[v]:
                continue

            for e in G.adj(v):
                self._relax(e)

    def _relax(self, e: DirectedEdge) -> None:
        """Relaxes an edge and updates state if a shorter path is found.

        Args:
            e (DirectedEdge): The directed edge to relax.
        """
        v, w = e.from_vertex(), e.to_vertex()
        new_dist = self._dist_to[v] + e.weight

        if self._dist_to[w] > new_dist:
            self._dist_to[w] = new_dist
            self._edge_to[w] = e
            heapq.heappush(self._pq, (new_dist, w))

    def _validate_edges(self, G: EdgeWeightedDigraph) -> None:
        """Ensures that the graph contains no negative‑weight edges.

        Args:
            G (EdgeWeightedDigraph): The graph to validate.

        Raises:
            ValueError: If any edge weight is negative.
        """
        for e in G.edges():
            if e.weight < 0:
                raise ValueError(f"Edge has negative weight: {e}")

    def has_path_to(self, v: int) -> bool:
        """Checks whether a path exists from the source to a vertex.

        Args:
            v (int): The vertex to check.

        Returns:
            bool: True if a path exists, otherwise False.
        """
        return self._dist_to[v] < float("inf")

    def dist_to(self, v: int) -> float:
        """Returns the shortest‑path distance to a vertex.

        Args:
            v (int): The vertex whose distance is requested.

        Returns:
            float: The shortest distance, or infinity if unreachable.
        """
        return self._dist_to[v]

    def path_to(self, v: int) -> Optional[Iterable[DirectedEdge]]:
        """Returns the shortest path from the source to a vertex.

        Args:
            v (int): The destination vertex.

        Returns:
            Optional[Iterable[DirectedEdge]]: A sequence of edges forming
            the shortest path, or None if no path exists.
        """
        if not self.has_path_to(v):
            return None

        path: Deque[DirectedEdge] = deque()
        e = self._edge_to[v]

        while e is not None:
            path.appendleft(e)
            e = self._edge_to[e.from_vertex()]

        return path

`init(G, s)`

Initializes the shortest‑path computation from a source vertex.

Parameters:

Name	Type	Description	Default
`G`	`EdgeWeightedDigraph`	The input directed graph.	required
`s`	`int`	The source vertex.	required

Raises:

Type	Description
`ValueError`	If any edge in the graph has a negative weight.

Source code in src/alnoms/dsa/algorithms/graph/dijkstra_sp.py

def __init__(self, G: EdgeWeightedDigraph, s: int):
    """Initializes the shortest‑path computation from a source vertex.

    Args:
        G (EdgeWeightedDigraph): The input directed graph.
        s (int): The source vertex.

    Raises:
        ValueError: If any edge in the graph has a negative weight.
    """
    self._validate_edges(G)

    self._dist_to = [float("inf")] * G.V()
    self._edge_to: List[Optional[DirectedEdge]] = [None] * G.V()
    self._pq: List[tuple] = []

    self._dist_to[s] = 0.0
    heapq.heappush(self._pq, (0.0, s))

    while self._pq:
        dist, v = heapq.heappop(self._pq)

        # Skip stale entries
        if dist > self._dist_to[v]:
            continue

        for e in G.adj(v):
            self._relax(e)

`dist_to(v)`

Returns the shortest‑path distance to a vertex.

Parameters:

Name	Type	Description	Default
`v`	`int`	The vertex whose distance is requested.	required

Returns:

Name	Type	Description
`float`	`float`	The shortest distance, or infinity if unreachable.

Source code in src/alnoms/dsa/algorithms/graph/dijkstra_sp.py

def dist_to(self, v: int) -> float:
    """Returns the shortest‑path distance to a vertex.

    Args:
        v (int): The vertex whose distance is requested.

    Returns:
        float: The shortest distance, or infinity if unreachable.
    """
    return self._dist_to[v]

`has_path_to(v)`

Checks whether a path exists from the source to a vertex.

Parameters:

Name	Type	Description	Default
`v`	`int`	The vertex to check.	required

Returns:

Name	Type	Description
`bool`	`bool`	True if a path exists, otherwise False.

Source code in src/alnoms/dsa/algorithms/graph/dijkstra_sp.py

def has_path_to(self, v: int) -> bool:
    """Checks whether a path exists from the source to a vertex.

    Args:
        v (int): The vertex to check.

    Returns:
        bool: True if a path exists, otherwise False.
    """
    return self._dist_to[v] < float("inf")

`path_to(v)`

Returns the shortest path from the source to a vertex.

Parameters:

Name	Type	Description	Default
`v`	`int`	The destination vertex.	required

Returns:

Type	Description
`Optional[Iterable[DirectedEdge]]`	Optional[Iterable[DirectedEdge]]: A sequence of edges forming
`Optional[Iterable[DirectedEdge]]`	the shortest path, or None if no path exists.

Source code in src/alnoms/dsa/algorithms/graph/dijkstra_sp.py

def path_to(self, v: int) -> Optional[Iterable[DirectedEdge]]:
    """Returns the shortest path from the source to a vertex.

    Args:
        v (int): The destination vertex.

    Returns:
        Optional[Iterable[DirectedEdge]]: A sequence of edges forming
        the shortest path, or None if no path exists.
    """
    if not self.has_path_to(v):
        return None

    path: Deque[DirectedEdge] = deque()
    e = self._edge_to[v]

    while e is not None:
        path.appendleft(e)
        e = self._edge_to[e.from_vertex()]

    return path

Topological Sorting.

Provides a topological ordering of a directed acyclic graph (DAG) using depth‑first search finishing times. The implementation relies on the reverse postorder of a DFS traversal. If the graph contains a cycle, the resulting order is not a valid topological sort, but the algorithm still produces an ordering based on DFS structure.

Design Characteristics: - O(V + E) time - Uses DFS reverse‑postorder - Assumes the input graph is a DAG unless validated externally

Classes:

Name	Description
`Topological`	Computes a topological order of a directed graph.

`Topological`

Computes a topological order of a directed graph.

The ordering is derived from the reverse postorder of a depth‑first search. This yields a valid topological order if and only if the graph is acyclic. Cycle detection is not performed here; callers should validate DAG properties externally if correctness is required.

Source code in src/alnoms/dsa/algorithms/graph/topological.py

class Topological:
    """Computes a topological order of a directed graph.

    The ordering is derived from the reverse postorder of a depth‑first
    search. This yields a valid topological order if and only if the
    graph is acyclic. Cycle detection is not performed here; callers
    should validate DAG properties externally if correctness is required.
    """

    def __init__(self, G: Digraph):
        """Initializes the topological sort computation.

        Args:
            G (Digraph): Directed graph on which to compute the ordering.
        """
        finder = DepthFirstOrder(G)
        self._order: Optional[Iterable[int]] = finder.reverse_post()

    def has_order(self) -> bool:
        """Indicates whether a topological order is available.

        Returns:
            bool: True if an order was computed. This does not guarantee
            that the graph is acyclic; it only reflects that an ordering
            exists based on DFS finishing times.
        """
        return self._order is not None

    def order(self) -> Iterable[int]:
        """Returns the computed topological order.

        Returns:
            Iterable[int]: Vertices in topological order.
        """
        return self._order

`init(G)`

Initializes the topological sort computation.

Parameters:

Name	Type	Description	Default
`G`	`Digraph`	Directed graph on which to compute the ordering.	required

Source code in src/alnoms/dsa/algorithms/graph/topological.py

def __init__(self, G: Digraph):
    """Initializes the topological sort computation.

    Args:
        G (Digraph): Directed graph on which to compute the ordering.
    """
    finder = DepthFirstOrder(G)
    self._order: Optional[Iterable[int]] = finder.reverse_post()

`has_order()`

Indicates whether a topological order is available.

Returns:

Name	Type	Description
`bool`	`bool`	True if an order was computed. This does not guarantee
	`bool`	that the graph is acyclic; it only reflects that an ordering
	`bool`	exists based on DFS finishing times.

Source code in src/alnoms/dsa/algorithms/graph/topological.py

def has_order(self) -> bool:
    """Indicates whether a topological order is available.

    Returns:
        bool: True if an order was computed. This does not guarantee
        that the graph is acyclic; it only reflects that an ordering
        exists based on DFS finishing times.
    """
    return self._order is not None

`order()`

Returns the computed topological order.

Returns:

Type	Description
`Iterable[int]`	Iterable[int]: Vertices in topological order.

Source code in src/alnoms/dsa/algorithms/graph/topological.py

def order(self) -> Iterable[int]:
    """Returns the computed topological order.

    Returns:
        Iterable[int]: Vertices in topological order.
    """
    return self._order

🔢 Sorting & Searching

Bubble Sort.

Implements the classic bubble sort algorithm, which repeatedly scans the array and swaps adjacent elements that are out of order. This version includes the standard early‑termination optimization: if a full pass completes with no swaps, the array is already sorted. An optional visualization mode yields intermediate array states after each swap.

Design Characteristics: - In‑place sorting - Stable behavior - O(N²) average and worst‑case time - O(N) best‑case time on already sorted input - O(1) auxiliary space - Visualization mode yields swap‑step snapshots

Classes:

Name	Description
`BubbleSort`	Static implementation of bubble sort.

`BubbleSort`

Bubble sort implementation.

Repeatedly compares adjacent elements and swaps them if they are in the wrong order. The algorithm terminates early if a full pass completes without any swaps, making it efficient for nearly sorted input.

Source code in src/alnoms/dsa/algorithms/sorting/bubble_sort.py

class BubbleSort:
    """Bubble sort implementation.

    Repeatedly compares adjacent elements and swaps them if they are in
    the wrong order. The algorithm terminates early if a full pass
    completes without any swaps, making it efficient for nearly sorted
    input.
    """

    @staticmethod
    def bubble_sort(
        arr: List[Any], visualize: bool = False
    ) -> Union[List[Any], Generator[List[Any], None, None]]:
        """Sorts the input list using bubble sort.

        If ``visualize`` is True, the function returns a generator that
        yields the array state after each swap. Otherwise, it returns the
        fully sorted list.

        Args:
            arr (List[Any]): The list to sort.
            visualize (bool): Whether to yield intermediate states.

        Returns:
            Union[List[Any], Generator[List[Any], None, None]]:
                Sorted list or generator of intermediate states.

        Complexity:
            Time: O(N²) average/worst, O(N) best case
            Space: O(1)
        """
        data = list(arr)
        n = len(data)

        def _algo():
            for i in range(n):
                swapped = False
                for j in range(0, n - i - 1):
                    if data[j] > data[j + 1]:
                        data[j], data[j + 1] = data[j + 1], data[j]
                        swapped = True
                        if visualize:
                            yield list(data)
                if not swapped:
                    break
            if not visualize:
                yield list(data)

        gen = _algo()
        return gen if visualize else list(gen)[-1]

`bubble_sort(arr, visualize=False)` `staticmethod`

Sorts the input list using bubble sort.

If visualize is True, the function returns a generator that yields the array state after each swap. Otherwise, it returns the fully sorted list.

Parameters:

Name	Type	Description	Default
`arr`	`List[Any]`	The list to sort.	required
`visualize`	`bool`	Whether to yield intermediate states.	`False`

Returns:

Type	Description
`Union[List[Any], Generator[List[Any], None, None]]`	Union[List[Any], Generator[List[Any], None, None]]: Sorted list or generator of intermediate states.

Complexity

Source code in src/alnoms/dsa/algorithms/sorting/bubble_sort.py

@staticmethod
def bubble_sort(
    arr: List[Any], visualize: bool = False
) -> Union[List[Any], Generator[List[Any], None, None]]:
    """Sorts the input list using bubble sort.

    If ``visualize`` is True, the function returns a generator that
    yields the array state after each swap. Otherwise, it returns the
    fully sorted list.

    Args:
        arr (List[Any]): The list to sort.
        visualize (bool): Whether to yield intermediate states.

    Returns:
        Union[List[Any], Generator[List[Any], None, None]]:
            Sorted list or generator of intermediate states.

    Complexity:
        Time: O(N²) average/worst, O(N) best case
        Space: O(1)
    """
    data = list(arr)
    n = len(data)

    def _algo():
        for i in range(n):
            swapped = False
            for j in range(0, n - i - 1):
                if data[j] > data[j + 1]:
                    data[j], data[j + 1] = data[j + 1], data[j]
                    swapped = True
                    if visualize:
                        yield list(data)
            if not swapped:
                break
        if not visualize:
            yield list(data)

    gen = _algo()
    return gen if visualize else list(gen)[-1]

Insertion Sort.

Implements the classic insertion sort algorithm, which builds the sorted array incrementally by inserting each element into its correct position relative to the already‑sorted prefix. The algorithm performs extremely well on partially sorted arrays and small subarrays. An optional visualization mode yields intermediate array states after each swap.

Design Characteristics: - In‑place sorting - Stable behavior - O(N) best‑case time on nearly sorted input - O(N²) worst‑case time - O(1) auxiliary space - Visualization mode yields swap‑step snapshots

Classes:

Name	Description
`InsertionSort`	Static implementation of insertion sort.

`InsertionSort`

Insertion sort implementation.

Builds the sorted array one element at a time by shifting larger elements to the right and inserting the current element into its correct position. Particularly effective for small or partially sorted datasets.

Source code in src/alnoms/dsa/algorithms/sorting/insertion_sort.py

class InsertionSort:
    """Insertion sort implementation.

    Builds the sorted array one element at a time by shifting larger
    elements to the right and inserting the current element into its
    correct position. Particularly effective for small or partially
    sorted datasets.
    """

    @staticmethod
    def insertion_sort(
        arr: List[Any], visualize: bool = False
    ) -> Union[List[Any], Generator[List[Any], None, None]]:
        """Sorts the input list using insertion sort.

        If ``visualize`` is True, the function returns a generator that
        yields the array state after each swap. Otherwise, it returns the
        fully sorted list.

        Args:
            arr (List[Any]): The list to sort.
            visualize (bool): Whether to yield intermediate states.

        Returns:
            Union[List[Any], Generator[List[Any], None, None]]:
                Sorted list or generator of intermediate states.

        Complexity:
            Time: O(N²) worst case, O(N) best case
            Space: O(1)
        """
        data = list(arr)
        n = len(data)

        def _algo():
            for i in range(1, n):
                for j in range(i, 0, -1):
                    if data[j] < data[j - 1]:
                        data[j], data[j - 1] = data[j - 1], data[j]
                        if visualize:
                            yield list(data)
                    else:
                        break
            if not visualize:
                yield list(data)

        gen = _algo()
        return gen if visualize else list(gen)[-1]

`insertion_sort(arr, visualize=False)` `staticmethod`

Sorts the input list using insertion sort.

If visualize is True, the function returns a generator that yields the array state after each swap. Otherwise, it returns the fully sorted list.

Parameters:

Name	Type	Description	Default
`arr`	`List[Any]`	The list to sort.	required
`visualize`	`bool`	Whether to yield intermediate states.	`False`

Returns:

Type	Description
`Union[List[Any], Generator[List[Any], None, None]]`	Union[List[Any], Generator[List[Any], None, None]]: Sorted list or generator of intermediate states.

Complexity

Source code in src/alnoms/dsa/algorithms/sorting/insertion_sort.py

@staticmethod
def insertion_sort(
    arr: List[Any], visualize: bool = False
) -> Union[List[Any], Generator[List[Any], None, None]]:
    """Sorts the input list using insertion sort.

    If ``visualize`` is True, the function returns a generator that
    yields the array state after each swap. Otherwise, it returns the
    fully sorted list.

    Args:
        arr (List[Any]): The list to sort.
        visualize (bool): Whether to yield intermediate states.

    Returns:
        Union[List[Any], Generator[List[Any], None, None]]:
            Sorted list or generator of intermediate states.

    Complexity:
        Time: O(N²) worst case, O(N) best case
        Space: O(1)
    """
    data = list(arr)
    n = len(data)

    def _algo():
        for i in range(1, n):
            for j in range(i, 0, -1):
                if data[j] < data[j - 1]:
                    data[j], data[j - 1] = data[j - 1], data[j]
                    if visualize:
                        yield list(data)
                else:
                    break
        if not visualize:
            yield list(data)

    gen = _algo()
    return gen if visualize else list(gen)[-1]

Merge Sort.

Implements the classic divide‑and‑conquer merge sort algorithm using an auxiliary array for merging. The algorithm guarantees O(N log N) time regardless of input distribution and is stable by construction. An optional visualization mode yields intermediate array states after each merge operation.

Design Characteristics: - Stable sorting - Deterministic O(N log N) time - Requires O(N) auxiliary space - Visualization mode yields merge‑step snapshots

Classes:

Name	Description
`MergeSort`	Static implementation of top‑down merge sort.

`MergeSort`

Top‑down recursive merge sort implementation.

The algorithm recursively divides the array into halves, sorts each half, and merges them using an auxiliary array. This version supports visualization by yielding intermediate states after each merge step.

Source code in src/alnoms/dsa/algorithms/sorting/merge_sort.py

class MergeSort:
    """Top‑down recursive merge sort implementation.

    The algorithm recursively divides the array into halves, sorts each
    half, and merges them using an auxiliary array. This version supports
    visualization by yielding intermediate states after each merge step.
    """

    @staticmethod
    def merge_sort(
        arr: List[Any], visualize: bool = False
    ) -> Union[List[Any], Generator[List[Any], None, None]]:
        """Sorts the input list using merge sort.

        If ``visualize`` is True, the function returns a generator that
        yields the array state after each merge operation. Otherwise, it
        returns the fully sorted list.

        Args:
            arr (List[Any]): The list to sort.
            visualize (bool): Whether to yield intermediate states.

        Returns:
            Union[List[Any], Generator[List[Any], None, None]]:
                Sorted list or generator of intermediate states.

        Complexity:
            Time: O(N log N)
            Space: O(N) auxiliary array
        """
        data = list(arr)
        aux = list(arr)

        def _merge(lo: int, mid: int, hi: int):
            # Copy to auxiliary array
            for k in range(lo, hi + 1):
                aux[k] = data[k]

            i, j = lo, mid + 1

            for k in range(lo, hi + 1):
                if i > mid:
                    data[k] = aux[j]
                    j += 1
                elif j > hi:
                    data[k] = aux[i]
                    i += 1
                elif aux[j] < aux[i]:
                    data[k] = aux[j]
                    j += 1
                else:
                    data[k] = aux[i]
                    i += 1

                if visualize:
                    yield list(data)

        def _sort(lo: int, hi: int):
            if hi <= lo:
                return
            mid = lo + (hi - lo) // 2
            yield from _sort(lo, mid)
            yield from _sort(mid + 1, hi)
            yield from _merge(lo, mid, hi)

        def _wrapper():
            yield from _sort(0, len(data) - 1)
            if not visualize:
                yield data

        gen = _wrapper()
        return gen if visualize else list(gen)[-1]

`merge_sort(arr, visualize=False)` `staticmethod`

Sorts the input list using merge sort.

If visualize is True, the function returns a generator that yields the array state after each merge operation. Otherwise, it returns the fully sorted list.

Parameters:

Name	Type	Description	Default
`arr`	`List[Any]`	The list to sort.	required
`visualize`	`bool`	Whether to yield intermediate states.	`False`

Returns:

Type	Description
`Union[List[Any], Generator[List[Any], None, None]]`	Union[List[Any], Generator[List[Any], None, None]]: Sorted list or generator of intermediate states.

Complexity

Source code in src/alnoms/dsa/algorithms/sorting/merge_sort.py

@staticmethod
def merge_sort(
    arr: List[Any], visualize: bool = False
) -> Union[List[Any], Generator[List[Any], None, None]]:
    """Sorts the input list using merge sort.

    If ``visualize`` is True, the function returns a generator that
    yields the array state after each merge operation. Otherwise, it
    returns the fully sorted list.

    Args:
        arr (List[Any]): The list to sort.
        visualize (bool): Whether to yield intermediate states.

    Returns:
        Union[List[Any], Generator[List[Any], None, None]]:
            Sorted list or generator of intermediate states.

    Complexity:
        Time: O(N log N)
        Space: O(N) auxiliary array
    """
    data = list(arr)
    aux = list(arr)

    def _merge(lo: int, mid: int, hi: int):
        # Copy to auxiliary array
        for k in range(lo, hi + 1):
            aux[k] = data[k]

        i, j = lo, mid + 1

        for k in range(lo, hi + 1):
            if i > mid:
                data[k] = aux[j]
                j += 1
            elif j > hi:
                data[k] = aux[i]
                i += 1
            elif aux[j] < aux[i]:
                data[k] = aux[j]
                j += 1
            else:
                data[k] = aux[i]
                i += 1

            if visualize:
                yield list(data)

    def _sort(lo: int, hi: int):
        if hi <= lo:
            return
        mid = lo + (hi - lo) // 2
        yield from _sort(lo, mid)
        yield from _sort(mid + 1, hi)
        yield from _merge(lo, mid, hi)

    def _wrapper():
        yield from _sort(0, len(data) - 1)
        if not visualize:
            yield data

    gen = _wrapper()
    return gen if visualize else list(gen)[-1]

Quick Sort (3‑Way Partitioning).

Implements Dijkstra’s 3‑way partitioning variant of Quicksort, which handles duplicate keys efficiently by dividing the array into three regions: less than, equal to, and greater than the pivot. This approach improves performance on inputs with many repeated values.

Design Characteristics: - In‑place sorting - Average‑case O(N log N) time - Worst‑case O(N²) time (rare with randomized input) - O(log N) recursion depth - Optional visualization mode yielding intermediate array states

Classes:

Name	Description
`QuickSort`	Static implementation of 3‑way partitioning Quicksort.

`QuickSort`

3‑way partitioning Quicksort implementation.

Uses Dijkstra’s partitioning strategy to efficiently handle arrays with many duplicate keys. The algorithm recursively sorts the subarrays containing elements less than and greater than the pivot.

Source code in src/alnoms/dsa/algorithms/sorting/quick_sort.py

class QuickSort:
    """3‑way partitioning Quicksort implementation.

    Uses Dijkstra’s partitioning strategy to efficiently handle arrays
    with many duplicate keys. The algorithm recursively sorts the
    subarrays containing elements less than and greater than the pivot.
    """

    @staticmethod
    def quick_sort(
        arr: List[Any], visualize: bool = False
    ) -> Union[List[Any], Generator[List[Any], None, None]]:
        """Sorts the input list using 3‑way partitioning Quicksort.

        If ``visualize`` is True, the function returns a generator that
        yields the array state after each swap or partitioning step.
        Otherwise, it returns the fully sorted list.

        Args:
            arr (List[Any]): The list to sort.
            visualize (bool): Whether to yield intermediate states.

        Returns:
            Union[List[Any], Generator[List[Any], None, None]]:
                Sorted list or generator of intermediate states.

        Complexity:
            Time: O(N log N) average, O(N²) worst‑case
            Space: O(log N) recursion
        """
        data = list(arr)

        def _sort(lo: int, hi: int):
            if hi <= lo:
                return

            lt, i, gt = lo, lo + 1, hi
            pivot = data[lo]

            while i <= gt:
                if data[i] < pivot:
                    data[lt], data[i] = data[i], data[lt]
                    lt += 1
                    i += 1
                    if visualize:
                        yield list(data)
                elif data[i] > pivot:
                    data[i], data[gt] = data[gt], data[i]
                    gt -= 1
                    if visualize:
                        yield list(data)
                else:
                    i += 1

            yield from _sort(lo, lt - 1)
            yield from _sort(gt + 1, hi)

        def _wrapper():
            yield from _sort(0, len(data) - 1)
            if not visualize:
                yield data

        gen = _wrapper()
        return gen if visualize else list(gen)[-1]

`quick_sort(arr, visualize=False)` `staticmethod`

Sorts the input list using 3‑way partitioning Quicksort.

If visualize is True, the function returns a generator that yields the array state after each swap or partitioning step. Otherwise, it returns the fully sorted list.

Parameters:

Name	Type	Description	Default
`arr`	`List[Any]`	The list to sort.	required
`visualize`	`bool`	Whether to yield intermediate states.	`False`

Returns:

Type	Description
`Union[List[Any], Generator[List[Any], None, None]]`	Union[List[Any], Generator[List[Any], None, None]]: Sorted list or generator of intermediate states.

Complexity

Source code in src/alnoms/dsa/algorithms/sorting/quick_sort.py

@staticmethod
def quick_sort(
    arr: List[Any], visualize: bool = False
) -> Union[List[Any], Generator[List[Any], None, None]]:
    """Sorts the input list using 3‑way partitioning Quicksort.

    If ``visualize`` is True, the function returns a generator that
    yields the array state after each swap or partitioning step.
    Otherwise, it returns the fully sorted list.

    Args:
        arr (List[Any]): The list to sort.
        visualize (bool): Whether to yield intermediate states.

    Returns:
        Union[List[Any], Generator[List[Any], None, None]]:
            Sorted list or generator of intermediate states.

    Complexity:
        Time: O(N log N) average, O(N²) worst‑case
        Space: O(log N) recursion
    """
    data = list(arr)

    def _sort(lo: int, hi: int):
        if hi <= lo:
            return

        lt, i, gt = lo, lo + 1, hi
        pivot = data[lo]

        while i <= gt:
            if data[i] < pivot:
                data[lt], data[i] = data[i], data[lt]
                lt += 1
                i += 1
                if visualize:
                    yield list(data)
            elif data[i] > pivot:
                data[i], data[gt] = data[gt], data[i]
                gt -= 1
                if visualize:
                    yield list(data)
            else:
                i += 1

        yield from _sort(lo, lt - 1)
        yield from _sort(gt + 1, hi)

    def _wrapper():
        yield from _sort(0, len(data) - 1)
        if not visualize:
            yield data

    gen = _wrapper()
    return gen if visualize else list(gen)[-1]

Selection Sort.

Provides a simple comparison‑based sorting algorithm that repeatedly selects the minimum element and swaps it into its correct position. This implementation supports optional step‑by‑step visualization via a generator interface.

Design Characteristics: - In‑place sorting - Deterministic O(N²) time - O(1) auxiliary space - Visualization mode yields intermediate array states

Classes:

Name	Description
`SelectionSort`	Static implementation of the selection sort algorithm.

`SelectionSort`

Selection sort implementation.

Repeatedly scans the unsorted portion of the array to find the minimum element and swaps it into its correct position. The algorithm is simple, stable in behavior, and useful for educational and demonstrative purposes.

Source code in src/alnoms/dsa/algorithms/sorting/selection_sort.py

class SelectionSort:
    """Selection sort implementation.

    Repeatedly scans the unsorted portion of the array to find the
    minimum element and swaps it into its correct position. The algorithm
    is simple, stable in behavior, and useful for educational and
    demonstrative purposes.
    """

    @staticmethod
    def selection_sort(
        arr: List[Any], visualize: bool = False
    ) -> Union[List[Any], Generator[List[Any], None, None]]:
        """Sorts the input list using selection sort.

        If ``visualize`` is True, the function returns a generator that
        yields the array state after each swap. Otherwise, it returns the
        fully sorted list.

        Args:
            arr (List[Any]): The list to sort.
            visualize (bool): Whether to yield intermediate states.

        Returns:
            Union[List[Any], Generator[List[Any], None, None]]:
                Sorted list or generator of intermediate states.

        Complexity:
            Time: O(N²)
            Space: O(1)
        """
        data = list(arr)
        n = len(data)

        def _algo():
            for i in range(n):
                min_idx = i
                for j in range(i + 1, n):
                    if data[j] < data[min_idx]:
                        min_idx = j
                data[i], data[min_idx] = data[min_idx], data[i]
                if visualize:
                    yield list(data)
            if not visualize:
                yield list(data)

        gen = _algo()
        return gen if visualize else list(gen)[-1]

`selection_sort(arr, visualize=False)` `staticmethod`

Sorts the input list using selection sort.

If visualize is True, the function returns a generator that yields the array state after each swap. Otherwise, it returns the fully sorted list.

Parameters:

Name	Type	Description	Default
`arr`	`List[Any]`	The list to sort.	required
`visualize`	`bool`	Whether to yield intermediate states.	`False`

Returns:

Type	Description
`Union[List[Any], Generator[List[Any], None, None]]`	Union[List[Any], Generator[List[Any], None, None]]: Sorted list or generator of intermediate states.

Complexity

Source code in src/alnoms/dsa/algorithms/sorting/selection_sort.py

@staticmethod
def selection_sort(
    arr: List[Any], visualize: bool = False
) -> Union[List[Any], Generator[List[Any], None, None]]:
    """Sorts the input list using selection sort.

    If ``visualize`` is True, the function returns a generator that
    yields the array state after each swap. Otherwise, it returns the
    fully sorted list.

    Args:
        arr (List[Any]): The list to sort.
        visualize (bool): Whether to yield intermediate states.

    Returns:
        Union[List[Any], Generator[List[Any], None, None]]:
            Sorted list or generator of intermediate states.

    Complexity:
        Time: O(N²)
        Space: O(1)
    """
    data = list(arr)
    n = len(data)

    def _algo():
        for i in range(n):
            min_idx = i
            for j in range(i + 1, n):
                if data[j] < data[min_idx]:
                    min_idx = j
            data[i], data[min_idx] = data[min_idx], data[i]
            if visualize:
                yield list(data)
        if not visualize:
            yield list(data)

    gen = _algo()
    return gen if visualize else list(gen)[-1]

Binary Search Utilities.

Provides classic binary search operations on sorted arrays, including exact‑match search and rank computation. Both operations run in O(log N) time and assume that the input list is already sorted in ascending order.

Design Characteristics: - Deterministic O(log N) time - Works on any comparable key type - Rank operation supports arrays with duplicates - No side effects; functions operate on the input list as read‑only

Classes:

Name	Description
`BinarySearch`	Static utilities for binary search and rank.

`BinarySearch`

Binary search and rank utilities.

Implements exact‑match binary search and a left‑leaning rank operation that counts how many elements are strictly less than a given key. Both methods assume the input list is sorted.

Source code in src/alnoms/dsa/algorithms/searching/binary_search.py

class BinarySearch:
    """Binary search and rank utilities.

    Implements exact‑match binary search and a left‑leaning rank
    operation that counts how many elements are strictly less than a
    given key. Both methods assume the input list is sorted.
    """

    @staticmethod
    def search(a: List[Any], key: Any) -> int:
        """Performs binary search for ``key`` in a sorted list.

        Args:
            a (List[Any]): Sorted list to search.
            key (Any): Target key.

        Returns:
            int: Index of ``key`` if found, otherwise -1.

        Complexity:
            Time: O(log N)
            Space: O(1)
        """
        lo = 0
        hi = len(a) - 1

        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if key < a[mid]:
                hi = mid - 1
            elif key > a[mid]:
                lo = mid + 1
            else:
                return mid
        return -1

    @staticmethod
    def rank(a: List[Any], key: Any) -> int:
        """Returns the number of elements strictly less than ``key``.

        Uses a left‑leaning binary search to find the first index at
        which ``key`` could be inserted while maintaining sorted order.
        This yields the count of elements smaller than ``key`` and works
        efficiently even with many duplicates.

        Args:
            a (List[Any]): Sorted list to examine.
            key (Any): Target key.

        Returns:
            int: Count of elements strictly less than ``key``.

        Complexity:
            Time: O(log N)
            Space: O(1)
        """
        lo = 0
        hi = len(a) - 1

        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if key <= a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        return lo

`rank(a, key)` `staticmethod`

Returns the number of elements strictly less than key.

Uses a left‑leaning binary search to find the first index at which key could be inserted while maintaining sorted order. This yields the count of elements smaller than key and works efficiently even with many duplicates.

Parameters:

Name	Type	Description	Default
`a`	`List[Any]`	Sorted list to examine.	required
`key`	`Any`	Target key.	required

Returns:

Name	Type	Description
`int`	`int`	Count of elements strictly less than `key`.

Complexity

Source code in src/alnoms/dsa/algorithms/searching/binary_search.py

@staticmethod
def rank(a: List[Any], key: Any) -> int:
    """Returns the number of elements strictly less than ``key``.

    Uses a left‑leaning binary search to find the first index at
    which ``key`` could be inserted while maintaining sorted order.
    This yields the count of elements smaller than ``key`` and works
    efficiently even with many duplicates.

    Args:
        a (List[Any]): Sorted list to examine.
        key (Any): Target key.

    Returns:
        int: Count of elements strictly less than ``key``.

    Complexity:
        Time: O(log N)
        Space: O(1)
    """
    lo = 0
    hi = len(a) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if key <= a[mid]:
            hi = mid - 1
        else:
            lo = mid + 1
    return lo

`search(a, key)` `staticmethod`

Performs binary search for key in a sorted list.

Parameters:

Name	Type	Description	Default
`a`	`List[Any]`	Sorted list to search.	required
`key`	`Any`	Target key.	required

Returns:

Name	Type	Description
`int`	`int`	Index of `key` if found, otherwise -1.

Complexity

Source code in src/alnoms/dsa/algorithms/searching/binary_search.py

@staticmethod
def search(a: List[Any], key: Any) -> int:
    """Performs binary search for ``key`` in a sorted list.

    Args:
        a (List[Any]): Sorted list to search.
        key (Any): Target key.

    Returns:
        int: Index of ``key`` if found, otherwise -1.

    Complexity:
        Time: O(log N)
        Space: O(1)
    """
    lo = 0
    hi = len(a) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if key < a[mid]:
            hi = mid - 1
        elif key > a[mid]:
            lo = mid + 1
        else:
            return mid
    return -1

🎯 Pointers

Pointer‑Based Algorithms.

Provides classic two‑pointer techniques, including Floyd’s Tortoise‑and‑Hare cycle detection algorithm for singly linked lists. These algorithms rely on constant‑space pointer manipulation and are widely used in linked‑list processing and fast/slow traversal patterns.

Design Characteristics: - O(1) auxiliary space - O(N) cycle detection - Works on any singly linked list with next references

Classes:

Name	Description
`CycleDetector`	Implements Floyd’s cycle‑finding algorithm.

`CycleDetector`

Cycle detection using Floyd’s Tortoise‑and‑Hare algorithm.

Uses two pointers moving at different speeds to determine whether a singly linked list contains a cycle. If the fast pointer ever meets the slow pointer, a cycle exists.

Source code in src/alnoms/dsa/algorithms/pointers/cycle_detector.py

class CycleDetector:
    """Cycle detection using Floyd’s Tortoise‑and‑Hare algorithm.

    Uses two pointers moving at different speeds to determine whether a
    singly linked list contains a cycle. If the fast pointer ever meets
    the slow pointer, a cycle exists.
    """

    @staticmethod
    def has_cycle(head: Optional[Node]) -> bool:
        """Detects whether a singly linked list contains a cycle.

        The algorithm advances a slow pointer by one step and a fast
        pointer by two steps. If the list contains a cycle, the two
        pointers eventually meet. If the fast pointer reaches the end of
        the list, no cycle exists.

        Args:
            head (Optional[Node]): Head of the singly linked list.

        Returns:
            bool: True if a cycle exists, otherwise False.

        Complexity:
            Time: O(N)
            Space: O(1)
        """
        if not head or not head.next:
            return False

        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:
                return True

        return False

`has_cycle(head)` `staticmethod`

Detects whether a singly linked list contains a cycle.

The algorithm advances a slow pointer by one step and a fast pointer by two steps. If the list contains a cycle, the two pointers eventually meet. If the fast pointer reaches the end of the list, no cycle exists.

Parameters:

Name	Type	Description	Default
`head`	`Optional[Node]`	Head of the singly linked list.	required

Returns:

Name	Type	Description
`bool`	`bool`	True if a cycle exists, otherwise False.

Complexity

Source code in src/alnoms/dsa/algorithms/pointers/cycle_detector.py

@staticmethod
def has_cycle(head: Optional[Node]) -> bool:
    """Detects whether a singly linked list contains a cycle.

    The algorithm advances a slow pointer by one step and a fast
    pointer by two steps. If the list contains a cycle, the two
    pointers eventually meet. If the fast pointer reaches the end of
    the list, no cycle exists.

    Args:
        head (Optional[Node]): Head of the singly linked list.

    Returns:
        bool: True if a cycle exists, otherwise False.

    Complexity:
        Time: O(N)
        Space: O(1)
    """
    if not head or not head.next:
        return False

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow is fast:
            return True

    return False

Algorithms (alnoms.dsa.algorithms)

🕸️ Graph Theory

BreadthFirstPaths

__init__(G, s)

dist_to(v)

has_path_to(v)

path_to(v)

DepthFirstOrder

__init__(G)

reverse_post()

DepthFirstPaths

__init__(G, s)

has_path_to(v)

path_to(v)

DijkstraSP

__init__(G, s)

dist_to(v)

has_path_to(v)

path_to(v)

Topological

__init__(G)

has_order()

order()

🔢 Sorting & Searching

BubbleSort

bubble_sort(arr, visualize=False) staticmethod

InsertionSort

insertion_sort(arr, visualize=False) staticmethod

MergeSort

merge_sort(arr, visualize=False) staticmethod

QuickSort

quick_sort(arr, visualize=False) staticmethod

SelectionSort

selection_sort(arr, visualize=False) staticmethod

BinarySearch

rank(a, key) staticmethod

search(a, key) staticmethod

🎯 Pointers

CycleDetector

has_cycle(head) staticmethod

Algorithms (`alnoms.dsa.algorithms`)

`BreadthFirstPaths`

`init(G, s)`

`dist_to(v)`

`has_path_to(v)`

`path_to(v)`

`DepthFirstOrder`

`init(G)`

`reverse_post()`

`DepthFirstPaths`

`init(G, s)`

`has_path_to(v)`

`path_to(v)`

`DijkstraSP`

`init(G, s)`

`dist_to(v)`

`has_path_to(v)`

`path_to(v)`

`Topological`

`init(G)`

`has_order()`

`order()`

`BubbleSort`

`bubble_sort(arr, visualize=False)` `staticmethod`

`InsertionSort`

`insertion_sort(arr, visualize=False)` `staticmethod`

`MergeSort`

`merge_sort(arr, visualize=False)` `staticmethod`

`QuickSort`

`quick_sort(arr, visualize=False)` `staticmethod`

`SelectionSort`

`selection_sort(arr, visualize=False)` `staticmethod`

`BinarySearch`

`rank(a, key)` `staticmethod`

`search(a, key)` `staticmethod`

`CycleDetector`

`has_cycle(head)` `staticmethod`