graphtage.search¶

A module for solving a search problem in an iteratively revealed search space.

Given: an iterator that yields an unknown but finite number of integer range objects, e.g., [100, 200], [50, 1000], [60, 500], …. Each integer range object has a member function that is guaranteed to tighten the bounds of the range, such that the range monotonically shrinks and converges toward a specific number (i.e., it conforms to the graphtage.bounds.Bounded protocol). For example, [100, 200].tighten() → [150, 160].tighten() → [150, 155].tighten() → [153, 153] → 153. Each object might have a different tighten function; we cannot make any assumptions about the rate of convergence, other than that the bounds are guaranteed to shrink with each call to tighten().

Goal: Create the most computationally efficient algorithm to determine the range object that converges to the smallest integer (i.e., with the fewest possible tightenings).

search classes¶

IterativeTighteningSearch¶

class graphtage.search.IterativeTighteningSearch(possibilities: Iterator[B], initial_bounds: Optional[graphtage.bounds.Range] = None)¶

Bases: graphtage.bounds.Bounded, typing.Generic

Implementation of iterative tightening search on a given sequence of graphtage.bounds.Bounded objects.

The search class itself is graphtage.bounds.Bounded, with bounds on the value of the optimal solution. Each call to IterativeTighteningSearch.tighten_bounds() will improve these bounds, if possible.

__bool__()¶: Returns whether or not this search’s bounds are definitive.

__init__(possibilities: Iterator[B], initial_bounds: Optional[graphtage.bounds.Range] = None)¶

Initializes the search.

Parameters

possibilities – An iterator yielding graphtage.bounded.Bounded objects over which to search.
initial_bounds – Bounds on the optimal solution, if known. Having good initial bounds can greatly speed up the search. However, if the initial bounds are incorrect (i.e., if the true optimal solution lies outside of initial_bounds, then the resulting solution may be incorrect.

property best_match¶

Returns the best solution the search has thus found.

Returns: The best solution the search has thus found, or None if it has not yet found a feasible solution.
Return type: Optional[B]

bounds() → graphtage.bounds.Range ¶: Returns the bounds of this object.

goal_test() → bool ¶: Returns whether best_match is the optimal solution.

remove_best() → Optional[B]¶

Removes and returns the current best solution found by the search, if one exists.

This enables one to iteratively sort the input sequence. However, this function is only guaranteed to return the globally optimal item if IterativeTighteningSearch.goal_test() returns True. Therefore, to generate a total ordering over the input sequence, you should tighten bounds until the goal is reached before each call to this function:

while search.tighten_bounds():
    while not search.goal_test() and search.tighten_bounds():
        pass
    if search.goal_test():
        yield search.remove_best()
while search.goal_test():
    yield search.remove_best()

However, if your goal is to produce a total ordering, graphtage.bounds.sort() is more efficient.

search() → B¶

Finds and returns the smallest item, fully tightened.

This is equivalent to:

while self.tighten_bounds():
    pass
return self.best_match

tighten_bounds() → bool ¶

Attempts to shrink the bounds of this object.

Returns: True if the bounds were tightened.
Return type: bool