txgraffiti.heuristics

txgraffiti.heuristics.fajtlowicz

txgraffiti.heuristics.fajtlowicz.dalmatian_accept(new_conj, existing, df)[source]

Determine whether to accept a new upper‐bound conjecture based on the Dalmatian heuristic.

The Dalmatian heuristic accepts new_conj if and only if:

It is valid on all rows under its hypothesis.

Its right‐hand side (RHS) is strictly smaller on at least one row compared to the minimum RHS of all existing upper‐bounds with the same hypothesis and same conclusion LHS.

Parameters:

new_conj (Conjecture) – Candidate conjecture of the form H → (lhs ≤ rhs).
existing (list of Conjecture) – Previously accepted conjectures to compare against.
df (pandas.DataFrame or KnowledgeTable) – Tabular data on which to evaluate hypotheses and RHS values.

Returns:

True if new_conj is globally valid and strictly tighter than every matching existing bound; False otherwise.

Return type:

bool

Examples

>>> import pandas as pd
>>> from txgraffiti.logic import Property, Predicate, Conjecture, Inequality
>>> from txgraffiti.heuristics.fajtlowicz import dalmatian_accept
>>> df = pd.DataFrame({
...     'alpha':     [1, 1, 1],
...     'beta':      [1, 1, 1],
...     'connected': [True, True, True],
... })
>>> P = Predicate('connected', lambda df: df['connected'])
>>> A = Property('alpha', lambda df: df['alpha'])
>>> B = Property('beta',  lambda df: df['beta'])
>>> weak   = P >> (A <= B + 2)
>>> strong = P >> (A <= B + 1)
>>> best   = P >> (A <= B)
>>> # No existing bounds ⇒ accept
>>> dalmatian_accept(best, [], df)
True
>>> # Reject the weaker conjecture
>>> dalmatian_accept(weak, [strong], df)
False
>>> # Accept the strictly tighter one
>>> dalmatian_accept(best, [strong], df)
True

txgraffiti.heuristics.delavina

txgraffiti.heuristics.delavina.sophie_accept(new_conj, accepted, df)[source]

Decide whether to accept a new conjecture based on its cover set.

A conjecture’s cover set is the set of rows where its hypothesis holds. Under the Sophie heuristic, we accept new_conj only if its cover set includes at least one row not already covered by the union of cover sets of all accepted conjectures.

Parameters:

new_conj (Conjecture) – The candidate conjecture whose hypothesis cover set is tested.
accepted (list of Conjecture) – Previously accepted conjectures. Their hypothesis masks are unioned to form the existing coverage.
df (pandas.DataFrame or KnowledgeTable) – The data on which hypotheses are evaluated.

Returns:

True if new_conj covers at least one additional row beyond the union of all accepted cover sets, False otherwise.

Return type:

bool

Examples

>>> import pandas as pd
>>> from txgraffiti.logic import Property, Predicate, Conjecture
>>> from txgraffiti.heuristics.delavina import sophie_accept
>>> df = pd.DataFrame({
...     'alpha':     [1, 2, 3, 4],
...     'connected': [True, False, True, False],
... })
>>> A = Property('alpha', lambda df: df['alpha'])
>>> P = Predicate('connected', lambda df: df['connected'])
>>> # conj1 covers rows 0 and 2
>>> conj1 = P >> (A <= 10)
>>> # conj2 covers the same rows → no new coverage
>>> conj2 = P >> (A >= 0)
>>> sophie_accept(conj2, [conj1], df)
False
>>> # conj3 covers row 0,2, plus row 1 (connected=False so hypothesis False)
>>> # so still no new coverage
>>> sophie_accept(conj3:= (P | ~P) >> (A >= 0), [conj1], df)
True

txgraffiti.heuristics.davila

txgraffiti.heuristics.davila.is_strict_subset(m1, m2)[source]

Check whether boolean mask m1 is a strict subset of mask m2.

That is, every True in m1 is also True in m2, and m2 has strictly more True entries than m1.

Parameters:

m1 (pandas.Series of bool) – Candidate subset mask.
m2 (pandas.Series of bool) – Candidate superset mask.

Returns:

True if m1 & ~m2 has no True values (so m1 ⊆ m2) and m2.sum() > m1.sum().

Return type:

bool

Examples

>>> import pandas as pd
>>> from txgraffiti.heuristics.davila import is_strict_subset
>>> m1 = pd.Series([True, False, True])
>>> m2 = pd.Series([True, True, True])
>>> is_strict_subset(m1, m2)
True
>>> # not a strict subset if sums equal
>>> is_strict_subset(m1, m1)
False

txgraffiti.heuristics.davila.morgan_accept(new_conj, existing, df)[source]

Accept new_conj only if no existing conjecture with the same logical conclusion has a hypothesis mask that strictly contains new_conj’s mask.

In other words, we reject new_conj if there is already a strictly more general conjecture (same bound but wider hypothesis coverage).

Parameters:

new_conj (Conjecture) – The candidate conjecture to test.
existing (list of Conjecture) – Previously accepted conjectures to compare against.
df (pandas.DataFrame or KnowledgeTable) – The data table on which to evaluate hypothesis masks.

Returns:

True if no strictly more general existing conjecture was found, False otherwise.

Return type:

bool

Examples

>>> import pandas as pd
>>> from txgraffiti.logic import Predicate, Property, Conjecture, Inequality
>>> from txgraffiti.heuristics.davila import morgan_accept
>>> df = pd.DataFrame({
...     'alpha':     [1, 2, 3],
...     'beta':      [3, 2, 1],
...     'connected': [True, True, True],
...     'tree':      [False, True, False],
... })
>>> P_gen  = Predicate('connected', lambda df: df['connected'])
>>> P_sub  = Predicate('tree',      lambda df: df['tree'])
>>> A = Property('alpha', lambda df: df['alpha'])
>>> B = Property('beta',  lambda df: df['beta'])
>>> # less general hypothesis on tree
>>> c1 = P_sub >> (A <= B)
>>> # more general hypothesis on connected
>>> c2 = P_gen >> (A <= B)
>>> # c2 covers strictly more rows → accept c2 but not c1 if c2 exists
>>> morgan_accept(c1, [c2], df)
False
>>> morgan_accept(c2, [c1], df)
True

txgraffiti.heuristics.davila.normalize_inequality_key(ineq)[source]

Produce a canonical key for an inequality so that it is always represented in “lhs <= rhs” form.

Parameters:: ineq (Inequality) – An inequality between two Properties, e.g. P >= Q or P < Q.
Returns:: key – A 3‐tuple (lhs_name, “<=”, rhs_name) such that the returned key always uses the <= operator, flipping >= or > by swapping operands if necessary.
Return type:: tuple of str

Examples

>>> from txgraffiti.logic import Property, Inequality
>>> from txgraffiti.heuristics.davila import normalize_inequality_key
>>> P = Property('alpha', lambda df: df['alpha'])
>>> Q = Property('beta',  lambda df: df['beta'])
>>> ineq1 = Inequality(P, '>=', Q)
>>> normalize_inequality_key(ineq1)
('beta', '<=', 'alpha')

txgraffiti.heuristics.davila.same_conclusion(a, b)[source]

Determine whether two conjectures share the same logical conclusion, up to flipping reversed inequalities.

Parameters:

a (Conjecture) – First conjecture whose conclusion is an Inequality.
b (Conjecture) – Second conjecture whose conclusion is an Inequality.

Returns:

True if their conclusions map to the same canonical key via normalize_inequality_key, i.e. they assert the same bound.

Return type:

bool

Examples

>>> from txgraffiti.logic import Predicate, Property, Conjecture, Inequality
>>> from txgraffiti.heuristics.davila import same_conclusion
>>> P = Predicate('connected', lambda df: df['connected'])
>>> A = Property('alpha', lambda df: df['alpha'])
>>> B = Property('beta',  lambda df: df['beta'])
>>> c1 = Conjecture(P, Inequality(A, '<=', B))
>>> c2 = Conjecture(P, Inequality(B, '>=', A))
>>> same_conclusion(c1, c2)
True